2020 ICPC Asia East Continent Final¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 40/470 | 7 | 9 | 13 |
A¶
solved by JLK
题意¶
给一个由大小写字母和数字组成的字符串，求满足本质上和\(namomo\)相同的子序列个数。（也就是长度为6，由四个不同字符组成，第三个和第五个相同，第四个和第六个相同）
\(1 \le n \le 10^6\)
题解¶
字符集大小是\(w=62\)，一种比较暴力的做法是枚举第三个和第四个字符，每次扫一遍计算。
要通过本题肯定要优化到\(O(nw)\)。
设第三第五个字符为\(a\)，第四第六为\(b\)。
从后往前扫，每次令当前的字符为\(a\)，然后在扫的过程中处理一下对于每个\(a\)，每个\(b\)的\(cnt_b\)及其平方。这样每次对于一个当前的\(a\)，枚举\(b\)，就可以算出后四个字符的方案数。而现在也知道了\(a\)和\(b\)，就知道前两个能取哪些，可以\(O(1)\)算出前两个的方案。
这样就是\(O(nw)\)。
B¶
solved by JLK
题意¶
一个\(n \times m\)的矩阵，每秒消失一个方块，问每秒还存在的方块构成多少矩形。（也就是矩形内部不能有空方块的个数）
\(1 \le n,m \le 500\)
题解¶
把每个方块的消失时间看做权值。问题等价于求每个时刻消失多少矩形。一个矩形的消失时间就是里面所有方块的权值最小值。
枚举两行，扫列，每一列的权值就是这一列在两行之间的方块权值最小值。
计算每一列作为最小值的贡献。用单调栈找到左边右边第一个比它小的即可。
\(O(n^2m)\)
C¶
solved by YZW
题意¶
题解¶
D¶
solved by JLK
题意¶
一个无向图，初始边权为1，有\(k\)单位的钱，每次可以花费1单位的钱来使一条边权为\(\frac 1a\)的边变为\(\frac 1{a+1}\)。有两个人要从各自起点走到各自终点，求最小的两人经过边权之和。
\(1 \le n \le 5000, 0 \le m \le 5000,0 \le k \le 10^9\)
题解¶
显然两人最终走的路径如果相交，那么一定是一段连续区间。
由于\(n\)不大，可以枚举相交路径的起点的终点。预处理出每两个点的距离。
这样对于每个情况，可以得到一个二元组\((a,b)\)，表示在这种方案下，一个人走的路有\(a\)条，两个人走的路有\(b\)条。（简单把几个距离相加肯定会有偏大的情况，但是这里面一定能找到最优方案）
还有一个性质就是，边权一定是在\(a\)，\(b\)的所有边里分别均分。
还有一个性质就是，\(b\)相同的情况下，\(a\)肯定越小越好，那么只保留最小的情况。
这样总共只有\(O(n)\)个方案需要计算，可以暴力一点，推一下式子然后直接二分套二分求出给\(a,b\)分别的边权，然后调整一下。
推式子指的是，可以比较硬币当前给\(a\)或者给\(b\)的边权差值，这样可以求出对于某个给\(a\)的分配，\(b\)最多分多少是比给\(a\)优的。先二分给\(a\)的，再二分给\(b\)的即可。后者是求出最多给\(b\)多少，前者是要求比\(k\)小的最大\(a\)。
\(O(n^2+n\log^2n)\)
E¶
upsolved by
题意¶
题解¶
F¶
solved by TYB
题意¶
签到。
题解¶
略。
G¶
upsolved by TYB
题意¶
给出长度为\(n\)的序列\(a\)，\(m\)次询问，每次给出\(L,R\)，求满足\(L\le l\le r\le R\)且\(a_l,a_{l+1},\dots,a_r\)中不同数的个数为奇数的\((l,r)\)的对数。
\(n,m\le5\times10^5\)
题解¶
考虑离线，扫描右端点\(r\)，维护一个长度为\(n\)的\(01\)序列，第\(i\)位为\(1\)表示区间\([i,r]\)中不同数的个数为奇数。那么对于每次新加进来的\(a_r\)，就是将\([poa[a_r]+1,i]\)这一段的\(01\)反转，这样一共有\(n\)次修改，设第\(i\)次修改后这个\(01\)序列的第\(j\)位为\(b_{i,j}\)。对于询问\(L,R\)，相当于求\(\sum_{i=1}^R\sum_{j=L}^Rb_{i,j}\)。所以需要一个数据结构支持区间取反，求历史版本和，这个可以用线段树解决。大概是记录区间答案和、区间\(0/1\)个数、上次修改的时间、上次修改开始有多长时间处于翻转/不翻转状态。
时间复杂度是大常数的\(\mathcal{O}(n\log n)\)。
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by TYB
题意¶
不想描述，大模拟。
题解¶
提高代码能力。
J¶
upsolved by
题意¶
题解¶
K¶
solved by JLK
题意¶
德扑，已经知道自己的两张牌和公共的三张牌，问是否必胜。
题解¶
如果自己不是同花顺，一定能被干掉。
如果自己是同花顺，分类讨论一下，能不能被大一点的同花顺压。
L¶
solved by YZW
题意¶
题解¶
M¶
upsolved by
题意¶
题解¶
记录¶
TYB过F(0:09)，JLK写A发现复杂度不对，换YZW写L。
YZW过L(0:35)，JLK再写A，RE一次后AC(0:52)。
JLK写D，WA一次后AC(2:41)。
TYB写I，但是比较麻烦，换JLK写K，然后过了(3:26)。
又换YZW写C过了(4:17)，JLK WA一次后过B(4:40)。
后来I交了几次都WA。
总结¶
JLK：这场自己犯的低级错误有点多，以后要注意。
TYB：提高代码能力。
YZW：该补补计算几何了……提高代码能力。
Dirt¶
A(-1)
B(-1)
D(-1)