中途吃了个饭做了个核酸，压线赛时 AK 了，希望不要挂分。
子集和问题是指，给定 \(n\) 个数字 \(a_1,a_2,\cdots, a_n\)，再给定一个目标 \(t\)，有多少种方法，能够选出一些数字，使得它们的和等于 \(t\)。注意每个数字可以重复选择多次。
小爱希望计算一些带有限制的子集和问题，她想知道，对于 \(1\le i\le n\)，如果规定不能选择 \(a_i\)，那么还有多少种方法，可以选出一些数字，使得它们的和等于目标 \(t\)？答案对 \(10^9+7\) 取模。
\(n\le 5000, a_i,t\le 10^4\)。
大体思路对于 \(1\le i\le n\)，都需要求出删去第 \(i\) 个数的方案数，因此考虑动态规划。
记 \(f[i,j]\) 表示前 \(i\) 个数之和为 \(j\) 的方案数，\(f[0,0]=1\)。由于每个数可以重复选取，\(f[i,j]=f[i-1,j]+f[i,j-a_i]\)，其中外层循环 \(i=1\sim n\)，内层循环 \(j=0\sim m\)。
同时，记 \(g[i,j]\) 表示 \(i\) 开始之后的数之和为 \(j\) 的方案数，\(g[n+1,0]=1\)。其状态转移方程与 \(f\) 类似但 \(i\) 的方向相反。
容易想到，对于删去 \(a_i\)，相当于前 \(i-1\) 个数和 \(i+1\) 开始之后的数组成 \(t\) 的方案数，可以枚举前 \(i-1\) 个数的和，则答案为 \(\sum f[i-1,j]\times g[i+1,t-j]\)。
这样的做法时空复杂度均为 \(O(nt)\)，时间上能够通过，但即使开 int 也可能 MLE，因此将 \(g\) 利用滚动数组优化，并且算出一组 \(g\) 后立刻计算相应的 \(ans\)，这样空间常数得到优化，用 int 可以通过。
f[0][0] = 1;
rep(i, 1, n) {
rep(j, 0, m) {
f[i][j] = f[i - 1][j];
if(j >= a[i]) f[i][j] = (f[i][j] + f[i][j - a[i]]) % mod;
}
}
g[(n + 1) & 1][0] = 1;
Rep(i, n, 1) {
rep(j, 0, m) {
g[i & 1][j] = g[(i + 1) & 1][j];
if(j >= a[i]) g[i & 1][j] = (g[i & 1][j] + g[i & 1][j - a[i]]) % mod;
ans[i] = (ans[i] + 1ll * f[i - 1][j] * g[(i + 1) & 1][m - j] % mod) % mod;
}
}
rep(i, 1, n) writeln(ans[i]);
给定一张图，有 \(n\) 个点，每个点有且只有一个后继，第 \(i\) 个点的后继编号为 \(t_i\)，这条边的权重为 \(w_i\)。
给定一个整数 \(k\)，从每个点出发，沿着给定的后继遍历，经过 \(k\) 条边后停止，请分别求出这些路径上的最大权重。
\(n,k\le 5\times 10^5,\ w\le 10^9\)。
大体思路如果你想到了许多复杂度做法，你可能已经用到了 LCA，那你为什么没有想到倍增呢？
倍增简单题，如果整个图是链状，那么显然是 ST 表的模板。现在有了后继，只需要一个辅助数组。
因此，我们定义 \(f[i,p]\) 表示节点 \(i\) 出发经过 \(2^p\) 条边得到的最大权值，\(g[i,p]\) 表示 \(i\) 的 \(2^p\) 级后继。
那么显然有 \(f[i,0]=w_i,g[i,0]=t_i\)；
f[i][p] = max(f[i][p - 1], f[g[i][p - 1]][p - 1]);
g[i][p] = g[g[i][p - 1]][p - 1];
对于 \(k\)，枚举二进制位，如果 \(k\) 的这一位为 \(1\)，那么 \(f[i,p]\) 产生贡献，并且令 \(i\) 指向 \(2^p\) 级后继。
read(n); read(k);
rep(i, 1, n) read(g[i][0]);
rep(i, 1, n) read(f[i][0]);
int P = log(k) / log(2) + 1;
rep(p, 1, P) {
rep(i, 1, n) {
f[i][p] = max(f[i][p - 1], f[g[i][p - 1]][p - 1]);
g[i][p] = g[g[i][p - 1]][p - 1];
}
}
rep(i, 1, n) {
int ans = 0, u = i;
rep(p, 0, P) if((k >> p) & 1)
ans = max(ans, f[u][p]), u = g[u][p];
writeln(ans);
}
就是这道题卡了我一会儿，然后我去做核酸了。
题目大意在大海中，有 \(n\) 座不确定坐标的岛屿。接下来，会陆续发现这些岛屿之间的相对位置关系，在发现的过程中，系统也会询问一些岛屿之间的距离：
-
若有两岛屿的相对位置关系被发现了，则输入格式为
D a b e，表示岛屿 \(a\) 在岛屿 \(b\) 的 \(D\) 方向 \(e\) 公里。\(D\) 必须是ESWN中的一个字母，分别表示东南西北四个方向，输入数据保证不会有矛盾的情况发生，但有些信息可能是重复多余的。 -
如果输入格式为
? a b，表示需要查询岛屿 \(a\) 在岛屿 \(b\) 之间的距离。如果 \(a\) 与 \(b\) 之间的相对关系尚不确定，则输出?。
注意，在计算距离时，所使用的定义是横纵坐标的差的绝对值之和，这种距离定义被称为城市距离或曼哈顿距离，而非常用的欧几里得距离。
大体思路其实这道题如果是欧几里得距离也能做。
\(a,b\) 之间的位置关系有传递性和方向性，因此考虑用带权并查集维护向量。
用 \(v_X\) 记录节点 \(X\) 指向其父亲节点 \(Y\) 的向量 \(\overrightarrow{XY}\)。在路径压缩时由于路径压缩改变父亲节点，设当前节点为 \(X\)，父亲节点为 \(Y\)，根节点为 \(R\)，则 \(\overrightarrow{XR}=\overrightarrow{XY}+\overrightarrow{YR}\)，而 \(\overrightarrow{YR}\) 在上一级函数中已经计算完成，因此直接令当前的 \(v_X\) 加上 \(v_Y\) 即可。
合并时，对于已经在同一个集合内的节点不予操作。否则，假设两个节点为 \(a,b\)，其所在集合的根节点分别为 \(R_a,R_b\)。根据 D a b e 语句，我们可以得到向量 \(\overrightarrow{ab}\)，现在要更新 \(\overrightarrow{R_a R_b}\)。显然有 \(\overrightarrow{R_aR_b}=\overrightarrow{R_aa}+\overrightarrow{ab}+\overrightarrow{bR_b}=v_b-v_a+\overrightarrow{ab}\)。
曼哈顿距离就是两个向量的 \(|\Delta x|+|\Delta y|\)。
另外，\(e\le 10^9\)，需要开 long long。
int n, m, fa[maxn];
struct Vector {
int x, y;
} v[maxn];
inline int find(int u) {
if(u == fa[u]) return u;
int rt = find(fa[u]);
v[u].x += v[fa[u]].x, v[u].y += v[fa[u]].y;
return fa[u] = rt;
}
inline void merge(int x, int y, int dir, int dis) {
// Dir x y dis, 0~3 = ESWN
int f1 = find(x), f2 = find(y);
if(f1 == f2) return;
fa[f1] = f2;
int dx = v[y].x - v[x].x, dy = v[y].y - v[x].y;
if(dir == 0) v[f1] = {dx - dis, dy};
else if(dir == 1) v[f1] = {dx, dis + dy};
else if(dir == 2) v[f1] = {dis + dx, dy};
else v[f1] = {dx, dy - dis};
}
signed main () {
read(n); read(m);
rep(i, 1, n) fa[i] = i;
while(m --) {
char op; int a, b, d;
ReadChar(op);
if(op == '?') {
read(a); read(b);
int f1 = find(a), f2 = find(b);
if(f1 != f2) puts("?");
else writeln(abs(v[a].x - v[b].x) + abs(v[a].y - v[b].y));
}
else {
read(a); read(b); read(d);
if(op == 'E') merge(a, b, 0, d);
else if(op == 'S') merge(a, b, 1, d);
else if(op == 'W') merge(a, b, 2, d);
else merge(a, b, 3, d);
}
// rep(i, 1, n) printf("%lld: (%lld, %lld) ", i, v[i].x, v[i].y);
// putchar('\n');
}
return 0;
}
给定 \(n\) 个数 \(a_i\)，求 \(1\sim t\) 之中有多少个数不是任何一个 \(a_i\) 的正整数倍。
\(n\le 20,t\le 10^{14}\)
大体思路容斥模板题。用一个 \(n\) 位的二进制数表示是否选 \(a_i\)。
每次对于所有选择的数求一个 \(lcm\)，然后根据数的个数的奇偶性判断答案加上或者减去 \(\left\lfloor \dfrac{t}{lcm}\right\rfloor\)。时间复杂度 \(O(2^nn\log a )\)，看上去似乎时间很紧，但其实其中的 \(n\) 是跑不满的。更精确的计算可以枚举 \(1\) 的个数然后用组合数导，但没啥意义。
需要注意的是，\(n\) 个 \(a_i\) 的最大公约数可能超过 long long 的范围，因此当求得的 \(lcm>t\) 时直接 break;。
代码非常简单，不给惹。