Dashboard - Codeforces Round #774 (Div. 2) - Codeforces

好耶，AK了。

总算是AK了一场div2

开局好巧不巧，电脑卡了，重启，撞更新了，结果赛后五分钟才进去。

最后剩五分钟惊险AK。

刚开始状态极差，大概在 E 题 AC 的时候状态慢慢上来了。

最后 F 题半小时 AC 也多亏了状态上来。

A

十分显然的结论：答案为 $\frac{s}{n^2}$

但是这难道不是多解吗？

可以发现没有 $n^2$ 拉满也就 $n^2-1$ ，所以 $n^2$ 的值一定是 $n^2$ 贡献的。

Submission #148308492 - Codeforces

B

排序+前缀和判定。

Submission #148315665 - Codeforces

C

暴力判断，当时发现二进制可以直接统计 $1$ 的个数判定，所以考虑 DFS 减阶乘。

一副能过得样子，就直接写了，之后发现其实这个的复杂度是确定的。

设 $top$ 是阶乘的上界，那么时间复杂度就是：$O(T2^{top}\log{n})$ ，经测试 $top=14$ ，搭配小常数和 CF 优秀的机子，跑的飞快，事实上算一下就会发现这个复杂度完全能过，只要常数不是特别爆炸。

Submission #148330270 - Codeforces

D

可以发现除了 $n=2$ 不会出现两个相邻的满足要求的点。

$n=2$ 特判，$n≠2$ 的话，只要两个满足要求的点不相邻就是合法的，不满足要求的点值等于 $1$ 就行了。

然后树形 DP 搞定。

Submission #148366316 - Codeforces

E

怎么说呢，会做了又不完全会做，专门恶心我这种不用纸想题，想题又只想个大概的人的。

交出了三记罚时，被迫赛事写了个暴力，来辅助调试和想出正解。

首先我看到的第一眼，先来个质因数分解：$\prod p_{i}^{a_{i}}$

设 $k$ 为 $a$ 的最大公因数，$mind$ 为 $k$ 的最小质因子，那么这个数字的贡献是 $m-\frac{m}{mind}$ 。（分数向下取整）

因为我想的是对于 $x^{ki}=x^{\frac{k}{mind}imind}$ ，结果 WA4 了，再写了暴力之后，我发现我目光还是狭隘了，事实上不仅 $k$ 能给 $i$ 因子， $i$ 也能给 $k$ 因子，他们甚至能交换因子，比如：$2^{32}=2^{2*3}$

也就是说不止要考虑 $k$ 的因子，还要考虑交换。

当时着实让我有点难受，当然，也不至于太难受，可以发现，当 $k=1$ 的时候贡献一定是 $m$ 的，因为数字没有交换的筹码了，而且因为交换因子只能从 $k$ 中调入调出，所以实际上一个数字的贡献是由 $k$ 决定的，不由这个数字的质因子决定。

设 $dp[i]$ 表示一个数字的 $k=i$ 时其的贡献，那么这个可以直接 $O(m\log{n})$ 遍历 $m$ 求出。（交换因子是什么花里胡哨的说法，还是暴力来的实在）

然后就做完了，$O((n+m)\log{n})$ ，但这道题目我还是有值得反思的地方的，至少从我罚时了三发以及刚开始做法假了的情况来看，我做这道题的经历绝对不能说是优秀的，还需要改进，下次还需要注意，这是应该进步的地方。

Submission #148360488 - Codeforces

赛后看QQ群，发现复杂度可以脱离 $m$ 的束缚？

然后思考了一下，容斥应该就可以了。

具体的说对于幂次 $x$ ，如果对于 $i$ 存在 $j≤m$ 使得 $ij=x$ ，那么说 $i$ 对 $x$ 满足要求。

可以发现，如果 $i,j$ 都对 $x$ 满足，那么 $lcm(i,j)$ 也对 $x$ 满足，这是容斥的正确性保证。

我们的时间复杂度瓶颈在求 $dp$ 数组，考虑优化，容斥求出，经典新手向容斥。

假设我们现在要求出 $dp[x]$ ，设对 $y$ 满足要求且小于等于 $x$ 的数组为 $a$ ，大小为 $len$ 。（默认升序排序、 $x$ 对 $y$ 满足要求）

如果 $len=1$ 则会对 $dp[x]$ 产生贡献，否则不会。

不难发现，直接上个容斥，一个子集只对最大元素贡献即可，正确性显然，如果实在要证明，拿上面的 $a$ 数组手操就会发现不符合要求的会被容斥掉，即可证明。

时间复杂度：$O(n\log{n})$ ，加个线性筛可以优化到 $O(n\log{\log{n}})$ （辗转相除法的复杂度），预处理 $\log$ 以内的 $gcd$ 可以 $O(n)$ 解决。

具体复杂度由实现决定

当然，没有代码，仅限口胡，口胡真快乐。

F

这道题目是真的NB啊。

一开始想直接暴力模拟构造，于是开始找规律，但是发现这种情况难以处理：

1 2 3

1 2 3

2 1 3

于是另辟途径，突然发现如果按下面方式构造出结果只需要 $\frac{n(n-1)}{2}$ 次。

1 1 1

2 2 2

3 3 3

这个 $\frac{n(n-1)}{2}$ 以及这个方式看起来就十分的可做，于是我便认为这应该就是正解的其中一步，事实上当时也就半小时时间了，这是我十几分钟思考中比较有用的成果，也只能用这个了。

但是关键是怎么构造出这个样子呢？

感觉这个题目的操作杂乱无章，找规律暴力构造应该是不太行了，应该需要思考一个量和操作绑定，证明操作数上界是 $\frac{n(n-1)}{2}$ 的。

于是过了不久想到一个值：每种数字按照最优策略分布，每个数字离最终所在位置的距离和。

比如：如果 $1$ 都在 $1$ 号柱子，最终肯定是要每个柱子都有一个 $1$ ，所以是 $\frac{n(n-1)}{2}$ 的。

对于任意一种局面怎么求这个呢？

考虑 $a$ 数组，表示某种数字 $x$ 在某个柱子上的数量，$b$ 是 bool 数组。

求的方法就是每次找到一个 $a[i]>0$ 的位置 $i$ ，向右走到第一个 $b[j]=0$ 的位置，然后 $a[i]—,b[j]=1$ ，同时加上往右走的次数。

这个为什么是对的呢，而且找的 $i$ 顺序不同不会影响结果吗？存在 $i,i+1$ （证明后面给出），使得往右走的过程中不可能从 $i$ 走到 $i+1$ ，断开，转成序列问题，这个时候结果就显然了。为什么要保证 $j$ 是往右走到的第一个呢？不仅是为了保证最优策略（可以证明不劣于不这样做），也是为了能支持断开的这个性质。（不劣于说明可能存在多个形式不同的最优策略）

而且不难看出这个数值的上界是 $\frac{n^2(n-1)}{2}$ 。

那么如何一次操作削掉 $n$ 个数值呢？

随便找到一对 $i,j$ ，满足第 $i$ 个柱子有至少两个 $j$ ，不断往右运 $j$ ，直到没有 $j$ 的柱子，因为没有 $j$ ，所以存在另外一个数字是有两个的，继续运，知道没有或者等于 $i$ 。

可以发现，这样可以稳定使数值减 $n$ ，所以总操作次数：$n(n-1)$ ，可以通过。

时间复杂度：$O(n^4)$，直接每个柱子维护大于 $1$ 个数的数字可以做到 $O(n^3)$ ，但没有必要。

Submission #148380191 - Codeforces

当然，赛时肯定是没想这么多的，感觉对就直接用了QMQ。

证明：

将所有位置的 $a$ 减减，随便选择一个位置断开成序列，然后跑前缀和，问题可以转化成证明存在一个位置断开使得所有前缀和非负，断开后跑前缀和，找到第一个负数位置前缀和，从后面一个位置断开，可以证明该过程一定会停下来。

再证明一下为什么该策略一定是最优策略：

首先过程一个抽象成另外一个过程：

  1. 选择一个 $a[i]>0$ 的位置 $i$ ，再随便选择一个空的坑位，可以发现任何策略都可以通过这种方式选出。
  2. 证明每一次选择选择右边第一个空的坑位不劣于其余选择，因此最优策略一定会出在经过调整过的选择策略中。
  3. 利用上面的证明证明这种决策的所有情况最终结果相同，所以是经过调整后的选择策略选出来的一定是最优策略。

当然，这个证明赛后补的，本来不打算补的，但是觉得这个问题十分的经典，就补了。

证明的时候有一种错觉，不需要证明最优策略，只需要证明操作上界即可，但是后面想想，发现不太对，其实确实可以不证明最优策略，但是一定要证明这种选择最终跑出来的操作一定要是一样的，不然选择不同的 $i$ 操作数不同就搞笑了。

顺便最后说个性质，从过程中看，操作数一定是 $n$ 的倍数。

总结一下，就是发现了局面 $B$ 可以以 $\frac{n(n-1)}{2}$ 的代价变成所求局面 $A$ ，然后通过和操作数绑定证明了某种策略可以以 $\frac{n(n-1)}{2}$ 的代价变成局面 $B$ ，最终以 $n*(n-1)$ 的代价通过此题。

不错的构造题，十分的妙。

不过最高兴的事情还是：我上 2300+ 了，好耶。