目录
- 0.「CF 1788F」XOR, Tree, and Queries
- 1.「CF 1815F」OH NO1 (-2-3-4)
- 2.「CF 1787F」Inverse Transformation
- 3.「CF 1797F」Li Hua and Path
- 4.「CF 1815B」Sum Graph
- 5.「AGC 022C」Remainder Game
- 6.「CTT 2021」「洛谷 P8986」基因编辑
- 7.「CTT 2021」「洛谷 P8985」魔塔 OL ⭐
- 8.「CF 1605F」PalindORme ⭐
- 9.「CTT 2021」「洛谷 P8993」算术
- 10.「CTT 2021」「洛谷 P8991」出题高手
- 11.「IOI 2019」「洛谷 P5812」天桥 ⭐
- 12.「AGC 022F」Checkers ⭐
- 13.「ABC 299Ex」Dice Sum Infinity
- 14.「CTT 2021」「洛谷 P8994」经典游戏
- 15.「CF 1821F」Timber
0.「CF 1788F」XOR, Tree, and Queries
- Link & Submission.
- 「A.构造」
树上路径的自由度太大了, 我们的首要目标是降低限制条件的自由度. 方法自然是 \(\dist(u,v)=\dist(u,1)\oplus\dist(v,1)\). 记 \(b_u=\dist(u,1)\), 最小化的目标也能描述为 \(\bigoplus_{2\nmid\deg(u)}b_u\). 到此, 我们仅需构造这样的 \(\{b\}\), 使得:
- \(b_1=0\);
- \(\forall~\text{required}~(u,v,x),~b_u\oplus b_v=x\).
分 bit 构造, 并查集描述相等或不等关系. 注意我们可以把一个集合内的所有 bit 取反, 若取反后 \(\bigoplus_{2\nmid\deg(u)}b_u\) 改变, 那么可以用这个集合调整该 bit, 让其一定不对答案贡献. 否则每个集合随便选一种安排即可. 复杂度 \(\mathcal O(n\alpha(n)\log V)\).
1.「CF 1815F」OH NO1 (-2-3-4)
- Link & Submission.
- 「A.构造」
嗯嗯嗯? *3500?
考虑这样一个问题: 给定无向图 \(G\) 和任意初始权 \(\{a\}\), 对于每条边, 允许将其恰一端点 \(+1\), 构造使得所有边两端的点权不同的方案. 这个问题挺简单, 只需要不断取出最小的 \(a_u\), 将此时以 \(u\) 为端点的未确定的边的 \(+1\) 贡献向另一端即可.
由于这一迭代过程是偏序的, 所以任意一个三角形在定向后都不是环. 换句话说, 一个三角形的贡献一定是 \([+0,+1,+2]\) 的排列. 我们可以在原始边上构造 \([0,1,2]\) 的排列来做到任意一种 \([+3,+4,+5]\) 的排列的贡献, 这样就规约到上一个问题了.
用桶维护取出最小值的过程可以做到 \(\mathcal O(n+m)\). 这种算法只会用到 \(\{1,2,3\}\) 三种边权.
2.「CF 1787F」Inverse Transformation
- Link & Submission.
- 「A.构造」
用置换环描述排列, 那么 \(\sigma(x,i)=\sigma(\sigma(x),i-1)\) 的结果就是 \(x\) 沿着有向边跳 \(2^i\) 步的位置. 研究从 \(a\) 到 \(a'\) 的变化过程: 对于一个置换环, 若长度为奇数, 则变换后的置换环涉及的元素集合仍然相同, 不会改变; 若长度为偶数, 置换环的元素会根据位置奇偶性被划分为两个子环. 那么 \(a'\) 倒推 \(a\), 就只需要将等大的环合并. 注意原始环长为奇数的置换环应该尽量多地合并, 以最小化 \(a\) 的置换环数. 可以做到 \(\mathcal O(n)\).
还是补叙一下: 需要最小化的式子显然等价于排列置换环数.
3.「CF 1797F」Li Hua and Path
- Link & Submission.
- 「A.树论-Kruskal 重构树」
听 Ruanap 在痛苦卡 \(\log^2\) 的常所以跑来写, 单 \(\log\) 写过之后 Ruanap 还在卡常. (笑
"恰好满足一个条件", 容斥嘛. 若只要求 \(u\) 是路径最小值, 合法路径数量就是小根 Kruskal 重构数的子树大小和. 要求 \(u\) 是路径最大值同理. 接下来需要减去 \(u\) 是最大值, \(v\) 是最小值的路径 \((u,v)\), 既然我们已经建出 KT 了, 不妨也从 KT 的角度思考. 非法路径 \((u,v)\) 满足的条件是, \(u\) 在大根 KT 上是 \(v\) 的祖先, 且 \(v\) 在小根 KT 上是 \(u\) 的祖先 — 一个简单的二维偏序, DFS 过程中维护 BIT 即可计算初始答案.
修改其实是纸老虎, 因为新增树必然满足父亲编号小于儿子编号. 通过简单讨论新增结点与其他结点的位置关系可以配合小根 KT \(\mathcal O(1)\) 算答案增量, 本题就 \(\mathcal O(n\log n+m)\) 结束了.
4.「CF 1815B」Sum Graph
- Link & Submission.
- 「A.构造」
有只狗狗 VP 被 B 卡了, 我不说是哪只 Para.
如果用很多个 + 连出依托答辩肯定没法讨论, 我们可以猜测连出来的东西一定很简单, 比如说… 链.
怎么构造链呢? 很简单, + n, + n+1 即可.
接下来自然分为两步: 先找一个端点 (向求树直径一样找啦), 再求每个点到端点的距离. 正好两个端点位置回答两种序列, 大功告成. 中途卡个 corner 可以做到 \(2n-1\) 次询问.
5.「AGC 022C」Remainder Game
- Link & Submission.
从高到低枚举答案的 bit, 大力搜索 check 可达性即可. 复杂度一看就能过. (
6.「CTT 2021」「洛谷 P8986」基因编辑
- Link & Submission.
烂活. 耐着性子读完题发现就是二维偏序样子的问题. \(\mathcal O(n\log n)\).
7.「CTT 2021」「洛谷 P8985」魔塔 OL ⭐
-
Link & Submission (被洛谷卡常了).
-
「A.分块」「B.std::bitset」
先想想怪兽固定时的最优策略, 这个貌似叫 Monster Hunting 问题, 可以贪心解决. 对于 \(a\le b\) 的怪兽, 按 \(a\) 升序挑战; 然后对于 \(a>b\) 的怪兽, 按 \(b\) 降序挑战. 我们可以用 \((\text{requirement},\text{delta})\) 这样的二元信息表达 "能战胜一个怪物集合" 的要求, 该信息的加法运算有结合律, 但无交换律.
四维偏序限制下无交换律的信息询问… 恐怕没什么合理的 \(\operatorname{polylog}\) 了, 可以想一些分块策略.
一般来说, 高维偏序查询有一个 \(\mathcal O(n^2k/\omega)\) 的做法: 对于第 \(i\) 维, 预处理该维度坐标值 \(\le x\) 的集合 \(S_{i,x}\), 那么查询点 \((x_1,x_2,\cdots,x_k)\) 的答案就是 \(\bigcup_{i=1}^kS_{i,x_i}\), 这一操作可以用 std::bitset 实现.
模仿这个算法, 我们先将所有怪兽按照贪心顺序排序, 并对序列分块. 对长度为 \(B\) 的整块预处理 \(2^B\) 中块内贡献, 然后处理查询时维护四个偏序关系的 std::bitset, 将每个压缩位放入对应块查询贡献. 取 \(B\) 在 \(\log_2n\) 左右, 复杂度大概比暴力少一个 \(\log n\).
8.「CF 1605F」PalindORme ⭐
-
Link & Submission.
-
「A.数学-组合计数」「A.DP-计数 DP」
什么说呢… 其实不算太难. 不太容易的思路是: 算合法需要去重, 算非法也需要去重, 但两个问题的去重难度可能是不一样的, 都值得考虑.
还是按照自然的思路来, 首先思考如何判断合法 \(\{b\}\). 注意回文条件就是 "一个 bit 的最先最后出现到各自端点等距", 我们从两侧向中间构造 \(\{a\}\), 维护已经出现的 bit 集合 \(S\), 那么迭代过程就是:
- 任取 \(x,y\in\{b\}\), 满足 \((x\cup S)=(y\cup S)\). 从 \(\{b\}\) 中删去 \(x,y\), 令 \(S\gets S\cup x\cup y\).
特别地, 为了处理落单的 \(x\), 我们允许:
- 在仅存在一个 \(x\in\{b\}\), 满足 \((x\cup S)=S\) 时, 从 \(\{b\}\) 中删去 \(x\).
那么, \(\{b\}\) 合法当且仅当迭代无法进行时, \(|\{b\}|\le1\). 反过来, \(\{b\}\) 非法当且仅当 \(|\{b\}|>1\), 均非 \(S\) 的子集, 且两两不满足 \((x,y)\) 的条件.
Key motivation: "能迭代" 是一个动态的限制, 但 "不能迭代" 是一个静态的限制. 即, 已知 "不能迭代" 时, 由于 \(S\) 稳定, 两两数值需要服从的条件是固定的, 我们更容易对其计数.
接下来的事情就是简单的计数工作啦. 令 \(f(\ell,c)\) 表示长度为 \(\ell\), 使用 \(c\) 个 bit 的非法序列数量; \(g(\ell,c)\) 表示任意序列数量; \(h(\ell,c)\) 表示不能迭代的序列数量. 后两者容易求出:
\[g(\ell,c)=\sum_{i=0}^c(-1)^{c-i}\binom{c}{i}2^{i\ell},\\ h(\ell,c)=\sum_{i=0}^c(-1)^{c-i}\binom{c}{i}(2^i-1)^{\underline\ell}. \]据此, 枚举非法序列被迭代掉的长度 \(i\) 和迭代完成后的 \(|S|=j\), 容斥得到:
\[f(\ell,c)=\sum_{i=0}^{\color{red}{\ell-1}}\sum_{j=0}^{m-1}\binom{\ell}{i}\binom{c}{j}\cdot(g(i,j)-f(i,j))\cdot 2^{(i-\ell)j}h(\ell-i,c-j). \]可以见到, \(2\nmid i\) 的枚举对应了上文中对 "落单的 \(x\)" 的处理. 上式中 \(i\) 的上界有一个小 corner: 当 \(2\nmid n\) 且 \(\ell=n\) 时, \(i\) 取到 \(\ell-1\) 将直接使序列合法, 我们不允许这种情况发生. 否则我们就认为 \(i=\ell-1\), 仅剩下一个元素时仍然非法. 直接计算三个 DP 数组, 可以做到 \(\mathcal O(n^2m^2)\).
9.「CTT 2021」「洛谷 P8993」算术
- Link & Submission.
- 「A.数学-数论」
结合一些生活经验, 我们很容易去猜测
\[\sum_{i=0}^{\ell-1}a_ib^{ki}\overset{?}{\equiv}\sum_{i=0}^{\ell-1}(-1)^ia_ib^{\ell-i-1}\pmod p, \]但很快就能发现这个 \(\equiv\) 是不一定成立的. 题目中也只要求倍数判定, 这导致我们很难建立其一个同余式研究变化的性质.
实际上, 左右两侧只需要满足同为 \(0\) 或同非 \(0\). 令 \(\vct a=\pmtr{a_0&a_1&\cdots&a_{\ell-1}}\), 进制则可描述为常向量 \(\vct u=\pmtr{1&b&\cdots&b^{\ell-1}}\), 初始数值 \(A=\vct a\cdot\vct u\). 而变换后的进制向量 \(\vct v\) 则满足 \(\vct v^{(i)}=(-1)^{i/k}b^{\ell/k-i/k+(i\bmod k)}\) (\(x/y\) 表示下取整除法), 变换后数值 \(B=\vct a\cdot\vct v\). 若判据成立, 就有:
\[\forall \vct a,~\vct a\perp\vct u\leftrightarrow\vct a\perp\vct v~(\Leftrightarrow\vct u\para\vct v). \]也就是说:
\[\exist\lambda,~\vct v\equiv\lambda\vct u\pmod p. \]研究 \(\vct u^{(0)}\) 和 \(\vct v^{(0)}\), 可知 \(\lambda=b^{\ell/k}\). 那么
\[\begin{array}{ccc} & b^i\equiv(-1)^{i/k}b^{-i/k+(i\bmod k)} &\\ \Leftrightarrow & b^{i/k\cdot(k+1)}\equiv(-1)^{i/k} &(\forall i). \end{array} \]于是得到最终结论:
\[b^{k+1}\equiv -1\pmod p. \]注意到必要条件是 \(b\perp p\), 所以 \(b^{\varphi(p)}\equiv1\pmod p\), \(1\) 和 \(-1\) 是接近的, 我们先取出 \(c=\ord_p(b)\), 那么亦有必要条件 \(c=2(k+1)\). 据此, 在 \(k\) 存在时, 最优的解就是 \(c/2-1\). 注意 \(p=2\) 的特判. 复杂度 \(\mathcal O(\sqrt p+T\log^2 p)\).
注意, long double 模乘 (在模数非常量时) 远快于 __int128 暴力.
10.「CTT 2021」「洛谷 P8991」出题高手
- Link & Submission.
欸~ 糕⤵️叟⤴️! 就仄? 欸这不氢氢悚悚嘛. 没瘆么难度.
题解做法: 基于随机化的支配对维护. 对于 \(l\), 有意义的 \(r\) 满足 \(s_r\) 是前缀最值, 贡献也是前缀最值. 这样以来期望只有 \(\mathcal O(n\sqrt n)\) 个支配对. 查询就是二维数点, 需要平衡复杂度. 当 \(n=5\times10^5\) 时, 需要进一步优化支配对数量. 注意到若 \(s_r\) 取到前缀最大值, 而存在一个 \(l<p<r\), 使得 \(s_p\le s_l<s_r\) 时, \(s_l\) 就不可能与更大的 \(s_r\) 产生贡献. 同理, \(s_l\) 在一段时间后也不可能与更小的 \(s_r\) 产生贡献, 此时跳出循环, 可以通过所有数据.
更加混乱邪恶: 下载测试数据观察 猜测答案区间不长. 钦定阈值 \(L\), 暴力求出所有区间长度 \(\le L\) 的答案, 顺带求解小区间询问. 当询问区间超过 \(L\) 时, 直接对区间内的小区间答案取 \(\max\), 这是个静态 RMQ. 经测试, \(n\le10^5\) 取 \(L=2\times10^3\), \(n=5\times10^5\) 时取 \(L=300\) 就能过.
11.「IOI 2019」「洛谷 P5812」天桥 ⭐
- Link & Submission.
- 「A.图论-最短路相关」「B.优化建图」「C.性质/结论」
对子任务 \(4\), 显然横向速度恒非负, 我们可以用持久化数组维护到达 \(x_i\) 时, 处于每种可能的天桥高度的最短距离. 根据简单的松弛性质, 在加入天桥端点时只需要用临近的两个可用天桥更新.
这个算法无法移植到一般情况, 因为很有可能出现 "绕路上天桥" 的最优策略, 例如样例. 况且, 左右横跳的次数可以轻松达到 \(\mathcal O(m)\), 所以子任务的算法大概可以彻底放弃了. 你这子任务的提示性呢?
冷静想一想, 我们要求最短路, 而直接维护的方法已经鉴定为 wasted, 优化建图后跑最短路算法不失为一种思路. 不过建图时, 结点数又是一大难题. 虽然天桥端点只有 \(\mathcal O(m)\), 但却有 \(\mathcal O(nm)\) 个可能的进入或走出天桥的位置, 我们必须整点最优性剪枝来减少这一数量.
Key observation (but unmotivated
标签：Set,Submission,ell,Solution,Link,CF,vct,mathcal,击碎 From： https://www.cnblogs.com/rainybunny/p/17345440.html