t1
给出一个图，求图中所有不同有根树的权值之和。
定义有根树权值为
d表示点的深度，根的深度为0.
n<=10 m<=1000
题解
还是类似于宝藏的状压。f[t][i][j]表示叶子距离根节点距离为t，非叶子节点为状态i,叶子节点为状态j，权值的和，g[t][i][j]表示方案数。
f[t][i][j]就可以转移到f[t+1][i|j][k](k和i|j不相交)，需要预处理出叶节点为j转移到叶节点为k的权值和，方案数。
代码如下：
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, m, x[2020], y[2020], w[2020], p = 1000000007; int f[11][1025][1025]; // cnt int g[11][1025][1025]; // sum ll c[1025][1025]; ll s[1025][1025]; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d%d%d", &x[i], &y[i], &w[i]); x[i]--; y[i]--; x[i + m] = y[i]; y[i + m] = x[i]; w[i + m] = w[i]; } m *= 2; for (int i = 0; i < 1 << n; i++) { for (int j = 0; j < 1 << n; j++) { if (i & j) { continue; } ll ts[11] = {}; ll tc[11] = {}; for (int k = 0; k < m; k++) { if ((i >> x[k] & 1) && (j >> y[k] & 1)) { tc[y[k]]++; ts[y[k]] += w[k]; } } c[i][j] = 1; s[i][j] = 0; for (int k = 0; k < n; k++) { if (j >> k & 1) { c[i][j] *= tc[k]; } } if (c[i][j] == 0) { continue; } for (int k = 0; k < n; k++) { if (j >> k & 1) { s[i][j] += c[i][j] / tc[k] * ts[k]; } } } } for (int i = 0; i < n; i++) { f[0][0][1 << i] = 1; g[0][0][1 << i] = 0; } for (int t = 0; t < n; t++) { for (int i = 0; i < 1 << n; i++) { for (int j = 0; j < 1 << n; j++) { if (i & j) { continue; } if (f[t][i][j] == 0) { continue; } int mask = (1 << n) - 1 - i - j; for (int k = mask;; k = (k - 1) & mask) { ll gc = (ll)g[t][i][j] * c[j][k]; ll fc = (ll)f[t][i][j] * c[j][k]; ll fs = (ll)f[t][i][j] * s[j][k] * (t + 1); f[t + 1][i | j][k] = (f[t + 1][i | j][k] + fc) % p; g[t + 1][i | j][k] = (g[t + 1][i | j][k] + gc + fs) % p; if (k == 0) { break; } } } } } printf("%d ", g[n][(1 << n) - 1][0]); return 0; }
t2 略
t3
4 个字符串，求LCS。每个字符串中，前三个每个数字⾄多出现2 次。
n<=10000.
可以记录前三个字符串每个数字出线的位置，在第四个字符串找到数d[i]时，在前三个里各取一个位置a[i].b[i],c[i]来与d[i]构成一个点。因为前面每个最多出现两次，所以最多8n个点，跑四位正序。
代码如下：
#include <bits/stdc++.h> #define MAXN 200005 using namespace std; int n, BIT[MAXN], ans, turn; struct Data{ int id, a, b, c; bool type; // false change / true query }op[4][MAXN]; int f[MAXN]; bool cmp(const Data &A, const Data &B) { if (turn == 1) { if (A.a != B.a) { return A.a < B.a; } if (A.b != B.b) { return A.b > B.b; } return A.c > B.c; } if (turn == 2A) { if (A.b != B.b) { return A.b < B.b; } return A.c > B.c; } assert(false); } int lowbit(int x){ return x & (-x); } void clear(int x) { x++; for (int i = x; i <= MAXN; i += i & -i) { BIT[i] = 0; } } void change(int x, int v) { x++; for (int i = x; i <= MAXN; i += i & -i) { BIT[i] = max(BIT[i], v); } } int query(int x) { x++; int re = 0; for (int i = x; i > 0; i -= i & -i) { re = max(re, BIT[i]); } return re; } void Work(int cnt) { // printf("start "); for (int i = 0; i < cnt; i++) { // printf("d%d %d %d %d %d ", op[2][i].id, op[2][i].a, op[2][i].b, op[2][i].c, op[2][i].type); if (!op[2][i].type) { change(op[2][i].c, f[op[2][i].id]); } else { f[op[2][i].id] = max(f[op[2][i].id], query(op[2][i].c - 1) + 1); } } for (int i = 0; i < cnt; i++) { if (!op[2][i].type) { clear(op[2][i].c); } } // printf("end "); } void CDQ(int now, int L, int R) { if (R - L <= 1) { return; } int mid = (L + R) / 2; int cnt = 0; CDQ(now, L, mid); for (int i = L; i < mid; i++) { if (now == 1) { op[now][cnt] = op[now - 1][i]; op[now][cnt].type = false; cnt++; } else if (!op[now - 1][i].type) { op[now][cnt] = op[now - 1][i]; cnt++; } } for (int i = mid; i < R; i++) { if (now == 1) { op[now][cnt] = op[now - 1][i]; op[now][cnt].type = true; cnt++; } else if (op[now - 1][i].type) { op[now][cnt] = op[now - 1][i]; cnt++; } } turn = now; sort(op[now], op[now] + cnt, cmp); if(now == 2) { // printf("%d %d %d %d ", now, L, R, cnt); Work(cnt); } else { CDQ(now + 1, 0, cnt); } CDQ(now, mid, R); } int A[50020]; int B[50020]; int C[50020]; int D[50020]; vector<int> pA[50020]; vector<int> pB[50020]; vector<int> pC[50020]; void read() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &A[i]); pA[A[i]].push_back(i); } for (int i = 0; i < N; i++) { scanf("%d", &B[i]); pB[B[i]].push_back(i); } for (int i = 0; i < N; i++) { scanf("%d", &C[i]); pC[C[i]].push_back(i); } for (int i = 0; i < N; i++) { scanf("%d", &D[i]); for (int ja = 0; ja < pA[D[i]].size(); ja++) { int pa = pA[D[i]][ja]; for (int jb = 0; jb < pB[D[i]].size(); jb++) { int pb = pB[D[i]][jb]; for (int jc = 0; jc < pC[D[i]].size(); jc++) { int pc = pC[D[i]][jc]; op[0][n] = {n, pa, pb, pc, false}; n++; } } } } } int main(){ read(); for (int i = 0; i < n; i++) { // printf("%d %d %d %d ", op[0][i].id, op[0][i].a, op[0][i].b, op[0][i].c); } for (int i = 0; i < n; i++) { f[i] = 1; } CDQ(1, 0, n); int ans = 0; for (int i = 0; i < n; i++) { ans = max(ans, f[i]); } // fprintf(stderr, "n = %d ", n); printf("%d ", ans); return 0; }