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)