Codeforces Round 954 (Div. 3)

发现自己的小号已经 unrated for div3 了

这什么神笔场，F 不会求割边和点双被卡科技了，G1 G2 赛时想出正解但是以为自己的复杂度是错的就没写。。。

比赛链接

Problems	AC
A. X Axis	○
B. Matrix Stabilization	○
C. Update Queries	○
D. Mathematical Problem	○
E. Beautiful Array	○
F. Non-academic Problem	⊕
G1. Permutation Problem (Simple Version)	⊕
G2. Permutation Problem (Hard Version)	⊕

A

Code

B

Code

C

Code

D

Code

E

给定一个整数数组 $a_1, a_2, \ldots, a_n$ 和一个整数 $k$。你需要通过最少的操作次数使这个数组变得美丽。

在应用操作之前，你可以随意打乱数组的元素。每次操作你可以执行以下步骤：

• 选择一个索引 $1 \leq i \leq n$，
• 将 $a_i$ 的值增加 $k$，即 $a_i = a_i + k$。

如果数组 $b_1, b_2, \ldots, b_n$ 满足 $b_i = b_{n - i + 1}$ 对于所有 $1 \leq i \leq n$ 成立，那么数组就是美丽的。

找到使数组美丽所需的最少操作次数，或者报告这是不可能的。

按剩余系分组，然后把是奇数的那一组挑出来，枚举让哪个成为特殊的就行了

Code

F 桥，点双，割边，tarjan

你有一个连通的无向图，其顶点编号为从 $1$ 到 $n$ 的整数。你的任务是最小化图中存在路径的顶点对 $1 \leq u < v \leq n$ 的数量。为此，你可以从图中恰好移除一条边。

找到使得存在路径的顶点对数量最小的情况！

不是哥们.jpg，这是 CF 还是 AT 啊，怎么搞个这种纯知识点板子题，一点思维含量都没有。

（关键是我还没学过点双和边双（（（（（（

赛后学习了下 jls 的板子

Code

G

给定一个长度为 $ n $ 的排列 $ p $。计算满足 $ p_i \cdot p_j $ 可以被 $ i \cdot j $ 整除的索引对 $ 1 \leq i < j \leq n $ 的数量。

$ n \leq 5 \cdot 10^5 $

对于一组 $(a[i], i)$，他们的 $gcd$ 是不重要的。同时先把 $gcd$ 除掉，记 $(a[i] / gcd, i / gcd)$ 为 $(x, y)$

$x$ 是多出来，$y$ 是缺少的。要想合法的话必须找到另外一组 $(u, v)$，使得 $u$ 能补上 $y$ 缺的，$x$ 能补上 $v$ 缺的，即 $u$ 是 $y$ 的倍数，$x$ 是 $v$ 的倍数

具体实现上，用两个 vector pos1, pos2。pos1[y].pb(x)，pos2[x].pb(y)

枚举 $y$，然后枚举 $y$ 的倍数 $u$。对于每个 $u$ 对应的一大堆 $v$，把这些 $v$ 对应的计数器加上 cnt[v]++。然后把 $y$ 所对应的 $x$ 的因子都找出来。因为这些因子是 $x$ 可能补上的 $v$。

记得要减去自己和自己配对的情况（y == 1），以及顺序颠倒算重的部分

Code