B题的测试数据似乎没有输出-1的情况？
2019.2 月赛题解
Xiejiadong edited 5 年，8 月前
致歉
A题由于出题人和验题人的疏忽，题面对于 feedback 的 0/1 书写有误，给选手造成不愉快的比赛体验。在此表示抱歉。
前言
这是一场“签到”竞速赛。
采用 ICPC 赛制的好处是，想到什么出什么，完全不用考虑区分度。
采用 ICPC 赛制的好处是，题目想怎么排序怎么排序，完全不用考虑难度。
没想到什么坏处，大概率会继续沿用。
这场月赛。差点摸着摸着就三月了。
| # | Tag | Idea | Developer | Tester |
|---|---|---|---|---|
| A | 构造 几何 | Kilo_5723 | Kilo_5723 | Weaver_zhu |
| B | 抽屉原理 | Kilo_5723 Xiejiadong | Kilo_5723 | ultmaster |
| C | 构造 | Xiejiadong | Xiejiadong | Special Judge |
| D | 数学 | Xiejiadong | Xiejiadong | Weaver_zhu ultmaster |
| E | 二分 拓扑排序 最长路 | Xiejiadong | Xiejiadong | ultmaster Kilo_5723 |
| F | 数学 滑动窗口 | Xiejiadong | Xiejiadong | ultmaster Kilo_5723 |
Problem A
First Solved：applese
如果知道球上两点，就能知道球心在两点连成线段的垂直平分面上。
以 $x$ 轴为例，因为原点在球内，球面和 $x$ 轴的正负半轴（含原点）一定各有一个交点。如果两个交点分别为 ($x_1,0,0$) 和 ($x_2,0,0$)，则球心一定在这两点所成线段的垂直平分面上。因为线段在 $x$ 轴上，所以所得到平面的表达式是 $x=\frac{x_1+x_2}{2}$，相当于确定了球心在 $x$ 轴上的坐标。
因此，只要求出两个交点的中点坐标即可。交点坐标可能含有小数，但是依旧可以通过二分法求出半轴上第一个不在球内，或最后一个在球内的点的坐标。对正负半轴各求一次，根据对称性，所得两点的中点坐标应该与真实交点中点坐标相同，因此可以在约 $2 \times 30=60$ 次操作内确定球心在 $x$ 轴上的坐标。
同样地，可以用此方法求出球心在 $y$ 轴，$z$轴上的坐标，得解。
有一个常见错误是：二分交点从 $10^9$ 开始。虽然 $x,y,z,r \le 10^9$，但交点坐标绝对值可以大于 $10^9$, 值 $\le 2 \times 10^9$。同时，此时的 $\frac{l+r}{2}$ 会在 $l+r$ 时爆 int。
Problem B
First Solved：hangyesheng
设 $a_i$ 是从第 $i$ 位到末位代表的整数，我们发现答案一定可以表达成 $a_i - a_j$ ($i < j$)的形式。
例如，对于 $1249$，$1000=1249-249$，$1200=1249-49$，$240$=$249-9$。因此，问题可以转化为找到一个最小的 $a_i-a_j$，使得 $a_i-a_j \mod m = 0$。
要使 $a_i - a_j \mod m$ 为 $0$，只需要 $a_i \mod m = a_j \mod m$。要使 $a_i-a_j$ 最小，首先需要 $a_i$ 最小，其次让 $a_j$ 最大。但是容易发现，在 $a_i$ 最小的情况下不可能有两个数 $a_j,a_k$ 同时满足条件，否则 $a_j,a_k$ 可以组成一个更小的解。因此，我们只要找到两个最小的 $a_i,a_j$，使其对 $m$ 同余即可。注意，$a_j$ 是可以等于 $0$ 的。
同时，因为抽屉原理，我们最多只要处理 $m+1$ 个 $a_i$ 就能找到答案。
Comments
Xiejiadong：一开始想了一道裸的抽屉原理，甚至还要SPJ，被毙了。
Problem C
First Solved：404 Not Found.
这是一道可以各凭所长过的题目，感觉允许操作次数也挺多的。
提供一种比较暴力的还原的思路：
我们通过针对位置 $(x,y)$ 的几次操作，达到四种交换：
- 仅针对 $(x,y)$ 与 $(x,y+1)$ 的交换（保证其他位置的不变）
- 仅针对 $(x,y)$ 与 $(x+1,y)$ 的交换（保证其他位置的不变）
- 仅针对 $(x+1,y)$ 与 $(x+1,y+1)$ 的交换（保证其他位置的不变）
- 仅针对 $(x,y+1)$ 与 $(x+1,y+1)$ 的交换（保证其他位置的不变）
这四种操作可以用暴力跑出来，当然也可以纯手工推，因为并不需要很多的操作次数，次数太多了也没法满足操作次数的上限。
也就是说，我们只要找到一个数现在在的位置和最终的目标位置，然后用类似于“车站调度”的方式，沿路一次交换即可。
四种交换方式所需要的最少操作次数是不同的，我们可以设计一种比较优秀的走法来减少更多的操作次数。
这题如果有其他好的解法，欢迎在评论区讨论。
Comments
ultmaster：我觉得正常的选手，读完这道题目就溜了。不会想写的。
Problem D
First Solved：dreamoon
签到题。
如果十进制数 $x$ 在 $k$ 进制下末尾恰好有 $m$ 个 $0$ ，显然满足 $x\equiv 0(mod\; k^m)$ 且 $x\not\equiv 0(mod\; k^{m+1})$ 。
而显然 $x\equiv 0(mod\; k^m)$ 包含了 $x\equiv 0(mod\; k^{m+1})$ ，直接就能算出来 $[1,l]$ 的范围内有多少满足要求的数，差分一下即可。
当然它不甘为一道纯粹的签到，所以会计算过程直接 long long 会溢出。要注意处理的一些 tigs ，比如，判断的乘法变除法、加分变减法，均可以避免这个问题。
Comments
Weaver_zhu：用 double 瞎判会不会溢出，结果精度炸了。改成 long double 就过了。
Problem E
First Solved：dreamoon
自从在 AGC06 做了“中位数金字塔”以后就一直想出一道关于中位数的题目，于是这题就出来了。
考虑二分答案，我们需要验证路径最大的中位数是否 $\ge mid$ 。
我们把所有的点权做 $-1/1$ 变换，即 $\ge mid$ 的点权变为 $1$ ，否则变为 $-1$ 。
根据题面路径中位数的定义，我们可以发现，如果这条路径的中位数 $\ge mid$ ，那么做了 $-1/1$ 变换以后，这条路径上的点权和 $\ge 0$ 。
而我们现在需要知道的问题是路径最大的中位数是否 $\ge mid$ ，也就是说，最大的路径点权是否 $\ge 0$ 。
跑一遍最长路就好了。而对于 DAG ，最长路只要 dp 一下，复杂度是保证 $\mathcal{O}(m)$ 。
Problem F
First Solved：applese
我们考虑对方差的式子做变换：
$\sigma ^2m^2$
$=\frac{(a_1-\bar{a})^2+(a_2-\bar{a})^2+\cdots +(a_m-\bar{a})^2}{m}\times m^2$
$=m[(a_1-\bar{a})^2+(a_2-\bar{a})^2+\cdots +(a_m-\bar{a})^2]$
$=m[a_1^2-2a_1\bar{a}+\bar{a}^2+a_2^2-2a_2\bar{a}+\bar{a}^2+\cdots +a_m^2-2a_m\bar{a}+\bar{a}^2]$
$=m[a_1^2+a_2^2+\cdots +a_m^2-2\bar{a}(a_1+a_2+\cdots +a_m)+m\bar{a}^2]$
$=m(a_1^2+a_2^2+\cdots +a_m^2)-2m\bar{a}(a_1+a_2+\cdots +a_m)+m^2\bar{a}^2$
$=m(a_1^2+a_2^2+\cdots +a_m^2)-2m\frac{a_1+a_2+\cdots +a_m}{m}(a_1+a_2+\cdots +a_m)+m^2(\frac{a_1+a_2+\cdots +a_m}{m})^2$
$=m(a_1^2+a_2^2+\cdots +a_m^2)-2(a_1+a_2+\cdots +a_m)^2+(a_1+a_2+\cdots +a_m)^2$
$=m(a_1^2+a_2^2+\cdots +a_m^2)-(a_1+a_2+\cdots +a_m)^2$
显然 $\sigma ^2m^2$ 的结果是整数。
要方差尽可能的小，肯定会选择大小相对变化不大的 $m$ 个数。也就是会选择在排序以后连续的一段数。
那么，我们直接维护连续 $m$ 个数的和以及平方和即可。
考虑到会超过long long的问题，所以数据范围比较小。
而 $a_i$ 的大小并不多，所以排序可以采用桶排序解决。
时间复杂度 $\mathcal{O}(n)$ 。
Comments
Weaver_zhu：这个是概率论的常规题。是不是送了一题啊。
ultmaster：这一眼滑动窗口。
恭喜 applese , dreamoon , SYSU_Zayin 喜提冠亚季军。
Comments
SuperSodaSea
调了两个半小时终于把C题过了……
我看了一下代码，用引用会出错的原因应该是 work1 和 work2 中对 pos[] 的修改影响到了参数吧，const 引用不代表值不会变
SuperSodaSea
比如说
#include <iostream>
int count;
void f1(int x) { std::cout << x << std::endl; ++count; }
void f2(const int& x) { f1(x); f1(x); f1(x); }
int main() { f2(count); }
结果是输出
0
1
2
const 引用只是代表“自己”不能修改它的值，而不是“别人”不能修改它的值
这个 B 好像确实没有 -1 啊。出题人要挨打了。