【笔记】杂题选讲 2024.10.5（DNF）

十一杂题选讲 - Virtual Judge (vjudge.net)

/mnt/e/codes/contests/20241008/sol.md

• [AGC004F] Namori
• [1406E] Deleting Numbers
• [1081G] Mergesort Strikes Back
• [1033E] Hidden Bipartite Graph
• [1254E] Send Tree to Charlie
• [1012E] Cycle sort
• [1284F] New Year and Social Network
• [1292E] Rin and The Unknown Flower
• [1548D2] Gregor and the Odd Cows (Hard)

[AGC004F] Namori

[AGC004F] Namori - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

最重要的观察是：将

• 所有点初始颜色为白。
• 每次操作可以处理一条边，其两个点如果颜色相同则都变成相反的颜色。
• 请使所有点的颜色反转。

转写为

• 找一棵生成树，做二分图黑白染色。
• 对于二分图上的边，每次交换两个点的颜色。
• 对于非二分图上的边，其两个点如果颜色相同则都变成相反的颜色。
• 请使所有点的颜色反转。

本题不在二分图上的边最多一条。剩余的讨论可以直接看 题解 AT2046 【AGC004F Namori】 - 洛谷专栏 (luogu.com.cn)。

启发：操作中带有“如果”是不好刻画的，像本题的操作可以通过黑白染色，将其转化为交换操作。

[1406E] Deleting Numbers

Deleting Numbers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个的话就直接对每个质因子考虑即可了。第一个质因子使用根号分治找出，然后就能一次询问判断 \(x\) 是否有其他质因子。质因子的次数使用二分求出。

[1081G] Mergesort Strikes Back

Mergesort Strikes Back - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

叶子上的贡献十分好求。然后发现现在合并就是将一个数与那个位置的前缀最大值绑在一起考虑了。

对着前缀最大值考虑很难。听课之后发现，可以直接对每个位置上的数考虑。固定 \(lhs\) 的第 \(i\) 个数和 \(rhs\) 的第 \(j\) 个数。设 \(lhs\) 并 \(rhs\) 的最大值为 \(mx\)，若 \(mx\in\{lhs_i, rhs_j\}\)，则它们一定会被排好序。否则它们的顺序变为固定的，有 \(1/2\) 的概率贡献逆序对。

启发：拆贡献。

[1033E] Hidden Bipartite Graph

Hidden Bipartite Graph - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个以为很难，没仔细想。首先肯定是搜出一棵生成树。如果我们能很快找出一条存在的边，那么我们只需要将这个过程 perform \(n-1\) 次就能找出一棵生成树。然后可以判断二分图的某一部内有没有互相连边，随意二分一下用 \(O(\log n)\) 次代价。所以怎么找出存在的边，不妨写 bfs，就是对于一个点 \(u\) 和未访问点集 \(S\)（没有必要重复搜所有的点），询问 \(\{u\}\cup S\) 减去 \(S\) 的答案就能知道有没有边，于是就能 \(O(\log n)\) 找出这条存在的边。还有边可以继续找，反正该过程不会超过 \(O(n)\) 次。

[1254E] Send Tree to Charlie

Send Tree to Charlie - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题首先观察到我们肯定是将有限制的 \(a_i\) 往目标点移动，到目标点的路径上会有对一个点连接的边中钦定某一条要最先操作，或者钦定某一条最后操作，或者钦定某一条在另一条之后操作。然后还观察到如果路径总和超过 \(2n\)（或者说很多次经过某个点）肯定是无解的。

听完课发现因为我们要数的是最终 \(a_i\) 形态而不是操作序列数，所以每个点上都应独立考虑。那么在一个点上，它相连的边有若干顺序限制，只在这个点上考虑限制，若每个点上都有解，则我们随便搞都能构造方案（例如，先选一条边，然后一直追溯它的前驱，然后操作，具体细节不重要，并注意到这可能对应多个方案但只会对应一种最终序列）。而每个点上因为是描述”紧挨“的限制，所以只会有一大堆链和一大堆非法的环。然后判掉一种情况之后，每个点的方案数就变成了一个阶乘。全部点的答案乘起来就是答案。

写代码的时候发现一种有趣的写法。atexit 函数。在全局开一个存答案的变量，初始为 \(0\)，然后在 main 的第一行调用 atexit(+[]() { cout << ans << endl; });，这样在判到无解之后直接 exit(0) 就能输出答案。有解的情况就修改 ans，正常退出的时候也会输出答案。

启示：注意对最终序列计数和对操作序列计数的差异。前者可能是刻画最终序列上每个点的性质，每个点之间可能是独立的。后者可能是刻画操作的性质，或它们之间的顺序与关联。两者不能混淆。

[1012E] Cycle sort

Cycle sort - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P6305 [eJOI2018] 循环排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一开始发现序列有重复就摆烂了，没往下做下去。但实际上可以

cin >> n >> S;
for (int i = 1; i <= n; i++) cin >> a[i], hua << a[i];
hua.build();
for (int i = 1; i <= n; i++) a[i] = b[i] = (int)hua(a[i]); // 0-indexed
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) if (a[i] != b[i]) g[a[i]].emplace_back(b[i], i);

先离散化 \(a_i\)，然后复制一份到 \(b_i\)，给 \(b_i\) 排序，然后 \(a_i\) 向 \(b_i\) 连边。然后求所有连通分量各自的欧拉回路，也可以达到和排列置换环一样的效果。

然后是原题怎么做，一开始还读错题了导致啥都不会，实际上做法是：丢掉长度为 \(1\) 的置换环后，将所有置换环分成两部分，一部分置换环各自做一次 cycle sort 结束（注意已经是置换环了，只用换一次）；另一部分首先将它们全部拍平到一个操作序列上输出做 cycle sort，这时每个置换环都有一个数字飞出去，另一个数字飞进来。只需要再用一次操作将它们反向弹飞即可，这样操作次数大大减少。显然只有 \(O(\text{置换环个数})\) 种本质不同的操作序列，枚举一下看看谁是答案。

启示：置换环相关的题目，如果发现有重复元素，不妨求欧拉回路。

[1284F] New Year and Social Network

New Year and Social Network - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题首先要观察到答案必定为 \(n-1\) 可太草了，冷静一下发现 Hall 定理直接满足。……

[1292E] Rin and The Unknown Flower

[1548D2] Gregor and the Odd Cows (Hard)