$Day1T1:$ 格雷码
$Link$
有一种二进制码称为格雷码。$1$ 位格雷码有两个，为 $0$ 和 $1$ 。
第 $i$ 位格雷码的生成方式为：前一半是第 $i-1$ 位的格雷码顺序排列，加上一个前缀 $0$ ，后一半是第 $i-1$ 位的格雷码倒序排列，加上一个前缀 $1$。
问第 $k$ 个 $n$ 位格雷码是多少。
$1\le n\le 64,0\le k<2^n$。
显然可以分治解决。
将编号的细节处理清楚，注意编号从 $0$ 开始。
视实现情况决定开 $long\ long$ 还是 $unsigned\ long\ long$。
时间复杂度 $O(n)$。
$code$
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 #include <iostream> #include <cstdlib> #include <cstdio> #define ll unsigned long long using namespace std ;inline ll read () ll f = 1 , x = 0 ; char ch; do { ch = getchar(); if (ch == '-' ) f = -1 ; }while (ch < '0' || ch > '9' ); do { x = x * 10 + ch - '0' ; ch = getchar(); }while (ch >= '0' && ch <= '9' ); return f * x; } int n;ll k, pw; inline void solve (int now) if (now == 1 ) { printf ("%lld" , k); return ; } if (k <= pw - 1 ) { printf ("0" ); pw >>= 1 ; solve(now - 1 ); } else { printf ("1" ); k = pw - 1 - (k - pw); pw >>= 1 ; solve(now - 1 ); } return ; } int main () n = read(); k = read(); pw = 1l l << (n - 1 ); solve(n); printf ("\n" ); return 0 ; }
$Day1T2:$ 括号树
$Link$
定义合法括号串为：
$()$ 是合法括号串。
如果 $A$ 是合法括号串，则 $(A)$ 是合法括号串。
如果 $A,B$ 均是合法括号串，则 $AB$ 是合法括号串。
有一棵有 $n$ 个节点的树，节点上有左括号或右括号。
设 $s_i$ 为从根到节点 $i$ 经过的节点组成的括号串，$k_i$ 为 $s_i$ 的合法括号子串数。
求 $(1\times k_1)\operatorname{xor} (2\times k_2)\operatorname{xor} \cdots \operatorname{xor} (n\times k_n)$。
$1\le n\le 5\times 10^5$。
部分分有 $55Pts$ 是链的情况，那我们先来考虑链的情况，即括号串不断拓展。
首先一个合法的括号串，一定是题面中的后两种情况组合而成的，并且它的结尾一定是右括号。
肯定不能枚举子串，考虑对每个右括号作为子串结尾计算贡献，记为 $f_i$，后面的右括号对前面的右括号的贡献显然没有影响，$i$ 点的答案就是 $\sum_{j=1}^{i} f_j$，前缀和统计即可。
$i$ 如果是左括号，或者是右括号但无法匹配，那么 $f_i=0$。
对于 $(A)$ 类合法括号串，显然 $A$ 中的右括号的贡献只与 $A$ 有关，外面的右括号的贡献与 $A$ 无关。
于是只要计算 $()()()$ 这种的贡献就好了，显然 $f_2=1,f_4=f_2+1=2,f_6=f_4+1=3$，与前一个最近的右括号有关。
如果合法括号串间被隔断，贡献就要重新从 $1$ 开始计算。
那么对于一个右括号 $i$，若与它匹配的左括号为 $j$，则可以得到 $f_i=f_{j-1}+1$。
如果被隔断，那么 $j-1$ 为左括号或无法匹配的右括号，$f_{j-1}=0$，就达到了重新计算的效果。
至于合法括号串这么套路的东西，当然是压栈解决啦。
于是就拿到了 $55Pts$。
考虑如何拓展到树上，此时只有一个问题：回溯。
大可以对于每个点单独开一个栈，然后直接 $MLE$。
注意到到达一个点时，要么向栈中压入一个数，要么弹出一个数。
记录这个改变的数，回溯的时候重新弹出或者压入即可。
时间复杂度 $O(n)$。
$code$
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 <iostream> #include <cstdlib> #include <cstdio> #include <vector> #define ll long long using namespace std ;inline int read () int f = 1 , x = 0 ; char ch; do { ch = getchar(); if (ch == '-' ) f = -1 ; }while (ch < '0' || ch > '9' ); do { x = x * 10 + ch - '0' ; ch = getchar(); }while (ch >= '0' && ch <= '9' ); return f * x; } const int N = 5e5 ;int n;string ch;int fa[N + 1 ];vector <int > to[N + 1 ];int st[N + 1 ], top;ll f[N + 1 ], sum[N + 1 ], ans; inline void dfs (int u) int tag = 0 ; if (ch[u - 1 ] == '(' ) { st[++top] = u; } else { if (top) { tag = st[top]; top--; f[u] = f[fa[tag]] + 1 ; } } sum[u] = sum[fa[u]] + f[u]; ans ^= sum[u] * u; for (int i = 0 ; i < to[u].size(); i++) dfs(to[u][i]); if (tag) st[++top] = tag; else top = max(top - 1 , 0 ); return ; } int main () n = read(); cin >> ch; for (int i = 2 ; i <= n; i++) { fa[i] = read(); to[fa[i]].push_back(i); } dfs(1 ); printf ("%lld\n" , ans); return 0 ; }
$Day1T3:$ 树上的数
$Link$
有一棵大小为 $n$ 的树，每个节点上都有一个数字 $x_i$，$x_i$ 仅出现一次且 $1\le x_i\le n$。
每次选择一条边将其删去，并将节点上的数字互换，求 $n-1$ 次操作后，字典序最小的按数字顺序得到的节点编号排列。
$T$ 组数据。
$1\le T\le 10,1\le n\le 2\times 10^3$。
显然，对于每个数字，总是应当贪心地移到编号尽量小的节点上。同时由于字典序的限制，按照 $1-n$ 的顺序进行贪心。
考虑对于一个数字 $x$，它想要从节点 $y_1$ 移到节点 $y_2$，有什么必要条件。
注意到这是一棵树，所以 $y_1\to y_2$ 的路径是唯一的一条链。
那不妨先来考虑链的情况。
为了方便叙述，我们将链水平摆放，并令 $y_1$ 在 $y_2$ 左边（否则将链翻过来看就好了）。
同时形象地，我们将 $y_1$ 称为起飞点，$y_2$ 称为降落点，$y_1$ 与 $y_2$ 之间的点称为中转点，与一个点相连的两条边分别称为左边的边和右边的边，容易得到要求有以下三个：
起飞点左边的边必须在右边的边之后删去，不然 $x$ 就跑到起飞点左边，永远到不了降落点了。
中转点都要满足左边的边在右边的边之前删去，否则 $x$ 就卡在中间了。
降落点右边的边必须在左边的边之前删去，与第一点同理。
解决了链，我们尝试将其搬到树上。
树与链的唯一区别，就是每一个节点有多条边连接，对限制条件稍加修改可以得到：
起飞点往降落点的那条边，必须是起飞点的边中第一个删除的。
中转点在 $y_1\to y_2$ 链上的两条边，必须紧挨着删除，离 $y_1$ 近的那条先山。
降落点从起飞点过来的那条边，必须是降落点的边中最后一个删除的。
也就是说，我们要维护每个点自己的边集删去的顺序，使用双向链表维护即可。
还有一点要注意，对于一个点的边集的链表，如果链头和链尾都确定了，那这条链必须包含了所有边，特判一下即可。
于是我们从小到大枚举每个数字所在的位置作为起飞点，$dfs$ 查找最小可能的降落点，并再次 $dfs$，更新路径上的链表。
时间复杂度 $O(Tn^2)$。
$code$
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 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 #include <iostream> #include <cstdlib> #include <cstdio> using namespace std ;inline int read () int f = 1 , x = 0 ; char ch; do { ch = getchar(); if (ch == '-' ) f = -1 ; }while (ch < '0' || ch > '9' ); do { x = x * 10 + ch - '0' ; ch = getchar(); }while (ch >= '0' && ch <= '9' ); return f * x; } const int N = 2e3 ;int tt;int n;int num[N + 1 ];struct Edge { int to, next; } edge[(N << 1 ) + 1 ]; int start[N + 1 ], size[N + 1 ], tot;int pre[N + 1 ][N + 2 ], nxt[N + 1 ][N + 2 ], rootl[N + 1 ][N + 1 ], rootr[N + 1 ][N + 1 ], len[N + 1 ][N + 1 ];int ans;inline void find (int u, int fa) int roota = rootl[u][fa], rootb = rootr[u][fa], lroot, rroot; if (!fa) { for (int i = start[u]; i; i = edge[i].next) { int v = edge[i].to; lroot = rootl[u][v]; rroot = rootr[u][v]; if (lroot != v || (pre[u][n + 1 ] == rroot && len[u][lroot] != size[u])) continue ; find(v, u); } } else { if (fa == rootb) { if (!pre[u][n + 1 ] && (nxt[u][n + 1 ] != roota || len[u][roota] == size[u])) ans = min(ans, u); for (int i = start[u]; i; i = edge[i].next) { int v = edge[i].to; lroot = rootl[u][v]; rroot = rootr[u][v]; if (lroot == roota || lroot != v || nxt[u][n + 1 ] == v) continue ; if (nxt[u][n + 1 ] == roota && pre[u][n + 1 ] == rroot && len[u][roota] + len[u][lroot] != size[u]) continue ; find(v, u); } } else { find(nxt[u][fa], u); } } return ; } inline void merge (int u, int a, int b) int lroot = rootl[u][a], rroot = rootr[u][b]; nxt[u][a] = b; pre[u][b] = a; for (int i = lroot; i && i != n + 1 ; i = nxt[u][i]) { rootl[u][i] = lroot; rootr[u][i] = rroot; } len[u][lroot] += len[u][b]; return ; } inline int tag (int u, int fa) if (u == ans) { pre[u][n + 1 ] = fa; nxt[u][fa] = n + 1 ; return 1 ; } int roota = rootl[u][fa], rootb = rootr[u][fa], lroot, rroot; if (!fa) { for (int i = start[u], v; i; i = edge[i].next) { v = edge[i].to; lroot = rootl[u][v]; rroot = rootr[u][v]; if (lroot != v || (pre[u][n + 1 ] == rroot && len[u][lroot] != size[u])) continue ; if (tag(v, u)) { nxt[u][n + 1 ] = v; pre[u][v] = n + 1 ; return 1 ; } } } else { if (fa == rootb) { if (!pre[u][n + 1 ] && (nxt[u][n + 1 ] != roota || len[u][roota] == size[u])) ans = min(ans, u); for (int i = start[u], v; i; i = edge[i].next) { v = edge[i].to; lroot = rootl[u][v]; rroot = rootr[u][v]; if (lroot == roota || lroot != v || nxt[u][n + 1 ] == v) continue ; if (nxt[u][n + 1 ] == roota && pre[u][n + 1 ] == rroot && len[u][roota] + len[u][lroot] != size[u]) continue ; if (tag(v, u)) { merge(u, fa, v); return 1 ; } } } else { tag(nxt[u][fa], u); } } return 0 ; } inline void init () n = read(); tot = 0 ; for (int i = 1 ; i <= n; i++) { num[i] = read(); start[i] = size[i] = 0 ; } for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= n + 1 ; j++) pre[i][j] = nxt[i][j] = len[i][j] = rootl[i][j] = rootr[i][j] = 0 ; for (int i = 1 , u, v; i < n; i++) { u = read(); v = read(); edge[++tot] = { v, start[u] }; start[u] = tot; edge[++tot] = { u, start[v] }; start[v] = tot; ++size[u]; ++size[v]; rootl[u][v] = rootr[u][v] = v; rootl[v][u] = rootr[v][u] = u; len[u][v] = len[v][u] = 1 ; } return ; } int main () tt = read(); while (tt--) { init(); for (int i = 1 ; i <= n; i++) { ans = n + 1 ; find(num[i], 0 ); tag(num[i], 0 ); printf ("%d " , ans); } printf ("\n" ); } return 0 ; }
咕咕咕。