G 有时间想，但不太擅长这种图论计数，就摆了。Ex 直接润。
感觉这场打得很烂，全程梦游，吃了 5 发罚时，很棒。
D - Max Multiple
给定 \(n\) 个数 \(a_1\sim a_n\)，选出 \(k\) 个数使得它们的和为 \(D\) 的倍数且最大化。输出这个和，或判断无解。
\(1\le k\le n\le 100,1\le D\le 100,0\le a_i\le 10^9\)
范围不大，考虑 DP。
设 \(f(i,j,p)\) 表示前 \(i\) 个数中选了 \(j\) 个数，它们的和 \(\bmod\ D \equiv p\) 的和的最大值。
则 \(f(i,j,p)=\max{\{f(i-1,j,k),f(i-1,j-1,(p-a_i)\bmod D)+a_i\}}\)。
直接转移即可。时间复杂度 \(\mathcal O(nkD)\)。注意判断状态合法性。
#include <bits/stdc++.h>
using i64 = long long;
const int maxn = 205;
int n,k,D,a[maxn];
i64 f[maxn][maxn];
bool g[maxn][maxn];
int main() {
scanf("%d %d %d",&n,&k,&D);
f[0][0] = 0;
g[0][0] = true;
for(int i = 1;i <= n;++ i) {
scanf("%d",&a[i]);
for(int j = k;j;-- j) {
for(int q = 0;q < D;++ q) {
if(!g[j - 1][q])continue ;
f[j][(q + a[i]) % D] = std::max(f[j][(q + a[i]) % D] , f[j - 1][q] + a[i]);
g[j][(q + a[i]) % D] |= g[j - 1][q];
}
}
}
if(!g[k][0]) {
puts("-1");
return 0;
}
printf("%lld\n",f[k][0]);
return 0;
}
E - Least Elements
给定 \(n,m,k,a_1\sim a_n\)，对于 \(\forall i\in [1,n-m+1]\)，求出将子序列 \(a_i\sim a_{i+m-1}\) 排序后前 \(k\) 项的和。
\(1\le k\le m\le n\le 2\times 10^5,1\le a_i\le 10^9\)。
显然可以滑动窗口，每次 \(i\gets i+1\)，删除 \(a_i\)，加入 \(a_{i+m}\)，用一个变量维护答案。
插入删除的一种方法是平衡树，因为我没有板子，考场上也不会 pb_ds，所以用了 std::vector 暴力插入删除，因为 std::vector 的 insert 和 erase 操作常数都极小，故可以通过本题，时间复杂度 \(\mathcal{O}(n^2)\)。至于标准的解法就要等别的大佬或着去看官方题解了。
#include <bits/stdc++.h>
#define pb emplace_back
const int maxn = 5e5 + 5;
using i64 = long long;
int n,m,k;
i64 a[maxn];
int main() {
scanf("%d %d %d",&n,&m,&k);
for(int i = 1;i <= n;++ i)
scanf("%lld",&a[i]);
if(k == m) {
i64 ans = 0;
for(int i = 1;i <= m;++ i)
ans += a[i];
printf("%lld ",ans);
for(int i = 2;i <= n - m + 1;++ i) {
ans -= a[i - 1];
ans += a[i + m - 1];
printf("%lld ",ans);
}
return 0;
}
std::vector<i64> G;
for(int i = 1;i <= m;++ i)
G.pb(a[i]);
std::sort(G.begin() , G.end());
i64 ans = 0;
for(int i = 0;i < k;++ i)
ans += G[i];
printf("%lld ",ans);
for(int i = 2;i <= n - m + 1;++ i) {
auto it = std::lower_bound(G.begin() , G.end() , a[i - 1]);
int sum = it - G.begin() + 1;
if(sum <= k) {
ans -= a[i - 1];
ans += G[k];
}
G.erase(it);
it = std::upper_bound(G.begin() , G.end() , a[i + m - 1]);
sum = it - G.begin() + 1;
if(sum <= k) {
ans -= G[k - 1];
ans += a[i + m - 1];
}
G.insert(it , a[i + m - 1]);
printf("%lld ",ans);
}
return 0;
}
F - Xor Minimization
给定一个长为 \(n\) 的序列 \(a_1\sim a_n\)，选择一个 \(x\)，使得 \(\forall i\in [1,n],a_i\gets a_i\operatorname{xor} x\) 后整个序列的最大值最小化。
\(1\le n\le 1.5\times 10^5,0\le a_i\lt 2^{30}\)
位运算相关的最小化问题，直接考虑从高到低按位处理。
把第 \(k\) 位为 \(0\) 的数划分到集合 \(A\)，为 \(1\) 的划分到 \(B\)。可以把 \(A\) 集合第 \(k\) 位全部变为 \(1\)，\(B\) 集合第 \(k\) 位全部变为 \(0\)，也可以不变动。决策的关键在于怎样让答案更小。
因为是从高到低枚举，可以发现，如果我们让指定某个集合第 \(k\) 位为 \(1\)，那么另一个集合无论 \(x\) 怎样取，它的最大值都不可能超过我们选择的这个集合。
换言之，最大值只和我们选择的集合有关，另一个集合可以直接丢弃。
那么，分治计算选择集合 \(A,B\) 时 \(0\sim k-1\) 位的答案，两者间取较小者即可。
时间复杂度 \(\mathcal O(n\log a_i)\)。
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
int n,a[maxn],c[32][maxn];
int solve(int x,int l,int r) {
int cur = l;
for(int i = l;i <= r;++ i)
if(!(c[x + 1][i] >> x & 1))
c[x][cur ++] = c[x + 1][i];
int mid = cur - 1;
for(int i = l;i <= r;++ i)
if(c[x + 1][i] >> x & 1)
c[x][cur ++] = c[x + 1][i];
//这里 [l,mid] 即集合 A，(mid,r] 即集合 B。
if(!x) {
//特判 x=0 的情况。
int res = 0;
for(int i = l;i <= r;++ i)
res += c[x][i] & 1;
if(res == 0||res == r - l + 1)return 0;
return 1;
}
if(mid == l - 1||mid == r)return solve(x - 1 , l , r);
return (1 << x) + std::min(solve(x - 1 , l , mid) , solve(x - 1 , mid + 1 , r));
}
int main() {
scanf("%d",&n);
for(int i = 1;i <= n;++ i)
scanf("%d",&a[i]),c[30][i] = a[i];
printf("%d\n",solve(29 , 1 , n));
return 0;
}