The 2021 ICPC Asia Taipei Regional Programming Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 26/? | 9 | 10 | 13 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
solved by JLK
题意¶
两个长度为\(n\)的字符串，可以选择把第二个串的某个子串翻转，求最多能匹配多少字符。
\(1 \le n \le 10^3\)
题解¶
假设两个串分别为a|b|c和d|e|f，e'为e的翻转。
如果把e翻转，那么贡献就是b和e'的匹配减去b和e的匹配。
考虑优化。可以算出第一个串每个后缀和第二个串每个前缀的翻转的匹配。这可以\(O(n^2)\)递推得到。那么b和e'的匹配就是b|c和(d|e)'的匹配减去c和f'的匹配。枚举两端点直接计算即可。
\(O(n^2)\)
C¶
upsolved by JLK
题意¶
有\(n\)个时刻，\(m\)个事件，有两种事件：
1、来了一个人，他在\([a,b]\)时刻有空。
2、来了一个任务，需要在\([c,d]\)时间完成。只要人和任务的交集不为空就可以做。选一个最晚来的能做的人做这个任务，并且这个人做完就走了。
求出每个任务是谁做的。
\(1 \le n \le 10^6,1 \le m \le 2\times 10^5\)
题解¶
其实比较暴力，不知道场上为啥想复杂了。
用线段树维护，每个人直接分成log个区间，每个区间维护一个vector，按来的先后插入。相当于区间更新，然后维护区间最大值。
对于一个任务就是询问区间最大值，询问完了之后需要删掉，直接到之前的log个区间里的vector删掉就可以了，vector里剩下的最大值可以作为新的区间最大值。
\(O(m\log m)\)（离散化）
D¶
solved by JLK
题意¶
有\(D\)个一位数字，第\(i\)个数字为\(d_i\)，给定\(K\)，求这些数字任意排列中模\(K\)余数最大的数。相同情况下选字典序最大的。
\(1 \le D \le 16,1 \le K \le 200,1 \le d_i \le 9\)
题解¶
先不考虑字典序，那么可以简单状压，\(Fr_{S,i}\)表示选取数字状态为\(S\)，余数为\(i\)，记录转移到这个状态的前一状态。
考虑字典序，可以按数位从大到小枚举，假设枚举到某个数位，当前数字是按字典序从大到小的，按顺序枚举当前状态，然后从大到小枚举下一个数字转移，就可以保证枚举到下一个数位的状态是按字典序从大到小的。
实际上直接状压有很多状态是可以忽略的，可以预处理优化常数。
\(O(2^DKD)\)
E¶
**upsolved by **
题意¶
题解¶
F¶
solved by TYB
题意¶
\(n\)张边与坐标轴平行的带颜色的海报依次覆盖，问最后能看到多少种颜色。
\(n\le4000\)
题解¶
显然可以离散化，这样坐标的大小就到了\(n\)的级别，然后就可以倒过来用并查集直接暴力染色了，每个格子只会被染色一次，\(\mathcal{O}(n^2)\)。
在这种问题中，离散化的时候要注意，原先不相邻的边在离散化后也不能相邻。为解决这个问题，一种方法是将点坐标\(+1/-1\)也一并离散化，二是将每个格子用其左上角的坐标代替。方法一会加大常数，在本题不适用。
G¶
solved by TYB
题意¶
签到。
题解¶
略。
H¶
**upsolved by **
题意¶
题解¶
I¶
solved by TYB
题意¶
签到。
题解¶
注意背包怎么写！正过来循环是无限背包！倒过来才能保证每个东西仅用一次！
J¶
solved by YZW
题意¶
题解¶
K¶
**upsolved by **
题意¶
题解¶
L¶
solved by YZW
题意¶
题解¶
M¶
solved by YZW
题意¶
题解¶
记录¶
JLK写A，WA一次后AC(0:08)。
YZW过M(0:13)。
JLK过B(0:29)。
TYB写F，WA了一次。换JLK。
JLK过D(1:28)。
F看了一段时间，没有找出问题。
TYB写G，TLE两次后AC(2:19)。
TYB写I，WA了一次。
先回去对拍F，改了一下，TLE一次后AC(3:25)。
然后找到I的问题，改了之后AC(3:34)。
一起看JL，YZW写L，式子没推好，WA一次后AC(4:18)。
J感觉题目很奇怪，YZW试了一下，然后过了(4:42)。
总结¶
TYB：我是SB。
Dirt¶
A(-1)
F(-2)
G(-2)
I(-1)
L(-1)