2025 年 6 月日祭
2025.6.2 问我怎么挂的
今天做题。
[洛谷 P2833] 等式 & [SGU 106] The equation
板子题啊，可是改了好久。主要死在向下、向上取整时没用
double（因为有负数）。[SPOJ NWERC11A] Binomial coefficients
这道题自己想到了枚举
，二分 ，也想到了会爆 long long，可是没想到枚举。对于
，进行二分；对于 ，枚举即可。 做的时候因为各种小问题挂了
发。 -
挺简单的呀。问我怎么挂的，其实是把
写成 了。还有另外一些小错。（比如步长写错了，还有负数导致的一些奇怪的问题。） 枚举
与每一对人，解 即可。 -
没想到是打表题。打表发现满足要求的九位数有
个，十位数自然就有 个。（原有基础上在开头加一个数。）十位数以上，每多一位，答案自然就 。九位数以下答案为 。
2025.6.3
-
神秘结论题。设
。模拟一个倒推的过程，容易发现，当且仅当 时有解，其中 是奇数， 是整数。若有解，模拟即可。
2025.6.27
也是莫名其妙断更了一个月。
也是终于把别样的 whk 草过去了。
今天补日祭。
欧拉函数、欧拉定理与线性筛专题
- 欧拉函数
- 欧拉定理
- 满足
的数的个数 满足 的个数 。
利用以上结论即可完成：
[Codeforces 1149D] Abandoning Roads
CF 3000* 远古题，洛谷黑，所以也算是首黑吗。
这题复杂度鬼能想出来。
首先先把重边断掉，这样就会形成若干个连通块。将这些连通块“缩点”之后，用 dij 做新图的最小生成树即可。具体地，设
表示当前在第 个点，已经到达的连通块为 的最短路径。显然每个连通块只会被访问一次，所以复杂度是 的。注意到当一个连通块的大小 时，若先离开这个连通块再回到这个连通块，至少要经过 条重边，而走连通块内部只需要最多 条轻边，所以显然不需要考虑这个连通块，因为跑 dij 的时候显然会选择走连通块内部而不会重复经过。那么连通块数量被优化到了 ，时间复杂度 。
2025.6.30
今日歌曲：Down Bad
昨天终于也是稳 1= 了。
今天补题。
[Atcoder ARC180D] Division into 3
很久之前一场模拟赛的题了。
一件显然的事情，就是一个区间的最大值
一定会做出贡献。若 放在第二段，那么当第一段与第三段的长度为 时可以取到最小值，用 ST 表维护即可。若 放在第一段，那么当第二段长度为 可以取到最小值。设 ，那么答案即为 。将询问离线再用单调栈与线段树维护 即可。若 放在第三段，则与放在第一段类似。 -
这道题显然是之前记过的，今天终于补了。
- Title: 2025 年 6 月日祭
- Author: Getaway_Car
- Created at : 2025-06-01 00:00:00
- Updated at : 2026-01-28 14:42:59
- Link: https://getawaycar1024.github.io/article/diary/2025/06/
- License: This work is licensed under CC BY-NC-SA 4.0.