2021-team1-C02

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2021-team1 返回]
== 概述 ==
solved: 7/10  dirt: 30%
rank: 8
[[Image(2021-C02.png,700px)]]
== 流水账 ==
开场发现别人签 H，Qza 便去看 H，然而不会。后来 Qza 去看 A 并猜了个假结论并 WA 了。后来 Qza 得到了正确地模型并又找到了假做法，又用 Dinic WA 了一发。而 Csr 感觉自己会做 H 了，把 Qza 撵下机后签掉了 H。Xqj 和 Csr 想出了 I 的充要条件并且过掉了 I。之后 Qza 又胡了个 A 的贪心想上去写，然而 Xqj 想到了一个看起来更对的做法，于是 Xqj 上机写而 Qza 去证明这个做法的正确性。Qza 第二天才证出来，不过考场上这个做法已经 proved by pp 了。之后 Csr 又想出了 D 的做法，遂上机开始写。与此同时 Qza 和 Xqj 讨论 J 并大概想清楚了状压 dp 做法，然后又口胡过了 C。Csr 被样例卡了之后换 Xqj 上去写 J，Qza 便和 Csr 一起查 D，捋了一遍思路后 Csr 知道自己错哪里了，就立刻上机。过了样例后一遍 AC。
之后 Xqj 继续写 J，Csr 和 Qza 一起想 G。Qza 想了个点双的假做法并告诉了 Csr。两人都知道不可能用 O(n) 的做法做 n=36 的题，但是并没有想到错误到底在哪里，于是两人都陷入了江局。Xqj 写到一半发现自己的 dp 需要四个枚举，是 O(13^4^*2^n^) 并不能过，Qza 发现好像可以预处理一些东西使得转移时少一层枚举。于是 Xqj 继续写 J，Qza 继续想 G，并去看了 F 的题意。
Xqj 过掉 J 后，Qza 和 Csr 决定让 Xqj 想 G。于是 Csr 先上机写 C，Qza 去想 F。后来 Xqj 感觉 G 直接暴力好像很对得起这个数据规模，所以开始想细节。而 Qza 在摸鱼。
Csr 的 WA 了 C 之后，发现题意里有说两只骑士不能共处一格，而这点 Xqj 和 Qza 都没有告诉 Csr。发现问题所在，Csr 迅速切掉了 C。
这时距离比赛结束已经没多少时间了，Csr 又推了一会儿 F 后，给出了 F 做法的基本框架。Qza 发现这个框架中有一部分是一个很简单的线段树，于是两个人开始想另一部分怎么完成。Qza 发现好像可以对大于根号 n 的质因子维护一堆 set 来查询，小于等于根号 n 的质因子可以在一棵很大的线段树上面二分。然后 Csr 发现小于根号 n 的质因子也可以直接 set，并不需要另外一棵线段树。于是大家会了 F，但时间不够了，就去读其他题的题意了，而没有做 F。
== 总结 ==
Qza：一整场都在摸鱼，除了给队伍贡献罚时之外并没有做出其他什么事。
Csr：今天我开始有一点点能口胡了！然而没有代码手TAT 其实我觉得我这场最大问题是C很短很好写，但没有早点把队友赶下来写C… 其实最后自己写出来的都是非常水的题5555 感觉不管单人还是组队自己都永远只会写水题
Xqj：
== 题解 ==
A: 由于每次变色会使一个同色连通块内所有点都变色，所以先考虑将图上的同色连通块缩成一个点。每次染色会导致一个点和周围所有邻接点变成同一个点，现在求最少多少次操作可以让这张图变成一个点。先考虑两个点，如果它们之间的最短路为 d，则其中一点至少经过 d 次变色才能使自己与另一个点相连；再考虑一个猜测：在最优方案中，变色只会发生在一个点上。这个对于树很好证明：由于一次染色至多让树上距离最远的两个点距离缩短 2，所以答案不低于直径的一半，而选取树的直径的中心恰能够保证在直径被缩为一个点前其他点都已经缩过了，所以这一定是个不劣的策略。容易知道，这个结论对于一个图也是成立的。对于任意一个点，可以将原图按照最短路建出一颗生成树，而这个点应该尽可能靠近直径的中心。所以做法很简单，就是同色点之间边权为 0，异色点之间边权为 1，用 Floyd 求出任意两点间的最短路，找到一个点，使得它到其它点的最远距离最短即可。
B: 当起点和终点连线不与圆相交或相交但弦长小于 t，则走直线即可。否则，如果 t=0，则过起点和终点分别做圆的切线，一定按照切线-弧-切线的方式走；否则若 t≠0，一定走折线。折线的长度遂长度为 t 的弦的个数增加而先减后增，所以可以三分。
C：容易想到，每一步走的方案基本是唯一的，当且仅当两只骑士能够跳到同一个位置时下一步的方案不是唯一的。由于没有哪个地方可以一步跳到两个 Shift，所以深搜的状态并不多，可以用深搜判断。也可以广搜，不断把满足条件的后继加入队列即可。
D：首先，对于任意两辆车 A、B，当某一时刻 B 超过了 A，则 A 永远不会再次超过 B。而这件事情发生当且仅当 A 初始时在 B 前面，且 B 的速度大于 A（速度为负也无妨）。于是对于所有车中最前面那辆车的速度随时间增加是单调不降的，最后一辆车的速度随时间是单调不增的。所以可以对于最前面的车和最后面的车都维护一个单调队列，初始位置相邻两辆车至多有一个时间点使得它们俩的位置互换，这个时间点可以计算。而距离是时间的一次函数，所以第一辆车与最后一辆车距离最近的时刻必然是某两辆车处于同一位置的时刻，两个单调队列至多产生 2n 个时间点，每个时间点内第一辆车和最后一辆车是哪一辆是确定的，所以可以把这 2n 个时间点拿出来直接计算、比较来得到答案。
E：
F：对于每个质因子分别考虑。对于任意一个质因子，维护一个 set，记录这个质因子出现的位置下标，则由该质因子产生的不合法区间为包含任意相邻两个质因子的区间的并。而每两个相邻的质因子所产生的几个不合法区间一定是一段左端点连续的区间，所以可以用区间加 1、区间查询 0 的个数来求合法区间的数目，由于永远不会出现负数，所以只需要用一棵线段树维护区间加、区间查询最小值、区间最小值计数即可。而原序列单点修改，就是删除一些质因子再加入一些质因子，所以可以先消除原质因子的影响，再加入新质因子的影响。可以对于每个质数维护一个 set，就可以很快地知道需要消除/加入影响的区间。
G：考虑最短路的数量，由于没有重边，所以最短路最多的情况大概是 k^n/k^ 这个级别。计算一下发现，最短路数量在 k=3 时取到最大值 531441，也就是说最短路数量不是很多。于是枚举最短路，然后从终点倒着往起点跑，选取最短路上的一个点相当于付出点权的代价，所以再跑一个单源最短路即可。单次时间复杂度 O(nlogn*k^n/k^)，44 组数据，看起来不稳，但是能过。
H：暴力维护从 1 到 i 所有区间的 gcd，这样的 gcd 值至多只有 O(log值域) 个。所以 i 从 1 到 n 扫一遍，暴力维护前面所有区间的 gcd（因为很少），把这些结果统计起来即可。
I：本题不能按照如何获得一种分解的方式来考虑，而应该考虑每种分解方式的等价条件是什么。先不考虑首项不为 1 的情况，记首项为 a，且有 m 项，和为 x（即要被分解的数），则 (2a+m-1)m=2x，考虑到 a>=1，所以 2a-1 是奇数，于是 (2a+m-1) 与 m 奇偶性不同，并且 (2a+m-1) 大于 m。而只要知道 (2a+m-1) 或者 m，则立刻能够确定分解情况。奇偶性不同这件事可以说明，2x 的所有 2 因子都在 (2a+m-1) 或 m 之内，所以先将 2x 的所有 2 因子丢掉，记剩下的数为 y，且 2x=2^n^y，则对于 y 的每一个因子 b，2^n^b 和 y/b 必然有一个大小关系，根据这个大小关系可以唯一解出一对 m 和 a，则唯一（因为 b 不同，y/b 就不同，所以一定不会重复）对应一种 x 的分解方式，于是 y 的因子数即为 x 分解的方案数。
J：记 f[i][j] 表示已经按过的按钮状态为 i（0 到 2^n^-1），最后一次按完按钮后结束于第 j （0 到 n-1）个金币的最短距离，则转移时枚举最后按的按钮是哪个、下一个按钮选哪个，由于选定了本次按钮是哪个、下一个按钮是哪个时，转移的最短路是可以预处理的，所以这个 dp 转移的复杂度为 O(n^2^*2^n^)；需要预处理对于每个按钮，收集其内所有金币并停到某个金币的最短距离。所以设 g[i][j] 表示第 i 个按钮，金币状态为 j 的最短距离，需要先n枚举按钮，再2^n枚举这个按钮的金币状态，然后n^2枚举上一个金币和下一个金币，这部分的复杂度为 O(n^3^*2^n^)；对于两个按钮之间的最短路，枚举两个按钮，枚举上一个按钮停在哪里，这部分的复杂度为 O(n^3^)。所以总复杂度为 O(n^3^*2^n^)。

[/wiki/2021-team1 返回]

概述

solved: 7/10 dirt: 30%

rank: 8

流水账

开场发现别人签 H，Qza 便去看 H，然而不会。后来 Qza 去看 A 并猜了个假结论并 WA 了。后来 Qza 得到了正确地模型并又找到了假做法，又用 Dinic WA 了一发。而 Csr 感觉自己会做 H 了，把 Qza 撵下机后签掉了 H。Xqj 和 Csr 想出了 I 的充要条件并且过掉了 I。之后 Qza 又胡了个 A 的贪心想上去写，然而 Xqj 想到了一个看起来更对的做法，于是 Xqj 上机写而 Qza 去证明这个做法的正确性。Qza 第二天才证出来，不过考场上这个做法已经 proved by pp 了。之后 Csr 又想出了 D 的做法，遂上机开始写。与此同时 Qza 和 Xqj 讨论 J 并大概想清楚了状压 dp 做法，然后又口胡过了 C。Csr 被样例卡了之后换 Xqj 上去写 J，Qza 便和 Csr 一起查 D，捋了一遍思路后 Csr 知道自己错哪里了，就立刻上机。过了样例后一遍 AC。

之后 Xqj 继续写 J，Csr 和 Qza 一起想 G。Qza 想了个点双的假做法并告诉了 Csr。两人都知道不可能用 O(n) 的做法做 n=36 的题，但是并没有想到错误到底在哪里，于是两人都陷入了江局。Xqj 写到一半发现自己的 dp 需要四个枚举，是 O(134*2n) 并不能过，Qza 发现好像可以预处理一些东西使得转移时少一层枚举。于是 Xqj 继续写 J，Qza 继续想 G，并去看了 F 的题意。

Xqj 过掉 J 后，Qza 和 Csr 决定让 Xqj 想 G。于是 Csr 先上机写 C，Qza 去想 F。后来 Xqj 感觉 G 直接暴力好像很对得起这个数据规模，所以开始想细节。而 Qza 在摸鱼。

Csr 的 WA 了 C 之后，发现题意里有说两只骑士不能共处一格，而这点 Xqj 和 Qza 都没有告诉 Csr。发现问题所在，Csr 迅速切掉了 C。

这时距离比赛结束已经没多少时间了，Csr 又推了一会儿 F 后，给出了 F 做法的基本框架。Qza 发现这个框架中有一部分是一个很简单的线段树，于是两个人开始想另一部分怎么完成。Qza 发现好像可以对大于根号 n 的质因子维护一堆 set 来查询，小于等于根号 n 的质因子可以在一棵很大的线段树上面二分。然后 Csr 发现小于根号 n 的质因子也可以直接 set，并不需要另外一棵线段树。于是大家会了 F，但时间不够了，就去读其他题的题意了，而没有做 F。

总结

Qza：一整场都在摸鱼，除了给队伍贡献罚时之外并没有做出其他什么事。

Csr：今天我开始有一点点能口胡了！然而没有代码手TAT 其实我觉得我这场最大问题是C很短很好写，但没有早点把队友赶下来写C… 其实最后自己写出来的都是非常水的题5555 感觉不管单人还是组队自己都永远只会写水题

Xqj：

题解

A: 由于每次变色会使一个同色连通块内所有点都变色，所以先考虑将图上的同色连通块缩成一个点。每次染色会导致一个点和周围所有邻接点变成同一个点，现在求最少多少次操作可以让这张图变成一个点。先考虑两个点，如果它们之间的最短路为 d，则其中一点至少经过 d 次变色才能使自己与另一个点相连；再考虑一个猜测：在最优方案中，变色只会发生在一个点上。这个对于树很好证明：由于一次染色至多让树上距离最远的两个点距离缩短 2，所以答案不低于直径的一半，而选取树的直径的中心恰能够保证在直径被缩为一个点前其他点都已经缩过了，所以这一定是个不劣的策略。容易知道，这个结论对于一个图也是成立的。对于任意一个点，可以将原图按照最短路建出一颗生成树，而这个点应该尽可能靠近直径的中心。所以做法很简单，就是同色点之间边权为 0，异色点之间边权为 1，用 Floyd 求出任意两点间的最短路，找到一个点，使得它到其它点的最远距离最短即可。

B: 当起点和终点连线不与圆相交或相交但弦长小于 t，则走直线即可。否则，如果 t=0，则过起点和终点分别做圆的切线，一定按照切线-弧-切线的方式走；否则若 t≠0，一定走折线。折线的长度遂长度为 t 的弦的个数增加而先减后增，所以可以三分。

C：容易想到，每一步走的方案基本是唯一的，当且仅当两只骑士能够跳到同一个位置时下一步的方案不是唯一的。由于没有哪个地方可以一步跳到两个 Shift，所以深搜的状态并不多，可以用深搜判断。也可以广搜，不断把满足条件的后继加入队列即可。

D：首先，对于任意两辆车 A、B，当某一时刻 B 超过了 A，则 A 永远不会再次超过 B。而这件事情发生当且仅当 A 初始时在 B 前面，且 B 的速度大于 A（速度为负也无妨）。于是对于所有车中最前面那辆车的速度随时间增加是单调不降的，最后一辆车的速度随时间是单调不增的。所以可以对于最前面的车和最后面的车都维护一个单调队列，初始位置相邻两辆车至多有一个时间点使得它们俩的位置互换，这个时间点可以计算。而距离是时间的一次函数，所以第一辆车与最后一辆车距离最近的时刻必然是某两辆车处于同一位置的时刻，两个单调队列至多产生 2n 个时间点，每个时间点内第一辆车和最后一辆车是哪一辆是确定的，所以可以把这 2n 个时间点拿出来直接计算、比较来得到答案。

E：

F：对于每个质因子分别考虑。对于任意一个质因子，维护一个 set，记录这个质因子出现的位置下标，则由该质因子产生的不合法区间为包含任意相邻两个质因子的区间的并。而每两个相邻的质因子所产生的几个不合法区间一定是一段左端点连续的区间，所以可以用区间加 1、区间查询 0 的个数来求合法区间的数目，由于永远不会出现负数，所以只需要用一棵线段树维护区间加、区间查询最小值、区间最小值计数即可。而原序列单点修改，就是删除一些质因子再加入一些质因子，所以可以先消除原质因子的影响，再加入新质因子的影响。可以对于每个质数维护一个 set，就可以很快地知道需要消除/加入影响的区间。

G：考虑最短路的数量，由于没有重边，所以最短路最多的情况大概是 kn/k 这个级别。计算一下发现，最短路数量在 k=3 时取到最大值 531441，也就是说最短路数量不是很多。于是枚举最短路，然后从终点倒着往起点跑，选取最短路上的一个点相当于付出点权的代价，所以再跑一个单源最短路即可。单次时间复杂度 O(nlogn*kn/k)，44 组数据，看起来不稳，但是能过。

H：暴力维护从 1 到 i 所有区间的 gcd，这样的 gcd 值至多只有 O(log值域) 个。所以 i 从 1 到 n 扫一遍，暴力维护前面所有区间的 gcd（因为很少），把这些结果统计起来即可。

I：本题不能按照如何获得一种分解的方式来考虑，而应该考虑每种分解方式的等价条件是什么。先不考虑首项不为 1 的情况，记首项为 a，且有 m 项，和为 x（即要被分解的数），则 (2a+m-1)m=2x，考虑到 a>=1，所以 2a-1 是奇数，于是 (2a+m-1) 与 m 奇偶性不同，并且 (2a+m-1) 大于 m。而只要知道 (2a+m-1) 或者 m，则立刻能够确定分解情况。奇偶性不同这件事可以说明，2x 的所有 2 因子都在 (2a+m-1) 或 m 之内，所以先将 2x 的所有 2 因子丢掉，记剩下的数为 y，且 2x=2ny，则对于 y 的每一个因子 b，2nb 和 y/b 必然有一个大小关系，根据这个大小关系可以唯一解出一对 m 和 a，则唯一（因为 b 不同，y/b 就不同，所以一定不会重复）对应一种 x 的分解方式，于是 y 的因子数即为 x 分解的方案数。

J：记 f[i][j] 表示已经按过的按钮状态为 i（0 到 2n-1），最后一次按完按钮后结束于第 j （0 到 n-1）个金币的最短距离，则转移时枚举最后按的按钮是哪个、下一个按钮选哪个，由于选定了本次按钮是哪个、下一个按钮是哪个时，转移的最短路是可以预处理的，所以这个 dp 转移的复杂度为 O(n2*2n)；需要预处理对于每个按钮，收集其内所有金币并停到某个金币的最短距离。所以设 g[i][j] 表示第 i 个按钮，金币状态为 j 的最短距离，需要先n枚举按钮，再2n枚举这个按钮的金币状态，然后n2枚举上一个金币和下一个金币，这部分的复杂度为 O(n3*2n)；对于两个按钮之间的最短路，枚举两个按钮，枚举上一个按钮停在哪里，这部分的复杂度为 O(n3)。所以总复杂度为 O(n3*2n)。

附加文件