AGC 随机做【暂时完结】【san 值掉光了】

· · 个人记录

虽然题题都不会做，但是就是停不下来啊……怎么办，再这样下去要变得奇怪了♥

AGC047E - Product Simulation

列一下我们能做的操作：

现在考虑原问题，一个显然的想法是

\sum_{i,j}[2^i]A\times[2^j]B\times 2^{i+j}

可以把 2^{i+j} 对应的系数处理出来（\log A\times \log B），然后直接自加即可。

AGC052A - Long Common Subsequence

我是 sb

## AGC052C - Nondivisible Prefix Sums - 一个合法序列中所有元素 $\times X$ 一定仍得到一个合法序列。 - 一个序列不合法是一个**非常**苛刻的条件，必须有一大堆相同元素，而且 $P$ 也必须很小。 我们考虑把整个序列的众数变为 $1$，不合法的一个必要条件是 $P-1+\sum_{a_i\neq 1}P-a_i\ge \sum[a_i=1]$。 然后……它也是充分条件。（标 准 结 局）DP 即可。 ## AGC052D - Equal LIS - 最终的 LIS 长度 $L'$ 必定小于等于原序列 LIS $L$。 - 考虑对原序列[分层](https://loj.ac/p/3548)。 - - 如果 $L=0\pmod 2$，那么这个问题总是有解：只需要把前 $L/2$ 层和后 $L/2$ 层划开即可。 - 对于 $L=1\pmod 2$……试试 $L/2+1$？ - - 如果 LIS 不唯一，那么已经成功了：只要有一个 $i$ 不同时存在于所有 LIS，不妨设 $i$ 的层数 $\ge L/2+1$（反之亦然），先按 $L/2, L/2+1$ 划开，再把 $i$ 重新划到另一边。这样 $i$ 所在的 LIS 被划为了 $L/2+1,L/2$，而 $i$ 不在的 LIS 被划为了 $L/2,L/2+1$。 - 对 LIS 唯一的情况实际上是类似的，我们只需要找到一个有相同功能的 $i$ 即可。我们断言：【划分成功当且仅当存在一个 $i$，$i$ 不在 LIS 中，且 $i$ 存在于一条长度为 $L/2+1$ 的 LIS 中】。 - 必要性是显然的，充分性则类似于刚刚的过程。 ## AGC052E - 3 Letters Anton 似乎对这种串颇有研究啊 如果有 AB、BC、CA 的结构我们就写下一个 $+1$；否则我们写下一个 $-1$。最后还要标记一下 $s_1$。这自然是一个双射。 再来考虑这个新序列的前缀和 $b$，可见我们可以直接通过 $b_i\bmod 3$ 来读出 $s_i$。而一次操作的效果就是令 $b_i\leftarrow b_i\pm 2$，一次操作合法当且仅当 $b$ 序列仍保持 $|b_i-b_{i-1}|=1$ 的性质。 于是答案至少是 $\min\sum|bs_i-bt_i|$（其中 $\min$ 枚举的是所有可能的 $bs_1,bt_1$），然后……它又是下界。 - 考虑所有 $bs_i\neq bt_i$ 的位置，我们必定可以把其中 $bs$ 最大者（最小者亦然）减去 $2$。分讨一下容易确定这一点。 剩下的工作已经很简单了。 ## AGC046D - Secret Passage 整个过程类似于，从 $S$ 的前缀中收集一定量的 $0/1$ 并插到其后缀里，当然也有可能会销毁一些 $0/1$。对于前缀 $i$，能否收集到 $j_0$ 个 $0$ 和 $j_1$ 个 $1$ 可以通过 DP 求出。 为了防止数重，只需要额外规定：$0$ 后只能插 $1$，$1$ 后只能插 $0$。也是 DP 即可。 ## AGC046E - Permutation Cover ![](https://xyix.github.io/images/fuck-constructive.png) 设总长为 $S$，显然，同种元素最多出现 $\lceil S/K\rceil$ 次，且出现 $\lceil S/K\rceil$ 次的元素最多 $(S-1\bmod K)+1$ 种。 然后，这又是一个充分条件！ 考虑出现次数最多的元素，不妨设为 $1$。 - 如果 $1$ 的数量恰好是 $\lceil S/K\rceil$，那么在 $1,K+1,2K+1,\ldots$ 放 $1$，直接令 $K\leftarrow K-1$ 继续递归； - 如果 $1$ 的数量恰好是 $\lfloor S/K\rfloor$，那么在 $K,2K,3K,\ldots$ 放 $1$，直接令 $K\leftarrow K-1$ 继续递归； - 否则任何元素的数量都 $<\lfloor S/K\rfloor$，考虑这样一个摆法：坐标每次 $+K$，如果超出范围就回到第一个没填的位置，直接把所有元素 sort 后依次填进去。不难发现这总是成功。 ## AGC051E - Middle Point 可见能造出的点就是所有 $\sum_iw_i(x_i,y_i)$，其中 $w_i$ 是由你任意指定的形如 $\dfrac{*}{2^*}$ 的权值，且 $w_i\ge 0,\sum w_i=1$。 我们断言，这等价于 - 在 $(x_i,y_i)$ 构成的凸包内（含边界）的 $\sum_iw_i(x_i,y_i)$ 中有多少整点？其中 $\sum w_i=1$，但不必有 $w_i\ge 0$。 好像不好证，但确实很直观（ 其实我们还可以把某个关键点移到原点，这样 $\sum w_i=1$ 的约束也解除了。 现在，形如 $\sum_iw_i(x_i,y_i)$ 的点结构十分简单，总是可以不断归约到 $n=2$ 的情形：对 $x$ 坐标辗转相除即可。不妨设新坐标系的两个基向量形如 $(x_1,y_1),(0,y_2)$。 一个整点 $(x,y)$ 合法当且仅当其在新坐标系上的坐标形如 $(*/2^*,*/2^*)$，即： - $x_1/\gcd(x_1,2^{\infty})$ 是 $x$ 的因子。 - $y_2/\gcd(y_2,2^{\infty})$ 是 $y-y_1\gcd(x_1,2^{\infty})/x_1$ 的因子。 好吧总之是个网格！而关键点必定在格点上，因此只需要用 pick 定理算一下凸包内点数即可。 ## AGC048B - Bracket Score 我们考虑，如果只看 AB 能不能方便地还原出括号序列。有这样一个贪心：栈顶有两个相同字符就认为一个是左括号一个是右括号，因此应当消掉。但如果这样 DP 是 $n^2$ 的，不能通过。 正解可能是个贪心？ 考虑刚才的 DP，如果第一个字符是 A，那么**所有偶位置的 A 必定会被认为是右括号，B 反之。**实际上就是**偶位置上的 A 数目与奇位置上的 A 相同。**这是一个充分必要条件。 先初始化为全 B，然后每次选一对元素置为 A，只要有收益就一直选即可。 ## AGC048C - Penguin Skating - 企鹅不能互相越过。 - $1$ 号企鹅要划到 $B_1$ 且 $B_1\neq 1$，那么当时 $2$ 号企鹅必处于 $B_1+1$。 - - 如果 $A_2>B_1+1$，那么已经失败了。 - 那么如果 $A_2\neq B_1+1$，$2$ 号企鹅划到 $B_1+1$ 时 $3$ 号企鹅必处于 $B_1+2$。以此类推，直到失败或存在 $A_i=B_1+i-1$。 然后令 $B_1$ 为边界，分治求解。 --- 有一个更好的推理方式：考虑以企鹅间的空格为基本对象，那么一次向左划实际上就是 $x_{i+1}\leftarrow x_{i+1}+x_i,x_i\leftarrow 0$，向右划反之。 自然，最终的一个非零 $x_i$ 必定是由一个区间 $[l,r]$ 合并产生的，不难证明总是需要且仅需要 $\max(i-l,0)+\max(0,r-i)$。 ## AGC048D - Pocky Game ~~为什么有人玩 Pocky Game 还会想着博弈论啊草，这种人真的能找到另一个玩家和 TA 玩 Pocky Game 吗？~~ ~~其实是因为 FirstLeft 和 SecondRight 都比较害羞，所以他们都不希望太主动~~ 当进入最后一堆时就变为了 nim 游戏。 如果还剩两堆，且先手所处的堆大小 $X\ge 2$，那么他已经赢了： - 如果最后一堆是一个先手必败堆，直接取 $X$。 - 如果最后一堆是一个先手必胜堆，取 $X-1$。后手操作一步，最后一堆就变成了先手必败堆，然后入场即可。 否则如果 $X=1$，那么胜负状态与最后一堆相反。 那么我们已经有了一个区间 DP 的想法：一个区间是否胜利与端点的堆大小有关，事实上不必是如上的 $\ge 2$，而可能是 $\ge $ 任何值（考虑这个 case：右边有一堆 1 和 2，左边的堆必须足够大才能保证先手在后手以任何速度把右边吃完的情况下都能胜利），而我们要 DP 的就是这个分界点。直接做就好了。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 105; int n; int A[maxn]; ll L[maxn][maxn]; ll R[maxn][maxn]; ll dfsL(int, int); ll dfsR(int, int); ll dfsL(int l, int r) { if (l == r) return L[l][r] = 1; if (L[l][r] != -1) return L[l][r]; if (dfsR(l + 1, r) > A[r]) L[l][r] = 1; else L[l][r] = A[r] - dfsR(l + 1, r) + dfsL(l, r - 1) + 1; return L[l][r]; } ll dfsR(int l, int r) { if (l == r) return R[l][r] = 1; if (R[l][r] != -1) return R[l][r]; if (dfsL(l, r - 1) > A[l]) R[l][r] = 1; else R[l][r] = A[l] - dfsL(l, r - 1) + dfsR(l + 1, r) + 1; return R[l][r]; } int main() { int T; scanf("%d", &T); while (T--) { memset(L, -1, sizeof(L)); memset(R, -1, sizeof(R)); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &A[i]); if (dfsL(1, n) <= A[1]) printf("First\n"); else printf("Second\n"); } } ``` ## AGC043C - Giant Graph 模拟赛搬 AGC，真有你的 考虑按权值从大到小贪心，图变成了 DAG；如果直接后继都未被选就选上该点。 ——这好像是博弈论中必败/必胜的定义啊？ 于是一个点被选（必败）当且仅当其 SG 值为 $0$，而三个维度也就变为了三个子游戏，一个点的 SG 值就是三个维度的 SG 值之异或。所欲求的答案也就变为了异或卷积。 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int p = 998244353; int qpow(int a, ll k, int mod) { int ans = 1; while (k) { if (k & 1) ans = 1LL * ans * a % mod; a = 1LL * a * a % mod; k >>= 1; } return ans; } const int maxn = 100005; int n; struct Graph { vector<int> G[maxn]; int SG[maxn]; int f[8192]; void build() { int m; scanf("%d", &m); while (m--) { int u, v; scanf("%d%d", &u, &v); if (u > v) swap(u, v); G[u].push_back(v); } for (int i = n; i; i--) { vector<int> lis; for (int j : G[i]) lis.push_back(SG[j]); sort(lis.begin(), lis.end()); for (int x = 0, j = 0; ; x++) { if (j >= (int)lis.size() || lis[j] > x) { SG[i] = x; break; } while (j < (int)lis.size() && lis[j] <= x) j++; } f[SG[i]] = (f[SG[i]] + qpow(10, 18LL * i % (p - 1), p)) % p; assert(SG[i] < 8192); } for (int i = 0; i < 13; i++) for (int s = 0; s < 8192; s++) if (!((s >> i) & 1)) { int ta0 = f[s], ta1 = f[s ^ (1 << i)]; f[s] = (ta0 + ta1) % p; f[s ^ (1 << i)] = (ta0 - ta1 + p) % p; } } } G1, G2, G3; int main() { scanf("%d", &n); G1.build(); G2.build(); G3.build(); int g[8192]; for (int i = 0; i < 8192; i++) g[i] = 1LL * G1.f[i] * G2.f[i] % p * G3.f[i] % p; for (int i = 0; i < 13; i++) for (int s = 0; s < 8192; s++) if (!((s >> i) & 1)) { int ta0 = g[s], ta1 = g[s ^ (1 << i)]; g[s] = (ta0 + ta1) % p; g[s ^ (1 << i)] = (ta0 - ta1 + p) % p; } int qaq = qpow(8192, p - 2, p); for (int i = 0; i < 8192; i++) g[i] = 1LL * g[i] * qaq % p; printf("%d\n", g[0]); } ``` ## AGC048E - Strange Relation 还真是 Strange Relation，完全不知道怎么入手。 - $x_1=0$。 - 可以把 $A_i,T$ 都离散化（因为我们实际上关心的只是 $A_i=k_iT+b_i$ 中的 $k_i$ 和 $b_i$）。 - $y_i>x_i$ 不是问题，只要反复 $+T$ 就一定可以消除。$y_i<x_i$ 也不是问题，这时候把 **x 直接清零**，就又有 $y\ge x$ 了。如果还有后续影响就继续递归。 - - 即，合法性总是可以轻松保证。 - 另外，由此可以推出：$i$ 后不会有 $[A_i+Tx_i-T,A_i+Tx_i)$ 中的元素，否则对它们中的下标最小者 $+T$，必定可以得到一个 $y_i\ge x_i$。 我们或许可以直接一个一个贪心过去？枚举 $x_i$ 不能接受。这并不是复杂度的问题，而是这样的策略太过复杂，当 $A_i$ 飘忽不定时"连续性"太差。 有没有对众 $A_i$（相对比较）独立的做法？——？？？这怎么可能呢？ --- 这是可能的。考虑删去 $A_1$ 并归约为一个子问题。 - 其他元素分为两类，$<A_i-T$ 和 $\ge A_i$，对于后者的 $x$ 集体减 $1$。这就得到了一个 $(A_2,A_3,\ldots,A_n)$ 的合法方案；而反过来，它的一个合法方案也必定可以通过其逆映射回到一个 $(A_1,\ldots,A_n)$ 的合法方案。 - - 于是，问题就变为求 $(A_2,\ldots,A_n)$ 的字典序最大的方案。不断递归即可。 剩下的工作只是一个 DP，已经非常显然了。 ```cpp #include<bits/stdc++.h> using namespace std; const int p = 1000000007; struct Z {int x; Z(int x0 = 0) : x(x0) {}}; int inline check(int x) { return x >= p ? x - p : x; } Z operator +(const Z a, const Z b) { return check(a.x + b.x); } Z operator -(const Z a, const Z b) { return check(a.x - b.x + p); } Z operator -(const Z a) {return check(p - a.x);} Z operator *(const Z a, const Z b) { return 1LL * a.x * b.x % p; } Z& operator +=(Z &a, const Z b) { return a = a + b; } Z& operator -=(Z &a, const Z b) { return a = a - b; } Z& operator *=(Z &a, const Z b) { return a = a * b; } Z qpow(Z a, int k) { Z ans = 1; for (; k; a *= a, k >>= 1) if (k & 1) ans *= a; return ans; } const int maxn = 55; int n, m, T; int A[maxn][maxn]; Z f[maxn][maxn]; int main() { scanf("%d%d%d", &n, &m, &T); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &A[i][j]); for (int i = 1; i <= n; i++) { Z ans = 0; for (int k1 = 1; k1 <= m; k1++) { memset(f, 0, sizeof(f)); f[i][0] = 1; for (int j = i - 1; j; j--) for (int x = 1; x <= n; x++) for (int k2 = 1; k2 <= m; k2++) if (A[i][k1] + T * x > A[j][k2]) f[j][x] += f[j + 1][x - 1]; else f[j][x - 1] += f[j + 1][x - 1]; for (int j = 1; j < n; j++) ans += j * f[1][j]; } printf("%d\n", ans * qpow(m, n - i)); } return 0; } ``` ## AGC049C - Robots **项目等级**：Euclid 假如现在有一堆 $5$，那么我们可以把第一个 $5$ 改成 $6$ 来直接摧毁 $5$ 号机器人，于是后面的 $5$ 球都会被忽略。 但还有一个问题：如果 $6$ 本身就能走到 $1$，而是让 $7$ 把 $5,6$ 都摧毁。事实上只要找到第一个 $B<A$ 的机器人，摧毁它前面连续的一段 $B\ge A$ 的机器人即可。 具体来说，最终方案中肯定是 $B<A$ 的安全机器人先走，摧毁所有 $B\ge A$ 的危险机器人。而我们有两种操作： - 给一个危险机器人减步数，让它变成安全机器人（显然，这个操作仅会进行一次，因为它会摧毁前面的所有危险机器人）； - 给一个安全机器人加步数，让它能摧毁更多的危险机器人（显然，这个操作的步数就是一操作结束后危险机器人的数量）。 而步数就是两者步数的 max（其实不是很显然）。直接爆枚即可。 ## AGC049D - Convex Sequence **项目等级**：Euclid 斜率最多根号种。这应当是一个值得利用的性质。 先枚举最小值，共 $M/N$ 种；然后枚举最小值出现的位置，共 $N$ 种。一共 $O(M)$ 种情况。 然后枚举斜率的分界点。其实就是反复执行以下操作： - $a_i\leftarrow a_i+1,a_{i+1}\leftarrow a_{i+1}+2,a_{i+2}\leftarrow a_{i+2}+3\ldots

就是个 O(\sqrt M) 个物品的背包？

又发现，当最小值和其出现的位置移动时，所对应的背包问题的物品集合差别不大，而我们是可以暴力删除任意物品的，这样就过了。

AGC049E - Increment Decrement

项目等级：Apollyon（因为被凸包的部分搞晕了很久）

ZJOI2020 序列（幻视）用类似的技巧，即分开考虑两种操作的贡献。

假设我们一操作把序列变成了 b，那么总步数为

\sum_{i}|a_i-b_i|+C\sum_{i=1}^{n+1}\max(b_i-b_{i-1},0)

其中 b_{n+1}=0。

自然考虑一个大力 DP，即枚举当前的 b。我们断言，DP 值关于当前的 b_i 是下凸的。（显然）

接下来考虑怎么能让这个做法在 a 变动时的连续性变好：这个最优化问题和"对所有方案求和"似乎矛盾很大。

考虑维护凸包上的拐点。我们断言：拐点的 x 坐标必定是 0 或 a_i。问题自然就变成怎么维护斜率（更具体一点是维护差分数组）。

回忆转移方程：

F(i+1,X)=|a_{i+1}-X|+\min_YF(i,Y)+\max(0,C(X-Y))

可见我们有三种选择：

再考虑到 |a_{i+1}-X| 的影响，这个过程就变为

现在回头来考虑所欲求的 F(i+1,0)，就有

F(i+1,0)=a_{i+1}+F(i,0)+\min_Y\sum_{j=1}^Y\text{d}F(i,j)

又由于 \text{d}F(i,j) 单调增，于是就是

F(i+1,0)=a_{i+1}+F(i,0)+\sum_{j}\min(\text{d}F(i,j),0)

终于！\text{d}F(i,j) 的贡献互相独立了！

剩下的工作已经很显然了。

AGC053B - Taking the Middle

项目等级：Euclid

考虑 Aoki 拿了什么牌：相当于 Aoki 有一个指针，初始时摆在中间，Takahashi 可以指挥它往哪个方向走半步。

尴尬之处在于 Aoki 可能因为一张牌已经被 Takahashi 拿了而跳过它。

给定一个集合，Aoki 什么时候恰能拿了这个集合？

然后这又是个必要条件。

AGC053C - Random Card Game

项目等级：Euclid

好像有点复杂。

关键在于【2N-1 低于 2N】这样的结构，由此，我们断言，答案为

n+\max_i\min_{A_j>B_i}j-i

由此，考虑计算 \max_i\min_{A_j>B_i}j-i\le X 的方案数。考虑特定 A_i，它不能是 A_{1\sim i-1},B_{1\sim \min(n,i+X)} 的最大值，若从后往前确定 A_i 则立即可见答案为

\prod_{i=1}^n\dfrac{\min(i+n,2i+X)-1}{\min(i+n,2i+X)}