https://iai.sh.cn/contest/77
T1. 美克斯
利用了 排列的特殊性质，
- 题目是排列 \(0\sim n-1\) ，所以每个数只出现一次。
- 如果要找区间 \([l, r]\) 的 \(mex\) ，就是找最小的不在这个区间的数。
- 不在区间的数要么出现在区间左边，要么出现在区间右边。
- 于是,我们只需要预处理一个前缀最小值，一个后缀最小值即可
f[l-1]是区间左边部分的最小值b[r+1]是区间右边部分的最小值- 两者取最小，就是第一个缺的数 → mex。
- 特别的，当l到r包含了所有数，答案为n。
#include <bits/stdc++.h>
using namespace std;
int n,q,l,r;
int a[100005];
int f[100005];//前缀最小值，f[i]表示前i个数中的最小值
int b[100005];//后缀最小值，b[i]表示从i到n的所有数中的最小值
int main() {cin>>n>>q;f[0]=n;//界外最小值为nb[n+1]=n;//界外最小值为nfor(int i=1;i<=n;i++){//输入cin>>a[i];f[i]=min(f[i-1],a[i]);//求前缀最小值}for(int i=n;i>=1;i--){b[i]=min(b[i+1],a[i]);//求后缀最小值}while(q--){//按提问回答cin>>l>>r;cout<<min(f[l-1],b[r+1])<<"\n";}return 0;
}
T2 二进制
数位dp，特别板子的题。记忆化搜索的数位DP板子拿过来修改一点点就行了！
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[70],len;
int dp[70][70];
int dfs(int pos,int pre,int limit)
{if(pos==0) return pre==k;if(!limit&&dp[pos][pre]!=-1)return dp[pos][pre];int res=0,up=limit?a[pos]:1;for(int i=0;i<=up;i++){res+=dfs(pos-1,pre+(i==1),limit&&i==up);}return limit?res:dp[pos][pre]=res;
}
int calc(int x)
{memset(dp,-1,sizeof dp);len=0;while(x){a[++len]=x%2;x/=2;}return dfs(len,0,1);
}
signed main()
{cin>>n>>k;cout<<calc(n)<<endl; return 0;
}
T3 斯瓦普
a[i]-b[i]看做数轴上的一个区间，这样数轴上就有n个区间，求可以覆盖n个区间任意一个端点的最小范围。
实现方法是创建一个包含两个数组元素对的数组，排序后使用滑动窗口技巧。通过两指针维护覆盖的索引数量，确保所有 n 个元素都被选择，最终求出最小的区间最大值减最小值。型复杂度 O(n log n)，
#include <bits/stdc++.h>
using namespace std;/*Problem: 斯瓦普思路：将所有 a_i, b_i 视为 (value, index) 的点，共 2n 个。对这些点按 value 排序，使用滑动窗口找最短的区间使得窗口内包含所有 index（每个 index 至少出现一次）。最小值即为窗口右值减左值的最小值。注意：- 使用 long long 存放值（a_i, b_i 可到 1e9，但差仍 fits int，习惯用 long long）- n 最大 2e5，所以总点数 4e5，排序和滑窗都在允许范围内
*/int main() {ios::sync_with_stdio(0);cin.tie(0);int n;cin>>n;vector<long long> a(n), b(n);for (int i = 0; i < n; ++i) cin >> a[i];for (int i = 0; i < n; ++i) cin >> b[i];// 构造 (value, index) 的数组，index 取 0..n-1vector<pair<long long,int>> v;v.reserve(2*n);for (int i = 0; i < n; ++i) {v.emplace_back(a[i], i);v.emplace_back(b[i], i);}sort(v.begin(), v.end());// 滑动窗口：维护计数 cnt[idx]，当覆盖数 covered==n 时窗口合法vector<int> cnt(n, 0);int covered = 0;long long ans = LLONG_MAX;int l = 0;int m = (int)v.size();for (int r = 0; r < m; ++r) {int idx = v[r].second;if (cnt[idx] == 0) ++covered;++cnt[idx];// 当前窗口 [l, r] 已经包含所有下标时，尝试收缩左边界以求最短while (covered == n && l <= r) {long long diff = v[r].first - v[l].first;if (diff < ans) ans = diff;// 尝试把 l 移右一位int lidx = v[l].second;--cnt[lidx];if (cnt[lidx] == 0) --covered; // 失去一个下标，窗口不再完整++l;}}cout << ans << '\n';return 0;
}