2021 ICPC ECFinal¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 27/356 | 6 | 7 | 13 |
A¶
solved by JLK
题意¶
签到，略。
题解¶
B¶
solved by TYB
题意¶
给一个数字串，求对于所有子串，有多少种不同的划分，可以把串划分为\(aabcab\)。（即对于同一个子串，划分方式不同算不同的方案）。
\(n\le 5000\)
题解¶
枚举\(ab\)的长度\(l\)和第二个\(a\)的起始位置\(i\)，那么需要知道两个信息：一是有多少\(k<l\)，使得\(s[i-k,i-1]=s[i,i+k-1]\)，二是原串的一个后缀中包含多少个\(ab\)子串。前者可以\(\mathcal{O}(n^2)\)预处理，后者可以手写hash做到\(\mathcal{O}(1)\)。为了尽量减少hash冲突，可以先枚举长度。
C¶
**upsolved by **
题意¶
题解¶
D¶
**upsolved by **
题意¶
题解¶
E¶
solved by TYB & JLK
题意¶
斗地主，没有大小王，每个玩家都可以看到所有人的牌，地主不想下家走掉，地主上家想同伴走掉，地主上家先出牌，且地主下家只有一张牌，问是否是地主下家走掉。
题解¶
策略如下：地主上家先出一张最小的，然后地主从小到大抗住下家，在地主打出最大的牌后，上家拿牌权，再传递一张给下家。然后讨论一些特殊情况就好了。
F¶
**upsolved by **
题意¶
题解¶
G¶
**upsolved by **
题意¶
题解¶
H¶
upsolved by TYB
题意¶
给一个\(n\times m\)的仅由\(0,1,?\)组成的矩阵，要求把\(?\)都替换成\(0/1\)，使得矩阵中形如
的\(2\times2\)矩阵数量最多，输出方案。
\(n,m\le100\)
题解¶
首先把所有\(x+y\)为奇数的\((x,y)\)位置上的\(01\)反转一下，转化为四个格子都相同的\(2\times2\)矩阵个数最多。
赛场上想歪了，考虑的是每个格子如何填。实际上，可以对每个\(2\times2\)子矩阵分别考虑，看它是全填\(0、1\)产生\(1\)的贡献，还是不产生贡献。那么就有很显然的最小割模型了。
最后的问题就是输出方案。在别人的代码那里看到了一个很好的方法：最后再跑一次bfs，将每个点根据源点能否到达它分成两边，那么就有了一个最小割的方案。
I¶
solved by YZW
题意¶
题解¶
J¶
solved by JLK
题意¶
\(n\)个点\(m\)条边的无向图，起点是1，除了起点之外每个点有一个怪兽，怪兽有自己的等级\(l_i\)。玩家的等级是\(l_1\)。每天可以打一个等级比玩家低的怪兽。每天一开始每个怪兽的等级增加\(B\)，打完怪兽之后玩家的等级增加\(A\)。
只有存在一条\(1\)到\(i\)的路径，路上怪兽都被打过了，才可以打\(i\)。
问到达\(n\)并打败怪兽的最小时间是多少。
\(1 \le n,m,A,B,l_i \le 2\times 10^5\)。
题解¶
可以规定每天必须要打一个怪兽，然后玩家第\(T\)天的相对等级就可以看做是\(l_1+(A-B)\times T-A\)，而怪兽等级视为不变。
\(A\le B\)比较简单，等级是不升的，肯定是越早通关越好。直接bfs，当天能打就过去打，不能打就不能过去，求到\(n\)的最短路。
\(A \gt B\)的情况稍微复杂一点。相当于玩家会升级，然后每天能打的怪兽会越来越多。每天可能到的点实际上是一个不断扩展的连通块，可以分层来考虑。
比如，第0天只能到达1点，第1天可以到达1邻接的能打过的点。第\(i\)天可以到达第\(i-1\)天的连通块邻接的能打过的点。
而不是每天都能扩展连通块的，所以需要打怪练级。最坏情况下会把当前连通块里所有怪物都打过之后才能到下一个点。
也就是说，第\(i\)天的连通块要满足\(siz_i \ge i\)。这样才能活到第\(i+1\)天，否则第\(i\)天就没法打怪。
稍微处理一下这个分层图，bfs一下即可。具体来说，就是每个点加入连通块的时间是，邻接的点里最早到达的点+1和能够打败这个点的怪兽的时间取max。
只要能活到到达\(n\)的那一天就是胜利。总之还是个bfs。
\(O(n+m)\)
K¶
**upsolved by **
题意¶
题解¶
L¶
solved by JLK
题意¶
\(n\)个点的树状数组，给出最后每个点是否是0，求最少用多少次树状数组的add操作可以满足最后情况。
\(1 \le n \le 10^5\)
题解¶
树状数组本质上就是树。每次add相当于是更新这个点到根的路径上所有点的权值。
考虑最后为0的点，它的子树对祖先的贡献都是0。那么就不管它。
对于最后不为0的点，会对祖先产生贡献。
但是两个子树的贡献是可以相互抵消的（只要求是否是0，没要求正负）。也就是说，如果一个点有至少两个不为0的儿子，那么这个点无论是0/1都不需要额外操作。
需要操作的只有两种：
如果只有一个不为0的儿子，而这个点是0，就必须额外操作一次来恢复0。
如果没有不为0的儿子，而这个点不是0，也要额外操作一次。
模拟一遍即可。\(O(n)\)
M¶
**upsolved by **
题意¶
题解¶
记录¶
JLK过A(0:09)，YZW写I，WA了一次。
JLK写L，然后发现假了，YZW改对了I(0:22)。
讨论了一会把L搞出来了(0:39)。
然后看B，一开始JLK读对了，但TYB读错了，写了个假代码。
注意到正确题意之后决定大力hash table，但单hash被卡了，WA两次后AC(2:06)。
YZW开始写D，JLK和TYB讨论E。
D WA了，找不出错。JLK开始写E，越写越觉得情况复杂，搞了很久才弄出正确策略，WA一次后AC(3:58)。
YZW继续搞D，JLK突然会了J，WA两次后AC(4:53)。
最后D放弃治疗乱试eps没过。
总结¶
JLK：搞分类讨论还不如多看看别的题
TYB：我不应该每次都不读打牌题让队友描述题意，如果这次我读了题，早点意识到这是斗地主就可以节省很多时间了。再写单hash吃屎。
YZW：谢谢几何。谢谢 float128。谢谢 long double 在不同平台下位数不同。
Dirt¶
B(-2)
E(-1)
I(-1)
J(-2)