2025/8/7胡题记录

23天前发布

最近忙着背科目一和学范畴论，根本没时间加训

CodeForces – 1439C. Greedy Shopping

刚看到题就想了很久但是不会做，然后发现自己没有注意到序列 \(\set{a_i}\) 是单调不增的。首先先考虑问题的弱化形式——没有修改的情况，实际上印象里以前并没有见过比较典型的能处理这类问题的模型，于是尝试分析购物情况，能够发现购买的商品一定是一段一段的，显然这是废话，但是不难发现一个情况：假如一段连续的购买是 \(a_l\) 到 \(a_r\) 这就意味着这个人是买不起 \(a_{r+1}\) 的，即 \(money<a_{r+1}\)，那么尝试分析下一次购买 \(a_x\) 是怎么样的，如果 \(a_x>{a_{r+1}\over2}\)，那么钱就会直接减少一半，再下一次的购买 \(a_y\) 一定是 \(a_y\le a_{r+1}-a_x<{a_{r+1}\over2}\)，而如果 \(a_x<{a_{r+1}\over2}\) 那么就直接说明下一次购买变成了原来的一半，这意味着购买的商品的段数一定是 \(\mathcal O(\log V)\) 级别的，于是就直接在线段树上二分即可，感觉困难的地方应该在于发现这一个性质，有一点点欧几里得辗转相除法的味道。

CodeForces – 1706E. Qpwoeirut and Vertices

求最小的边使得图联通，一闻就是最小生成树的味道，实际上就是在最小生成树模拟，一旦最小生成树的过程中某个要求被满足了就回答当前处理的边即可，实现方法应该有很多种，比如重构树或者整体二分。

CodeForces – 1712E2. LCM Sum (hard version)

这个题目乱七八糟的，感觉就是纯乱搞+大力分类讨论。首先容易分析出 \(k|lcm(i,j,k)\)，并且如果 \(k<lcm(i,j,k)\) 则 \(2k\le lcm(i,j,k)\)，所以实际上能够做到 \(lcm(i,j,k)<i+j+k\) 的情形是很少的，只能允许 \(lcm(i,j,k)=k\) 或者 \(lcm(i,j,k)=2k\) 且 \(i+j>k\)。

对于第一种情况，设 \(\sigma(a,b):=\sum_x [x\ge b]\wedge[x|a]\) ，则第一类就是想办法维护 \(\sum_{l\le x\le r}\sigma(x,l)^2\) 和 \(\sum_{l\le x\le r}\sigma(x,l)\)。考虑像莫队一样对询问进行修改: \((l,r) \rightarrow (l,r+1)\) 和 \((l,r) \rightarrow (l-1,r),(l+1,r)\)。第一类修改就是直接二分即可，第二类修改的话钦定 \(r\) 相同的情况下 \(l\) 递减，那么对于 \(\sum \sigma\) 的修改就是一个整除分块，对于 \(\sum\sigma^2\) 的情形就会比较复杂，具体情况如下：\(l\) 的变动影响的 \(\sigma\) 具有形式 \(\sigma(k\cdot l,l),1\le k\le \lfloor{r\over l}\rfloor\)，所以可以再换一种表达方式: \(\theta(k,l):=\sigma(k\cdot l,l)\)，根据调和级数可知 \(\theta\) 的有效位是 \(\mathcal O(V\log V)\) 的，而从 \((l,r)\) 变到 \((l’,r)\) 就是在 \(\theta(\cdot,l)\) 的前缀和上做整除分块，因此这一部分的维护的时间复杂度就是由整除分块贡献，不过还需要预处理 \(\theta\) ，时间复杂度是 \(\mathcal O(q\sqrt V+V\log V)\)

QOJ – 7661. Japanese Lottery

精妙的数学题，之前见过，但是当时苦于找不到合适的数学工具来描述交换的行为，前几天群中有人提及置换故而恍然大悟，故可从置换合成的角度来描述这一题目的行为。

题面：称二元置换为交换，对交换列 \(\set{\sigma_i}\) ，进行总共 \(q\) 次操作，每次操作形如在该列中某个位置插入一个交换或者移除某个交换，对于操作完后的长度为 \(m’\) 的交换列 \(\set{\sigma’_i}\) ，求最长的递增序列 \(\set{a_i}:1\le a_1<a_2<…<a_n\le m’\) 的长度 \(n\) 使得 \(\sigma=\sigma_{a_1}\circ\sigma_{a_2}\circ\sigma_{a_3}\circ…\circ\sigma_{a_n}=I\)

先说明上述问题的结论：设 \(\sigma\) 中有 \(s\) 个环，那么至少需要移除 \(|\sigma|-s\) 个置换，并且这个值可以取到。

证明如下：

先证明下界，假设将 \(\sigma_{1}\circ\sigma_{2}\circ\sigma_{3}\circ…\circ\sigma_{m’}\) 中的某一项移除后的乘积为 \(\sigma’\) ，那么存在交换 \(\alpha\) 使得 \(\sigma’=\sigma \circ\alpha\)。
这是因为对于两个交换 \(\alpha,\beta\) 而言 \(\alpha\circ\beta=\beta\circ(\beta\circ\alpha\circ\beta)\) ，而可以验证，\(\beta\circ\alpha\circ\beta\) 也是一个交换，
这就给我们提供了一个将某一个交换逐项向后移动的工具，总而言之，对于要删除的那一项，可以一项项的把那一项向后移动到末尾，于是就有 \((\sigma’)\circ\alpha=\sigma \Longrightarrow\sigma’=\sigma\circ\alpha\)

而想把 \(\sigma\) 变成 \(I\) 则至少需要给 \(\sigma\) 右乘 \(|\sigma|-s\) 个交换，而每移除一个交换就相当于给 \(\sigma\) 右乘一个交换，于是至少需要移除 \(|\sigma|-s\) 次。

再证明取等，考虑取等的条件就是要做到这 \(|\sigma|-s\) 次右乘每次都能把一个环断成两个环，即每移除一个交换就要断掉一个环，则可以考虑证明当 \(s<|\sigma|\) 时总是存在这样的能够移除的交换。对于当前的（已经经过若干轮移除的交换列）\(\set{\sigma_i}\) 设 \(\lambda_i:=\sigma_{1}\circ\sigma_{2}\circ\sigma_{3}\circ…\circ\sigma_{i}\) 则 \(\lambda_{i+1}=\lambda_i\circ \sigma_{i+1}\) ，可以理解为 \(\lambda_i\) 经过了 \(\sigma_{i+1}\) 的变换得到了 \(\lambda_{i+1}\)，于是从后往前找到第一个 \(x\) 使得 \(\lambda_x\) 的环比 \(\lambda_{x-1}\) 少，那么移除掉 \(\sigma_x\) 必然使得 \(\sigma\) 的环增多，这是因为，\(x\) 后的变换都是把环裂开的，而如果