526互联

The 2023 ICPC Asia Shenyang Regional Contest

发布时间 2023-12-29 16:28:02作者: DMoRanSky

https://codeforces.com/gym/104869

C. Swiss Stage

对着图片抄最短路，一开始 BO3 搞成 3 了其实是 2 改半天。

E. Sheep Eat Wolves

看到 100 认为不太能贪心，不用性质就能 dp bfs 做，状态是 \(100*100*2\) 的（这边剩几只狼几只羊，人在哪边），转移枚举狼羊数量的时候保证船两边的都满足狼 - 羊 > Q 就行，不超过 2e8

J. Graft and Transplant

一开始被坑了以为是怎么暴力，写完发现链就是阶乘级别的。

首先如果 \(u, v\) 有叶子就操作不了，否则必然可以操作，而且 \(swap(u, v)\) 树的结构是一样的。等价就是把两个点合并起来，然后插了一个叶子。

这样考虑原来两边度数都 \(>1\) 的边，考虑每次操作一次少一条这样的边，且操作时候别的店度数不会改变，所以就看这样边奇偶性。

K. Maximum Rating

答案是连续的，考虑从最小变到最大，每次 swap 相邻两个，答案变化不超过 1。

最大的就是正数数量，最小的就是先把负的放前面（把负数提前严格优）就看能憋住几个正数，就是把数从小到大排，前面有多少个数的和 \(\le\) 负数和的绝对值。动态开点线段树单 log，注意叶子可以多个 cnt。

D. Dark LaTeX vs. Light LaTeX

注意 \(O(n^2)\) 题哈希通常可以被完全规避。

比如这题先把俩恰好都是一半的判了（也可以 \(n^2\) LCP 不哈希）

考虑至少有一个串浸没过一半，不妨是 \(s\)，否则可以 reverse 再做一遍。枚举平方串前一半在 s 上的区间，这样右边可以拼接的位置（比如设为 s 这边部分的长度是 \(1 \sim 长度 - 1\)）可以算 s 的 LCP，得到有个上界，然后那边可以算从 s 这个区间右侧开始有多少个 t 跟他匹配再这个位置区间里，前缀和处理下啥的，注意细节。

B. Turning Permutation

一开始全错了，看成没有排列逆，就是板子对着 dp （状态 \(n^3\) 记录个数，最后一个的相对位置，倒数俩的相对顺序）dfs 输出，后来想通过加一维记录最小值位置的修一下，发现是并行的根本修不了。

不如直接枚举前缀，钦定前缀是啥（\(n^2\)），这样相当于逆是固定了值小的，然后值大的位置还不知道，就类似之前的 dp 按位置 dp，遇到固定的就当做最小的拼接就行了。\(O(n^5)\)

M. Outro: True Love Waits

讨论的太麻烦一开始还想成有向边直接假了。

首先感觉是对称的，比如问题等价于 0 到 t ^ s。所以很多都是递归问题。

打表或者手动观察，其实其按照两位一个循环节，遵循 \(00\rightarrow01\rightarrow11\rightarrow 10\rightarrow 00\) 这个子结构。最低维度是这样，高维是递归的。

每个数事实上会出现 最低位连续 0 的个数 / 2 （下取整个）0。

如果是 \(2i\) 位的子结构（从 00 回到 00，一开始先rev 2i - 1 的 1）事实上是 \(2^{2i}\) 条路的

  1. 考虑先第一次走到终点，之后走的位置就是 \(\sum_i^{k-1} 4^i\)
  2. 考虑如何第一次到，按两维从高到低考虑，这样高的不会影响低的，不用管高的影响，问题还是 00 开始，什么时候第一次到 01 / 11 / 10？打表其实可以发现步数是 1,2,3 倍关系，不难理解其实是对称的都是先走过一遍低位的所有循环节再+1（例如 01 就是 \(\sum_{i为低维度的偶数} 2^i + 1\)）

I. Three Rectangles

H. Line Graph Sequence