做题记录 (2024/8)
一些难题/好题/做完比较有感触的题会写进来。每月一篇，不定时更新。
难度评分：思维/代码，满分 \(10\)。
不保证作为题解是合格的。
题面可以从 submission 点进去看。
注：NOIPSC = NOIP simulation contest
CF1991F. Trangle Formation
Difficulty: \(3.5/2\)
考虑怎样的序列一个三角形也不能构成。
考虑两根长为 \(1\) 的木棍，则下一根长度 \(\ge2\)，再下一根 \(\ge3\)，在下一根 \(\ge5\)……于是第 \(i\) 根的长度最小值是斐波那契数列的第 \(i\) 项。这玩意是指数增长的，不到 \(50\) 项就会爆出 \(10^9\)。
这时再随便来几根就可以组成两个三角形了（理论最小值是 \(t=48\) 根）。所以 \(r-l+1\ge t\) 的时候直接 ok 了。
考虑 \(r-l+1<t\) 怎么做。结论是排序后这两个三角形要么是两组分开的连续三个，要么是连续六个。暴力即可。时间复杂度 \(\Theta(q(t\log t+\binom 63t))\)。
CF1991I. Grid Game
Difficulty: \(8/6.5\)
神仙交互题，咕。
P2482. [SDOI2010] Pig Kingdom War
Difficulty: \(1.5/9\)
题目本身没啥好说的。大模拟。调了 \(\texttt{3h}\)，写了 \(\texttt{5KB}\)。以下是我的一些唐氏 bug。
- 一个人出决斗结果自己似了，然后他继续出牌？
- check 任何东西的时候请跳过似人。
- 决斗可以和任何人决。
- 反贼不会决忠臣（只会决主公）。
- 不能只通过身份确定是否要无懈（例如，主公会无懈类反贼）。
- 决斗只在开始时可以被无懈，但南蛮/万箭是在判每个人之前 check 无懈，并且只对他自己有效。
AGC066B. Decreasing Digit Sums
Difficulty: \(5.5/3\)
讲个笑话：本人在该场中 \(\texttt{3h}\) 切了 \(0\) 题，但是开了 unrated
一般来说数字越来越大数位和也会有越来越大的趋势。所以需要一些观察。
考虑 \(5^{50}\) 的倍数。注意到 \(f(5^{50}\cdot2^i)=f(10^i\cdot5^{50-i})=f(5^{50-i})\)，相当于数字会变得越来越小。这是我们想要的。
但是只取一个数还是不行的。根据大数定律，数字越大，下降的趋势就会越明显。考虑随一堆 \(5^{50}\cdot i\) 拼起来，中间用 \(0\) 隔开以免进位产生影响。这样大概就能很快随出来。实测取 \(100\) 个可以秒出解。把数直接交上去就行了。
NOIPSC14B. Add Number / ARC153D. Sum of Sum of Digits
Difficulty: \(4.5/4.5\)
进位不太好处理，考虑数位 dp。直接枚举每个数是否进位显然不行，注意到后 \(i\) 位产生进位只能是后 \(i\) 位最大的若干个数。于是设 \(dp_{i,j}\) 表示后 \(i\) 位中，最大的 \(j\) 个数产生进位的最小代价。转移枚举下一位数字填啥就行了。
如果直接转移需要 \(\Theta(n)\) 计算状态和值。双指针优化即可做到（均摊）\(\Theta(1)\) 转移。
总复杂度 \(\Theta(n\log_\Sigma V(\log n+\Sigma))\)。\(\log n\) 可以基数排序省掉但是没必要。
NOIPSC13B. Jiangqiao Escaping on Tree / P3006. [USACO11JAN] Bottleneck G
Difficulty: \(6/4\)
没理解透。还要回来看。
首先发现人够的话到父亲的边永远是灌满的。人不够了就永远灌不满了。
所以可以分成两个阶段，而分界点就是 \(\dfrac{\text{初始人数}}{\text{净输出量}}\)。
一旦灌不满了，它连向父亲的边就没用了。可以把它和父亲合并起来。
然后因为某些神仙原因可以直接把它的净输出量和初始人数全部加到他父亲上就行了。再在并查集上合并两点即可。
询问在每次阶段变化中间就可以顺便回答了。变化时间可以 pq 维护。时间复杂度 \(\Theta(n\log n+q\log q)\)。
NOIPSC14C. Coloring Plans
Difficulty: \(5/3\)
这题赛时差不多已经想出来但没时间写了。主要是赛时胡了好几个假做法。。。
限制就是一个点能到的点构成的生成子图所有环长都是偶数。枚举所有限制的话可以用 dfs 树，一条非树边就会加一个限制，一共最多 \(\Theta(nm)\) 个。处理限制可以线性基，用 bitset，每个限制可以做到 \(\Theta(\frac{m^2}w)\)。
总复杂度 \(\Theta(\frac{nm^3}w)\)，但是跑不满一点。跑得嗖嗖快。
NOIPSC14D. Connecting Vertices / AGC065D. Not Intersect
Difficulty: \(9.5/2.5\)
大神仙计数题。没理解透。之后回来看。
AGC065C. Avoid Half Sum
Difficulty: \(6/2\)
首先有一个 MO 结论：
有 \(n\) 个物体，第 \(i\) 个物体的质量 \(a_i\) 满足 \(1\le a_i\le i\)，且 \(\sum_{i=1}^na_i\) 为偶数。则可以将 \(n\) 个物体全部放入天平的左盘或右盘，使得天平平衡。
做法就是从后往前依次放轻的那边就行了。
然后原题可以转化为给每个位置赋一个重量使得天平无法平衡。
然后你对着结论的证法一顿推，你会推出结论是有解当且仅当存在一个数使得比它小的奇数的个数小于它的值减 \(1\)。直接做就行了。\(\Theta(n\log n)\)。
CF1997F. Chips on a Line
Difficulty: \(3/2.5\)
一眼秒了。不想认真讲。
首先我不知怎么一眼就想到了赋权，然后自然而然想到斐波那契。然后发现 \(f_1=f_2=1\) 完美。
然后 dp 两下就做完了。时间是 \(\Theta(n^2xf_x)\)。
AGC066C
Difficulty: \(7/3\)
经过我数小时的打表找规律思考，发现一个串可以删空当且仅当可以划分成若干个满足以下条件的子串：
- \(\texttt A\) 的数量是 \(\texttt B\) 的两倍；
- 两端字符中至少有一个是 \(\texttt B\)。
回到原题，考虑 dp。可以发现只需转移满足上述条件的自传就可以了。随便优化一下就行了。时间复杂度 \(\Theta(n)\)。
P9720. [EC Final 2022] Map
Difficulty: \(5/5.5\)
不会计算几何啊。。。
以下记 \(f\) 操作为从公园跳到地图，\(g\) 为从地图跳到公园。
首先先 \(g\) 再 \(f\) 不如直接走，不但走的距离大而且浪费两次操作。
那么可以发现，最终一定是先 \(f\) 若干次，然后走到某个点，然后 \(g\) 回去若干次。
于是爆枚 \(f,g\) 的次数，算出要走的是从哪到哪，取个 \(\min\) 就行了。时间复杂度 \(\Theta(Tn^2)\)。
标签：submission,记录,可以,texttt,50,2024,Difficulty,做题,Theta From： https://www.cnblogs.com/No-play-Yes-splay/p/18339703/practice-2024-08