Solution Set - “让季节停止哽咽”

• 0.「CTT 2017」「洛谷 P4004」Hello world!
• 1.「CTT 2017」「洛谷 P4006」小 Y 和二叉树
• 2.「CTT 2017」「洛谷 P4226」避难所
• 3.「AGC 023F」01 on Tree
• 4.「AGC 024C」Sequence Growing Easy
• 5.「UR #1」「UOJ #21」缩进优化
• 6.「JOISC 2022」「LOJ #3694」一流团子师傅
• 7.「JOISC 2022」「LOJ #3695」鱼 2
• 8.「JOISC 2022」「LOJ #3696」复兴计划
• 9.「UR #1」「UOJ #22」外星人
• 10.「CF 1286D」LCC
• 11.「CF 618G」Combining Slimes ⭐
• 12.「QOJ #4219」Insects ⭐
• 13.「CF 1188E」Problem from Red Panda
• 14.「CF 1023G」Pisces ⭐
• 15.「UR #1」「UOJ #23」跳蚤国王下江南 ⭐

0.「CTT 2017」「洛谷 P4004」Hello world!

• Link & Submission.
• 「B.复杂度平衡」

  写答辩 \(\to\) 听 Para 赞美最短解 \(\to\) 冲到题解区看最短解 \(\to\) 叉掉最短解并赞美作者 \(\to\) 写答辩.

  这步长根号分治和修改次数均摊的味儿太明显了. 在步长大于 \(\sqrt n\) 时, 一切操作都能暴力. 在步长小于 \(\sqrt n\) 时, 我们需要快速找到路径上非 \(1\) 的 \(a\) 值, 顺便维护同余步长的 \(a\) 和. 我们对步长 \(k<\sqrt n\) 单独建一棵树, 每个点的新爹是原来的 \(k\) 级爹, 然后找非 \(1\) 可以直接 DSU, 维护和就在 DFN 序列上分块维护差分以平衡复杂度. 最后可以做到 \(\mathcal O(n\sqrt n\log\log n+q\sqrt n)\), 可能还要加个 DSU 的复杂度. (

1.「CTT 2017」「洛谷 P4006」小 Y 和二叉树

• Link & Submission.
• 「B.贪心」

  答案序列的第一个点显然是度数 \(<3\) 的编号最小的点, 记为 \(r\). 接下来考虑第二个点, 它可能是 \(r\) 右子树内的点或者 \(r\) 的父亲. 对于前者, 这是一个子问题, 直接用 (以 \(r\) 为根) 子树内度数 \(<3\) 的编号最小的点作为结果. 如果 \(r\) 一定要有右子树和父亲, 就用较小者当右子树.

  如果没有呢? 设 \(r\) 的邻接点为 \(x\), 我们需要决策 \(x\) 当爹还是当儿. 如果 \(x\) 子树内的满足条件的最小点仍 \(>x\), 显然当爹更优秀. 否则, 即使这一最小值 \(=x\), 此时 \(x\) 度数 \(\le2\), 让它当儿的决策空间包含当爹的决策空间, 其他情况直接形成优劣关系, 所以都应该让 \(x\) 当儿.

  最后, 预处理以 \(r\) 为根的子树最优点, 然后贪心搜一边就能求出结果. \(\mathcal O(n)\).

2.「CTT 2017」「洛谷 P4226」避难所

• Link & Submission.
• 「A.构造」

  其实答案已经写在样例里啦. 研究 \(6\times6\times6=3\times3\times3\times8\) 的一般情况: 设素数 \(x\) 是满足 \(x^3\le b\) 的最大素数, \(y\) 是满足 \(y^2>b\) 的最小素数, 那么 \(\overline{(xy)(xy)(xy)}\) 就会被贪心算法误判为 \(\overline{yyy(x^3)}\). 当然, 这里需要满足 \(x^2y>b\), 一个很 OI 的解决办法是小范围暴力或者打表 (枚举所有三位数判断), 因为这个问题只会在 \(b\) 足够小时发生. 暴力复杂度毛估 \(\mathcal O(b^4\log b)\) (所以建议打表), 大范围直接暴力扫素数可以做到 \(\mathcal O(b^{1/4}\log b)\), 挺快的 w.

3.「AGC 023F」01 on Tree

• Link & Submission.

  那个… 这个 trick 是不是有什么名字呢? 树形拓扑限制, 贪心向爹合并就行. 一个序列整体可以记作 \((\text{one},\text{zero},\text{inv})\), 对它 exchange argument 即有贪心策略. \(\mathcal O(n\log n)\).

4.「AGC 024C」Sequence Growing Easy

• Link & Submission.

  放过一道水题, 就会不想写更多不那么水的题的题解, 所以!

  填出值 \(k\) 的方案是唯一的: 放一个 \([0,1,2,\dots,k]\) 在它前面. 所以只有 \(a\) 值刚好和这个吻合的部分可以节约操作次数. 此外, 若 \(a_i>a_{i-1}+1\) 或者这样的序列会覆盖 \(0\) 位置, 就一定无解. \(\mathcal O(n)\).

5.「UR #1」「UOJ #21」缩进优化

• Link & Submission.

  兔在以前的博客里鸣过警钟: \(a=kx+r\), \(x,k\) 可以同时枚举. \(\mathcal O(n+V\log V)\).

  为什么会做到 UR 的题?

6.「JOISC 2022」「LOJ #3694」一流团子师傅

• Link & Submission.
• 「A.构造」「B.二分-二分答案」

  "二分答案" 的 tag 比较乱入, 实在是找不到合适的 tag 啦. 但这的确是一道很好的 learn to use binary search 的题.

  前三个子任务很好想: 我们不断尝试取出出现位置尽量靠前的一串