2018 ICPC Asia Jakarta Regional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 29/443 | 10 | 12 | 12 |
B¶
upsolved by JJLeo
题意¶
\(n\) 个节点的树，\(q\) 次以下三种操作之一：
- 删掉一个未被删除的点。
- 复原一个删掉的点。
- 选择一个未被删除的点，对该点所在连通块中的所有点，距离该点距离为偶数的权值 \(+x\)，距离为奇数的权值 \(-x\)。同时输出该连通块中的点数。
一条边存在当且仅当两个端点都没有被删。
如果一个点最终被删掉了，则它的权值和为删掉之前的权值。一个点被复原它的权值也为它删掉之前的权值。
所有操作结束后，输出所有节点的权值和。
(\(1 \le n,q \le 10^5\))
题解¶
随便确定一个点为根。
距离该点距离为偶数的权值 \(+x\)，距离为奇数的权值 \(-x\) 这个操作，可以简化为：
- 如果该点深度为偶数，则该连通块所有点权值 \(+x\)。
- 如果该点深度为奇数，则该连通块所有点权值 \(-x\)。
最后将所有深度为奇数的点权值变为负数即可。
首先需要一种算法找到 \(x\) 所在连通块没被删的点中深度最小的点 \(y\)：
一种方法是树剖+树状数组，不断跳找到第一个被删节点的重链后，在这条链上二分。
另一种更好写的方法是，一个点被删就对子树中每个点 \(+1\)，复原再 \(-1\)，每个点的权值即为有多少个祖先被删，倍增找到第一个权值不同的祖先即可。
两种方法复杂度均为 \(O\left(\log ^2 n\right)\)。
接着依次处理两个查询操作：
增删节点，多次询问每个连通块大小
设 \(\textit{siz}_i\) 是以 \(i\) 为根的子树的大小，\(T(i)\) 以 \(i\) 为根的子树的中点的集合。
通过维护每个点的一个权值 \(s_i\)，使得 \(\displaystyle \textit{siz}_x- \sum_{i \in T(x)} s_i\) 等于以 \(x\) 为根子树中和 \(x\) 连通点的数量。如果被删的节点之间没有祖先关系，那么直接令被删点 \(i\) 的权值为 \(\textit{siz}_i\) ，其它点 \(s_i=0\) 即可。如果出现了祖先关系，那么这样会算重，需要进行一些调整：
- 当 \(x\) 被删除时，设 \(x\) 所在连通块没被删的点中深度最小的点为 \(y\)，令 \(s_x=\displaystyle \textit{siz}_x- \sum_{i \in T(x)} s_i\)，若 \(y\) 不为根则令 \(s_y\) 减去 \(s_x\)。
- 当 \(x\) 被复原时，设 \(x\) 所在连通块没被删的点中深度最小的点为 \(y\)，若 \(y\) 不为根则令 \(s_y\) 加上 \(s_x\)，再将 \(s_x\) 变为 \(0\)。
这样类似差分思想的处理，可以始终满足我们的需求，因此询问 \(x\) 所在连通块大小时，找到 \(x\) 所在连通块没被删的点中深度最小的点 \(y\)，\(\displaystyle \textit{siz}_y- \sum_{i \in T(y)} s_i\) 即为答案。
增删节点，多次给一个点所在连通块的每个点增加一个值，最后只询问一次所有点权值和
每个点维护两个权值 \(a_i\) 和 \(b_i\)。
找到 \(x\) 所在连通块没被删的点中深度最小的点 \(y\)，直接给 \(y\) 子树中每个点 \(a_i\) 和 \(b_i\) 均增加对应的权值。当点 \(x\) 被删时将 \(b_x\) 设为 \(0\)，当点 \(x\) 被复原时，将 \(x\) 子树中所有点 \(a_i\) 减去 \(b_x\)，相当于把不连通多加的部分减掉。
当被删的节点之间没有祖先关系时，上述做法是正确的，否则如果先复原 \(x\) 再复原 \(y\) 且 \(y\) 是 \(x\) 的祖先，那么就会让 \(x\) 子树中的点多减去 \(y\) 祖先增加的权值。
因此需要进行调整，我们对 \(b_i\) 的含义进行重定义，代表 \(i\) 被删后所有 \(i\) 的祖先给 \(i\) 子树多加的权值和，同时在节点增删时进行一些操作：
- 当 \(x\) 被删除时，设 \(x\) 所在连通块没被删的点中深度最小的点的父节点为 \(y\)，则 \(y\) 也被删除，根据定义，令 \(b_x=b_y\)；特别地，若 \(y\) 不存在 (即 \(x\) 没有祖先被删除)，令 \(b_x=0\)。
- 当 \(x\) 被复原时，设 \(x\) 所在连通块没被删的点中深度最小的点的父节点为 \(y\)，则 \(y\) 也被删除，则只让 \(x\) 中子树减掉 \(x\) 祖先但不是 \(y\) 祖先这些点所多加的值，即为 \(b_x-b_y\)；特别地，特别地，若 \(y\) 不存在 (即 \(x\) 没有祖先被删除)，减去 \(b_x\)。此外，需要注意，根据 \(b_i\) 的定义，子树中不仅 \(a_i\) 要减去该值，\(b_i\) 同样要减去该值。
最后将所有被删除的点再复原，那么点 \(i\) 的权值即为 \(a_i\)。
上述操作均可以用 dfn 序 + 树状数组完成 (单点修改区间查询和单点查询区间修改)，复杂度瓶颈在找到 \(x\) 所在连通块没被删的点中深度最小的点 \(y\)，因此总时间复杂度为 \(O\left(n \log n + q \log ^2 n\right)\)。
C¶
upsolved by JJLeo
题意¶
构造一个最短的字符串 \(\in {\{0,1,\ldots,m-1\}}^*\)，要求至少出现了 \(k\) 个长度为 \(n\) 的子串。(\(1 \le n \le 10^5\)，\(1 \le m \le 10\)，\(1 \le k \le \min\left(m^n,10^5\right)\))
题解¶
字符串最短为 \(n+k-1\)，这样才能有 \(k\) 个长度为 \(n\) 的子串。考虑如下的有向图：
- 每个字符串 \(s \in {\{0,1,\ldots,m-1\}}^{n-1}\) 代表一个点，\(s \overset{a}{\to} t\) 存在当且仅当 \(s\) 删掉第一个字符、在末尾添加 \(a\) 后等于 \(t\)。
显然每个点的入度出度均为 \(m\)，因此这个图有欧拉回路。
随便选一个节点当起点，设该点的字符串为 \(s\)，接着遍历欧拉回路，依次将边上的字符添加到 \(s\) 后面。将最后得到的字符串看作环，每个字符串 \(s \in {\{0,1,\ldots,m-1\}}^n\) 恰好出现了一次。这是因为图中每个点和一条指出去的边都唯一确定了一个 \(s \in {\{0,1,\ldots,m-1\}}^n\)，一共有 \(m^n\) 个这样的二元组，对应 \(m^n\) 个字符串。遍历整个欧拉回路的过程相当于不断滑动长度为 \(n-1\) 的窗口。
关于寻找欧拉回路，首先复习一下 Hierholzer 算法：
从起点出发 dfs，每经过一条边就将其删掉，每个点回溯时入栈，最后从栈顶到栈底输出栈中元素即得到欧拉回路。
上述流程等价于每次删掉一个环，那么剩下的图还是欧拉图，由归纳假设可得算法的正确性。
本题我们只需找到长度为 \(k\) 的欧拉路径，当 \(m^n\) 较大时不可能把整个欧拉回路跑出来，因为在回溯时才入栈，调用上述算法有可能递归 \(m^n\) 次而栈内点数仍 \(<k\)。
因为上述算法只是一个简化版，完整版的 Hierholzer 需要维护两个栈 \(a\) 和 \(b\)，每遍历到一个点将其加入 \(a\)，回溯时将该点从 \(a\) 中弹出加入 \(b\)，那么任意时刻 \(a\) 从栈底到栈顶以及 \(b\) 从栈顶到栈底都是一条合法的欧拉路径。
这样至多遍历 \(O(k)\) 个点就能得到答案了。实现过程中，使用 deque 记录当前点对应的字符串，并在递归函数内记录入边上的字符即可。因为 \(m\) 较小，直接用一个 set 记录每个长度为 \(n\) 的字符串是否出现来实现记录每条边是否被删，并暴力遍历，总复杂度为 \(O(km \log k + n)\)。
题解中当 \(n\) 较大时直接输出随机字符串，实际上并不需要。
E¶
solved by Bazoka13
题意¶
题解¶
F¶
solved by
题意¶
题解¶
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
K¶
upsolved by
题意¶
题解¶
记录¶
0h：开局有人过I，感觉假人，ZYF喂了个L题，MJX扔了个A题。过5min左右一堆人过了I确实是个大签到，CSK过了。L题范围只有60，暴力DP就好了，写完MJX和ZYF看了会不知道哪错了，发现题里要求没有前导0，改了就过了。MJX搞了个做法，一个情况处理不了，CSK搞了个小数据的方法改了下就可以了。互相喂了几个题的题意，看榜有几个人过了D，扫了一下题面和样例感觉是个sb题，ZYF和MJX想了想有好多corner case，加了一堆感觉差不多就交了。WA了后有一个corner case漏了，改了过了。
1h：ZYF搞了个J的做法，改了个状态就开写了，MJX看K就是一个经典题（沈阳的）。CSK搞了搞G的 \(O(n^3\log{n})\) 的做法，被 ban 了，H开始只会暴力，润了。CSK开始看E，把EF的题意喂给MJX。ZYF把J做完MJX把做法喂给ZYF，ZYF把K也过了。
2h：CSK说了一下E的大致做法，MJX YY了一下感觉无比正确，CSK开冲！MJX ZYF挂机GH，感觉G可以暴力 \(O(n^3)\) 做，但是暴力用 vector 存会 MLE，ZYF直接写了个链表来存，空间就很小了但是一直调不对。隔壁训练结束了，mian记错时间了，没人来主持会议，MJX开始电话轰炸。
3h：CSK写完了MJX观察了一波感觉大概挺对的交了WA了，ZYF改不出来了直接写了个vector不管了，大概在极限数据下卡到了256MB下，交了过了，数据爆弱就只用了50MB，迷惑。CSK改了下变成T了，MJX ZYF一起看感觉复杂度对对的，应该被卡常了，CSK改了一堆STL，然后最后交了个C++20飞快的过了，之前那个直接改成c++20也过了，迷惑。ZYF想了想H巨简单，给MJX过了一下就直接写了。MJX YY了一个F的做法，感觉很对，让CSK check了一下扔给ZYF去写了。
4h：第一发WA了，CSK随手构造一个hack的数据，ZYF改完过了。剩了个BC，MJX感觉B完全不可做，去乱搞C了。想了想都不咋会，直接开始随机了，然后果然就T了，测了一下个数比较满的时候就巨慢，不会了，寄！
After end：G std竟然是 \(O(n^3\log{n})\) 的，不能接受！