Rank
A. 花间叔祖
签到题,但没切。
一眼出思路找最大公因数,过了大样例发现同余的情况也合法,然后开始优化,成功从 68pts 到了 88 pts。
考虑正解,首先答案不是一就是二。若答案是一,即所有数可在模某数 \(x\) 意义下同余。不妨将每个数化成 \(a_i=k\times x+d\) 的形式,则若存在一个 \(x\) 使得所有的 \(d\) 都相等,那么有 \(a_i-a_j=\left(k_i-k_j\right)\times x\),所以我们对排序后的差值进行求 gcd,复杂度为 \(\mathcal{O(n)}\)。
B. 合并r
有趣的题面,但题比较 ex。
看到题就开始想部分分了,首先对于 \(n=1\),显然 \(k\) 只能为 \(1\),那么答案也是 \(1\)。
对于 \(k=1\),赛时由于 \(n==5\) 的情况手模错了导致推出了假结论,恼。
正解是 dp。设 \(f_{i,j}\) 为共 \(i\) 个数和为 \(j\) 的方案数,显然加入一个 \(1\),即 \(f_{i-1,j-1}\) 可对答案产生贡献。
其次,由于 \(j\) 是由若干个 \(\frac{1}{2^i}\) 加和得到的,那么显然 \(\frac{j}{2}\) 可以由若干个 $$\frac{1}{2^{i+1}} 得到,因此第二个状态转移方程为 \(f_{i,j}+=f_{i,2\times j}\)。
注意边界问题,\(f_{0,0}=1\)。
C. 回收波特
很大方啊,给了 60pts 的暴力分。
首先看到 Subtask1 中 \(n\times m\le 10^8\),显然想让你用 \(\mathcal{O(nm)}\) 的做法解,最无脑的一个,每次操作枚举每个没有到达终点的波特,记录位置最后输出答案即可。
Subtask2 中给了 \(x_i\le 10^3\)。思考一下,\(3\times 10^5\) 的波特只出现在这 \(1000\) 个位置,显然可以把每个波特映射到初始位置上,按每个位置求解,复杂度为 \(\mathcal{O(x_{max}m)}\),时限两秒,可过。
正解提供了一个很厉害的思路:对于某一时刻,若两个波特的坐标关于原点对称,那么之后的所有移动二者都是对称的。
我们每次只维护一段符号相同的区间 \(\left[l,r\right]\) 的情况。
若在执行当前操作后符号不完全相同了,则利用上面的对称性,将符号不同的两边中元素数量较少的一边删去。
最后 dfs 一遍推出被扔掉的点的信息。
D. 斗篷
正解差分+扫描线。
题意倒很简单,关键是如何维护信息。
标签:10,CSP,frac,集训,times,答案,mathcal,波特,模拟 From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18320835