2019.2 月赛题解

Xiejiadong edited 1 年,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)$ 的几次操作,达到四种交换:

这四种操作可以用暴力跑出来,当然也可以纯手工推,因为并不需要很多的操作次数,次数太多了也没法满足操作次数的上限。

也就是说,我们只要找到一个数现在在的位置和最终的目标位置,然后用类似于“车站调度”的方式,沿路一次交换即可。

四种交换方式所需要的最少操作次数是不同的,我们可以设计一种比较优秀的走法来减少更多的操作次数。

这题如果有其他好的解法,欢迎在评论区讨论。

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

xtu-天涯

标程在哪呀QWQ

Xiejiadong

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

SuperSodaSea

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

Xiejiadong

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

applese

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

Xiejiadong

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

applese

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

applese

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

Xiejiadong

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

zzudyl

a题的输入输出怎么理解

Xiejiadong

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

despacito

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

Xiejiadong

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

BanFcc

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

Xiejiadong

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

BanFcc

可是这不是个DAG吗

Xiejiadong

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

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

MAOooo

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

Xiejiadong

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

MAOooo

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

SuperSodaSea

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

MAOooo

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

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

MAOooo

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

applese

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

你当前正在回复 博客/题目
存在问题!