炼石计划 11 月 11 日 CSP-S 十连测 #9【补题】 - 比赛 - 梦熊联盟 (mna.wang)
\(100+60+20+15 = 195\)。
复盘
顺序开题。T1 是二分板子。写之前思考好了所有代码细节直接写代码。一遍过了所有大样例。
T2。题意好麻烦。
\(35\) 分是极易的。跳过 \(25\) 分部分分，直接想正解。
有三个变量 \(a, b, c\) 肯定要枚举一个。那当然是先尝试枚举 \(a\)。此时 \(N_1 = N_0 \bmod a = (N^2 + 1) \bmod a\) 确定了，剩下的就比较好做。
中间尝试推了很长时间的式子，都是基于同余的，不知道怎么推到歪成那样的。数学式子变形还要多练。
剩下的是 \((N_1+b) \bmod c = N_3\)。感觉正解不太好做，先尝试 \(35+25=60\) 分吧。
最终化简到了一个形如 \((b + c) \bmod c = k\) 的形式。发现暴力枚举的复杂度是调和级数。直接写！
最终大样例都过了。手造数据 1 1 2000 跑了三秒多，不太妙。将 std::sort 改成桶拍后仅 0.1 秒。放心了。
T3 田忌赛马。我不是孙膑所以我不会。写了阶乘的 \(20\) 分就跑路了。
T4 神迷题。变量很多。顺好题意后发现 我 连 \(n = 2\) 的 15 分 都 不 会。
大悲。我不想在 T4 爆零。于是骗分启动。
最初尝试输出 \(\min a_i\)，但是小数据正确性极低大数据正确性为 \(0\)。遂放弃。
脑中突然闪过一个想法：我可以强制让同一棵珠子每次都减小相同的高度。感觉 \(n = 2\) 的正确概率挺大（我也不知道为什么，只是感觉）。然后就写了。
手造了两组 \(n = 2\) 的样例都正确。我发现这个骗分策略可以不仅局限于 \(n \le 2\)。具体的我写了个 dfs，思路与上面相同，过了 \(n = 3\) 的样例 1。
虽然我只给它测了三组数据，但是我猜测这个程序能拿不少分。至少 \(n = 1\) 的能过吧。
然后写了 T1 + T2 60 的对拍。
赛后发现 T4 的 \(n \le 2\) 全过了，其余的全 T 了。原因是 dfs 复杂度不对。喜+悲。
所以应该是一分没挂？？？
做的好的及不足
-
没有在 T1 的二分细节上浪费时间。
-
T4 猜结论猜中了（虽然这样做一定是错误的但是有分）。
-
T2 推式子时因为正负号错了浪费了很长时间。
知识点
T1：二分。
T2：数学。
题解
T1. 查询
如果没有重复，那么 \(x\) 是序列中的第 \(k\) 小，等价于序列中存在恰好 \(k - 1\) 个数 \(< x\)。
有重复后，如果 \(x\) 是序列中的第 \(k\) 小，那么序列中 \(< x\) 的数的数量应 \(< k\)，且 \(x\) 最大。于是可以二分。
问题转化成求有多少 \((i, j)\) 满足 \(a_j + b_jc_i < mid\)。
枚举 \(j\)。那么 \(c_i < \lceil \frac{mid-a_j}{b_j} \rceil\)。二分即可。
T2. 枚举
\(N\) 没用。可以一步直接求 \(N_0 = N^2 + 1\)。此时：
\[N_1 = N_0 \bmod a \\ N_2 = N_1 + b \\ N_3 = N_2 \bmod c \]注意到当 \(N_3\) 确定时，满足条件的对 \((N_2, c)\) 的数量是调和级数。我们将这些对预处理。
考虑计算答案。枚举 \(a\)，这样就能求出 \(N_1\)。
根据条件二，不难发现如果确定了 \(N_1, N_2\)，那么 \(b\) 是唯一确定的。如果 \(b\) 存在则需要满足 \(0 \le N_2 - N_1 \le P\)。
所以我们可以在预处理的 \((N_2, c)\) 对序列里二分。
看代码理解更好：提交记录 #607099 - 梦熊联盟 (mna.wang)
标签：11,二分,炼石,bmod,T2,T1,枚举,9.8 From： https://www.cnblogs.com/2huk/p/18403191