2021 ICPC Southeastern Europe Regional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 6/? | 11 | 12 | 14 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
solved by TYB
题意¶
给出一个\(k\times n\)的矩阵\(A\)，定义\(B_j=\sum_{i=1}^kA_{i,j}\)。\(q\)次操作，设第\(i\)次操作后的矩阵\(A\)是第\(i\)个版本，初始的是第\(0\)个版本，三种操作：
1、在第\(t\)个版本矩阵的基础上，第\(p\)行第\(l\)到\(r\)列的数加上\(x\)。
2、在第\(t\)个版本矩阵的基础上，第\(p\)行第\(l\)到\(r\)列的数变为\(y\)。
3、询问第\(t\)个版本矩阵第\(l\)到\(r\)列数的最小值。
\(n\le2.5\times10^5,q\le20000,k\le4\)
题解¶
注意到\(k\)很小，考虑线段树维护这样一个东西：\(B'_S=\sum_{S的第i位为1}A_{i+1,j}\)的区间最小值，那么询问就是\(B'_{2^k-1}\)的区间最小值。对于\(1\)操作，直接找到对应的\(B'\)加即可；对于\(2\)操作，可以从之前的状态推过来。对于版本的操作，可以考虑主席树或者建出操作树。
复杂度\(\mathcal{O}(q2^k\log n)\)。
C¶
solved by JLK
题意¶
\(n\)个点的树，每个点有颜色\(c_i\)，求有多少联通子图，满足某一个颜色出现超过一半。
\(1 \le n \le 3000,1 \le c_i \le n\)
题解¶
首先有个\(O(n^3)\)的做法，就是枚举过半的颜色，然后树形DP，这个颜色看做1，其他颜色看做-1，相当于是让子图权值和大于0，用基于子树siz的树形DP即可。
实际上，假设枚举颜色\(c\)，这个颜色一共有\(n_c\)个点，那么做DP的时候最多只用枚举\([-n_c,+n_c]\)范围的下标即可。和子树siz取min来做DP，据题解说是\(O(n\times n_c)\)的。
那么总共就是\(O(n^2)\)。
D¶
**upsolved by **
题意¶
题解¶
E¶
solved by YZW
题意¶
题解¶
F¶
solved by JLK
题意¶
打怪，有\(N\)回合，每回合怪可能使用R药水，你可以攻击一次造成\(X\)伤害，以及使用P药水，药水一共能用\(K\)次。怪有属性，用一次R药水会让\(r+1\)，用一次P药水会让\(p+1\)，并且如果\(r>0\)，可以同时让\(r-1\)。每回合的伤害为\(X+P\times p-R\times r\)。给定怪每回合使用R药水的情况，求最多造成多少伤害。
\(1 \le N,X,R,P \le 10^6,0 \le K \le N\)
题解¶
如果没有R，那么肯定是让P药水尽可能早用。
如果有R，那么肯定是让P药水尽可能早用或者在R的时刻用，因为如果要用P抵消R的影响，那么肯定会放在R的时刻用P。
有R的时候收益为\((R+P)\times (n-i+1)\)，没有R的时候收益为\(P\times (n-i+1)\)。
把所有R的时刻和不用R的时刻拉出来分开看，两类时刻都是越早用P越优。也就是收益都是单调递减的，可以用类似归并的写法取前\(K\)大的收益即可。
\(O(N)\)
G¶
solved by JLK
题意¶
\(2n\)个点的完全图，每个点有属性\((a_i,b_i)\)，两个点之间的边权为\(\max\{|a_i-a_j|,|a_i-b_j|,|b_i-a_j|,|b_i-b_j|\}\)。求最大权匹配。
\(1 \le n \le 10^5,0 \le a_i,b_i \le 10^9\)
题解¶
由于绝对值，最优情况下，每个点对答案的贡献肯定是\(\max\{a_i,b_i\}\)或者\(-\min\{a_i,b_i\}\)。也就是说要选\(n\)个点取\(\max\)，选\(n\)个点取\(-\min\)，使得总和最大。
可以先把所有的都看成\(\max\)，然后把\(n\)个点改成\(-\min\)，每个点改后会有一个差值，取前\(n\)大的差值，把这些点改掉即可。
\(O(n\log n)\)
H¶
**upsolved by **
题意¶
题解¶
I¶
upsolved by JLK
题意¶
有两个\(N\times M\)的01矩阵，每次可以把A矩阵中的某一个同色连通块反色，若干次操作后，求两个矩阵最少的不同格子数。
\(1 \le N,M \le 100\)
题解¶
不同最少，也就是相同最多。先把不做操作的相同格子数求出来。
把每个连通块看做一个点，相邻连通块连边。把反色看成选点，每个连通块选了会有一个贡献（可正可负），代表反色后相同格子数的增量。
实际上操作合法的充要条件是没有同时选相邻的点。因为两个相邻连通块同时反色是不可能做到的。
那么问题转化为选若干个点，使得相邻点不同时选，并且权值最大。可以使用最大流解决，经典模型，源点连某个颜色，另一个颜色连终点，边权为选点的贡献。相邻的点连INF的边。所有边权减去最大流（最小割）就是选点的最佳方案。
如果贡献是负的，那么肯定不反色，直接忽视这个点即可。
J¶
solved by TYB
题意¶
长度为\(2n\)的仅由\(A,B,C\)组成的串，\(A\)可与后面的\(B,C\)匹配，\(B\)可与后面的\(C\)匹配，问是否有完美匹配。
\(n\le10^5\)
题解¶
考虑如果只有\(A,B\)，那么前面的\(A\)要尽量多，后面的\(B\)要尽量多。
所以从左到右扫\(C\)，让它先和最前面的\(B\)匹配，若没有再和最后面的\(A\)匹配。
然后再让\(A,B\)匹配即可。
K¶
solved by YZW
题意¶
题解¶
L¶
solved by TYB
题意¶
长度为\(3n\)的仅由\(A,B,C\)组成的串，每次操作可以把一个子串的所有字母变成某个字母，问最少操作次数，使得每种字母的出现次数都为\(n\)。
\(n\le3\times10^5\)
题解¶
可以发现答案至多为\(2\)，考虑从左到右扫，直到某个字母的出现次数为\(n\)，然后另外两个字母的次数一定\(<n\)，再把后面的改两次补到\(n\)即可。
所以只需要判断是否可以一次操作解决。
M¶
solved by YZW
题意¶
题解¶
L¶
solved by YZW
题意¶
题解¶
记录¶
YZW过N(0:04)，JLK过A(0:09)和G(0:24)。
YZW写K，WA了一次。
TYB写J，WA了一次，换JLK写F，期间TYB改过了J(0:55)，然后JLK过F(0:57)。
JLK写C，TLE，发现做法假了。
YZW继续写K，过了(1:23)。
TYB写L，WA两次后AC(2:14)。
YZW打了个表觉得M可以做，开始写M。期间JLK和TYB想出了B。
YZW过M(3:05)，TYB写B，JLK和YZW看CE，想出了E。
TYB过B(3:32)，YZW写E。
写到一半JLK想先试一试C的乱搞，又TLE两次后AC(4:02)。
YZW过E(4:25)。
JLK写I，WA两次，最后时间不够有个小bug没看出来。
总结¶
TYB：对网络流的模型还不太熟悉，I其实是裸的二分图最大权独立集。
Dirt¶
C(-3)
J(-1)
K(-1)
L(-2)