The 2021 China Collegiate Programming Contest (Harbin)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 24/? | 8 | 9 | 12 |
A¶
**upsolved by **
题意¶
题解¶
B¶
solved by JLK
题意¶
签到，略
题解¶
C¶
solved by TYB
题意¶
给一棵以\(1\)为根的有根树，若\(i\)为叶子节点，其需要被染色为\(c_i\)，每次操作可以把某个子树所有的叶子节点染成任意颜色，求最小的操作次数。
\(n\le10^5,c_i\le n\)
题解¶
有个很显然的做法：对每个节点维护染好以它为根子树的最小操作次数，以及在保证操作次数最小的情况下第一次能把整棵子树染成的颜色集合。求一个点\(x\)的答案时，首先把它所有儿子的答案加起来，然后设所有儿子颜色集合组成的可重集中，出现最多的颜色出现了\(c\)次，\(ans[x]-=c\)。
考虑线段树合并，若某种颜色在集合中，则对应位置为\(1\)，否则为\(0\)。那么每次操作相当于把所有儿子的线段树合并起来，然后把非最大值的位置变成\(0\)，最大值的位置变成\(1\)。线段树维护区间最大最小值，以上两种操作都可以暴力完成，因为\(1\)的总个数是\(\mathcal{O}(n)\)的，删去一个\(1\)需要\(\mathcal{O}(\log n)\)的时间，总复杂度\(\mathcal{O}(n\log n)\)。实现时需要注意如何保证删掉的点以后不会再被访问，如一个点代表的区间最大值是\(0\)的话就可以将这个点删去。
D¶
solved by TYB
题意¶
给定\(p,q\)，\(p,q\)可以同时删去同一个可重集里的数并去掉前导零得到\(p',q'\)，且要保证\(\frac{p}{q}=\frac{p'}{q'}\)，求\(p'\)的最小值。
\(0<p,q<2^{63}\)
题解¶
十进制下最多\(19\)位，于是可以直接暴力枚举分子\(p\)留下哪些位的数，然后判断是否合法。注意由于前导零会自动地被删除，所以最后可删除的\(0\)的个数是一个区间。
E¶
solved by TYB
题意¶
签到。
题解¶
略。
F¶
**upsolved by **
题意¶
题解¶
G¶
solved by YZW
题意¶
题解¶
H¶
solved by TYB
题意¶
给两个长度为\(n\)的序列，分别记为\(a,b\)，和一个整数\(k\)，一次操作可以选择满足\(1\le p\le n-2k+1\)的\(p\)，然后对所有\(i\in[0,k-1]\)，交换\(a_{p+i}\)和\(a_{p+i+k}\)的值，问若干次操作后两个序列能否相等。
\(n\le10^5\)
题解¶
不太懂，感觉见过类似的题，猜了个结论就过了。官方题解的证明还不太想看
考虑把下标按\(\%k\)的值分组，那么每次操作显然会使每一组逆序对的奇偶性反转，所以直接猜所有组逆序对的奇偶性相同是充要条件，如果一个组里有重复的数，显然可以规定其奇偶性，不会影响。
I¶
solved by JLK
题意¶
有\(n\)个数\(A_i\)，每次操作可以自定义一个序列\(B_1,\cdots,B_m(1 \le B_i \le n)\)，可以重复，让每个\(A_{B_i}\)减去\(2^{i-1}\)。求最少需要多少次可以变成全0。
\(1 \le n \le 10^5,1 \le A_i \le 10^9\)
题解¶
实际上和数的个数没有关系，只需要知道每个二进制位是1的数的个数。
设\(c_i\)为\(i\)这一位二进制为1的数的个数。
关键是可以把一个\(2^i\)拆成两个\(2^{i-1}\)。也就是让\(c_i-1,c_{i-1}+2\)。
最后合法的条件是，从高位往低位排列，\(c_i\)是不降的。最少的次数就是\(c_i\)的最大值。
如果采用调整的方法，会比较麻烦，复杂度也不好分析。实际上可以直接枚举这个最大值（也就是\(c_0\)）。这个数值是\(O(n)\)级别的。
为了让序列尽可能合法，从低位往高位枚举，肯定是尽可能贴近这个最大值，直到用完高位。
比较方便的做法就是把所有\(c_i\)都不断+2，直到顶到\(c_{i-1}\)的上界。然后把\(c_{i+1}\)减掉。这样如果出现负数也是合法的，可以调整回去。而如果出现一个\(c_{i}\ge c_{i}\)，就不合法。
由于二进制位数是\(\log n\)，复杂度为\(O(n\log n)\)。
J¶
solved by YZW
题意¶
题解¶
K¶
**upsolved by **
题意¶
题解¶
L¶
upsolved by TYB
题意¶
给出\(n\)个串\(t_i\)，每个串有权值\(w_i\)，定义\(f(S)=\sum_{i=1}^noccur(S,t_i)\times w_i\)，\(occur(S,t_i)\)为\(t_i\)在\(S\)中的出现次数。再给出一个长为\(m\)的串\(S\)，\(q\)次操作，分为两种：把\(S\)的后\(l\)个字符改为\(c\)；询问\(f(S[1,l])\)。以上的串均为数字串。
\(n,\sum|t_i|\le10^5,m,q\le3\times10^5\)
题解¶
考虑没有修改，单次询问怎么做。
建出\(t\)串的AC自动机，在每个字符串结尾节点的位置加上\(w_i\)的权值，求fail的时候加上fail的权值，让\(S\)串在上面跑，记录个前缀和即可。
考虑修改怎么做。用一个栈维护原串，栈中每个元素可用一个五元组\((l,r,o,s,x)\)表示，含义是对应着原串的\([l,r]\)区间，该区间所有字符都是\(o\)，原串从\(1\)开始到\(r\)在自动机上经过节点的权值和为\(s\)，最后到了\(x\)节点。只需要对AC自动机的每个节点倍增预处理出从该节点出发，连续匹配\(2^i\)个数字\(j\)后到达的节点以及路上经过的权值和即可快速维护这个栈的信息，询问的时候在栈上二分即可。可以发现修改与染色操作类似，由均摊分析可知复杂度正确。
记录¶
YZW过J(0:04)，JLK过B(0:09)，TYB过E(0:22)。
YZW写F，马上被JLK叉掉了。TYB写D，JLK和YZW看I。
TYB WA了一次，JLK写I，过了(1:14)。
TYB改D，又WA了两次后AC(1:48)。
YZW写G，WA一次后AC(2:23)。
TYB写C，TLE两次后AC(3:08)。
一起看F和H，TYB猜了个结论过了H(3:41)。
JLK想了个F的做法，但是感觉太复杂，时间不够没写。
后来又看了L，没啥想法。YZW乱搞F没过。
总结¶
TYB：这场的题细节好多……
Dirt¶
C(-2)
D(-3)
G(-1)
H(-1)