社区讨论

Snakes Round #2 得分情况与题解

SSnakes
学术版参与者 22已保存回复 42

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
42 条
当前快照
1 份
快照标识符
@mi6m0l6e
此快照首次捕获于
2025/11/20 07:04
4 个月前
此快照最后确认于
2025/11/20 07:30
4 个月前
查看原帖
本次比赛在洛谷举办。

得分情况与统计

总分最高分：288
第一题最高分：100
第二题最高分：100
第三题最高分：88
250以上人数：19
200以上人数：28
100以上人数：87
报名人数：1.1K
提交人数：305

Changing

算法一

我会随机！
由于我忘了设置多组数据，期望得分00至100100。

算法二

我会模拟！
复杂度O(t2)O(t^2)，期望得分6060。
但是很多人忘记题目给出的是环形……

算法三

我会正解！
实际上是数学题，显然时刻tt第kk盏灯的状态为
(∑i=0tCtia(k+i−1) mod n+1) mod 2\left(\sum_{i=0}^t C_t^ia_{(k+i-1) \bmod n+1}\right) \bmod 2
求和即可。复杂度O(t)O(t)，期望得分100100。

Calculating

算法一

我会推公式！
将ff分解质因数得到f=p1k1p2k2..pjajf=p_1^{k_1}p_2^{k_2}..p_j^{a_j}，则题目实际上要求：
ans=∑f=lr∏i=1jpiai+1ans=\sum_{f=l}^r\prod_{i=1}^j p_i^{a_i+1}
记ff因数个数为d(f)d(f)，则由排列组合可得：
∏i=1jpiai+1=d(f)\prod_{i=1}^j p_i^{a_i+1}=d(f)
则原式化为：
ans=∑f=lrd(f)ans=\sum_{f=l}^rd(f)
暴力统计答案。时间复杂度O(r2)O(r^2)，期望得分4040。

算法二

我会拆询问！
实际上，我们有：
ans=∑i=1rd(i)−∑j=1l−1d(j)ans=\sum_{i=1}^rd(i)-\sum_{j=1}^{l-1}d(j)
考虑如何求∑i=1rd(i)\sum_{i=1}^rd(i)，对于[1,r][1,r]的整数kk，kk作为因数在[1,r][1,r]中出现了⌊rk⌋\left\lfloor \frac rk \right\rfloor次，显然对答案的贡献为⌊rk⌋\left\lfloor \frac rk \right\rfloor。
则：
ans=∑i=1r⌊ri⌋−∑j=1l−1⌊l−1j⌋ans=\sum_{i=1}^r\left\lfloor \frac ri \right\rfloor-\sum_{j=1}^{l-1}\left\lfloor \frac {l-1}j \right\rfloor
枚举kk，统计答案。时间复杂度O(2r)O(2r)，期望得分6060到7070之间。

算法三

我会分块！
注意到⌊rk⌋\left\lfloor \frac rk \right\rfloor最多有2r2\sqrt r种取值，我们对其分类统计答案即可。做法类似没有莫比乌斯函数的莫比乌斯反演。
时间复杂度O(4r)O(4\sqrt r)，可通过全部测试点。
**PS:**至于为什么会有100100个测试点……这是个好问题。

Coloring

算法一

我会随机！
没试过，期望得分4040以下。

算法二

我会骗分！
按从左往右，从上往下的顺序依次填颜色，期望得分6060。

算法三

我会贪心！
手玩几个例子不难发现把相同颜色的放在一起更优。每次填颜色，贪心找一块在边界且尽可能大的位置，放下该颜色的所有格子。期望得分7070至9090。

算法四

我会搜索！
搜索时间复杂度O(cnm)O(c^{nm})，超时无疑。
嘿嘿嘿。

算法五

我会物理！
哦豁？搜索其实很靠近正解，但是时间太慢。我们考虑模拟退火。
每次操作交换两个在联通块边界的格子，计算答案是否更优，按概率更新。

算法六

等等……为啥会是9090？
因为你可能会陷入局部最优解。
多随机几次就好了。
时间复杂度O(O(跑得过))，期望得分100100。

回复

共 42 条回复，欢迎继续交流。

正在加载回复...