2024.9 做题记录

001. CF2002E Cosmic Rays CF*2300

标签：思维，栈

题意：

给定 \(n\) 个元组，\((a_i,b_i)\)，表示有 \(a_i\) 个 \(b_i\) 按顺序排列在一起。一次操作可以删除以下数字：

1. 在第 \(1\) 个位置的数字
2. \(s_i ≠ s_{i-1}\) 的位置 \(i\)

问每个前缀最多成操作多少次。

Observation：

1. 问每个前缀最多能撑住几轮操作，其实暗示我们利用前面的答案以某种方式推出后面的答案。
2. 手玩样例可以发现，如果对于 \(x\) 个元组，\(b_i\) 全都不相同，那么答案即为 \(max(a_1,a_2,...,a_x)\)。证明也是比较显然的。
3. 我们考虑处理权值相同的情况，我们简化问题进行讨论——只考虑两个权值相同的块夹着一个不同权值块的情况。将三个块的大小设为 \(x,y,z\)。如果 \(z≤y\)，那么根本不会有任何贡献，答案还是前面的。如果 \(z>y\) 且 \(x≤y\)，那么其实就会加上这个块的贡献，不过这种情况我们在代码中其实是可以直接压进去不管的。如果 \(x>y\) 且 \(z>y\)，那么就会把 \(y\) 消了，然后 \(x\) 和 \(z\) 拼在一起。然后这个串可以撑住的轮数就变为了 \(x+z-y\)。
4. 两个权值相同夹着中间的块不管是什么，我们只需要知道它能撑住的轮数即是它的 \(y\)。

Doubt：

想到这里就感觉想不下去了。当时的想法是因为看到标签里有 dp，看怎么样能找到前面相同的权值然后用数据结构优化一下。结果解法是栈，有些震惊。

Solution：(after seeing le0n's tutorial)

有点像单调栈的意思。

1. 如果前面的块大小比你现在压进来的小，那他根本就没用，直接更新一下现在消了的次数然后直接从栈里踢出去即可。
2. 如果权值和自己相同，更新自己的大小为 \(a_i+stk_{top}-maxx\)，这根据的是性质 \(3\)。然后把这个块踢出去，为什么呢？因为你自己合并之后还会压进来更大的块。
3. 其他情况就不能吞或合并了，因为人家比你的大小大，你影响不了人家。
4. 把自己这个更新后的元组压进栈，最大值更新，做完了。

002. CF906D Power Tower CF*2700

标签：扩展欧拉定理

虽然 2700 但不怎么难的题。

扩展欧拉定理降幂塔的另一大板子（第一个是上帝与集合的正确用法）。

题意：

给定数组 \(a\)，每次给定区间 \([l,r]\)，询问 \(a_l^{{a_{l+1}}^{...^{a_r}}}\)。

Observation：

1. 看到幂塔，想到扩展欧拉定理+快速幂的光速幂解法。
2. \(\varphi\) 函数的层数是 \(logp\) 级别的，也就是说每次询问的复杂度都是双 \(log\)（有一层快速幂）。而 \(\varphi\) 变为 \(1\) 后上面的也不用管了。（上一个板子的结论）
3. 发现需要用到的 \(\varphi\) 值就那么几个，完全可以根号 \(n\) 单点查，或者提前预处理（推荐这个）

Solution:

1. 预处理出要使用的模数
2. 递归处理询问（DFS）
3. 快速幂略有不同，大于 \(p\) 需要模 \(p\) 再加 \(p\)。
4. 暴力计算即可

003. CF242E XOR on Segment CF*2000

标签：线段树，位运算

题意：

在一个序列上做两种操作

1. 询问区间和
2. 区间异或 \(x\)

Solution：

比较经典的一个 trick 吧。关于区间位运算的，就考虑状压线段树或者拆位线段树。这里拆位线段树比较好写，于是就写了空间开销较大的拆位。

对于数的每一位维护一颗线段树。

1. 于是对于修改操作——异或 \(x\)。就是把 \(x\) 拆成二进制数，如果 \(x\) 这一位为 \(0\)，那么就没有改变，否则在区间线段树上，这一位全部取反。而其和的变化就是 \(sum\) 变为了 \(r-l+1-sum\)。懒标记记录这个区间是否翻转即可，下传操作是显然的。
2. 对于求和，显然的，就是
   \[\sum^{log(maxn)}_{i=0} Sum(i,l,r) \times 2^{i} \]

另外注意建树的时候，每一位都要 PushUp 就好。

004. CF438D The Child and Sequence CF*2300

标签：线段树，势能分析

题意：

在一个序列上做三种操作：

1. 询问区间和
2. 区间对 \(x\) 取模
3. 单点修改

Observation：

1. 发现一个势能性质就好，就是区间取模次数是 \(log(a_i)\) 级别的，于是进行类似 GSS4 的暴力单点改就好
2. 什么时候不改？显然的，区间最大值小于 \(x\) 就不改。

Solution：

1. 对于操作 \(1\)，维护区间 \(sum\)。
2. 对于操作 \(2\)，如 observation 所提到的，进行单点暴力修改。
3. 对于操作 \(3\)，暴力修改。
4. 记得 PushUp，但因为没有懒标记，所以不用 PushDown。

005. CF434D Water Tree CF*2100

标签：线段树，树链剖分

题意：

给出一棵以 \(1\) 为根节点的 \(n\) 个节点的有根树。每个点有一个权值，初始为 \(0\)。\(m\) 次操作。操作有 \(3\) 种：

1. 将点 \(u\) 和其子树上的所有节点的权值改为 \(1\)。
2. 将点 \(u\) 到 \(1\) 的路径上的所有节点的权值改为 \(0\)。
3. 询问点 \(u\) 的权值。

Solution：

就，就直接树链剖分。注意处理 \(1\) 和 \(0\) 的优先级。如果没有 tag 记得设为 \(-1\) 而不是 \(0\)，因为会造成歧义。

点查询的话，其实维护区间和就好，并没有必要为了点查询进行额外的麻烦操作。

区间改 \(0\) 就把 tag 和 sum 都赋值为 \(0\)。区间改 \(1\)，就把和赋值为 \(r-l+1\) 即可。

006. CF600E Lomsat gelral CF*2300

标签：线段树合并

题意：

有一棵 \(n\) 个结点的以 \(1\) 号结点为根的有根树。每个结点都有一个颜色，颜色是以编号表示的，\(i\) 号结点的颜色编号为 \(c_i\)。如果一种颜色在以 \(x\) 为根的子树内出现次数最多，称其在以 \(x\) 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。你的任务是对于每一个 \(i∈[1,n]\)，求出以 \(i\) 为根的子树中，占主导地位的颜色的编号和。

Solution：

考虑对每一个节点建一棵权值线段树，而每次算贡献其实就是将自己节点的权值线段树向自己的父亲合并。而权值线段树所要维护的就是出现次数的最大值和最终的答案。

如何计算这个节点总的答案？很简单，就是 \(sgt_{root_u}.ans\)，因为最终的所有答案都会合并到以 \(root_u\) 为根节点的线段树上。

唯一要注意的细节就是权值线段树的合并问题，还有加点较为麻烦，更新部分可以考虑加一个 PushUp 函数减小码量。

007. UVA437 The Tower of Babylon 提高+/省选-

标签：拆点，动态规划

看紫书看到这么个题，于是就混进来一道 Uva。

题意：

有 \(n\) 种长方体，边长为 \(a,b,c\)。可以任意调转长方体的方向。现在进行长方体堆叠，满足 \(a'<a\) 且 \(b'<b\) 的长方体可以堆叠在边长为 \(a,b,c\) 的长方体上面。问最高能堆叠到什么高度。

Solution：

其实还是挺简单的，首先由于可以翻转，考虑把 \(a,b,c\) 按任意顺序排列，拆为 \(6\) 个点（好像 \(2\) 个就够，但是 \(6\) 个好想）。随后对这 \(6n\) 个点按题目要求建图。

注意到题目中是天然的二维偏序关系，于是这个图是一个 有向无环图。在这个 DAG 上面跑 Toposort 求出最长路即可。

最后答案是所有的 \(dis\) 取一个 \(max\)。

008. CF1209G1 Into Blocks (easy version) CF*2000

标签：并查集，STL-set

题意：

给定序列 \(A\)。每次改动需要花费 \(cnt_x\) 的代价将所有权值为 \(x\) 的位置全都改换为另一个权值 \(y\)（自己定）。最终要求所有相同的数都连续出现。问最小代价。

Observation：

1. 我们发现，相交的区间和不交的区间有本质区别。于是先想到维护每个权值的左右端点。
2. 在一群相交的线段里面，所花费的最小代价就是区间长度减去数最多的一个权值的个数。
3. 把所有贡献加起来就是答案。

Solution：

1. 考虑经典 Trick，使用 set 的神奇排序维护区间交，并使用 dsu 并查集把交的线段放一个集合里。
2. 怎样维护区间求交？详见会场预约那题。大概就是：

bool operator < (const Line &x) const
{
    return R < x.L;
}

然后如果交就会判定为相等，但是其实有点细节。比如合并的这段代码：

int minn = ll[i], maxn = rr[i];
while(pos != s.end())
{
    Union(i, (*pos).id);
    minn = min(minn, (*pos).L);
    maxn = max(maxn, (*pos).R);
    s.erase(pos);
    pos = s.find(Line{ll[i], rr[i], cnt[i], i});
}
s.insert(Line{minn, maxn, cnt[i], i});

要维护 \(minn\) 和 \(maxn\) 是因为，有可能前面的线段和你有交，和后面的线段也有交，而唯独和你没交，于是因为你把它们删了，于是就不可能合并到一个集合了，所以说，你得维护目前的最小左和最大右端点才能维护交。

3. 后面就是暴力统计就行。

这做法比较 naive，貌似还有更好的做法。

009. P3071 [USACO13JAN] Seating G 省选/NOI-（真实难度 提高+/省选-）

标签：线段树，区间合并线段树

题意：

有一排 \(n\) 个座位，\(m\) 次操作。\(A\) 操作：将 \(a\) 名客人安置到最左的连续 \(a\) 个空位中，没有则不操作。\(L\) 操作：\([a,b]\) 的客人离开。

求 \(A\) 操作的失败次数。

Solution：

如果不是连续的，也有另外一种做法，就是二分 + 线段树，这种要求连续的更难一些。

其实与 GSS3 区间最大子段和非常像甚至还弱化了。在一个 \(01\) 序列上做操作。对于线段树上每一个节点 \(p\)，维护其最长 \(1\) 连续段 \(anscnt\)，包含左端点的最长 \(1\) 连续段 \(lcnt\)，包含右端点的最长 \(1\) 连续段 \(rcnt\)。另外记录一个 tag 维护区间推平为 \(0/1\)。

线段树的 PushUp 是难点，但是被 GSS3 完美覆盖了，所以直接上代码：

if(Sgt[lc(p)].anscnt == Sgt[lc(p)].R - Sgt[lc(p)].L + 1) Sgt[p].Lcnt = Sgt[lc(p)].anscnt + Sgt[rc(p)].Lcnt;
else Sgt[p].Lcnt = Sgt[lc(p)].Lcnt;
if(Sgt[rc(p)].anscnt == Sgt[rc(p)].R - Sgt[rc(p)].L + 1) Sgt[p].Rcnt = Sgt[rc(p)].anscnt + Sgt[lc(p)].Rcnt;
else Sgt[p].Rcnt = Sgt[rc(p)].Rcnt;
Sgt[p].anscnt = max(max(Sgt[lc(p)].anscnt, Sgt[rc(p)].anscnt), Sgt[lc(p)].Rcnt + Sgt[rc(p)].Lcnt);

建树和更新的时候细节都有些多，需要想清楚。

下一步是求连续区间左端点。

1. 如果其左子树的最长 \(1\) 连续段已经大于等于要求，那么优先递归左子树（要求编号最小）。
2. 如果恰好跨过中间，也就是左子树的 \(rcnt\) 加上右子树的 \(lcnt\) 是大于等于要求的话，那么就返回 \(mid\) 减左子树的 \(rcnt\) 再加 \(1\)，这很好理解。
3. 否则就是在右边，递归右子树。

复杂度？这样只会递归一边，复杂度是必定有保证的。是一种 类似线段树二分 的方法。

有个双倍经验是 Hotel G。

010. P2962 [USACO09NOV] Lights G

标签：高斯消元

题意：

给出一张 \(n\) 个点 \(m\) 条边的无向图，每个点的初始状态都为 \(0\)。

你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由 \(0\) 变成 \(1\) 或由 \(1\) 变成 \(0\)。

你需要求出最少的操作次数，使得在所有操作完成之后所有 \(n\) 个点的状态都是 \(1\)。

Solution：

看到 \(n \leq 35\)，考虑乱搞。注意到每个点的“变化操作”相当于一个系数只有 \(0/1\) 的 \(n\) 元方程。而对于每一个元 \(i\)，我们要让其值为 \(1\)。

因为我们考虑且仅考虑其在模 \(2\) 意义下的值，所以我们可以使用 异或高斯消元。

最后如果没有自由元的话答案就是 \(1\) 的个数，有自由元的话暴力搜索即可。注意此时其实不用折半搜索，因为自由元的个数理论上是不会超过一半的，搜索回溯复杂度可以接受。