CF1844
Miko35
·
·
个人记录
D - Row Major
考虑不被 n 整除的最小正整数 c，那么 [1, c-1] 中所有正整数两两有连边，答案最小为 c；而 1,2,\ldots,c,1,2,\ldots c,1,2,\ldots 的循环是合法的。
场上莽了个 O(n\cdot d(n))，属于是过了都不知道自己为什么过，成为了脑力下人。
E - Great Grids
首先一个 2\times 2 方格的两条对角线，一定是一组相同另一组不同。
想了很久用一些很几何的东西来刻画这个条件无果，尝试把 a,b,c 替换为 0,1,2，则发现 2\times 2 方格的下一行只可能是上一行在模 3 意义下 \pm 1，由此可知原网格图每一行也只可能是上一行 \pm 1，非常的 nice。
对于列也有同样的结论。也就是说知道了左上角、每行的增量 c_i\in \{0,1\}、每列的增量 l_i\in \{0,1\}，即可确定原网格图。
考虑题目中的限制，其等价于限定一组 c_i 与 d_j 之间的等于/不等的关系，使用带权并查集可以解决。
F - Min Cost Permutation
先考虑 c\ge 0 的情况，显然从小到大排序是最优解，证明可以调整。
对于 c<0 的情况，只考虑权值最小显然是反过来，从大到小排序。
而保证字典序最小，可以逐位贪心地选取小数放到下一位，后面的依然按大小排序最优，虽然我也不知道为什么，但感性理解好像很正确。这样做到 O(n^2)，解决 F1。
不妨我挪前面来的是 a_i，剩下没填的数中其前驱后继为 a_{i-1},a_{i+1}(a_{i-1}\ge a_{i}\ge a_{i+1})，最大的为 a_{m}，填的上一个数为 b。不妨 f(x)=|x-c|，则我们需要 f(a_{i}-a_{i-1})+f(a_{i+1}-a_{i})-f(a_{i+1}-a_{i-1})=f(a_i-b)+f(a_{m}-a_i)-f(a_{m}-b) 成立。
引理：若 x\leq y，f(x)+f(y)\leq f(x-1)+f(y+1)。
几何意义，把 x,y 各挪开一格，其到 c 的距离之和不减。
-
考虑左式，令 a_{i}-a_{i-1}=x,a_{i+1}-a_{i}=y，显然 x,y<0，把一个挪到 0 另一个挪到 x+y 后 f(x+y) 是不减的，也就是左式 f(x)+f(y)-f(x+y)\leq f(0)=|c|。
-
考虑右式，a_m-a_i>0，f(a_m-a_i)=a_m-a_i-c=|a_m-a_i|-c，所以右式 \ge |c|。
所以取等的条件就是左右式都等于 |c|。左式成立就是“a_{i-1}-a_{i+1}\leq |c|”或“a_i 等于 a_{i+1},a_{i-1} 中某一个”，右式成立就是“b-a_i\leq |c|”。拿个 set 随便搞一下。
G - Tree Weights
对于树边 (u,v)，不妨 u<v，考虑 u\rightarrow u+1\rightarrow\ldots\rightarrow v 的路径，其长度之和的奇偶性只与 (u,v) 这条边的奇偶性有关。
由此可以确定每条边的末位，而后去掉末位，重新计算每组 (i,i+1) 并右移一位继续做下去。
H - Multiple of Three Cycles