本文记录了 0xfaner 的 AGC 题解
写在前面 0xfaner 在情人节的夜里打了一场 Codeforces 的 Div.2。但是他 D 题也不会，E 题赛后一分钟才写完，实在是菜得不行。
AtCoder Grand Contest（简称 AGC）题目以思维难度高而出名。 0xfaner 奋发图强，从这一天夜里开始板刷 AGC，但是才五场 AGC 就写了三个月。
本文将会记录 0xfaner 的刷题过程和全部题解。
AGC001 题意 给定长度 $2n$ 的序列，从中两两配对成 $n$ 对，每一对的价值为两者中的较小值。询问最大价值之和。
解法 一对的价值取决于较小值，那么较大值则应当尽可能地小。对于任意一个元素而言都应该取大于它的最小元素。
排序后两两一取即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 #include <bits/stdc++.h> using namespace std ;#define N 101 int a[N], n, ans;int main () scanf ("%d" , &n); for (int i = 1 ; i <= 2 * n; i++) scanf ("%d" , &a[i]); sort(a + 1 , a + 2 * n + 1 ); for (int i = 1 ; i <= n; i++) ans += a[(i << 1 ) - 1 ]; printf ("%d\n" , ans); return 0 ; }
题意 给定一个正三角形的边长 $n$，现有一条光线从某条边上距离顶点 $x$ 的地方射出。该光线每次遇到三角形的边或该光线曾经经过的地方就会反射，直到回到射出点为止。询问你该光线经过的路径长度。
解法 画图总结发现，该光线会不断将三角形划分为平行四边形。对于已知长边 $a$ 和短边 $b$ 的平行四边形，该光线在其中经过的路径长度为 $\lfloor \dfrac{a}{b} \rfloor \times 2b$。特别地，如果 $a|b$ 那么路径长度需要减去一个 $b$，并且此时光线将回到射出点。
使用递归法求解即可，理论时间复杂度 $\mathcal{O}(\log n)$。总结规律也可以得到 $\mathcal{O}(1)$ 的公式 $ans=3(n-gcd(n,x))$。
代码 1 2 3 4 5 6 7 8 9 10 11 #include <bits/stdc++.h> using namespace std ;#define ll long long ll ans (ll n, ll x) { return x ? (ans(x, n % x) + n / x * x * 2 ) : -n; }ll x, n; int main () scanf ("%lld%lld" , &n, &x); if (n < x + x) x = n - x; printf ("%lld\n" , n + ans(n - x, x)); return 0 ; }
题意 给定一颗 $n$ 个节点的树，可以在保证树的连通性的情况下删去一部分节点。
询问最少删去多少节点，使得树的直径为 $k$。
解法
时间复杂度 $\mathcal{O}(n^2)$
代码 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 #include <bits/stdc++.h> using namespace std ;#define ll long long #define N 2010 #define M 4010 int hd[N], nx[M], e[M];int n, k, ans = -1 ;int dfs (int x, int fa, int dep) int num = dep > k / 2 ; for (int i = hd[x]; i; i = nx[i]) if (e[i] != fa) num += dfs(e[i], x, dep + 1 ); return num; } int main () scanf ("%d%d" , &n, &k); for (int i = 1 , Num = 0 , x, y; i < n; i++) { scanf ("%d%d" , &x, &y); nx[++Num] = hd[x], hd[x] = Num, e[Num] = y; nx[++Num] = hd[y], hd[y] = Num, e[Num] = x; } if (k & 1 ) { for (int i = 1 ; i <= n; i++) for (int j = hd[i]; j; j = nx[j]) { int x = dfs(i, e[j], 0 ) + dfs(e[j], i, 0 ); if (ans == -1 || ans > x) ans = x; } } else for (int i = 1 ; i <= n; i++) { int x = dfs(i, 0 , 0 ); if (ans == -1 || ans > x) ans = x; } printf ("%d\n" , ans); return 0 ; }
题意 给定一个长度为 $M$ 元素和为 $n$ 的序列 $A = \{ a_1,a_2,\dots,a_m \}$。
称一个字符串 $S$ 为 $A$ 的特殊回文串当且仅当该字符串长度为 $M$ 且满足其前 $a_1$ 项、接下来 $a_2$ 项、接下来 $a_3$ 项……都是回文串。
现在要求你构造一个序列 $B$，使得有且仅有一个字符串满足其既是重排后的 $A$ 的特殊回文串也是 $B$ 的特殊回文串。
解法 结论 $1$：若 $A$ 中奇数个数超过两个则无解。
要求一个子串是回文串，相当于要求一些位置的字符相同。如果对对应位置相互连边，那么要求所有字符相同则相当于要求这些点在同一个联通块内。那么至少要连 $n-1$ 条边，共计 $2n-2$ 个端点。
每个偶数长度的回文串每个点都会成为一条边的端点，但是奇数长度中间那个字符不会连边，就会少一个端点。
由于是两次划分，总端点数不会超过 $2n$。所以若奇数长度的个数超过两个，显然边数不够。
结论 $2$：若第 $1$ 到 $n$ 个字符组成回文串且第 $1$ 到 $n-1$ 个或第 $2$ 到 $n$ 个字符组成回文串，则这 $n$ 个字符相同。
结论 $3$：若 $n$ 为奇数且第 $1$ 到 $n-1$ 个字符与第 $2$ 到 $n$ 个字符组成回文串，则这 $n$ 个字符相同。
由这 $3$ 个结论，我们得到解法：
在 $A$ 中把奇数放在首尾， $B$ 相对 $A$ 有 $b_1=a_1+1$ , $b_m=a_m−1$，对于其它 $i \in [2,n-1]$。
特别的，对于 $m=1$ 的情况构造为 $1,a_1−1$。
代码 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 #include <bits/stdc++.h> using namespace std ;#define N 100010 int a[N], n, m, num;int main () scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= m; i++) { scanf ("%d" , &a[i]); num += a[i] & 1 ; } if (num > 2 ) { printf ("Impossible\n" ); return 0 ; } for (int i = 2 ; i < m; i++) if (a[i] & 1 ) swap(a[(a[1 ] & 1 ) ? m : 1 ], a[i]); for (int i = 1 ; i < m; i++) printf ("%d " , a[i]); printf ("%d\n" , a[m]); if (m == 1 ) a[++m] = a[1 ], a[1 ] = 0 ; a[1 ]++; printf ("%d\n" , (--a[m]) ? m : --m); for (int i = 1 ; i < m; i++) printf ("%d " , a[i]); printf ("%d\n" , a[m]); return 0 ; }
题意 给定 $n$ 个包，第 $i$ 个包里有一个编号为 $i$ 的棍子、 $a_i$ 个肉和 $b_i$ 个菜。你可以任选两个不同的背包，把这两个背包里所有的肉和菜都用两根棍子串起来形成一个烤串，问能串出多少种烤串。
称这两种烤串不同当且仅当至少有一根棍子的编号不同或肉和菜的数目不同或排列方式不同。
解法 易知任意一对 $i,j$ 对答案的贡献为 $\mathcal{C}_{a_i+b_i+a_j+b_J}^{a_i+a_j}$，则 $\displaystyle ans = \sum_{1 \leq i< j \leq n} \mathcal{C}_{a_i+b_i+a_j+b_j}^{a_i+a_j}$。
该公式计算时间复杂度 $\mathcal{O}(n^2)$，不能满足条件，考虑对其优化。
对 $\mathcal{C}_{a_i+b_i+a_j+b_J}^{a_i+a_j}$ 进行抽象，可以理解为从坐标 $(-a_i,-b_i)$ 出发，每次只能沿 $x$ 轴或 $y$ 轴正方向移动一单位长度，最终到达 $(a_j,b_j)$ 的方案数。
那么定义 $f(i,j)$ 表示从 $(i,j)$ 左下方任意 $(-a_s,-b_s)$ 出发，每次只能沿 $x$ 轴或 $y$ 轴正方向移动一单位长度，最终到达 $(i,j)$ 的方案数.
所以 $ans = \dfrac{\sum_{i=1}^n f(a_i,a_j) - \sum_{i=1}^n \mathcal{C}_{2(a_i+a_j)}^{2a_i}}{2}$，其中 $f(a_i,a_j)$ 可以 DP 求解。
代码 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 #include <bits/stdc++.h> using namespace std ;#define Pii pair<int, int> #define ll long long #define mod 1000000007 #define N 10001 #define S 2000 ll Qpow (ll x, ll n) { ll s = 1 ; while (n) { if (n & 1 ) s = s * x % mod; x = x * x % mod; n >>= 1 ; } return s; } ll inv (ll x) { return Qpow(x, mod - 2 ); }ll fac[N], ifac[N]; ll C (int x, int y) { return fac[x] * ifac[x - y] % mod * ifac[y] % mod; }void Prepare () fac[0 ] = 1 ; for (ll i = 1 ; i < N; i++) fac[i] = fac[i - 1 ] * i % mod; ifac[N - 1 ] = inv(fac[N - 1 ]); for (ll i = N - 1 ; i; i--) ifac[i - 1 ] = ifac[i] * i % mod; } Pii P[S * S]; int d[S << 1 | 1 ][S << 1 | 1 ], n;int main () scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) scanf ("%d%d" , &P[i].first, &P[i].second); Prepare(); for (int i = 1 ; i <= n; i++) d[S - P[i].first][S - P[i].second]++; for (int dis = 1 ; dis <= S << 2 ; dis++) for (int i = max(0 , dis - (S << 1 )); i <= min(S << 1 , dis); i++) { int j = dis - i; if (i) d[i][j] = (d[i][j] + d[i - 1 ][j]) % mod; if (j) d[i][j] = (d[i][j] + d[i][j - 1 ]) % mod; } ll ans = 0 ; for (int i = 1 ; i <= n; i++) { int x = P[i].first, y = P[i].second; ans = (ans + d[x + S][y + S]) % mod; ans = (ans - C(2 * x + 2 * y, 2 * x) + mod) % mod; } printf ("%lld\n" , ans * inv(2 ) % mod); return 0 ; }
题意 给定长度为 $n$ 的序列 $p$，对任意两个满足 $|i-j|\geq k$ 并且 $|p_i-p_j| = 1$ 的 $p_i$ 和 $p_j$，可以进行交换。
求任意次操作之后可得的最小字典序的序列。
解法 令 $i$ 的位置为 $q_i$，从这个角度考虑问题和给定的操作，就是每次交换相邻的两个数，并且它们要满足差不小于 $k$，使得最终 $1$ 的位置尽量靠前， $2$ 的位置尽量靠前，依此类推。
可以发现差小于 $k$ 的数的相对位置不会发生变化，并且满足这个条件的排列都是合法排列。
可以证明最小字典序的 $q$ 一定对应最小字典序的 $p$。求出最小字典序后在 $i$ 前面的数一定都是比 $i$ 小或者比 $i$ 大且差小于 $k$ 且在原来 $q$ 中就在 $i$ 前面的数。这样就保证了 $i$ 在不比它小的数中尽可能靠前，就得到了最小字典序的 $p$。
那么如果 $|i−j|<k$ 并且 $p_i<p_j$ 那么从 $i$ 向 $j$ 连边，求这张图的最小字典序拓扑排列即可。
其中边数最多可达 $n^2$，考虑优化。每个点只需要连向左右最小的满足条件的数即可。
代码 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 #include <bits/stdc++.h> using namespace std ;#define N 2000010 int p[N], a[N], b[N];struct node { int l, r, mid, minn; } s[N << 2 ]; void build (int di, int l, int r) s[di].l = l, s[di].r = r, s[di].mid = l + r >> 1 , s[di].minn = 1e9 ; if (l == r) return ; build(di << 1 , l, s[di].mid), build(di << 1 | 1 , s[di].mid + 1 , r); } void ins (int di, int x, int v) if (s[di].l == s[di].r) { s[di].minn = v; return ; } ins(x <= s[di].mid ? di << 1 : di << 1 | 1 , x, v); s[di].minn = min(s[di << 1 ].minn, s[di << 1 | 1 ].minn); } int query (int di, int l, int r) if (l <= s[di].l && s[di].r <= r) return s[di].minn; if (r <= s[di].mid) return query(di << 1 , l, r); if (l > s[di].mid) return query(di << 1 | 1 , l, r); return min(query(di << 1 , l, r), query(di << 1 | 1 , l, r)); } int hd[N], nx[N << 1 ], e[N << 1 ], Num;void adde (int x, int y) priority_queue <int > q;int n, k, In[N];int main () scanf ("%d%d" , &n, &k); for (int i = 1 , x; i <= n; i++) { scanf ("%d" , &x); a[x] = i; } for (int i = 1 ; i <= n / 2 ; i++) swap(a[i], a[n - i + 1 ]); build(1 , 1 , n); for (int i = n; i >= 1 ; i--) { int x = query(1 , max(1 , a[i] - k + 1 ), a[i]); if (x > 0 && x <= n) adde(a[i], a[x]); x = query(1 , a[i], min(n, a[i] + k - 1 )); if (x > 0 && x <= n) adde(a[i], a[x]); ins(1 , a[i], i); } for (int i = 1 ; i <= n; i++) for (int j = hd[i]; j; j = nx[j]) In[e[j]]++; for (int i = 1 ; i <= n; i++) if (!In[i]) q.push(i); int num = 0 ; while (!q.empty()) { int u = q.top(); q.pop(); b[++num] = u; for (int i = hd[u]; i; i = nx[i]) if (!(--In[e[i]])) q.push(e[i]); } for (int i = 1 ; i <= n / 2 ; i++) swap(b[i], b[n - i + 1 ]); for (int i = 1 ; i <= n; i++) p[b[i]] = i; for (int i = 1 ; i <= n; i++) printf ("%d\n" , p[i]); }
AGC002 题意 给定两整数 $a$ 与 $b$，询问区间 $[a,b]$ 的乘积为正数负数还是 $0$。
解法
$a \leq 0 \leq b$ 时为 $0$
$a>0$ 时为正数
$b<0$ 时若 $b-a$ 为偶数数则为负数，否则为正数。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <bits/stdc++.h> using namespace std ;int a, b;int main () scanf ("%d%d" , &a, &b); if (a > 0 ) puts ("Positive" ); else if (b >= 0 ) puts ("Zero" ); else if ((b - a) & 1 ) puts ("Positive" ); else puts ("Negative" ); return 0 ; }
题意 初始有 $n$ 个盒子， $1$ 号盒子中有一个红球，其余盒子中均有一个白球。
按顺序给定 $m$ 次操作，每次从 $x$ 号盒子中随机取一个球放到 $y$ 号盒子中。
询问你最后有多少盒子中可能存在红球。
解法 模拟这个过程即可，令 $a_i$ 表示 $i$ 号盒子中球的数量， $v_i$ 表示当前 $i$ 号盒子中是否有可能存在红球。
每次 $a_i$ 减到 $0$ 时只需让 $v_i$ 变为 false 即可。时间复杂度 $\mathcal{O}(n)$
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std ;#define N 100001 int a[N], v[N], n, m;int main () v[1 ] = true ; scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= n; i++) a[i] = 1 ; for (int i = 1 , x, y; i <= m; i++) { scanf ("%d%d" , &x, &y); if (v[x]) v[y] = true ; if (a[x] == 1 ) v[x] = false ; a[x]--, a[y]++; } int num = 0 ; for (int i = 1 ; i <= n; i++) if (v[i]) num++; printf ("%d\n" , num); return 0 ; }
题意 给定 $n$ 根绳子，第 $i$ 根绳子长度为 $a_i$。现在这 $n$ 根绳子按顺序首尾连接了起来（打结），你可以每次选择长度不小于 $l$ 的一段，并把它的某一个结断开。
询问你把这些结全部断开的方案。
解法 可以发现只要存在相邻两段的长度和不小于 $l$ 即可。
找到该结点，分别从左到右解开左边的结点，从右到左解开右边的节点，最后再解开该节点即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> using namespace std ;#define N 100001 int a[N], n, m;int main () scanf ("%d%d" , &n, &m); int add = 0 ; for (int i = 1 ; i <= n; i++) scanf ("%d" , &a[i]); for (int i = 1 ; i < n; i++) if (a[i] + a[i + 1 ] >= m) add = i; if (add) { puts ("Possible" ); for (int i = 1 ; i < add; i++) printf ("%d\n" , i); for (int i = n - 1 ; i > add; i--) printf ("%d\n" , i); printf ("%d\n" , add); } else puts ("Impossible" ); return 0 ; }
题意 给定一个无向图， $q$ 次询问。每次询问给出两个点 $x$ 与 $y$，求以 $x,y$ 为起点的两条长度和不少于 $z$ 的路径中的边的编号的最大值的最小值。
解法 一个比较容易想到的做法是对每一个询问单独处理，并查集维护联通块，直接二分答案。
$\mathcal{O}(n)$ 建好并查集后可以 $\mathcal{O}(1)$ 求出 $x$ 和 $y$ 所在联通块的大小之和（ $x$ 和 $y$ 联通需要特判）。
但是该做法时间复杂度 $\mathcal{O}(qn\log m)$，考虑对其优化。
注意到询问间并查集有重复构造，其实可以复用。所以采用整体二分的思想，时间复杂度 $\mathcal{O}(n\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 #include <bits/stdc++.h> using namespace std ;#define N 100010 int f[N], ans[N], num[N];int n, m, q;int find (int x) return x == f[x] ? x : f[x] = find(f[x]); }void Union (int a, int b) int fa = find(a), fb = find(b); if (fa == fb) return ; if (num[fa] > num[fa]) swap(a, b); f[fa] = fb, num[fb] += num[fa]; } int size (int a, int b) int fa = find(a), fb = find(b); if (fa == fb) return num[fa]; return num[fa] + num[fb]; } struct edge { int a, b; } edg[N]; struct data { int x, y, z, id; }; struct Divide { int l, r, ansl, ansr; }; vector <data> que[2 ];vector <Divide> Div[2 ];int main () scanf ("%d%d" , &n, &m); for (int i = 1 , x, y; i <= m; ++i) { scanf ("%d%d" , &x, &y); edg[i] = (edge){x, y}; } scanf ("%d" , &q); for (int i = 1 , x, y, z; i <= q; ++i) { scanf ("%d%d%d" , &x, &y, &z); que[0 ].push_back((data){x, y, z, i}); } Div[0 ].push_back((Divide){0 , q - 1 , 0 , m}); int p = 0 ; while (Div[p].size()) { int cur = 1 ; Div[p ^ 1 ].clear(), que[p ^ 1 ].clear(); for (int i = 1 ; i <= n; ++i) f[i] = i, num[i] = 1 ; for (int i = 0 ; i < (int )Div[p].size(); ++i) { int num = 0 ; if (Div[p][i].ansl == Div[p][i].ansr) { for (int j = Div[p][i].l; j <= Div[p][i].r; ++j) ans[que[p][j].id] = Div[p][i].ansl; continue ; } int mid = (Div[p][i].ansl + Div[p][i].ansr) >> 1 ; for (; cur <= mid; ++cur) Union(edg[cur].a, edg[cur].b); for (int j = Div[p][i].l; j <= Div[p][i].r; ++j) if (size(que[p][j].x, que[p][j].y) >= que[p][j].z) que[p ^ 1 ].push_back(que[p][j]), num++; if (num) Div[p ^ 1 ].push_back((Divide){(int )que[p ^ 1 ].size() - num, (int )que[p ^ 1 ].size() - 1 , Div[p][i].ansl, mid}); num = 0 ; for (int j = Div[p][i].l; j <= Div[p][i].r; ++j) if (size(que[p][j].x, que[p][j].y) < que[p][j].z) que[p ^ 1 ].push_back(que[p][j]), num++; if (num) Div[p ^ 1 ].push_back((Divide){(int )que[p ^ 1 ].size() - num, (int )que[p ^ 1 ].size() - 1 , mid + 1 , Div[p][i].ansr}); } p ^= 1 ; } for (int i = 1 ; i <= q; ++i) printf ("%d\n" , ans[i]); return 0 ; }
题意 给定 $n$ 堆糖果，第 $i$ 堆有 $a_i$ 个糖果。两人博弈，每次可以取尽最大的一堆糖果，或者从所有堆中取走一个糖果。取走最后一颗糖果的输，问均采取最优策略时的胜方。
解法 把这 $n$ 个糖果从大到小排好序以后建立直方图后对应成格点。发现两种操作分别是删去最左边一列和删去最下面一行。
转化为坐标，可以理解为初始坐标 $(1,1)$，每次可以向上或向右移动一格，最先无法移动的人赢。
可以发现处在同一条斜率为 $1$ 的直线上的点对应的胜败状态是相同的，所以任意一点的胜败状态可以直接由边界状态推得。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <bits/stdc++.h> using namespace std ;#define N 100001 int a[N], n;int main () scanf ("%d" , &n); for (int i = 1 ; i <= n; ++i) scanf ("%d" , &a[i]); sort(a + 1 , a + n + 1 , greater<int >()); int add = 1 , adds = 1 ; while (add < n && a[add + 1 ] >= add + 1 ) add++; while (a[adds + 1 ] >= add) adds++; int ans = ((a[add] - add) & 1 ) || ((adds - add) & 1 ); puts (ans ? "First" : "Second" ); return 0 ; }
题意 给定 $n$ 种颜色的球，每种颜色有 $k$ 个。将这 $n \times k$ 个球排成一排， 并将每一种颜色最左边的球涂成第 $n + 1$ 种颜色。问最终的颜色序列有多少种。
解法 因为每种颜色第一次出现的位置会被涂成另一种颜色。那么标记这 $n$ 个位置为特殊位置，假定这 $n$ 个特殊位置的球的初始颜色从左到右颜色是 $1$ 到 $n$，最后答案再乘 $n!$ 即可。
令 $dp[i][j]$ 表示已经涂完前 $i$ 种颜色，并已经涂了 $j$ 个特殊颜色的方案总数。
易知此时普通颜色位置涂了 $(k−1)\times i$ 个，再加上被涂成特殊颜色的格子，所以共确定了 $(k−1)\times i+j$ 个格子。并且显然有 $i \leq j$，于是考虑 DP 转移。
考虑 $dp[i][j]$ 对于其他的贡献：
下一个格子选择涂特殊颜色：$dp[i][j+1]$ += $dp[i][j]$
下一个格子涂最终序列中颜色 $i+1$：$dp[i+1][j]$ += $\mathcal{C}_{k(n−i)−(j−i)−1}^{k−2} dp[i][j]$
需要特判 $k=-1$
代码 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 #include <bits/stdc++.h> using namespace std ;#define mod 1000000007 #define ll long long #define N 2001 int n, k;ll fac[N * N], inv[N * N], dp[N][N] = {1 }; ll Qpow (ll x, ll n) { ll s = 1 ; while (n) { if (n & 1 ) s = s * x % mod; x = x * x % mod; n >>= 1 ; } return s; } ll C (int n, int m) { if (m < 0 || m > n) return 0 ; return fac[n] * inv[m] % mod * inv[n - m] % mod; } int main () scanf ("%d%d" , &n, &k); if (k == 1 ) { puts ("1" ); return 0 ; } for (int i = fac[0 ] = 1 ; i <= n * k; i++) fac[i] = fac[i - 1 ] * i % mod; inv[n * k] = Qpow(fac[n * k], mod - 2 ); for (int i = n * k; i; i--) inv[i - 1 ] = inv[i] * i % mod; for (int i = 0 ; i <= n; i++) for (int j = i; j <= n; j++) { dp[i][j + 1 ] = (dp[i][j + 1 ] + dp[i][j]) % mod; ll s = C(k * (n - i) - (j - i) - 1 , k - 2 ) + dp[i + 1 ][j]; dp[i + 1 ][j] = dp[i][j] * s % mod; } printf ("%lld" , dp[n][n] * fac[n] % mod); return 0 ; }
AGC003 题意 给定二维平面 $n$ 次移动方向（上下左右），每次移动长度自定，询问 $n$ 次移动后能否回到起始点。
解法 左右与上下要么都有，要么都没有即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 #include <bits/stdc++.h> using namespace std ;#define N 1001 char c[N];int X0, Y0, X1, Y1;int main () scanf ("%s" , c); int n = strlen (c); for (int i = 0 ; i < n; i++) (c[i] == 'N' ? X0 : c[i] == 'W' ? Y0 : c[i] == 'S' ? X1 : Y1) = 1 ; puts (((X0 ^ X1) || (Y0 ^ Y1)) ? "No" : "Yes" ); return 0 ; }
题意 给定 $n$ 种卡牌，第 $i$ 种卡牌权值为 $i$，有 $a_i$ 张。每次可以不放回取出差值不超过 $1$ 的一对卡牌。
询问最多可以取出多少对卡牌。
解法 贪心即可，从小到大每次比自己小 $1$ 的那种卡牌如果有剩就直接取，否则自己和自己配对即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <bits/stdc++.h> using namespace std ;#define ll long long #define N 100010 int a[N], n;ll ans; int main () scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) { scanf ("%d" , &a[i]); if (a[i] && a[i - 1 ]) a[i]--, ans++; ans += (a[i] >> 1 ), a[i] &= 1 ; } printf ("%lld\n" , ans); return 0 ; }
题意 给定一个序列，每次可以交换距离为 $1$ 或 $2$ 的一对元素，询问你最少交换多少次距离为 $1$ 的元素，可以使这 $n$ 个元素从小到大排列。
输入为 $[1,n]$ 且保证无重复元素。
解法 因为输入保证无重复元素，所以每个元素的最终位置都已确定。现在给定了每个元素的初始位置，那么就知道了每个元素的位移，而若位移是偶数，则只需要每次交换距离为 $2$ 即可，若位移为奇数，则需要 $1$ 次交换距离为 $1$ 的元素。
假定 $n$ 个元素中位移为奇数的元素有 $k$ 个，易证 $k$ 为偶数。答案就是 $\dfrac{k}{2}$。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <bits/stdc++.h> using namespace std ;#define N 100010 int a[N], b[N], n, k;int main () scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) { scanf ("%d" , &a[i]); b[i] = a[i]; } sort(b + 1 , b + n + 1 ); for (int i = 1 ; i <= n; i++) if ((lower_bound(b + 1 , b + n + 1 , a[i]) - b - i) & 1 ) k++; printf ("%d\n" , k >> 1 ); return 0 ; }
题意 给定长度为 $n$ ($1 \leq n \leq 10^5$) 的序列 $S$ ($1 \leq s_i \leq 10^{10}$)，要求从中选出尽可能多的数，使得任意一对选中的数之积不为立方数。
解法 首先假定有 $s_is_j=x^3$，对其分析。
根据唯一分解定理，对于每一个 $s_i$，有 $\displaystyle s_i = \prod_{i=1}^{m} p_i^{k_i}$ , 若 $s_i$ 能与 $s_j$ 配对，则 $\displaystyle a_i = \prod_{i=1}^{m} p_i^{k_i \bmod 3}$ 同样可以和 $s_j$ 配对。这样一来多个 $s_i$ 就可以对应到同一个 $a_i$。
这样就可以将这 $n$ 个 $s_i$ 分为 $k$ 类 $a_i$。预处理出 $10^{\frac{10}{3}}$ 以内的质数（约有 $300$ 个）可以优化时间复杂度，这样分类的总时间复杂度即可降为 $\mathcal{O}(300n)$。
对于每一类质数，和它对应成完全平方数的只有一类。如此两两配对，每一对贪心取最大的一类即可。最坏时间复杂度 $\mathcal{O}(n \log n)$
这样总时间复杂度即为 $\mathcal{O}(n \log n + 300n)$ （但是实现有点繁琐
代码 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 #include <bits/stdc++.h> using namespace std ;#define ll long long #define N 300010 #define S 100000 int prime[N], snum = 325 , pnum;bool p[N];void EulerSieve (int n) for (int i = 2 ; i <= n; i++) { if (!p[i]) prime[++pnum] = i; for (int j = 1 ; j <= pnum; j++) { if (i * prime[j] > n) break ; p[i * prime[j]] = true ; if (i % prime[j] == 0 ) break ; } } } ll s[N], a[N]; int n, len[N], k[N], num[N];int id[N], ans;bool cmp (int x, int y) return a[x] < a[y]; }int main () EulerSieve(S); scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) { scanf ("%lld" , &s[i]); k[i] = len[i] = 0 , a[i] = 1 ; for (int j = 1 ; j <= snum; j++) { if (s[i] % prime[j]) continue ; int m = 0 ; while (s[i] % prime[j] == 0 ) s[i] /= prime[j], m++; if (m %= 3 ) k[i] |= ((m & 1 ) << len[i]), len[i]++, a[i] *= prime[j]; } if (s[i] > 1 ) { if (s[i] < S) k[i] |= (1 << len[i]), len[i]++, a[i] *= s[i]; else { ll ss = sqrt (s[i]); if (ss * ss != s[i]) ans++, i--, n--; else len[i]++, a[i] *= ss; } } } for (int i = 1 ; i <= n; i++) id[i] = i; sort(id + 1 , id + n + 1 , cmp); for (int l = 1 , r = 1 ; l <= n; l = r + 1 , r = l) { while (r < n && a[id[r]] == a[id[r + 1 ]]) r++; if (a[id[l]] == 1 ) { ans++; continue ; } int maxn = (1 << len[id[l]]) - 1 ; for (int i = l; i <= r; i++) num[k[id[i]]]++; for (int i = l; i <= r; i++) { int x = k[id[i]], y = (maxn ^ k[id[i]]); if (num[x] >= num[y]) ans += num[x], num[x] = num[y] = 0 ; } } printf ("%d\n" , ans); return 0 ; }
题意 给定一个长度为 $n$ 的序列 $S$，元素按顺序为 $1,2\dots n$。
接着给定 $q$ 次操作，每次操作给定一个正整数 $q[i]$。首先先把序列 $S$ 无穷重复，然后把前 $q[i]$ 项截取出来成为新的序列 $S$。
求这 $q$ 次操作后， $1$ 到 $n$ 在序列 $S$ 中分别出现的次数。
解法 首先可以发现若有第 $i$ 次操作与第 $j$ 次操作满足 $i<j$ 且 $q[i] \geq q[j]$，那么第 $j$ 次操作将会无效化第 $i$ 次操作。
那么可以将所有的无效操作剔除，得到一系列 $q[i]$ 不断增大的操作。
这样我们就发现每一次操作后的序列相对于操作前的序列而言，就是将这段序列重复若干次，然后在加上这个序列的一段前缀。这个前缀的长度是 $q_i \bmod q_{i-1}$。
同时我们发现这个前缀是可以不断向前查询的，并且每次长度都是不断地取模然后减小。观察性质可以发现每次至少减少为原来的一半。
同时巧妙运用差分来优化时间复杂度。
代码 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 #include <bits/stdc++.h> using namespace std ;#define ll long long #define N 100010 int q, n, num;ll len[N], val[N], ans[N], x; void search (ll x, ll v) if (x == 0 ) return ; int add = upper_bound(len + 1 , len + num + 1 , x) - len - 1 ; if (add) { val[add] += (x / len[add]) * v; search(x % len[add], v); } else ans[1 ] += v, ans[x + 1 ] -= v; } int main () scanf ("%d%d" , &n, &q); len[++num] = n; while (q--) { scanf ("%lld" , &x); while (num && len[num] >= x) num--; len[++num] = x; } val[num] = 1 ; for (ll i = num - 1 ; i; i--) { val[i] += len[i + 1 ] / len[i] * val[i + 1 ]; search(len[i + 1 ] % len[i], val[i + 1 ]); } ans[1 ] += val[1 ], ans[len[1 ] + 1 ] -= val[1 ]; for (ll i = 1 ; i <= n; i++) printf ("%lld\n" , ans[i] += ans[i - 1 ]); return 0 ; }
题意 给定一个 $n$ 行 $m$ 列的方格图，格点全部为黑色或者白色，保证黑色格点之间联通。
现将该方格图作为 $1$ 级构型，定义 $k$ 级构型为：$k$ 级构型由 $n$ 行 $m$ 列个块构成，如果该块对应位置在 $1$ 构型中为黑色，则该块为 $k-1$ 构型，否则为与 $k-1$ 构型同尺寸的全白方格图。
这样我们可以大概构想出这是一个分形，特别的， $0$ 级构型为一个 $1$ 行 $1$ 列的黑色方格。
现在给定 $n,m,k$ 和 $1$ 级构型，询问 $k$ 级构型中联通块的数量。
解法 如果 $1$ 级构型中存在两个黑块在相对位置相邻，如一个在 $[i,1]$ 一个在 $[i,m]$，或者一个在 $[1,i]$ 一个在 $[n,i]$。那么 $2$ 级构型中左右相邻或者上下相邻的两块将会相互连通。
假定 $1$ 级构型中有 $s$ 个黑色格点，称黑块为 $1$ 级构型中的黑色连通块。
如果 $1$ 级构型中同时存在左右和上下对应相邻的黑块，那么可以知道所有的黑块都相互连通，答案为 $1$。而如果都不存在，那么所有的黑块都不互相连通，答案为 $s^{k-1}$。
而当只存在左右相邻或只存在上下相邻时，需要运用公式：$C=V-E$ , $C$ 为联通块数量， $V$ 为点数， $E$ 为边数。
只需要计算出答案中有多少黑块，以及有多少对黑块互相连接即可，使用矩阵快速幂加速运算。
代码 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 #include <bits/stdc++.h> using namespace std ;#define mod 1000000007 #define ll long long #define N 1010 #define M 2 int num, s0, s1, num0, num1, n, m;ll k; char s[N][N];ll Qpow (ll x, ll n) { n %= (mod - 1 ); ll s = 1 ; while (n) { if (n & 1 ) s = s * x % mod; x = x * x % mod; n >>= 1 ; } return s; } struct Matrix { ll a[M][M]; Matrix() { memset (a, 0 , sizeof a); }; Matrix operator *(Matrix &x) { Matrix s; for (int i = 0 ; i < M; i++) for (int j = 0 ; j < M; j++) for (int k = 0 ; k < M; k++) s.a[i][j] = (s.a[i][j] + a[i][k] * x.a[k][j] % mod) % mod; return s; } }; int main () scanf ("%d%d%lld" , &n, &m, &k); for (int i = 1 ; i <= n; i++) { scanf ("%s" , s[i] + 1 ); for (int j = 1 ; j <= m; j++) if (s[i][j] == '#' ) num++, s0 += (s[i - 1 ][j] == '#' ), s1 += (s[i][j - 1 ] == '#' ); if (s[i][1 ] == '#' && s[i][m] == '#' ) num1++; if (i == n) for (int j = 1 ; j <= m; j++) if (s[1 ][j] == '#' && s[n][j] == '#' ) num0++; } if ((num0 && num1) || k == 0 ) { printf ("1\n" ); return 0 ; } else if (num0 == 0 && num1 == 0 ) { printf ("%lld\n" , Qpow(num, k - 1 )); return 0 ; } if (num0 == 0 ) { swap(num0, num1); swap(s0, s1); } Matrix A, ans; A.a[0 ][0 ] = num, A.a[1 ][0 ] = s0, A.a[1 ][1 ] = num0; ans.a[0 ][0 ] = ans.a[1 ][1 ] = 1 ; k--; while (k) { if (k & 1 ) ans = ans * A; A = A * A; k >>= 1 ; } printf ("%lld\n" , (ans.a[0 ][0 ] - ans.a[1 ][0 ] + mod) % mod); return 0 ; }
AGC004 题意 给定一个长方体的长宽高，将该长方体切为两部分，且切完后长宽高也是整数。询问两部分体积之差最小值。
解法 当长宽高中至少一个为偶数时，可以将该长方体均匀切开，体积差为 $0$，否则取长宽高中最小的两项相乘即可。
代码 1 2 3 4 5 6 7 8 9 #include <bits/stdc++.h> using namespace std ;long long s[3 ];int main () scanf ("%lld%lld%lld" , &s[0 ], &s[1 ], &s[2 ]); sort(s, s + 3 ); printf ("%lld\n" , (s[0 ] & 1 && s[1 ] & 1 && s[2 ] & 1 ) ? s[0 ] * s[1 ] : 0 ); return 0 ; }
题意 给定一个初始空集合，每次有两种操作可选：
给定 $a_i$ 和 $x$，询问是的集合中元素恰为 $1$ 到 $n$ 的最小代价。
解法 假定最终集合中元素 $i$ 在加入集合前值为 $b_i$ ( $1 \leq b_i \leq i$ )，令 $c_i=i-b_i$，那么 $c_i$ 即表示元素 $i$ 增大的次数。
易知元素必按照 $c_i$ 递减的顺序加入集合，操作 $2$ 执行的次数为 $c_1$。
那么只需要枚举 $c_1$ 的值，即可确定操作 $2$ 执行的次数。同时可以确定 $c_2$ 到 $c_{n}$ 范围在区间 $[0,c_1]$。即 $b_i$ 取值范围在 $[i-c_1,i]$，那么 $b_i$ 只需取该区间内 $a$ 最小的点即可。
$\mathcal{O}(n^2)$ 预处理 $a$ 数组，算出任意区间的最小值即可（当然也可以建 ST 表）。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std ;#define ll long long #define N 2001 int f[N][N], n;ll ans = 1e18 , x; int query (int l, int r) return l > 0 ? f[l][r] : min(f[l + n][n], f[1 ][r]); }int main () scanf ("%d%lld" , &n, &x); for (int i = 1 ; i <= n; i++) scanf ("%d" , &f[i][i]); for (int i = 1 ; i <= n; i++) for (int j = i + 1 ; j <= n; j++) f[i][j] = min(f[i][j - 1 ], f[j][j]); for (int i = 0 ; i < n; i++) { ll sum = 0 ; for (int j = 1 ; j <= n; j++) sum += query(j - i, j); ans = min(ans, sum + x * i); } printf ("%lld\n" , ans); return 0 ; }
题意 给定一个 01 矩阵 $s$，要求构造两个同尺寸的 01 矩阵 $a$ 和 $b$，使得 $a$ 和 $b$ 对应位置相与后的结构恰为 $s$。
同时要求 $a$ 和 $b$ 均满足矩阵中 $1$ 的部分联通，输入数据保证 $s$ 的边界均为 $0$。
解法 构造 $a$ 矩阵左边界均为 $1$， $b$ 矩阵右边界均为 $1$。
然后 $a$ 矩阵涂满奇数行（不包括右边界）， $b$ 矩阵涂满偶数行（不包括左边界）。
对于 $s$ 中为 $1$ 的部分， $a$ 和 $b$ 中均涂 $1$ 即可。
代码 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 #include <bits/stdc++.h> using namespace std ;#define N 501 int n, m, a[N][N], b[N][N];int main () scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= m; j++) { char c = getchar(); if (c == '\n' ) c = getchar(); a[i][j] = b[i][j] = c == '#' ; } for (int i = 1 ; i <= n; i++) { a[i][1 ] = b[i][m] = 1 ; if (i & 1 ) for (int j = 1 ; j < m; j++) a[i][j] = 1 ; else for (int j = 2 ; j <= m; j++) b[i][j] = 1 ; } for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) putchar (a[i][j] ? '#' : '.' ); putchar ('\n' ); } putchar ('\n' ); for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) putchar (b[i][j] ? '#' : '.' ); putchar ('\n' ); } return 0 ; }
题意 给定一个正整数 $k$ 一个长度为 $n$ 的序列 $a$， $a_i$ 表示从 $i$ 从发， $1$ 步后会到达 $a_i$。
询问最少需要修改 $a_i$ 多少次，可以使得从任意一个点出发， $k$ 步后都停留在 $1$ 号节点。
输入保证在不进行修改的情况下，从任意一个点出发，最终都能到达城镇。
解法 易知最后的图将会是一个以 $1$ 号节点为根节点的树，且树的最大深度不超过 $k$。
从叶子节点出发，每次遇到深度为 $k$ 的节点就将该节点连到 $1$ 号节点上即可。
代码 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 #include <bits/stdc++.h> using namespace std ;#define N 100001 vector <int > e[N];int n, k, ans;int dfs (int u) int l = 1 , d; for (int v : e[u]) if ((d = dfs(v)) == k) ans++; else l = max(d + 1 , l); return l; } int main () scanf ("%d%d" , &n, &k); for (int i = 1 , x; i <= n; i++) { scanf ("%d" , &x); if (i > 1 ) e[x].push_back(i); else ans += x != 1 ; } for (auto v : e[1 ]) dfs(v); printf ("%d\n" , ans); return 0 ; }
题意 给定一个 $n \times m$ 的网格，其上分布着一些小机器人，以及一个唯一的出口。
现在每次可以选择上下左右四个方向之一，让所有的机器人们全部向指定方向移动一个单位距离。越出边界或进入出口的机器人将会立刻消失，询问最多可以让多少机器人通过出口。
解法 $f[i][j][k][l]$ 表示在四个方向的边界分别为 $i,j,k,l$ 时能通过的最多机器人。
因为卡了空间，所以用将状态压缩一下。
代码 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 #include <bits/stdc++.h> using namespace std ;#define dmax(x, y) x = max(x, y); #define N 110 #define M 10000001 int n, m, addx, addy, ans;int a[N][N], b[N][N], f[M];char c[N];inline int pos (int i, int j, int k, int l) return ((i * (n - addx + 1 ) + j) * addy + k) * (m - addy + 1 ) + l + 1 ; } int main () scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= n; i++) { scanf ("%s" , c + 1 ); for (int j = 1 ; j <= m; j++) { a[i][j] = a[i][j - 1 ] + (c[j] == 'o' ); b[i][j] = b[i - 1 ][j] + (c[j] == 'o' ); if (c[j] == 'E' ) addx = i, addy = j; } } for (int i = 0 ; i < addx; i++) for (int j = 0 ; j <= n - addx; j++) for (int k = 0 ; k < addy; k++) for (int l = 0 ; l <= m - addy; l++) { int s = f[pos(i, j, k, l)]; ans = max(ans, s); if (addx - i - 1 > j) dmax(f[pos(i + 1 , j, k, l)], s + a[addx - i - 1 ][min(addy + l, m - k)] - a[addx - i - 1 ][max(addy - k - 1 , l)]); if (addx + j + 1 <= n - i) dmax(f[pos(i, j + 1 , k, l)], s + a[addx + j + 1 ][min(addy + l, m - k)] - a[addx + j + 1 ][max(addy - k - 1 , l)]); if (addy - k - 1 > l) dmax(f[pos(i, j, k + 1 , l)], s + b[min(addx + j, n - i)][addy - k - 1 ] - b[max(addx - i - 1 , j)][addy - k - 1 ]); if (addy + l + 1 <= m - k) dmax(f[pos(i, j, k, l + 1 )], s + b[min(addx + j, n - i)][addy + l + 1 ] - b[max(addx - i - 1 , j)][addy + l + 1 ]); } printf ("%d\n" , ans); return 0 ; }
题意 给定一棵树或基环树，每个节点可以被染为白色或黑色，初始均为白色。每次可以选择一对颜色相同的相邻节点，并将其颜色反转，询问能否让所有节点的颜色均变为黑色。
解法 神题，分三种情况讨论：
树 首先按照节点深度的奇偶对节点进行分类，这样这颗树就被转化为二分图。
审视目标：将二分图中所有点的颜色反转。
这样不如改变初始颜色，假定树中深度为偶数的节点一开始都是黑色，深度为奇数的节点一开始都是白色。这样一来，目标没变，而操作变成了：每次可以选择一堆颜色不同的相邻节点，并将其颜色交换。
这样一来，要求两侧所有点的颜色反转，只要有两种颜色的数量相等即可。
记 $s_i$ 表示以 $i$ 为根节点的子树中两种颜色的数量的差值，那么答案即为 $\displaystyle \sum_{i=1}^n{abs(s_i)}$。
这里 $s_i$ 蕴含了第二种含义，即 $s_i$ 必须要和自己的父节点进行交换的次数。不然颜色数量不等，无法让该子树实现目标。
奇环 断开环上任意一条边，将其转化为树，这样就有该边两边的点在同一侧。
有奇环的情况下不需要两种颜色的数量相等。而只需要颜色的差值为偶数即可。
将差值降到该边两边的点的那一侧中，使得颜色数相等，然后用树的方法解决。
偶环 断开环上任意一条边，将其转化为树，这样就有该边两边的点不在同一侧。
假设该边进行了 $k$ 次操作，因为操作有方向性，所以可能 $k$ 为负数。
答案即为 $\displaystyle |k| + \sum_{i=1}^n abs(s_i+kx_i)$。
其中 $\sum_{i=1}^n abs(s_i+kx_i)$ 可以看作数轴取点问题，易知取中位数最优。
代码 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 #include <bits/stdc++.h> using namespace std ;#define N 500001 #define M 1000001 int fa[N], d[N], f[N], su, sv;int hd[N], nx[M], e[M], num;int n, m, ans;void dfs (int x, int dep) d[x] = dep, f[x] = dep & 1 ? 1 : -1 ; for (int i = hd[x]; i; i = nx[i]) { if (e[i] == fa[x]) continue ; if (d[e[i]]) { su = x, sv = e[i]; continue ; } fa[e[i]] = x; dfs(e[i], dep + 1 ); f[x] += f[e[i]]; } } int main () scanf ("%d%d" , &n, &m); for (int i = 1 , x, y; i <= m; i++) { scanf ("%d%d" , &x, &y); nx[++num] = hd[x], hd[x] = num, e[num] = y; nx[++num] = hd[y], hd[y] = num, e[num] = x; } dfs(1 , 1 ); if (m == n - 1 ) { if (f[1 ]) return (puts ("-1" ), 0 ); for (int i = 1 ; i <= n; i++) ans += abs (f[i]); } else if ((d[sv] - d[su]) & 1 ) { if (f[1 ]) return (puts ("-1" ), 0 ); vector <int > vec; while (sv != su) vec.push_back(f[sv]), d[sv] = 0 , sv = fa[sv]; sort(vec.begin(), vec.end()); int mid = vec[vec.size() / 2 ]; ans = abs (mid); for (int i = 1 ; i <= n; i++) if (d[i]) ans += abs (f[i]); for (auto i : vec) ans += abs (i - mid); } else { if (f[1 ] & 1 ) return (puts ("-1" ), 0 ); int del = -f[1 ] / 2 ; ans = abs (del); while (su) f[su] += del, su = fa[su]; while (sv) f[sv] += del, sv = fa[sv]; for (int i = 1 ; i <= n; i++) ans += abs (f[i]); } printf ("%d\n" , ans); return 0 ; }
AGC005 题意 给定只包含字符 S 和 t 的字符串 $s$，不断执行删除 $s$ 中最左边的子串 ST ，直到 $s$ 中不再包含 ST 为止。
输出最后的 $s$。
解法 用栈处理即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std ;#define N 200010 char s[N], sta[N];int top;int main () scanf ("%s" , s); int n = strlen (s); for (int i = 0 ; i < n; i++) if (top) { if (s[i] == 'S' ) sta[++top] = 'S' ; else if (sta[top] == 'S' ) top--; else sta[++top] = 'T' ; } else sta[++top] = s[i]; printf ("%d\n" , top); return 0 ; }
题意 给定长度为 $n$ 的序列 $a$，求：$\displaystyle \sum_{l=1}^n \sum_{r=l}^n \min(a_l,a_{l+1},\dots, a_r)$
解法 预处理每一个 $a_i$ 在多少区间中作为最小值即可。
向左右分别拓展出最长距离，用单调栈处理。
代码 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 #include <bits/stdc++.h> using namespace std ;#define ll long long #define N 2000010 int a[N], n;int sta[N], top;int l[N], r[N];int main () scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) scanf ("%d" , &a[i]); for (int i = 1 ; i <= n; i++) { while (top && a[i] <= a[sta[top]]) r[sta[top--]] = i - 1 ; sta[++top] = i; } while (top) r[sta[top--]] = n; for (int i = n; i; i--) { while (top && a[i] <= a[sta[top]]) l[sta[top--]] = i + 1 ; sta[++top] = i; } while (top) l[sta[top--]] = 1 ; ll ans = 0 ; for (int i = 1 ; i <= n; i++) ans += (ll)(r[i] - i + 1 ) * (i - l[i] + 1 ) * a[i]; printf ("%lld\n" , ans); return 0 ; }
题意 给定长度为 $n$ 的序列 $a$，询问能否构造出一棵包含 $n$ 个节点的树，满足节点 $i$ 到其他节点的距离的最大值为 $a_i$ .
解法 从树的直径的求法出发进行思考。
记树的直径为 $k$，那么有 $\displaystyle k =\max_{i=1}^n a_i$。
不难想到只要能构造出直径，那么其他节点都可以构造出来。
而直径上点到其他点的最远距离变化规律如下：
$k$ 为奇数：$k \rightarrow k-1 \rightarrow \dots \rightarrow \lfloor \frac{k+1}{2} \rfloor \rightarrow \lfloor \frac{k+1}{2} \rfloor \rightarrow k-1 \rightarrow k$
$k$ 为偶数：$k \rightarrow k-1 \rightarrow \cdots \rightarrow \frac{k}{2} \rightarrow k-1 \rightarrow k$
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> using namespace std ;#define N 101 int num[N], n, maxn, minn = N;int main () scanf ("%d" , &n); for (int i = 1 , x; i <= n; i++) { scanf ("%d" , &x); num[x]++; maxn = max(maxn, x); minn = min(minn, x); } int mid = (maxn + 1 ) >> 1 ; bool flag = (minn >= mid) && (num[mid] == (maxn & 1 ) + 1 ); for (int i = maxn; i > mid && flag; i--) if (num[i] < 2 ) flag = false ; puts (flag ? "Possible" : "Impossible" ); return 0 ; }
题意 给定正整数 $n$ 和 $k$，询问 $n$ 的全排列 $a$ 中有多少满足 $\forall i \in[1,n], |a_i -i| \neq k$。
解法 可以想到用总方案数减去非法方案数即可，这里需要对非法方案数进行容斥，即：
式中 $g(i)$ 表示至少有 $i$ 个位置非法的方案数。
考虑将每一个位置和每一个值都看作点，构成一个二分图，如果 $i$ 号位不可以填 $j$，则从 $i$ 向 $j$ 连边，这样就得到了一个二分图，问题就变成了选 $i$ 条边的方案数。
单独把每一条链拉出来并首尾相连，即构成了一条长为 $2n$ 的链，在这条链上进行 DP 即可。
令 $f[i][j][0/1]$ 表示前 $i$ 个位置中有 $j$ 个不合法，当前点是否与上一点相连的方案数，则有：
代码 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 #include <bits/stdc++.h> using namespace std ;#define ll long long #define mod 924844033 #define N 2001 int n, k, num;bool vis[N << 1 ];ll fac[N] = {1 }, f[N << 1 ][N][2 ] = {1 }; int main () scanf ("%d%d" , &n, &k); for (int i = 1 ; i <= n; i++) fac[i] = fac[i - 1 ] * i % mod; for (int i = 1 ; i <= k; i++) for (int l = 1 ; l <= 2 ; l++) for (int j = i; j <= n; j += k) { num++; if (j != i) vis[num] = true ; } for (int i = 0 ; i < 2 * n; i++) for (int j = 0 ; j <= n; j++) { f[i + 1 ][j][0 ] = (f[i][j][0 ] + f[i][j][1 ]) % mod; if (vis[i + 1 ]) f[i + 1 ][j + 1 ][1 ] = f[i][j][0 ]; } ll ans = 0 ; for (int i = 0 ; i <= n; i++) { ll s = (f[2 * n][i][0 ] + f[2 * n][i][1 ]) * fac[n - i] % mod; ans = (ans + (i & 1 ? mod - s : s)) % mod; } printf ("%lld\n" , ans); return 0 ; }
题意 给定一棵红树和一棵蓝树，两棵树节点数均为 $n$ 且共用这 $n$ 个节点。
现在这两棵树上各有一个人，分别是 $x$ 和 $y$，位置分别为 $addx$ 和 $addy$。两人均只能沿着自己所在的树的边轮流移动， $x$ 先行，当 $x$ 和 $y$ 处于同一节点时游戏结束。
$x$ 希望游戏尽可能晚结束， $y$ 希望游戏尽可能早结束。询问你游戏什么时候结束，若不能结束则输出 -1 。
解法 可以想到红树上可能存在 安全边 ，即 $x$ 到达该边所在的某一端点后即可在这条边上左右横跳而不会被 $y$ 捉住。
一条边是安全边的充要条件是，这条边的两端点在蓝树的上的距离大于 $2$。这样 $y$ 就不能同时“威慑”这条边的两个端点，即两端点间同一时间至多有一个点被“威慑”。
分别以 $addx$ 和 $addy$ 作为红树和蓝树的根，预处理每一个根节点到每一个节点的距离（即深度）。
对于任意一个点 $i$，如果 $y$ 到它的距离不长于于 $x$ 到它的距离，则以该点为根节点的的红树的子树中即使存在安全边， $x$ 也无法到达。
如果不存在安全边或无法到达安全边，那么检查所有 $x$ 能到达的节点，最大深度即为回合轮数。每轮两次操作，所以答案为最大回合轮数乘二。
代码 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 #include <bits/stdc++.h> using namespace std ;#define N 200001 #define M 21 vector <int > ex[N], ey[N];void init (int n, vector <int >* e) for (int i = 1 , u, v; i < n; i++) { scanf ("%d%d" , &u, &v); e[u].push_back(v); e[v].push_back(u); } } int fx[N], fy[N][M], dx[N], dy[N];void dfsy (int u) for (auto v : ey[u]) { if (v == fy[u][0 ]) continue ; fy[v][0 ] = u, dy[v] = dy[u] + 1 ; for (int i = 1 ; i < M; i++) fy[v][i] = fy[fy[v][i - 1 ]][i - 1 ]; dfsy(v); } } int lca (int u, int v) if (dy[u] < dy[v]) swap(u, v); for (int i = M - 1 ; ~i; i--) if (dy[fy[u][i]] >= dy[v]) u = fy[u][i]; if (u == v) return u; for (int i = M - 1 ; ~i; i--) if (fy[u][i] != fy[v][i]) u = fy[u][i], v = fy[v][i]; return fy[u][0 ]; } int ans;void dfsx (int u) if (dx[u] >= dy[u]) return ; if (~ans) ans = max(ans, dy[u] << 1 ); for (auto v : ex[u]) { if (v == fx[u]) continue ; fx[v] = u, dx[v] = dx[u] + 1 ; if (dy[v] + dy[u] - 2 * dy[lca(u, v)] > 2 ) ans = -1 ; dfsx(v); } } int main () int n, addx, addy; scanf ("%d%d%d" , &n, &addx, &addy); init(n, ex); init(n, ey); dfsy(addy); dfsx(addx); printf ("%d\n" , ans); return 0 ; }
题意 解法 代码