NOI2026 做题记录 三

CF698F Coprime Permutation

link
进行一些合理猜测。

• 质因子集合相同的数可以任意互换：显然 \(\gcd(i, j)\) 与 \(1\) 的关系只与质因子集合有关。
  
• 对于质数 \(x,y\) 而言，如果 \(\lfloor \frac{n}{x}\rfloor=\lfloor \frac n y \rfloor\)，我们可以将 \(x,y\) 的倍数整体互换。
  

我们通过打表，可以发现上面两个条件就是充分必要的，于是直接做即可。
CF1693F I Might Be Wrong

link
结论：我们只有可能操作 \(c_0=c_1\) 的区间。
为什么呢？假如我们操作了一个区间 \(c_0-c_1=d>0\)，首先这个区间的第一个数必须是 \(1\)(如果是 \(0\)，不妨让左端点右移一位肯定更优），我们不妨重新选择一个右端点满足这个新的区间 \(c_0=c_1\)，那么我们只用了 \(1\) 的代价把一些 \(0\) 丢到了最左边，至少将问题递归到了 \(d-1\) 的子问题，如此递归，最多 \(d+1\) 次 \(c_0=c_1\) 的操作就可以完成原来的操作。
因此，每次操作，我们肯定要让区间的在包含第一个 \(1\) 的同时，让它的右端点越向右，同时满足 \(c_0=c_1\) 即可。时间复杂度 \(O(n)\)。
CF1299D Around the World

link
翻译一下题意，我们可以删掉一些与 \(1\) 相连的边，删掉后，包含 \(1\) 的连通块内，不存在一个简单环的集合，满足这个集合的异或和为 \(0\)。
先删掉 \(1\)，对于每个连通块，如果这个连通块是线性有关的，那么这个连通块必须和 \(1\) 断开。否则可以和 \(1\) 连接，但是要求所有与 \(1\) 相连的连通块的所有简单环都是线性无关的。我们发现把把本题值域很小，一一因此考虑把所有简单环插入线性基内，对不同的线性基 DP 即可，复杂度 \(O((n+B)B)\)，其中 \(B\) 为不同的线性基个数，在本题 \(V\le 31\) 的条件下 \(B=374\)。
CF1554E You

link
结论：每一种给 \(n-1\) 条边定向的方案与 \(a_u\) 的方案构成双射。
证明：我们考虑证明定向后每个节点的度数 \(deg_u\)，和 \(a_u\) 的定义等价，于是考虑证明不同的定向方向一定能产生不同的 \(deg_u\)。对于一个叶子节点 \(u\)，他与父亲的链边决定了的 \(deg_u\)；在确定叶子节点后我们把他删掉，不断迭代即可得到定向方案。
由此可以产生推论，\(\sum a_u=n-1\)；总方案数为 \(2^{n-1}\)。
如果 \(k>1\)，可以直接唯一确定定向方案，我们对于可能有答案的 \(k,k>1\)(即满足 \(k|n-1\)) 单独跑一遍暴力，剩下的所有方案都满足 \(k=1\)。本题最大的难点在构造双射。\(O(nd)\)，其中 \(d\) 为 \(n-1\) 的因子个数，可以通过一些分析做到 \(O(n\omega)\)，\(\omega\) 为 \(n-1\) 的质因子个数。
CF698F Coprime Permutation

link
进行一些合理猜测。

• 质因子集合相同的数可以任意互换：显然 \(\gcd(i, j)\) 与 \(1\) 的关系只与质因子集合有关。
  
• 对于质数 \(x,y\) 而言，如果 \(\lfloor \frac{n}{x}\rfloor=\lfloor \frac n y \rfloor\)，我们可以将 \(x,y\) 的倍数整体互换。
  

我们通过打表，可以发现上面两个条件就是充分必要的，于是直接做即可。
CF1693F I Might Be Wrong

link
结论：我们只有可能操作 \(c_0=c_1\) 的区间。
为什么呢？假如我们操作了一个区间 \(c_0-c_1=d>0\)，首先这个区间的第一个数必须是 \(1\)(如果是 \(0\)，不妨让左端点右移一位肯定更优），我们不妨重新选择一个右端点满足这个新的区间 \(c_0=c_1\)，那么我们只用了 \(1\) 的代价把一些 \(0\) 丢到了最左边，至少将问题递归到了 \(d-1\) 的子问题，如此递归，最多 \(d+1\) 次 \(c_0=c_1\) 的操作就可以完成原来的操作。
因此，每次操作，我们肯定要让区间的在包含第一个 \(1\) 的同时，让它的右端点越向右，同时满足 \(c_0=c_1\) 即可。时间复杂度 \(O(n)\)。
CF1299D Around the World

link
翻译一下题意，我们可以删掉一些与 \(1\) 相连的边，删掉后，包含 \(1\) 的连通块内，不存在一个简单环的集合，满足这个集合的异或和为 \(0\)。
先删掉 \(1\)，对于每个连通块，如果这个连通块是线性有关的，那么这个连通块必须和 \(1\) 断开。否则可以和 \(1\) 连接，但是要求所有与 \(1\) 相连的连通块的所有简单环都是线性无关的。我们发现把把本题值域很小，一一因此考虑把所有简单环插入线性基内，对不同的线性基 DP 即可，复杂度 \(O((n+B)B)\)，其中 \(B\) 为不同的线性基个数，在本题 \(V\le 31\) 的条件下 \(B=374\)。
CF1554E You

link
结论：每一种给 \(n-1\) 条边定向的方案与 \(a_u\) 的方案构成双射。
证明：我们考虑证明定向后每个节点的度数 \(deg_u\)，和 \(a_u\) 的定义等价，于是考虑证明不同的定向方向一定能产生不同的 \(deg_u\)。对于一个叶子节点 \(u\)，他与父亲的链边决定了的 \(deg_u\)；在确定叶子节点后我们把他删掉，不断迭代即可得到定向方案。
由此可以产生推论，\(\sum a_u=n-1\)；总方案数为 \(2^{n-1}\)。
如果 \(k>1\)，可以直接唯一确定定向方案，我们对于可能有答案的 \(k,k>1\)(即满足 \(k|n-1\)) 单独跑一遍暴力，剩下的所有方案都满足 \(k=1\)。本题最大的难点在构造双射。\(O(nd)\)，其中 \(d\) 为 \(n-1\) 的因子个数，可以通过一些分析做到 \(O(n\omega)\)，\(\omega\) 为 \(n-1\) 的质因子个数。
CF1852E Rivalries

link
对于所有的 \(a_i=x\)，只有最左边的位置 \(l\) 和最右边的位置 \(r\) 是有用的，我们把每个数抽象成一个三元组 \((l, r, x)\)。
对于 \(xL,|a_i-a_j|\le L\)，并让 \(L\gets L+a_i+a_j\)。我们发现这个过程可以直接暴力跳，操作的次数不会超过 \(O(\log V)\) 次。
证明：如果吞并了比自己小的水桶，如果下一次还能吃且吃了 \(x\)，那么有 \(x>L\)，两次操作内 \(L\) 至少翻倍；如果 \(L\) 这一次吞了两个比他更大的，那么 \(L\) 直接变成原来的至少三倍。
用喜欢的数据结构维护即可，复杂度 \(O(q\log^2 V)\)。
CF2119F Volcanic Eruptions

link
当前点与岩浆的距离不会增大。我们只需要保证终点合法即可。
当跳到一对相邻的 \(11\) 之后，我们可以无限延长路径。我们至多只会跳一对相邻的 \(11\)。
考虑解的形态。枚举最后的终点 \(t\)，我们在 \(st\to t\) 的路径上可能会选择走出路径跳一对 \(11\) 再走回来，在这之前的所有路径要求 \(-1,1\) 交错，这样把解分成了三个结构。预处理每个点出发到 \(11\) 对的最短路径，再从 \(st\) 开始 dfs，容易 \(O(n)\) 求出答案。
CF2127F Hamed and AghaBalaSar

link
转化题意，我们把一个 \(a\) 分成尽可能多段，每一段的结尾都是 \(a_n\)，贡献即为每一段的结尾-开头值之和。
记 \(S(n, m, k)\) 表示 \(n\) 个变量 \(a_1\dots a_n\) 满足 \(a_i\in [0, k]\land \sum a_i=m\) 的合法的 \(a\) 的方案数。
枚举 \(a_n=k\)。

• 每一段尾 \(i\) 的贡献，这里每出现一个结尾就会有 \(k\) 的贡献：
  

• \(i=n\)，方案数为 \(S(n-1, m-k, k)\)。
  
• \(i\neq n\)，方案数 \(S(n-2, m-k-k, k)\)。
  

• 每一段开头的贡献：
  

• \(i=1\)，要求 \(a_n=k\)，此时每个数是平等的，\(a_1\) 的期望即 \(\frac {m-k}{n-1}\)，方案有 \(S(n-1, m-k, k)\)。
  
• \(i\in [2, n-1]\)，要求 \(a_{i-1}=a_n=k\)，\(a_i\) 的期望 \(\frac {m-k-k}{n-2}\)，方案数为 \(S(n-2, m-k-k, k)\)。
  
• \(i=n\)，此时要求 \(a_{n-1}=a_n=k\)，方案数 \(S(n-2, m-k-k, k)\)，期望即为 \(k\)。
  

复杂度是调和级数 \(O(m\log m)\)。
CF2034H Rayan vs. Rayaneh

link
等价于找到一个集合 \(S\)，满足 \(\forall x \in S,\gcd_{(y\in S \setminus x)} y \nmid x\)。
对每个 \(x\in S\) 分解质因子，条件可以看成，对于每个 \(x\)，满足存在质数 \(p\)，满足 \(p\) 在 \(x\) 中的次幂是严格最小的。
反过来思考，设 \(C=p_1^{r_1}\times p_2^{r_2}\times\dots\times p_k^{r_k}\)，\(f_x\) 为 \(a\) 中 \(x\) 的倍数个数，如果有 \(\forall i \in [1, k], f_{C/{p_i^{r_i}}}a_i\) 的 \(a_j\) 都是 \(a_i\) 的倍数即可。
本题较为卡常，需要给暴搜加上减枝才可通过。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

感谢分享