怎么都会 G 啊我跟你们爆了。
D
因为边权 <2^{10}，所以任意路径的 XOR 值也 <2^{10}。考虑 f_{i,j} 记录是否存在到达点 i 的，XOR 和为 j 的路径，进行广搜/记忆化搜索即可。时间复杂度 O((N+W)w)。
int main(){
cin.tie(0)->sync_with_stdio(0);
read(n),read(m);
for(int i = 1;i <= m;i ++){
read(u),read(v),read(w);
e[u].eb(v,w);
}
g[1][0] = true;
q.ep(1,0);
while(q.size()){
auto [u,vle] = q.front();q.pop();
for(auto [v,w] : e[u]){
if(g[v][vle ^ w]) continue;
g[v][vle ^ w] = true;
q.ep(v,vle ^ w);
}
}
for(int i = 0;i < N;i ++){
if(g[n][i]){
printf("%d\n",i);
suc = true;
break;
}
}
if(!suc) printf("-1\n");
return 0;
}
E
注意到 H,M 的值域很小，考虑 DP，f_{i,j} 表示杀死第 i 只怪物，剩余生命值为 j 时，可以剩余的最大魔力值。不存在的状态和边界设为负无限。时间复杂度 O(NH)。
int main(){
cin.tie(0)->sync_with_stdio(0);
read(n),read(h),read(m);
for(int i = 1;i <= n;i ++) read(a[i]),read(b[i]);
memset(mg,-0x3f,sizeof(mg));
mg[0][h] = m;
for(int i = 1;i <= n;i ++){
suc = false;
for(int j = 0;j <= h;j ++){
mg[i][j] = mg[i - 1][j] - b[i];
if(mg[i][j] >= 0) suc = true;
}
for(int j = a[i];j <= h;j ++){
mg[i][j - a[i]] = max(mg[i][j - a[i]],mg[i - 1][j]);
if(mg[i][j - a[i]] >= 0) suc = true;
}
if(!suc){
fal = true;
printf("%d\n",i - 1);
break;
}
}
if(!fal) printf("%d\n",n);
return 0;
}
F
考虑把一种字符看作 1，另一种字符看作 -1，求多少个子矩阵和为 0。
如果不是二维数组的子矩阵而是一维数组的子串，那么这是好操作的，开个桶记录前缀和 s_i=x 的出现次数即可，做法就不细讲了。
那么我们考虑枚举所选矩阵的 u 和 d，对于第 i 列第 u 行到第 d 行的元素和称为 x_i，求一维数组 x 有多少个子串和为 0，累加答案即可。时间复杂度 O(H^2W)=O((HW)W)。
当 H>W 时改为枚举列（交换 H 和 W 即可），时间复杂度为 O(\sum(HW)\min(H,W))，令 n\leftarrow 3\times 10^5，最坏情况为 O(n\sqrt{n})。
代码写得非常丑陋。
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> T;
while(T --){
ans = 0;
cin >> h >> w;
for(int i = 0;i < h;i ++){
cin >> s[i];
a[i].resize(w + 1);
for(int j = 0;j < w;j ++) a[i][j] = 1 - 2 * (s[i][j] == '.');
}
if(h > w){
for(int i = 0;i < h;i ++){
tmp[i].resize(w + 1);
for(int j = 0;j < w;j ++) tmp[i][j] = a[i][j];
}
for(int i = 0;i < w;i ++){
a[i].resize(h + 1);
for(int j = 0;j < h;j ++) a[i][j] = tmp[j][i];
}
swap(h,w);
}
for(int i = 0;i < h;i ++){
sum[i].resize(w + 1);
for(int j = 0;j < w;j ++) sum[i][j] = a[i][j] + (i ? sum[i - 1][j] : 0);
}
for(int i = 0;i < h;i ++){
for(int j = i;j < h;j ++){
for(int k = 0;k < w;k ++) x[k] = sum[j][k] - (i ? sum[i - 1][k] : 0);
v.clear();
int sum = 0;
cnt[N] = 1;
for(int k = 0;k < w;k ++){
sum += x[k];
ans += cnt[N + sum];
cnt[N + sum] ++,v.eb(sum);
}
for(auto i : v) cnt[N + i] = 0;
}
}
printf("%lld\n",ans);
}
return 0;
}
/*
hhw
3e5^1.5
##.
#..
*/