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)