2022 China Collegiate Programming Contest (CCPC) Weihai Site¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 29/? | 9 | 9 | 13 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
**upsolved by **
题意¶
题解¶
C¶
solved by YZW
题意¶
题解¶
D¶
solved by JLK
题意¶
简单状压DP，略
题解¶
E¶
solved by TYB
题意¶
题解¶
F¶
solved by TYB
题意¶
题解¶
G¶
solved by YZW
题意¶
题解¶
H¶
**upsolved by **
题意¶
题解¶
I¶
solved by TYB
题意¶
题解¶
J¶
solved by JLK
题意¶
\(n\) 个数 \(a_i\)，\(k\) 个限制，形如 \(a_i=x\) 的数量不超过 \(y\)。
两个人玩游戏，每次选中一个数，使其-1，并且始终要满足限制。
不能操作者输，问谁赢。
\(1 \le n \le 10^5,0 \le k \le 10^5,0 \le x\le 10^9\)
题解¶
可以数轴看成是一个水管，每个数字看做一单位的水，那么数字不断减少就是往下流，并且水管不同部位的宽度不同。但只要没有宽度为 \(0\) 的点，就能一直流下去。
也就是说，终态其实是确定的。总操作步数也是确定的，算出步数就知道谁赢了。
那么可以从小到大枚举 \(a_i\)，看每个数最后在哪里。具体来说，应该找到比 \(a_i\) 小的宽度为 \(0\) 的最大的点 \(j\)，\(a_i\) 最后就会到 \(j\) 的位置上。直接让 \(j\) 的宽度减一，后面不断重复这一步骤即可。
可以用 set、map 等维护。
\(O(n\log n)\)
K¶
solved by YZW
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
M¶
**upsolved by **
题意¶
题解¶
记录¶
TYB过E(0:09)，JLK过A(0:24)，然后一起讨论G，YZW推了一下式子并开始写，WA一次后AC(0:47)。
JLK过J(1:07)。
YZW写C，WA两次后AC(1:48)。
期间JLK和TYB讨论I，不确定贪心的策略。上机后试了一下，过不了样例。
JLK提出一个方法，TYB开始写。
JLK看了D，感觉可做。然后和YZW讨论K，YZW推了一下式子发现可以写。
I TLE一次，JLK帮忙卡常后AC(3:04)。
然后JLK写D，写完没过样例，先换YZW写K。
K WA了一次，JLK调过了D并AC(3:52)。此时TYB会了F。
K又WA了两次，JLK打算写个对拍，没拍出来，但YZW找到了错误并AC(4:24)。
TYB写F，WA一次后AC(4:46)。
总结¶
Dirt¶
C(-2)
F(-1)
G(-1)
I(-1)
K(-3)