2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 35/3185 | 8 | 8 | 13 |
1001¶
solved by JLK
题意¶
签到，略
题解¶
1002¶
solved by YZW
题意¶
题解¶
1003¶
upsolved by
题意¶
题解¶
1004¶
upsolved by
题意¶
题解¶
1005¶
upsolved by
题意¶
题解¶
1006¶
solved by YZW
题意¶
题解¶
1007¶
solved by YZW
题意¶
题解¶
1008¶
solved by JLK&TYB
题意¶
定义\(v(l,r)=\max\limits_{l \le i \lt j \le r} \gcd(a_i,a_j)\)。给定一个\(n\)的排列，对于每个\(x\in [1,n]\)，求出\(v(l,r)=x\)的\((l,r)\)对数。
\(2 \le n \le 10^5\)
题解¶
考虑一个点对的贡献。对于\(l \le i \lt j \le r\)，一定有\(v(l,r)\ge\gcd(a_i,a_j)\)。而对所有\(\gcd(a_i,a_j)\)取\(\max\)就是\(v(l,r)\)。可以枚举一个数，然后看它的所有倍数，那么所有倍数里相邻的点对就有可能对包含它的区间产生贡献。假设\(x\)的两个位置相邻的倍数为\(a_p,a_q\)。那么可以把这个贡献挂在\(q\)上，相当于一个二元组\((p,x)\)。
枚举右端点\(r\)，对于每个左端点\(l\)，在我们上述处理之后，就相当于是对挂在\([1,r]\)的左右二元组，求出\(l \le p\)的\(\max(x)\)。对于所有把\(v(l,r)\)变成了区间取\(\max\)。
每个点对对不同左端点的贡献相当于一个单调栈，\(v(l,r)\)是随着左端点减小而单调不减的。如果暴力维护的话，可以每次重构单调栈，然后枚举左端点算每个\(v(l,r)\)。
先不考虑单调栈的维护，只考虑对答案的计算，那么单调栈实际上是把整个序列的贡献分成了若干段，而这些段并不是每次都改变的。可以记录一下每个二元组出现的时刻（即右端点），在被删除或者被覆盖一部分的时候通过现在的时刻，统计出这一段的贡献。
而单调栈的维护可以用一个set，每次删除的二元组一定是之前加入的，总共加入和删除的次数和总二元组次数同级。
\(O(n\log^2 n)\)
1009¶
upsolved by TYB
题意¶
签到
题解¶
略
1010¶
upsolved by
题意¶
题解¶
1011¶
solved by JLK
题意¶
打砖块大原题，好像没啥可写的。
题解¶
1012¶
solved by YZW
题意¶
题解¶
1013¶
upsolved by
题意¶
题解¶
记录¶
JLK签1001(0:06)，TYB签1009(0:12)。
YZW做1012，WA一次后AC(0:40)。
JLK和TYB讨论1006，MLE了一次，又改做法，但是尝试很久没有特别好的做法。
期间YZW过了1002(1:10)，1007(1:52,WA一次)。
然后YZW又过来把1006过了(2:30)。
JLK写1011，没处理好WA了两发后AC(3:20)。
然后TYB写1008。JLK和YZW看剩下几题，但都没什么思路。
还剩1h的时候YZW去1012抄板子。TYB遇到了做法上的问题，JLK修了，但是TYB不太会写，JLK接盘。
快结束的时候写完了1012和1008，但是一直交不上去。最后1008 AC(4:57)，1012 RE。
总结¶
JLK：HDU OJ好烂啊
Dirt¶
F(-1)
G(-1)
K(-2)
L(-1)