第 13 届山东省 icpc 省赛 vp
总结:
2024 / 4 / 4
赛时:7 / 12:A B D G I J L
https://codeforces.com/gym/104417
最近开始康复训练,和昊哥 vp 了一场省赛。
前期签到蛮顺利,基本 1个多小时就出了 5 题,然后卡在了 E,后面 B 的实现也弄了蛮久,好在过了 J 题,vp 在省内应该是可以排到前 30 左右。
SUA 出的题很有区分度,出的很好!!
值得总结的题:
E:
-
赛时发现了先坐操作 \(1\),然后在做操作 \(2\) 显然是抵消的,所以最优操作必然是先不停的除 \(k\),然后再用操作 \(1\)。
-
然后后面昊哥发现了两个操作可以看成在 \(k\) 进制下的操作,每次相当于左移一位然后可以任意添加某个数到末尾位,或者直接右移,除掉一位。
-
后面卡在了如何判断一个 \(x\) 通过若干次操作 \(1\) 弄成 \(m\) 的倍数,钻进了如何精确知道某个 \(m\) 的倍数的思维定式,其实我们不难发现操作 \(1\) 形成的数是有范围的:\([nk^p,nk^p+k^p-1]\),故我们只要看是否存在一个 \(m\) 的倍数落在这个区间,就变成了一个简单的问题,只要看第一个大于等于 \(nk^p\) 的 \(m\) 的倍数是否在超过右边界即可。
-
不难发现这样一直做操作 \(1\) 必然会有解的,当这个值域区间范围长度超过了 \(m\),那么必然存在一个 \(m\) 的倍数。
-
所以只要暴力枚举操作 \(2\) 然后暴力做操作 \(1\) 即可,这里可以考虑 \(nk^p\mod m\) 的值,还差多少到 \(0\),然后就可以看看这个区间长度是否够,这样就可以判断了,否则实现起来可能要
__int128
。
B:
- 自己的反思,赛时是昊哥做的,赛时我没想到怎么实现,后面下来补了一下。
- 不难发现我们其实要考虑能接就接任务,对于某一种类的人的需求数量,我们肯定贪心的做要求少的先,然后尽可能获得奖励人员,再去做,这里就可以用堆来维护,然后观察到我们每完成一个任务,然后我们下一次只要在检查该任务带来奖励的人员种类即可,因为其它种类的人员数量不变,显然不会导致能够继承新的任务,只有可能是我某一项人变多了满足了某一个任务才可以,想到这里就很关键了,这样复杂度就是对的。
- 故我们只要弄个哈希表套堆,然后每次把完成的任务弄进队列,然后下一次检查奖励的种类,以此进行,最后答案就是出队次数。
L:
- 赛时和昊哥快速讨论出了思路,我们给出了每次就相当于从一个 \(1\times 1\) 的放个往外扩展,每次的 \(L\) 形就只有 \(4\) 种摆放,只要有一种可以摆就按此摆放,由于给出的是一个正方形,我们必然可以通过 \(n-1\) 次扩展完成构造。
D:
- 很快发现可以二分答案,然后检查 \(k\) 这个答案行不行,然后我列出了式子和昊哥讨论了一下,很快就发现了两侧分别按照 \(v+w-k\) 和 \(w\) 排序,贪心按照大对应大搞一下即可。
G:
- 我很快发现 \(i-j=a_i-a_j\iff i-a_i=j-a_j\)
- 然后可以把这个式子一样值的分在一组,那么显然贪心每次选组内最大的两个连边即可。
J:
- 比较 trick 的题,对于二进制问题,不难想到高位到低位贪心,我们只要枚举到底答案在哪一位比 \(V\) 大即可,相当于枚举二进制公共前缀,然后每次做一次连通性,把所有有这个这个公共前缀的边权的变弄进来,那么显然在一个连通块的任意两个点 \(u,v\) 都存在满足条件的路径。
- 所以思路就是弄 \(60\) 个并查集搞一下完事了,最后别忘了检查 \(=V\) 的情况。