2018 ICPC Asia Jakarta Regional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 46/? | 9 | 11 | 12 |
A¶
solved by JLK
题意¶
从01串\(S\)变到\(T\)，每次操作可以插入、删除、替换任意一个字符。
给定\(S\)，要求找到一个\(T\)，使得\(S\)变到\(T\)的最少操作次数\(\gt \frac {|S|}2\)。
\(1 \le |S| \le 2000\)
题解¶
如果\(S\)内\(0\)和\(1\)的个数不相等，那么可以直接把所有的字符变成较少的那个数。
如果相等，考虑第一位，如果第一位是0，就把它变成1，其他所有都变成0。
因为操作次数一定至少是\(S\)和\(T\)中0（或1）的个数之差。相等的时候还需要多做一次操作，让第一位取反一定会让操作数变多。
B¶
upsolved by JLK
题意¶
\(n\)个齿轮啮合成一棵树，\(q\)次操作：
1：取出其中一个齿轮。
2：将一个已经取出的齿轮放回原位置（角度和取出时相同）。
3：将某个没取出的齿轮顺时针旋转\(\alpha\)度（相邻的齿轮旋转方向相反）。每次还行乣输出所有齿轮旋转的角度之和。
最后输出每个齿轮最终的顺时针角度之和。
\(1 \le n,q \le 10^5\)
题解¶
3操作的询问本质上就是问当前连通块里点的个数，可以简单用树剖+BIT维护。
不考虑1、2操作，只有旋转的话，可以以某个点为根，把所有操作推到根上（注意正负），当做是旋转了根节点的齿轮。唯一的区别就是有些点是正转，有些是反转，这和点到根的距离的奇偶性有关。可以先当做所有操作都是正着转，最后输出的时候判断深度的奇偶性，然后反转的取反即可。
先考虑1操作，在以1为根的有根树上，\(x\)被删除，设\(y\)是\(x\)子树内的点，\(z\)是\(x\)子树外的点。可以当做是\(x\)为根的子树独立出来。那么删除\(x\)之后，如果把\(y\)的操作放在\(x\)上，这样对\(z\)就没有影响了。但是没有实际分离出子树，\(z\)会把操作放到根上，会影响\(y\)。
考虑将\(y\)得到的值修正。我们当做\(x\)是独立出来的，所以\(y\)的角度取决于\(x\)的角度。但是\(x\)在删除前可能已经有一些外部旋转带来的角度。那么可以在删除的时候将\(x\)已有的外部旋转带来的角度当做一个挂在\(x\)上的操作，这样就可以放心断开\(x\)了。
用这样的思想，在2操作时，就是把\(x\)塞回去，但是\(x\)不在的这段时间的外部操作是不能进来的。最暴力的方法就是把外界操作直接当做一个在\(x\)点的反转，直接屏蔽了这段时间的外部操作。而这样对于\(x\)点本身的角度有一点问题，需要额外对于\(x\)记录一下差值，输出的时候减掉。
因此实际上就是找到一个点的祖先里最近的一个被删除的点，路径上的角度和就是这个点的旋转角度。
用树剖+线段树可以维护这些东西，细节比较多。
\(O((n+q)\log^2 n)\)
C¶
upsolved by TYB
题意¶
给出\(m\)个个位数。用它们构造一个最短的数字串，使得这个串所有长度为\(n\)的连续子串，至少有\(k\)种。
\(1\le n\le10^5,1\le m\le10,k\le \min(m^n,10^5)\)
题解¶
首先可以大胆猜测答案串的长度恰为\(n+k-1\)，即不会出现重复的连续子串。考虑如何构造，我们有一种暴力做法：可以建出一个有向图，每条边代表一个长度为\(n\)的子串，由于该有向图所有点出入度相等，因此存在欧拉回路，只需要找到一条欧拉回路即可，这也印证了结论。这样的复杂度为\(m^n\)。考虑\(n\)比较大的时候，可以把\(n\)变成一个较小的\(n'\)，使得\(m^{n'}\)恰好大于\(k\)，因为只要前面的\(n'\)位不同，子串就一定不同，这样就解决了本题。
D¶
solved by JLK
题意¶
\(R\times C\)的方格，有冰面和地面，如果走到冰面上，会一直朝当前方向滑行，直到碰上地面或者边界。现在要把一些冰面变成地面，使得从任意一个位置出发，都存在一种移动方案能够停留在所有位置（滑过不算）。求最少变的数量。
\(1 \le R,C \le 500\)
题解¶
首先除了四条边的内部区域一定要是地面，否则无论怎么走都不能在内部冰面停留。
然后考虑四条边，在不是四个角的边界上至少要有一个地面，否则外部无法到达内部。
还有一些特殊情况，比如行列只有1或2的情况。
E¶
**upsolved by **
题意¶
题解¶
F¶
solved by YZW
题意¶
题解¶
G¶
solved by TYB
题意¶
给一个\(n\)个点\(m\)条边的简单无向图，要求通过加边把这个图变为完全图，加边的规则为若\(\deg_x+\deg_y\ge k\)，且可以在\(x,y\)间连一条边，求\(k\)最大可以是多少。
\(2\le n\le500,0\le m<\frac{n(n-1)}{2}\)
题解¶
首先可以想到二分，但复杂度为\(\mathcal{O}(n^3\log n)\)，无法通过。考虑不用二分，我们可以先将\(k\)设为一个很大的值，并且维护一个当前可以连的边的集合。当这个集合为空时，表明我们必须把\(k\)变小，且至少变为当前\(\deg_x+\deg_y\)的最大值。否则我们把这些边连上，并检查是否由于点的度数变大，有新的边可以加进集合，这样连完所有边后的\(k\)就是答案。
\(k\)的初值为\(\mathcal{O}(n)\)，每次变小要用\(\mathcal{O}(n^2)\)的时间找最小值；边数为\(\mathcal{O}(n^2)\)，每加一条边要更新\(\mathcal{O}(n)\)个点，故复杂度为\(\mathcal{O}(n^3)\)。
H¶
solved by TYB
题意¶
给一个长度为\(n\)的序列，每个位置可能是\(-1,0,1\)之一，要求把所有\(0\)改为\(-1\)或\(1\)，使得该序列满足给出的\(k\)个形如区间\([l,r]\)的和\(\ge x\)的限制且字典序最小。
\(1\le n\le10^5,0\le k\le10^5\)
题解¶
可以先默认所有\(0\)都为\(1\)，判断有无解，再贪心，尝试把每个位置改为\(-1\)。假设现在判断第\(i\)位的\(1\)能否改成\(-1\)，可以用堆维护一个包含\(i\)位置的区间集合，堆中的二元组\((a,b)\)表示当前在第\(a\)个限制下，\(sum[l_a,r_a]\)最多还能减小\(b\)，若这个最小值\(\ge2\)，则可以把\(i\)位置改为\(-1\)，且堆中所有数要减去\(2\)，打标记实现即可。
I¶
solved by YZW
题意¶
签到。
题解¶
略。
J¶
solved by YZW
题意¶
比较签到。
题解¶
略。
K¶
solved by YZW
题意¶
给定一个无向图 \(G\)，求其最大边匹配，换言之，其线图 \(L(G)\) 的最大匹配。
\(1\leq |V|, |E|\leq 10^5\)
题解¶
我们给出如下结论：对于 \(G\) 的连通块，设其边数为 \(|E'|\)，则连通块的最大边匹配为 \(\left\lfloor |E'|\over 2 \right\rfloor\)。
如何构造方案？对于树，构造方案是显然的，自底向上贪心即可。对于图，我们可以遍历得到其 DFS 树，对于返祖边 \((u,v)\)，将祖先 \(v\) 复制为新点 \(v'\)，以 \((u,v')\) 替换 \((u,v)\) 即可得到树，从而可以构造方案。
时间复杂度是线性的。
L¶
solved by TYB
题意¶
签到。
题解¶
略。
记录¶
YZW过I(0:05)，JLK讨论后过A(0:09)。
TYB写L，WA一次后AC(0:30)。
JLK写D，WA一次后AC(0:47)。
TYB写G，YZW和JLK讨论J。
TYB写了一会发现复杂度有问题，换YZW写J，JLK和TYB讨论G。
YZW WA一次后AC(1:11)，然后TYB过了G(1:23)。
TYB写H，WA一次后AC(1:44)。
跟榜看K（其他题过的人不多），卡了很久只会乱搞，JLK尝试乱搞，WA了两次。
换题，发现F可做，YZW WA一次后AC(3:46)。
之后YZW想到了K的正解，WA一次后AC(4:22)。
最后讨论发现BCE都有思路，但没时间了。
总结¶
JLK：不要卡题！！！！！
Dirt¶
D(-1)
F(-1)
H(-1)
J(-1)
K(-3)
L(-1)