Difference between revisions of "2019 ICPC China Xi'an Invitational Programming Contest"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 30: Line 30:
  
 
*C 题 出 题 人 签 到 大 失 败(大嘘)。
 
*C 题 出 题 人 签 到 大 失 败(大嘘)。
 
*C 题样例锅了导致榜上一直没人交,也就产生了很多“本来能一血”的假象。实际上在队友告诉我 C 过了一片(看错题号)之后写完没过样例,手算了一遍感觉肯定是题目锅了之后,差点直接交一发等 rejudge(抢一血),后来冷静一下求稳放弃了。不过这时候榜上已经有一发 WA 的了,可能人家不仅开得准、写得快,而且自信又果断,比不了。
 
  
 
*L 题为了求稳暴力反复检查了好多次,浪费了一些时间(明明平时我最莽)。深刻意识到了现场交题时不可能像平时一样放松。
 
*L 题为了求稳暴力反复检查了好多次,浪费了一些时间(明明平时我最莽)。深刻意识到了现场交题时不可能像平时一样放松。
Line 137: Line 135:
 
题意:给定一棵有 $n$ 个节点的树,求这棵树上每条路径上,边权异或和为 $0$ 的子路径的数量和。
 
题意:给定一棵有 $n$ 个节点的树,求这棵树上每条路径上,边权异或和为 $0$ 的子路径的数量和。
  
题解:定义 $dep(u)$ 是 $u$ 的深度 (根节点深度为 $0$),$son(u)$ 是以 $u$ 为根的子树中的节点数,$E(u,v)$ 为 $u$ 到 $v$ 的路径,$F(u,v)$ 是 $u$ 到 $v$ 的路径的边权异或和。
+
题解:定义 $dep(u)$ 是 $u$ 的深度(根节点深度为 $0$),$son(u)$ 是以 $u$ 为根的子树中的节点数,$E(u,v)$ 为 $u$ 到 $v$ 的路径,$F(u,v)$ 是 $u$ 到 $v$ 的路径的边权异或和。
  
 
我们可以按 $u,v$ 的位置关系将所有 $F(u,v)=0$ 分类:如果 $u$ 是 $v$ 的祖先,这条路径对答案的贡献是 $(n-son(w)) \times son(v)$,其中 $w$ 是 $v$ 到 $u$ 路径上除 $u$ 之外深度最深的节点。否则,这条路径对答案的贡献是 $son(u) \times son(v)$。
 
我们可以按 $u,v$ 的位置关系将所有 $F(u,v)=0$ 分类:如果 $u$ 是 $v$ 的祖先,这条路径对答案的贡献是 $(n-son(w)) \times son(v)$,其中 $w$ 是 $v$ 到 $u$ 路径上除 $u$ 之外深度最深的节点。否则,这条路径对答案的贡献是 $son(u) \times son(v)$。
Line 159: Line 157:
 
Solved by Xiejiadong. 00:50 (+)
 
Solved by Xiejiadong. 00:50 (+)
  
题意:可以给一个飞船升级,每次升级花费 $c$ ,可以通过的路径长度 $+d$ ,可以通过的边总数 $+e$ 。求最小的花费,能从 $1$ 到 $n$ 。
+
题意:可以给一个飞船升级,每次升级花费 $c$ ,可以通过的路径长度 $+\;d$ ,可以通过的边总数 $+\;e$ 。求最小的花费,能从 $1$ 到 $n$ 。
  
 
题解:二分最小的升级次数。
 
题解:二分最小的升级次数。

Latest revision as of 07:05, 13 August 2019

Replay

Xiejiadong:

  • 主办方为了增加收入(?),现场座位挤在一起。
  • 四点求面积这种题目都能锅,提前预感到了正赛锅会比较大。
  • 果然正赛连样例都能锅。
  • 题面表述乱七八糟,全靠连蒙带猜得知题意。
  • H 题题面表述不清,大概程序有一个坑点,正准备再交的时候,上一发显示 correct 。
  • 听说 E 题连 $O(nq)$ 的暴力都能过,出题人造树的数据连个链都没有,怕是用脚造的数据。
  • 评测队列积压严重。甚至 $5$ min 才能出结果。
  • 打印效率奇低,甚至送过来的还是一部分代码。
  • $0$ min 过签到都没抢到一血,看来都提早开题了。
  • 比赛打到 12 点的时候就开始犯困了,想来想去都是 GCJ 的锅。

Kilo_5723:

  • 空调坏了,赛场热的(哔—)。
  • 两道出锅的题目都是我写的,差点心态崩 twice 。
  • C 题 出 题 人 签 到 大 失 败(大嘘)。
  • L 题为了求稳暴力反复检查了好多次,浪费了一些时间(明明平时我最莽)。深刻意识到了现场交题时不可能像平时一样放松。
  • 最后一道空间树 + 三维并查集,空间树用了很愚蠢的写法导致三维并查集没调完。感觉这场的锅全都是我背,瑟瑟发抖。

Weaver_zhu:

  • 热身赛终于给 python 的 eval() 一个大秀的机会
  • 上完厕所回来会感觉机房的门相当于一个巨型暖气
  • 出题人计算几何有问题
  • 有一题看了下队友刚交上去的代码,发现有个细节假了。结果还没出来就建议直接改了再交,结果竟然过了。
  • 上来直接推了 B 的式子,结果到结束也没能开始写代码
  • I 题一直以为自己的方法很完美,也不难写,也测了很多数据。结束前还没出来时背后出了好多汗,锅坐实了。
  • 以后前一天晚上得多睡一会,以及最后一小时大概率是要有取舍的。

Problem A

Solved by Xiejiadong. 00:00 (+)

贪心。签到。

0min 过题成就 get 。

Problem B

Upsolved by Weaver_zhu.

题意:求 $\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{n}\prod\limits_{k=1}^{n}m^{gcd(i,j)}[k | gcd(i,j)]$ 。

随便化一化式子就出来了,不过常数很紧。

题解:用欧拉降幂转化为求和 $=\sum\limits_{k=1}^{n}kd(k)\sum\limits_{i=1}^{n/k}\sum\limits_{j=1}^{n/k}[gcd(i,j)==1]$ 相当于枚举 $gcd(i,j)=k$ 。

注意到 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[gcd(i,j)==1]=2\sum\phi(i)-1$ 直接用通用莫比乌斯反演会反演显然超时,这样考虑基数就能用杜教筛了。

线性筛预处理前 $10^7$ 的 $d(i), \phi(i)$ ,大的 $id(i)$ 可以用交换循环顺序+数论分块求。

Problem C

Solved by Kilo_5723. 01:33 (+)

题意:给定一个圆,圆之外中心高度以下的部分不能被经过,圆内部也不能被经过,求圆上最低点到圆外中心高度之上任意一点的最短路。

题解:先把原点放到圆心,再把终点 $x$ 坐标变成绝对值。$\frac {1}{4} \pi r$ 的路径是必走的,然后如果 $x>r$,从 $(r,0)$ 直线走过去就可以了,如果 $x<r$,算一下要走过的弧度,再求之后的直线距离即可。

Problem D

Solved by Weaver_zhu. 01:30 (+)

题意:将军战力有战力点数全部分成两边,有不能再同一边的两两的将军关系,求一种分配使得两边分差最小。

题解:肯定在哪里做到过。二分图染色,然后把小的那一堆两边加上,大的减小的值是一个新的物品,然后就是裸的背包。

Problem E

Solved by Xiejiadong. 04:29 (+1)

题意:支持树上某一点到根路径上所有点 and 一个值, or 一个值,链上做 nim 游戏。

题解:显然 nim 游戏就是求个异或。

常规操作,拆位。

and 一个值和 or 一个值,转换一下就是链上所有的数置 $0/1$ ,线段树维护就好了。

树上的链处理,树链剖分一下。

(模版没有,自己发明,初始化锅了,好久才发现。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Upsolved by Weaver_zhu. (-4)

题意:给定数列 $a^{k},....,a^{k+n-1} (\mod p)$ 和 $n$ 其中 $1 \le a_i \le 10^5$ ,求是否有唯一的 $a,p \le 10^{10}$ 。

题解:等比数列显然是不唯一的,周期出现但是不包含 $1$ 显然是不存在的。

$n \le 2$ 显然是不唯一的。剩下的非等比数列一定存在 $a[i]^2 \not = a[i-1]a[i+1]$ 然后发现 $p | abs(a[i-1]a[i+1]-a[i]^2)$ 枚举素因数就能求 $p$ 了,然后一个一个验证。

注意会爆 long long , exBSGS 判 $k$ 是否存在也要改成快速乘。

Problem J

Solved by Kilo_5723. 02:28 (+)

题意:给定一棵有 $n$ 个节点的树,求这棵树上每条路径上,边权异或和为 $0$ 的子路径的数量和。

题解:定义 $dep(u)$ 是 $u$ 的深度(根节点深度为 $0$),$son(u)$ 是以 $u$ 为根的子树中的节点数,$E(u,v)$ 为 $u$ 到 $v$ 的路径,$F(u,v)$ 是 $u$ 到 $v$ 的路径的边权异或和。

我们可以按 $u,v$ 的位置关系将所有 $F(u,v)=0$ 分类:如果 $u$ 是 $v$ 的祖先,这条路径对答案的贡献是 $(n-son(w)) \times son(v)$,其中 $w$ 是 $v$ 到 $u$ 路径上除 $u$ 之外深度最深的节点。否则,这条路径对答案的贡献是 $son(u) \times son(v)$。

我们发现,第二种路径可以拆成两条第一种路径,因此维护每个节点向上的第一种路径,并统计在此节点交汇的所有第二种路径的贡献,用启发式合并维护。

Problem K

Unsolved.

Problem L

Solved by Kilo_5723. 00:36 (+)

题意:给定一个长度为 $n$,每个元素均不同的序列,可以将偶数位和前面的奇数位互换,可以将前一半和后一半互换(如果有中间元素,中间元素不变),问可以从初始序列达到多少个不同的序列。

题解:找规律。对 $n=1,3$ 的情况特判,剩下的情况里 $n \%4=0$ 时答案是 $4$,$1$ 时是 $2n$,$2$ 时是 $n$,$3$ 时是 $12$。

Problem M

Solved by Xiejiadong. 00:50 (+)

题意:可以给一个飞船升级,每次升级花费 $c$ ,可以通过的路径长度 $+\;d$ ,可以通过的边总数 $+\;e$ 。求最小的花费,能从 $1$ 到 $n$ 。

题解:二分最小的升级次数。

验证的时候从 $1$ 开始 BFS ,所有能够拓展的边全部拓展,显然 BFS 先到的满足了通过边数最小的要求,可以拓展的边满足了可以通过的路径长度要求。

判断此时 $1$ 到 $n$ 是否联通即可。