CF1070A Find a Number
一个朴素的想法是设 \(dp_{x,y}\) 表示模 \(d\) 为 \(x\) 且和为 \(y\) 的最小值，那么答案就是 \(dp_{0,s}\)。
自然初始状态为 \(dp_{0,0}=0\)，但是我们发现这个转移关系是带环的，所以说要把这个 dp 换成最短路。
直接从 \((0,0)\) 为源跑一遍 bfs 即可，时间复杂度 \(O(sd)\)。
CF1840G1 In Search of Truth (Easy Version)
猜环长这种东西，有个经典的类似 BSGS 的猜法。
考虑设置一个步长 \(B\)，先一步一步地跳，把环的前 \(B\) 个位置给跳上，并标记好是在第几步被跳到的。
随后按照我们设置的步长 \(B\) 步一次地跳，因为余数小于除数，所以这么跳完一圈之后一定会落在前 \(B\) 个位置上，又因为我们知道前 \(B\) 个位置是环上的第几个点，所以我们可以直接算出环长。
取 \(B=\sqrt n\) 可以得到 \(2\sqrt n\) 左右的上界询问次数，可以通过 Easy Version。
CF731E Funny Game
因为二人都选最优的决策，所以说我们的决策是跟未来有关的，考虑倒着 dp，设 \(dp_i\) 表示 \([i,n]\) 这个后缀内的最大得分。
记 \(s_i\) 表示前缀和数组，容易发现考虑 \([i,n]\) 这个后缀时 \(s_{i-1}\) 的贡献是一定要被算上的，所以我们就有转移 \(dp_i=\max_{j>i}\{-dp_j+sum_{j-1}\}\)，显然维护个后缀 \(\max\) 就能快速转移，时间复杂度 \(O(n)\)。
CF1826E Walk the Runway
视每个物品拥有 \(m\) 个属性的话，那么选择两个物品的限制其实是一种 \(m\) 维偏序。显然地，如果 \(a,b\) 能同时选且 \(b,c\) 能同时选，那么 \(a,b,c\) 也是能一块选走的。
所以如果我们能够处理出任意两个物品之间能否都选，那么我们按照任意一维排序后从前往后 dp 就能统计出答案了（因为要满足限制任意一维一定是递增的），所以就去思考怎么处理这个东西。
多维偏序本身就有经典的 bitset 解法，这里我们也可以试下。先把 \(m\) 维全都分开考虑，把所有物品按照当前考虑的这一维属性排序，然后每个物品在单独这一维下能选的物品就是它前面的物品，那我们直接把 \(m\) 维可选的物品取个并即可，可以使用 bitset 维护。
细节：排序后要对每个相同的段考虑。
时间复杂度 \(O(nm\log n+\frac{n^2m}{w}+n^2)\)，分别是排序、bitset 和 dp 的复杂度。
CF1638E Colorful Operations
这不是板子题/xk。
考虑颜色段均摊，先上一个 set 用来维护连续段，思考如何维护加法操作。
不妨采用标记的方式，令 \(tag_x\) 表示颜色 \(x\) 应该额外加上的值，对于 Add 操作直接在 \(tag\) 数组上修改。对于区间覆盖操作时，假设有一段区间 \([l,r]\) 要从颜色 \(x\) 覆盖成 \(y\)，那直接为 \([l,r]\) 这段区间加上 \(tag_x-tag_y\)，减去 \(tag_y\) 是因为之前给颜色 \(y\) 的加法这段区间不应该算上。输出时直接加上对应位置的 \(tag\) 即可。
上面的操作只需要一个树状数组来维护，根据经典结论总时间复杂度为 \(O(q\log n)\)。
简要说下正确性：容易发现每一次区间染色操作至多会使整个序列的连续段个数加 \(1\)，同时我们可能会删除一些连续段，但是每个连续段至多只会被删除一次，每次加入/删除连续段的复杂度是 set 的 \(\log\)，所以总复杂度为 \(O(q\log n)\)。
CF1697E Coloring
考虑对于每个点求出来到其它点的最短距离，然后再向达到最短距离的点连一条单向边。
我们取出所有的极大的双向联通子图，如果这个子图是完全图那么其所有点要么同色要么互不相同，否则全都互不相同。
对于可以染成同色的点集我们称之为同色点集，那我们先对所有同色点集做一个背包，设 \(dp_i\) 表示使用 \(i\) 种颜色的方案数，每个同色点集可以贡献的颜色数为 \(1\) 或点集大小。
答案即为 \(\sum_{i=1}^n\binom{n}{i}i!dp_i\)，也就是选出来 \(i\) 种颜色再考虑染色顺序。
时间复杂度 \(O(n^2)\)。
标签：26,log,2024.7,题解,复杂度,tag,同色,物品,dp From： https://www.cnblogs.com/los114514/p/18325211