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

From EOJ Wiki
Jump to navigation Jump to search
 
(5 intermediate revisions by 2 users 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)$。
 +
 +
我们发现,第二种路径可以拆成两条第一种路径,因此维护每个节点向上的第一种路径,并统计在此节点交汇的所有第二种路径的贡献,用启发式合并维护。
  
 
== Problem K ==
 
== Problem K ==
Line 157: 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$ 是否联通即可。