比赛链接
这次三道题虽然没有什么特别难的知识点，但思维难度都不小，连神假仙都说 B 有难度，我在考试时打了三个暴力，结果最后居然排在第三名。。。
给定一棵以 1 1 1 q q q x x x s s s
主要考点：树形 DP，dsu on tree。
典型的树上背包。
由于这是一个静态问题，考虑先预处理出所有答案，然后再 O ( 1 ) O(1) O ( 1 )
我们枚举每个点，然后依次把它子树中的点塞进它的背包，每塞一个点显然是 O ( s ) O(s) O ( s ) O ( n 2 s ) O(n^2s) O ( n 2 s ) 30 % 30\% 3 0 % 50 % 50\% 5 0 % O ( n s 2 ) O(ns^2) O ( n s 2 )
我们把两种算法合并一下，显然，我们可以直接把某一个儿子的答案作为初始答案，然后把其他的在这个点的子树中但不在这个儿子的子树中的点一个一个地塞进背包。
这里引出一个叫 dsu on tree 的东西，中文名叫树上启发式合并，它的核心思想跟上面说的那个合并之后的算法很像，都是把一个特定的儿子的答案拿来直接用，再枚举其他儿子，最终算出正确答案。
那么这个儿子到底是谁呢。
重儿子啊。
对于一个点来说，由于计算它的答案时是直接把重儿子的先拿来用，所以遍历重儿子的时间复杂度是 O ( 1 ) O(1) O ( 1 ) O ( n s ) O(ns) O ( n s ) O ( n 2 s ) O(n^2s) O ( n 2 s ) O ( n s log n ) O(ns\log n) O ( n s log n )
接下来证明一下这个复杂度（以下内容借鉴了一下 OI Wiki）。
我们像树剖一样定义轻边和重边，显然，对于任意节点，从根到它的路径上的轻边数量不会超过 log n \log n log n 2 2 2 log n \log n log n u u u u u u u u u log n \log n log n log n \log n log n O ( s ) O(s) O ( s ) O ( n s log n ) O(ns\log n) O ( n s log n )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 #include <bits/stdc++.h> #define rep(i, l, r) for(int i = (l); i <= (r); i++) #define per(i, r, l) for(int i = (r); i >= (l); i--) #define debug(x) cerr<<#x<<" = " <<x using namespace std;namespace IO{ char buf[1 <<23 ],*p1=buf,*p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) #define isdigit(c) (c>=48&&c<=57) #define isalpha(c) ((c>=65&&c<=90)||(c> =97&&c<=122)) template <typename T> inline void read (T &x) { x=0 ; register int f=1 ; register char ch=getchar (); while (!isdigit (ch)) ch=getchar (); while (isdigit (ch)) { x=(x<<1 )+(x<<3 )+(ch^48 ); ch=getchar (); } } template <typename T,typename ... Args> inline void read (T& t, Args&... args) { read (t);read (args...); } } using namespace IO;typedef long long ll;const int N = 5e3 +10 , inf = 0x3f3f3f3f ;int n, q, ms, tot, w[N], a[N], siz[N], son[N], dfn[N], rk[N], x[N*20 ], s[N*20 ];ll dp[N][N]; vector<int > edge[N]; void dfs1 (int u, int f) siz[u] = 1 ; rep (i, 0 , edge[u].size ()-1 ) { int v = edge[u][i]; if (v != f) { dfs1 (v, u); son[u] = siz[son[u]] > siz[v] ? son[u] : v; siz[u] += siz[v]; } } } void dfs2 (int u, int f) tot++; dfn[u] = tot; rk[tot] = u; if (son[u]) dfs2 (son[u], u); rep (i, 0 , edge[u].size ()-1 ) { int v = edge[u][i]; if (v != f && v != son[u]) dfs2 (v, u); } } void dfs (int u, int f) if (son[u]) dfs (son[u], u); rep (i, 0 , ms) if (i >= a[u]) dp[u][i] = max (dp[son[u]][i], dp[son[u]][i-a[u]]+w[u]); else dp[u][i] = dp[son[u]][i]; rep (i, 0 , edge[u].size ()-1 ) { int v = edge[u][i]; if (v != f && v != son[u]) dfs (v, u); } if (son[u]) rep (i, dfn[son[u]]+siz[son[u]], dfn[u]+siz[u]-1 ) per (j, ms, a[rk[i]]) dp[u][j] = max (dp[u][j], dp[u][j-a[rk[i]]]+w[rk[i]]); } int main () read (n); rep (i, 1 , n-1 ) { int u, v; read (u, v); edge[u].push_back (v); edge[v].push_back (u); } dfs1 (1 , 0 ); dfs2 (1 , 0 ); rep (i, 1 , n) read (w[i], a[i]); read (q); rep (i, 1 , q) { read (x[i], s[i]); ms = max (ms, s[i]); } dfs (1 , 0 ); rep (i, 1 , q) printf ("%lld\n" , dp[x[i]][s[i]]); return 0 ; }
给定一张无向图，每次从这张图中选一个最大的生成森林，输出每条边应该被选到第几个生成森林中。
主要考点：并查集，二分答案。
首先一个极大的生成森林应该是指从这张无向图的每个连通块中都任意找一棵生成树，这样的森林一定是最大的。
我们考虑把这些边一条一条地加入到这些生成森林中，由于每个森林的每个点的度都至少为 1 1 1 d d d d d d
由于我们首先保证编号靠前的森林是极大的，所以如果一条边可以被加入到某个森林中，它也一定可以被加入到后面的所有森林中。
那么这样就好办了，对于一条边，我们可以直接二分出它应该加入到哪一个森林中，用并查集来维护这个森林中的连通情况，就像 Kruskal 一样，但这样就又会有一个问题，并查集需要开多大？
看起来，并查集需要开 n m nm n m d d d d d d 2 m 2m 2 m 2 m 2m 2 m
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #include <bits/stdc++.h> #define rep(i, l, r) for(int i = (l); i <= (r); i++) #define per(i, r, l) for(int i = (r); i >= (l); i--) #define min(a, b) (a < b ? a : b) using namespace std;namespace IO{ char buf[1 <<23 ],*p1=buf,*p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++) #define isdigit(c) (c>=48&&c<=57) #define isalpha(c) ((c>=65&&c<=90)||(c> =97&&c<=122)) template <typename T> inline void read (T &x) { x=0 ; register char ch=getchar (); while (!isdigit (ch)) ch=getchar (); while (isdigit (ch)) { x=(x<<1 )+(x<<3 )+(ch^48 ); ch=getchar (); } } } using namespace IO;typedef long long ll;const int N = 1e6 +10 , inf = 0x3f3f3f3f ;int n, m, u[N], v[N], in[N], ans[N];vector<int > f[N]; int find (int x, int p) return f[x][p] == x ? f[x][p] : f[x][p] = find (f[x][p], p); } int main () read (n); read (m); rep (i, 1 , m) { read (u[i]); read (v[i]); in[u[i]]++; in[v[i]]++; } rep (i, 1 , n) { f[i].push_back (0 ); rep (j, 1 , in[i]) f[i].push_back (i); } register int tot = 1 ; rep (i, 1 , m) { register int l = 1 , r = min (in[u[i]], in[v[i]]); while (l < r) { register int mid = (l+r)>>1 ; if (find (u[i], mid) == find (v[i], mid)) l = mid+1 ; else r = mid; } register int t1 = find (u[i], l), t2 = find (v[i], l); f[t1][l] = t2; printf ("%d\n" , l); } return 0 ; }
给出一个长度为 n n n a a a n − 1 n-1 n − 1 n − 1 n-1 n − 1 1 1 1 a 1 a_1 a 1
主要考点：Lucas 定理，FWT。
为了表述方便，我们把第 i i i a 1 a_1 a 1 b i b_i b i t t t
我们考虑一个数 t j t_j t j b i b_i b i b i b_i b i t j t_j t j t j t_j t j b i b_i b i i i i j − 1 j-1 j − 1 ( i j − 1 ) \dbinom{i}{j-1} ( j − 1 i ) k k k j − 1 j-1 j − 1
这样的话，对于第 i i i a 1 a_1 a 1 ( i 0 ) \dbinom{i}{0} ( 0 i ) t 1 t_1 t 1 ( i 1 ) \dbinom{i}{1} ( 1 i ) t 2 t_2 t 2 … \dots … ( i n ) \dbinom{i}{n} ( n i ) t n t_n t n
由于一个数异或两次相当于没有异或，所以这里我们只关心 ( i k ) \dbinom{i}{k} ( k i ) ( i k ) m o d 2 \dbinom{i}{k}\mod 2 ( k i ) m o d 2
( i 0 k 0 ) ⋅ ( i 1 k 1 ) ⋅ ( i 2 k 2 ) ⋯ ( i p k p ) m o d 2 \dbinom{i_0}{k_0}\cdot\dbinom{i_1}{k_1}\cdot\dbinom{i_2}{k_2}\cdots\dbinom{i_p}{k_p}\mod 2
( k 0 i 0 ) ⋅ ( k 1 i 1 ) ⋅ ( k 2 i 2 ) ⋯ ( k p i p ) m o d 2
其中 i p i_p i p k p k_p k p i i i k k k p p p
如果这个式子最后的结果为 0 0 0 b i b_i b i i p = 0 i_p=0 i p = 0 k p = 1 k_p=1 k p = 1 ( i p k p ) m o d 2 \dbinom{i_p}{k_p}\mod 2 ( k p i p ) m o d 2 0 0 0 i i i k k k A A A B B B B ⊇ A B\supseteq A B ⊇ A i i i
有一个叫 FWT 的算法能在 O ( n log n ) O(n\log n) O ( n log n )
我们设 d p i , j dp_{i,j} d p i , j i i i j j j i i i
d p i , j = { d p i , j + 1 ( i j = 0 ) d p i , j + 1 ⊕ d p i − 2 j , j + 1 ( i j = 1 ) dp_{i,j}=\begin{cases}dp_{i,j+1} & (i_j=0)\\dp_{i,j+1}\oplus dp_{i-2^j,j+1} & (i_j=1)\end{cases}
d p i , j = { d p i , j + 1 d p i , j + 1 ⊕ d p i − 2 j , j + 1 ( i j = 0 ) ( i j = 1 )
其中 i j i_j i j i i i j j j d p i , p dp_{i,p} d p i , p p p p i i i t i t_i t i d p i , 0 dp_{i,0} d p i , 0 d p i , j dp_{i,j} d p i , j d p i , j + 1 dp_{i,j+1} d p i , j + 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> #define rep(i, l, r) for(register int i = (l); i <= (r); ++i) using namespace std;int dp[8388618 ];int main () register int n, m = 1 , t = 0 , b, c, d; register long long ans = 0 ; scanf ("%d%d%d%d%d" , &n, &dp[0 ], &b, &c, &d); while (n > m) m <<= 1 , t++; rep (i, 1 , n-1 ) dp[i] = (1ll *dp[i-1 ]*(dp[i-1 ]+b)+c)%d; rep (j, 0 , t) rep (i, 0 , m) if ((i>>j)&1 ) dp[i] ^= dp[i^(1 <<j)]; rep (i, 0 , n-1 ) ans ^= dp[i]*(i+1ll ); printf ("%lld" , ans); return 0 ; }
