A. MEXanized Array
题意
给你三个数\(n\)、\(k\)、\(x\)，让你求出能否构造出mex为\(k\)，且所有数字都不超过\(x\)，大小为\(n\)的数组。
线索1
如果有存在-1情况，先想啥时候不可能，如果能一下子找到-1的情况，这个题会很简单，因为可以的情况反推过去很容易，如果特判复杂就想想是不是诈骗规律了，这个题就特判，然后贪心做即可。
点击查看代码
void solve() {
int n, k, x;
cin >> n >> k >> x;
if(k > n || x < k - 1) {
cout << "-1\n";
return;
}
int sum = 0;
for(int i = 0; i <= k - 1; ++i) {
sum += i;
}
//剩余n - k个数
if(x - (k - 1) <= 1) {
//cout << n << " " << k << " " << x << "\n";
for(int i = 1; i <= n - k; ++i) sum += k - 1;
}else {
for(int i = 1; i <= n - k; ++i) sum += x;
}
cout << sum << "\n";
}
B. Friendly Arrays
题意
你有两个数组\(a\)跟\(b\)，长度大小分别为\(n\)跟\(m\) ，你可以操作任意次，从\(b\)里面任意选择一个数|上\(a\)数组所有数，最后需要求出\(a_i\)异或的可能最小值，跟最小值。
线索
线索1
想想|的性质，以及^的性质
线索2
n为奇数时候，明显，尽可能的让更多的位为1，那么异或出来位置都是1，即是最大值。n为偶数，尽可能的让更多的位为1，那么异或出来位置都是0，即是最小值。
点击查看代码
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
rep(i, 0, n - 1) cin >> a[i];
int ok = 0;
rep(i, 0, m - 1) cin >> b[i], ok |= b[i];
int mx = 0, mn = 0;
if(n & 1) {
for(auto& x : a) {
mx ^= (ok | x);
mn ^= x;
}
}else {
for(auto& x : a) {
mx ^= x;
mn ^= (ok | x);
}
}
cout << mn << " " << mx << "\n";
}
C. Colorful Table
题意
给你一个数字都\(\leq k\)的大小都为\(n\)的数组，按照题意构造出一个二维数组\(b\)，问你从\(1-k\)每个数字，包含所有的\(i\)的最小矩阵是多大。
线索
线索1
尝试在构造出的矩阵中，找到最可能出现的每个数字可能出现的边界位置
线索2
我们可以发觉一个规律，边界出现位置，是左边大于等于他的数最远的一个位置，右边反之。答案即是r - l + 1的二倍
点击查看代码
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
vector<vector<int> > pos(k + 1);
rep(i, 1, n) {
cin >> a[i];
pos[a[i]].push_back(i);
}
vector<int> ans(k + 1, 0);
int l = 1e6, r = 0;
for(int i = k; i >= 1; --i) {
if(pos[i].size() == 0) continue;
for(auto&x : pos[i]) {
l = min(l, x);
r = max(r, x);
}
//cout << l << " " << r << "\n";
ans[i] = (r - l + 1) * 2;
}
rep(i, 1, k) cout << ans[i] << " \n"[i == k];
//cout << "\n";
}
summary
看到构造题，大部分都是规律+模拟，往找规律方向想，这个题提供了找到如何查找一个数组中所有数，比自己大的数的左右边界解决skill，限制了一定了数据范围前提。
D. Prefix Purchase
题意
你有一个初始化全为\(0\)大小为\(n\)的数组\(a\)，总体力为\(k\)，有一个消耗列表数组\(c\)，每次你可以消耗\(c_i\)的体力，在数组\(a\)的\([1，i]\)这个区间都加上\(1\)，操作任意次，体力不够就不能操作，尽可能让\(a\)字典序最大。
线索1
操作次数肯定越多越好，很显然第一个思路就是一直操作最小的消耗ci
线索2
观察样例2，使用2次3，跟一次3一次4，其实本质是将一次操作更换了成了4，在保证次数不变的前提下。
线索3
保证总次数不变的情况下，我们一直往后找次小值的最右边的位置，这里需要处理一个后缀最小值，找到以后，看是否影响替换次数，不影响，我们就用剩下的体力接着替换，同时记得差分记录。最后输出原数组即可
点击查看代码
void solve() {
int n, k;
cin >> n;
vector<int> c(n + 2, 0);
map<int, int> mp; //记录每个数最后出现的位置 找次小值边界用
rep(i, 1, n) {
cin >> c[i];
mp[c[i]] = i;
}
cin >> k;
vector<int> suf(n + 2); //后缀最小值
suf[n] = c[n];
for(int i = n - 1; i >= 1; --i) {
suf[i] = min(c[i], suf[i + 1]);
}
int mn = 1; //找出最小值位置
rep(i, 1, n) {
if(c[i] <= c[mn]) mn = i;
}
int cnt = k / c[mn]; //总次数
int left = k % c[mn]; //剩下的体力
int pos = mn;
vector<int> d(n + 2, 0); //差分数组
d[pos] = cnt; //最小值位置先加上cnt次
for(int i = pos + 1; left && i <= n; ++i) {
//如果不是最后位置的次大值 或者 不是次大值 就跳过
if(suf[i] != c[i] || mp[c[i]] != i) continue;
//更换当前的次大值体力不够用了
if(c[i] - c[pos] > left) break;
//看能替换多少次过来
int add = min(left / (c[i] - c[pos]), d[pos]);
d[pos] -= add; //上一个位置减回去
d[i] += add;
left -= add * (c[i] - c[pos]);
pos = i; //更新位置 继续往后找
}
//rep(i, 1, n) cout << d[i] << " \n"[i == n];
//差分还原
for(int i = n - 1; i >= 1; --i) d[i] += d[i + 1];
rep(i, 1, n) cout << d[i] << " \n"[i == n];
}
summary
贪心题，注意模拟的细节，d提供了找最右次大值的skill