Codeforces Round #545 (Div. 1)

本来开头两道题写得挺快的，然后第三题想了一会儿胡出一个scc计算gcd的做法，写了一发凭借信仰交了上去结果一发pp了？然后第四题沙雕了想了很久才会，于是罚时瞬间变多。结果后面两题都没时间看了，赛后感觉e题考场上还是可做的...

最后自豪的成为c题fst的一员，因为naive写萎了一个地方。

题目链接 (opens new window)

A. Skyscrapers

题意：给定一个$n\times m$的矩阵，对于所有$1\le i\le n,1\le j\le m$，计算将第$i$行及第$j$列共同离散化并保持第$i$行元素之间相对大小不变、第$j$列元素之间相对大小不变至少需要几个不同的值。$n,m\le 1000$。

题解：签到题，首先对每一行和每一列单独离散化。对于第$i$行和第$j$列，由于除了交点之外其他元素之间无影响，因此只要把离散化后的两个数组交点的位置对齐并计算长度即可。复杂度$O(nm\log nm)$。

B. Camp Schedule

题意：给定两个$01$字符串$s$、$t$，求一个$s$的重新排列使得$t$作为子串出现在$s$中的次数最大。$|s|,|t|\le 500000$。

题解：更签到的题。由于可以将$s$随意重新排列因此只需保留$s$中$0$和$1$的个数。考虑开头设为$t$一定最优（如果可以的话），接下来想要出现新的$t$，可以利用$t$的最长border尽量少用一些字符。那么可以用kmp或者别的方法求出$t$的最长border，之后只要贪心放就可以了。复杂度$O(|s|+|t|)$。

C. Museums Tour

题意：有一张$n$个点$m$条边的有向图，每个点有一个博物馆并且走一条边需要恰好一天。这个世界一周有$d$天，博物馆每周的开放情况是一样的。现在告诉你每个点的博物馆一周内的开放情况（星期几是否开放），希望你求出在一周中的第$1$天从$1$号点出发最多能参观几个不同的博物馆。$n,m\le 100000,d\le 50$。

题解：这题什么都好就是pretest太弱了...容易想到先将原图分解为若干个强连通分量。先考虑每个强连通分量内部的情况，易知对于一个强连通分量中的每个点$x$，都存在一个$d$的因子$c$，使得假如能在星期$a$到达点$x$，那么一定能在星期$(a+c)modd$到达$x$（这里的星期从$0$开始标号）。其中$c$在数值上等于$d$以及强连通分量内所有环的长度的最大公约数。此时我们不妨将强连通分量内的某个点设为关键点，假设在星期$0$从这个点出发，那么对于每个强连通分量内的点来说，都存在一个$[0,c)$之间的数$e$使得$e$是最小的满足能在星期$e$到达该点的数字。不妨将每个点的$e$值记为它的$id$。

那么首先我们假设我们已经知道了每个强连通分量的$c$，考虑如何进行$dp$。我们可以设$f_{i,j}$表示到达标号为$i$的强连通分量，且如果走到这个强连通分量中$id$为$0$的点时最小为星期$j$，那么在之前能参观的最多的博物馆数目。转移方程应该不难得出，只要注意$j$这一维在转移时应该如何变化即可。

最后考虑如何对每个强连通分量计算$c$。一个简单的方法是从状态$x,0$（可以在星期$0$到达$x$）开始dfs（只经过强连通分量内部的边），找出所有能到的状态。那么$c$以及每个点的$id$就不难得出了。复杂度$O((n+m)d)$。

D. Cooperative Game

题意：交互题。有$10$个小朋友在一个“$\rho$”上玩游戏。“$\rho$”是由$t+c$个点组成的，每个点只有一条出边。从起点开始有一条长度为$c$的链，链的尾端指入一个长度为$c$的环，其中指向的那个点就是终点。现在小朋友不知道$t$和$c$的值，但他们可以进行不超过$3(t+c)$次移动，每次可以令任意个不同的人向出边走一步，走完后告诉你哪些小朋友在一个点上。你要让所有小朋友都到达终点。

题解：学过pollard rho的应该都对这道题感到熟悉。pollard rho有两种判圈的方法——floyd和倍增。虽然倍增比较常用但是这道题更适用floyd判圈。

首先只移动$0$和$1$，每次令$0$走两步，令$1$走一步。可知当它们相遇时一定都走入了环中。那么此时再令$0$不停走，直到再和$1$相遇，那么就可以知道环的长度$c$。

此时令$2$向前走$c$步，再将$2\sim 9$一起移动，直到$2$和$3\sim 9$相遇，可知他们一定都在终点。最后令$0$和$1$一起走到和$2\sim 9$相遇即可。

直接这样做可能会导致交互次数过多，但是可以发现$2$先走的$c$步可以和$0$同时进行，于是就可以在次数限制之内完成了。

E. Train Car Selection

题意：维护一个数组，支持这些操作：

$1$、在前端塞入$k$个$0$。

$2$、在后端塞入$k$个$0$。

$3$、对于数组中每个数，假设它是数组的第$i$个，那么令它的值加上$b+s(i-1)$。

每次操作完后，询问数组中的最小值以及最左边的最小值的位置。

操作个数$q\le 300000$。

题解：首先可以发现向数组前端塞入$0$挺滑稽的，因为永远是最晚插入的最前面一个比较小。于是可以将前后分开维护，每次将前后的答案取$min$即可。于是只关注如何维护后面。

那么可以发现对于同时塞入的一段，第一个数永远是这一段中最小的，于是可以只保留第一个数。那么或许可以维护一个递减的单调栈，因为后面的数比前面大肯定没救了。但是可以发现在加上一个一次函数后单调栈可能不一定单调了。这时我们发现对于栈中的点，可以以数组下标为第一维当前值为第二维表示成一个点集。可以发现一定是形成一个下凸壳比较优，否则中间的点一定不会成为最小值。从值单调变成斜率单调以后即使加上一个一次函数也是满足单调性的，于是就可以直接做了。复杂度$O(q)$。

F. Matches Are Not a Child's Play

题意：给定一棵$n$个点的树，每个点点权互不相同。定义树的消除规则为每次选择点权最小的度数为$1$的点消除。有三种操作：

$1$、将某个点的点权设为当前最大点权$+1$。

$2$、询问假如要消除整棵树，那么某个点是第几个被消除的。

$3$、询问假如要消除整棵树，那么两个点哪个先被消除。

$n\le 200000$，操作个数$q\le 200000$。

题解：第三个操作显然是滑稽我们不管它。此时我们假设之前点权最大的点是$y$，现在改为了$x$，那么对消除序列有什么修改。可以画图考虑发现只是将树链$x,y$之间的点按从$y$到$x$的顺序移动到了最后，其他点的相对消除顺序是不变的。那么我们可以将这个操作等价的改为将树链$x,y$的点权赋值为一个比较大的公差为$1$的等差数列，修改点权的同时维护权值线段树就可以知道每个点的排名。

有一种方法是使用lct，将权值为一段连续等差数列的链合并在一棵$Splay$内。每次相当于设根为$y$，然后将$x$向上$access$，每次轻重链切换时顺便修改权值线段树就可以了。只是需要注意打标记时下传的顺序，因为赋值和翻转是同时存在的~~（我才不会说我因为标记下传的规则调了一年呢）~~。复杂度$O(n{\log }^{2}n)$。