2019.2 月赛题解

Xiejiadong edited 6 年前

致歉

A题由于出题人和验题人的疏忽，题面对于 feedback 的 0/1 书写有误，给选手造成不愉快的比赛体验。在此表示抱歉。

前言

这是一场“签到”竞速赛。

采用 ICPC 赛制的好处是，想到什么出什么，完全不用考虑区分度。

采用 ICPC 赛制的好处是，题目想怎么排序怎么排序，完全不用考虑难度。

没想到什么坏处，大概率会继续沿用。

这场月赛。差点摸着摸着就三月了。

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\mathrm{mod}m=0$。

要使 $a_i-a_j\mathrm{mod}m$ 为 $0$，只需要 $a_i\mathrm{mod}m=a_j\mathrm{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 }^2{m}^2$
$=\frac{(a_1-\overline{a}{)}^2+(a_2-\overline{a}{)}^2+\cdots +(a_m-\overline{a}{)}^2}{m}\times m^2$
$=m[(a_1-\overline{a}{)}^2+(a_2-\overline{a}{)}^2+\cdots +(a_m-\overline{a}{)}^2]$
$=m[a_1^2-2a_1\overline{a}+{\overline{a}}^2+a_2^2-2a_2\overline{a}+{\overline{a}}^2+\cdots +a_m^2-2a_m\overline{a}+{\overline{a}}^2]$
$=m[a_1^2+a_2^2+\cdots +a_m^2-2\overline{a}(a_1+a_2+\cdots +a_m)+m{\overline{a}}^2]$
$=m(a_1^2+a_2^2+\cdots +a_m^2)-2m\overline{a}(a_1+a_2+\cdots +a_m)+m^2{\overline{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 }^2{m}^2$ 的结果是整数。

要方差尽可能的小，肯定会选择大小相对变化不大的 $m$ 个数。也就是会选择在排序以后连续的一段数。

那么，我们直接维护连续 $m$ 个数的和以及平方和即可。

考虑到会超过long long的问题，所以数据范围比较小。

而 $a_i$ 的大小并不多，所以排序可以采用桶排序解决。

时间复杂度 $\mathcal{O}(n)$ 。

Comments

Weaver_zhu：这个是概率论的常规题。是不是送了一题啊。

ultmaster：这一眼滑动窗口。

恭喜 applese , dreamoon , SYSU_Zayin 喜提冠亚季军。

Comments

xtu-天涯

6 年前

标程在哪呀QWQ

回复 1 0

Xiejiadong

6 年前

AC那道题目以后可以看到所有的提交代码。std不直接公开的。

回复 0 0

SuperSodaSea

6 年前

B题的测试数据似乎没有输出-1的情况？

回复 1 0

Xiejiadong

6 年前

这个 B 好像确实没有 -1 啊。出题人要挨打了。

回复 0 0

applese

6 年前

话说我A题是看完题完全没看0/1表示啥默认1是在里面了，然后等你们发了announcement我才知道原来刚开始写的是反的，233333

回复 1 0

Xiejiadong

6 年前

验题人也没发现。过了好多人也没说啥。以为就相安无事了。

回复 0 0

applese

6 年前

我B好像忘判-1了，也过了……

回复 0 0

applese

6 年前

我记得是过了好久都看到榜上只有我一个A……我还在懵逼……

回复 0 0

Xiejiadong

6 年前

直到 dreamoon 发了 question 一查才发现。

回复 0 0

zzudyl

6 年前

a题的输入输出怎么理解

回复 0 0

Xiejiadong

6 年前

题面里叙述了交互的方式。

回复 0 0

despacito

6 年前

方差这道题为啥复杂度是O(n)?难道可以不用排序的吗？

回复 0 0

Xiejiadong

6 年前

因为 $a_i$ 的范围很小，所以可以采用桶排序。已在题解中补充。

回复 0 0

BanFcc

6 年前

E题的图保证联通怎么理解啊。。。

回复 0 0

Xiejiadong

6 年前

保证是一张 $n$ 个点的联通图

回复 0 0

BanFcc

6 年前

可是这不是个DAG吗

回复 0 0

Xiejiadong

6 年前

但数据随机乱造可能会出现两个DAG的情况吧。

只是为了避免不必要的问题，所以做了申明。

回复 0 0

MAOoo

6 年前

C题为啥都没人写。。比赛11发有10发是我贡献的（然而都是re）

回复 0 0

Xiejiadong

6 年前

这个RE，吓得我以为出锅了......

回复 0 0

MAOoo

6 年前

我这调着调着发现把函数参数的const引用改成普通的就ac了，大佬能教教原因么。。

回复 0 0

SuperSodaSea

6 年前

调了两个半小时终于把C题过了……
我看了一下代码，用引用会出错的原因应该是 work1 和 work2 中对 pos[] 的修改影响到了参数吧，const 引用不代表值不会变

回复 0 0

MAOoo

6 年前

大佬能教教const引用数值变化的具体原理么。。还有就是我把work函数写成普通，调用work12的函数继续用const引用依然re了。。

回复 0 0

SuperSodaSea

6 年前

比如说

#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 引用只是代表“自己”不能修改它的值，而不是“别人”不能修改它的值

0 0

MAOoo

6 年前

我懂了，我传进去的是pair的两个元素但是函数的实质修改了这个pair

回复 0 0

applese

6 年前

太难写了，然后觉得自己搞的还是错的，就没管了

回复 0 0