【比赛记录】CFR954（Div.3）

· · 个人记录

记录

A-F 切掉，但是细节都很多，调的时间比较长。G 不会。

题解

A. X Axis

枚举 + 循环判断即可，略过不表。

B. Matrix Stabilization

把所有需要操作的格子找出来，按照要求排序，依次处理直到为四周的最大值，显然不会有格子被重复操作，复杂度正确。

C. Update Queries

显然操作序列都可以排序。把操作下标用桶存一下，操作字符升序排序，顺序处理，每到一个可以操作的下标 i 就使用剩余的最小值修改，若需要对其操作多次可以看作用最大的若干个修改过后用最小值覆盖掉，所以这样一定是合法且最优的。

D. Mathematical Problem

枚举每一个位置作为空出来的位置，然后可以得到剩余数的序列 b。考虑如何操作让结果尽量小，发现若有 0 一定是 0，其他的 1 全乘进去，而大于 1 的直接加起来一定最优，因为已经不考虑 1，剩余的两个数 a+b 一定不大于 ab，时间复杂度 O(Tn^2)

E. Beautiful Array

发现两个数 x,y 要变为相等必须保证两数模 k 相等，需要消耗的操作次数为 \left|\frac xk-\frac yk\right|。所以按照对 k 取模的余数分组。

若 n 为偶数则必须每组都有偶数个，在每组里每相邻两个放到对应位置即为代价最小。若 n 为奇数则只能有一组个数为奇数，其他组里同样计算代价，在奇数组里求出前缀和后缀每两个组合的代价和，枚举把哪一个放在正中间，取最小值即可。

F. Non-academic Problem

发现若去掉的边不是割边，去掉后答案仍为 \frac{n(n-1)}2，否则就把整个图分成了两部分，每一部分单独为 \frac{k(k-1)}2。只要 Tarjan 跑出割边然后树上求出子树大小，枚举断掉每个点连向父亲的边即可。

G. Permutation Problem

整个题目的复杂度都依赖于 O(n\ln n) 调和级数枚举倍数。

题意即为找 i,j 的数量使得 \frac{p_ip_j}{ij} 为整数。考虑去掉本身的影响，设 g=\gcd(p_i,i)，记录 a_i=\frac{p_i}{g},b_i=\frac{i}{g}，所以就变成了 b_j \mid a_i 且 b_i\mid a_j 的数量。

过程即为枚举每个 B，处理所有 b_i=B 的 i。再枚举 B 所有的有效倍数 A，记录下所有 a_j=A 的 b_j 出现次数，再回来用所有 b_i=B 的 a_i 查找其因数在前面的 b_j 中出现的次数，就是满足条件的方案数。

实现上必须每次只对有效元素进行操作和清空，不能在值域上进行，否则复杂度不对。同时还要减去自己与自己搭配的方案数，也就是 i \mid p_i 的个数，再除掉每组重复的 2 次即为答案。