Difference between revisions of "2019 ICPC Xuzhou Onsite"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "== Replay == Xiejiadong: * 垃圾键盘,无数次 想打 “\n” 直接回车就下去了。 * 热身赛感觉是办给主办方的。开始时间延迟将近一小时,...")
 
 
(14 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
Xiejiadong:
 
Xiejiadong:
  
* 垃圾键盘,无数次 想打 “\n” 直接回车就下去了。
+
* 银川以后整个队伍就有一种任务达成的迹象。整个训练的状态极差。
* 热身赛感觉是办给主办方的。开始时间延迟将近一小时,结束时间却没有变动。
+
* 开局前半小时甚至提交都没有。第一发提交 A 还 wa 了,第二发提交 A 又 wa 了,而且此时 Kilo 和 Weaver 在 A 和 C 疯狂交互上机,手里握着一个 F ,感觉这把要打 Cu 滚回去了。
* 这个比赛不论是 “Ningxia Competition Area” 还是 “Ningxia Railway Station” 抑或是 “44rd” 或者 “IUPC” 从里到外、从上到下都透露着一股神秘的气息。
+
* 可喜的是,前期三题过去以后,基本都是 1A 到了中后场,算是挽救了一把。
* 从网络赛开始的各个环节,没有一个环节是好的。幸运的是,正赛没有出现任何大问题。
+
* 总算做到了一道纯字符串题。
* 主办方人手赠送一份中宁枸杞作为伴手礼好评。
+
* 左手东华,右手上大,上海三连坐。
* 宾馆和比赛场地不是一般的近,第一次体会到了比赛当日八点起床的爽感。
+
* 完成了 “不丢脸” 的小目标。
* 十分感谢 qls 和其他技术负责人连夜检查题目、导入题目。保证了比赛的正常进行。
+
* 恭喜蔡队出线。
* 整个宁夏的承办方、志愿者都是尽心尽力在维护比赛的正常进行。
 
* 算是比较顺畅的一场比赛。
 
* 最后一个小时还是一如往常的在压抑中进行, Weaver_zhu 还是一如往常的在最后 10min 带来了 surprise .
 
* 去年 “徐州+桂林” 的时候,F0RE1GNERS 在徐州 rank3 出线;今年 “厦门+银川” 我们也拿到了 rank3 ,希望剧本重演。
 
* 静等圣诞节开奖。
 
  
 
Kilo_5723:
 
Kilo_5723:
  
* 想说的都被说了。
+
* 做了一道只有自己没见过的原题。
* 最后一个小时临危受命去搞 L,和 D 互抢机时,最后还是没搞出来。结束后一看代码发现一个地方变量名写错了,等重现赛出了看看是不是赛后 5 min 补题。
 
* 一起等圣诞节开奖。
 
  
 
Weaver_zhu:
 
Weaver_zhu:
Line 27: Line 20:
  
 
Solved by Kilo_5723. 00:55 (+2)
 
Solved by Kilo_5723. 00:55 (+2)
 +
 +
题意:给定 $L,R$,在 $[L,R]$ 中选择一段连续的区间使得异或和最小。
 +
 +
题解:又是自己出过的题的变种,感觉都快变成 old ass problem 了。
 +
 +
首先,$1$ ~ $n$ 的前缀异或和可以分四种情况讨论,在 $n \mod 4 = 0,1,2,3$ 的四种情况下分别是 $n,1,n+1,0$。显然,如果区间长度稍大,一定能找到异或和为 $0$ 的子区间。只需要枚举 $l \in [L,L+10],r \in [R-10,R]$ 的情况就可以了。
  
 
== Problem B ==
 
== Problem B ==
Line 35: Line 34:
  
 
Solved by Weaver_zhu. 00:46 (+)
 
Solved by Weaver_zhu. 00:46 (+)
 +
 +
题意:判断区间素数密度大于 $\frac{1}{3}$
 +
 +
题解:大的区间不要了,小的区间筛。开场写了 min25,又怕被卡常重构代码,其实不会卡
  
 
== Problem D ==
 
== Problem D ==
Line 43: Line 46:
  
 
Solved by Weaver_zhu. 02:30 (+)
 
Solved by Weaver_zhu. 02:30 (+)
 +
 +
题意:$Z = a_1! \times ... \times a_n!$ 求 最大的 $i$ 使得 $b_i=Z \times X^i$ 能整除 $Y$
 +
 +
题解:统计素数个数就完事了,据隔壁队说卡常,侥幸一遍过
  
 
== Problem F ==
 
== Problem F ==
  
 
Solved by Xiejiadong. 01:26 (+)
 
Solved by Xiejiadong. 01:26 (+)
 +
 +
题意:给出 $x$ 求任意一组解满足 $a^3+b^3+c^3=x$ 且 $|a|,|b|,|c|\le 5\cdot 10^3,0\le x\le 200$ 。
 +
 +
题解:考虑预处理出所有 $|a|,|b|\le 5\cdot 10^3$ 的情况,枚举所有的 $x$ ,再枚举 $c$ ,判断是否存在这样的 $a,b$ 。
 +
 +
直接用 map 是不大行的,无论是时间复杂度还是内存上本地都跑不出来,差点电脑死机了。
 +
 +
考虑用数组存下所有的情况,排序以后,再在其中二分。
 +
 +
打表直接输出即可。
  
 
== Problem G ==
 
== Problem G ==
Line 55: Line 72:
  
 
Solved by Kilo_5723. 03:57 (+1)
 
Solved by Kilo_5723. 03:57 (+1)
 +
 +
题意:给出 $n$ 个整数,支持两种操作:
 +
 +
1)修改一个数。
 +
 +
2)对一个区间内的数,求出用其子集之和其不能表示的最小的正整数是多少。
 +
 +
题解:
 +
 +
先考虑给定一些数,用子集之和不能表示的最小的正整数如何计算。
 +
 +
将所有数排序之后,从小到大考虑。令第 $i$ 个数为 $a_i$,$s_i\sum_{i=1}^{n}a_i$,首先,显然前 $i$ 个数只可能表示 $s_i$ 内的数,然后可以发现:如果前 $i-1$ 个数可以表示 $s_{i-1}$ 以内所有的数,则若 $a_i<=s_{i-1}+1$,则前 $i$ 个数可以表示 $s_i$ 以内的数,否则这些数只能表示 $s_i-1$ 以内的数。
 +
 +
根据这个特性,我们定义一个块为:升序的整数序列 ${a_i}$,其中 $a_i<=s_{i-1}+a_1$。这样的块可以保证如果 $k$ 以内的整数都可以被表示并且 $k>=a_1-1$,那么 $s_n+k$ 以内的数也可以被表示。
 +
 +
显然,对于任何一个区间,如果将其贪心地从小到大分割成这样的块,那么最终得到的块数是 $O(\log(range))$ 的,其中 $range$ 代表值域,并且这样的块可以线性合并。因此,用线段树维护区间的所有块,每次单点更新时向上更新每个节点内的块,每次询问时对根节点的块查询。复杂度 $O(q\log(n)\log(range))$。
  
 
== Problem I ==
 
== Problem I ==
Line 71: Line 104:
  
 
Solved by Xiejiadong. 03:24 (+)
 
Solved by Xiejiadong. 03:24 (+)
 +
 +
题意:给出一棵树,树上每个节点都有一个字母,每次可以选择一个节点,从它开始向他的父节点走,沿路记下字母。
 +
 +
每次询问给出一个节点以及走的步数,求整棵树上可以走出多少这样的字符串。
 +
 +
题解:考虑如果对于每一个节点变成向他的孩子走,题目就转换成了后缀的问题。
 +
 +
如果能够处理出来所有节点往下走的字符串,建立 SAM ,在其中做子串定位以及统计当前子串状态出现的次数就好了。
 +
 +
考虑到这是一个树,每次记录当前节点对应在广义 SAM 的节点编号,回溯的时候,暴力的跳父亲的 SAM 节点,在 insert 即可。
  
 
== Problem M ==
 
== Problem M ==
  
 
Solved by Weaver_zhu && Kilo_5723. 01:50 (+)
 
Solved by Weaver_zhu && Kilo_5723. 01:50 (+)
 +
 +
题意:定义 critical point 为树上点 $u, c(w) = \sum\limits_{v\in T}d(w,v), c(u) = min\{c(w)\}$,然后求有根树每个子树的 critical point
 +
 +
题解:critical point 就是重心,考虑当前重心,一定在孩子子树重心到自己的路径上,二分(二分一阶导数,也就是移动一格的代价,也就是子树大小和子树外大小)就完事了

Latest revision as of 12:14, 4 December 2019

Replay

Xiejiadong:

  • 银川以后整个队伍就有一种任务达成的迹象。整个训练的状态极差。
  • 开局前半小时甚至提交都没有。第一发提交 A 还 wa 了,第二发提交 A 又 wa 了,而且此时 Kilo 和 Weaver 在 A 和 C 疯狂交互上机,手里握着一个 F ,感觉这把要打 Cu 滚回去了。
  • 可喜的是,前期三题过去以后,基本都是 1A 到了中后场,算是挽救了一把。
  • 总算做到了一道纯字符串题。
  • 左手东华,右手上大,上海三连坐。
  • 完成了 “不丢脸” 的小目标。
  • 恭喜蔡队出线。

Kilo_5723:

  • 做了一道只有自己没见过的原题。

Weaver_zhu:

Problem A

Solved by Kilo_5723. 00:55 (+2)

题意:给定 $L,R$,在 $[L,R]$ 中选择一段连续的区间使得异或和最小。

题解:又是自己出过的题的变种,感觉都快变成 old ass problem 了。

首先,$1$ ~ $n$ 的前缀异或和可以分四种情况讨论,在 $n \mod 4 = 0,1,2,3$ 的四种情况下分别是 $n,1,n+1,0$。显然,如果区间长度稍大,一定能找到异或和为 $0$ 的子区间。只需要枚举 $l \in [L,L+10],r \in [R-10,R]$ 的情况就可以了。

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 00:46 (+)

题意:判断区间素数密度大于 $\frac{1}{3}$

题解:大的区间不要了,小的区间筛。开场写了 min25,又怕被卡常重构代码,其实不会卡

Problem D

Unsolved.

Problem E

Solved by Weaver_zhu. 02:30 (+)

题意:$Z = a_1! \times ... \times a_n!$ 求 最大的 $i$ 使得 $b_i=Z \times X^i$ 能整除 $Y$

题解:统计素数个数就完事了,据隔壁队说卡常,侥幸一遍过

Problem F

Solved by Xiejiadong. 01:26 (+)

题意:给出 $x$ 求任意一组解满足 $a^3+b^3+c^3=x$ 且 $|a|,|b|,|c|\le 5\cdot 10^3,0\le x\le 200$ 。

题解:考虑预处理出所有 $|a|,|b|\le 5\cdot 10^3$ 的情况,枚举所有的 $x$ ,再枚举 $c$ ,判断是否存在这样的 $a,b$ 。

直接用 map 是不大行的,无论是时间复杂度还是内存上本地都跑不出来,差点电脑死机了。

考虑用数组存下所有的情况,排序以后,再在其中二分。

打表直接输出即可。

Problem G

Unsolved.

Problem H

Solved by Kilo_5723. 03:57 (+1)

题意:给出 $n$ 个整数,支持两种操作:

1)修改一个数。

2)对一个区间内的数,求出用其子集之和其不能表示的最小的正整数是多少。

题解:

先考虑给定一些数,用子集之和不能表示的最小的正整数如何计算。

将所有数排序之后,从小到大考虑。令第 $i$ 个数为 $a_i$,$s_i\sum_{i=1}^{n}a_i$,首先,显然前 $i$ 个数只可能表示 $s_i$ 内的数,然后可以发现:如果前 $i-1$ 个数可以表示 $s_{i-1}$ 以内所有的数,则若 $a_i<=s_{i-1}+1$,则前 $i$ 个数可以表示 $s_i$ 以内的数,否则这些数只能表示 $s_i-1$ 以内的数。

根据这个特性,我们定义一个块为:升序的整数序列 ${a_i}$,其中 $a_i<=s_{i-1}+a_1$。这样的块可以保证如果 $k$ 以内的整数都可以被表示并且 $k>=a_1-1$,那么 $s_n+k$ 以内的数也可以被表示。

显然,对于任何一个区间,如果将其贪心地从小到大分割成这样的块,那么最终得到的块数是 $O(\log(range))$ 的,其中 $range$ 代表值域,并且这样的块可以线性合并。因此,用线段树维护区间的所有块,每次单点更新时向上更新每个节点内的块,每次询问时对根节点的块查询。复杂度 $O(q\log(n)\log(range))$。

Problem I

Unsolved.

Problem J

Unsolved. (-5)

Problem K

Unsolved.

Problem L

Solved by Xiejiadong. 03:24 (+)

题意:给出一棵树,树上每个节点都有一个字母,每次可以选择一个节点,从它开始向他的父节点走,沿路记下字母。

每次询问给出一个节点以及走的步数,求整棵树上可以走出多少这样的字符串。

题解:考虑如果对于每一个节点变成向他的孩子走,题目就转换成了后缀的问题。

如果能够处理出来所有节点往下走的字符串,建立 SAM ,在其中做子串定位以及统计当前子串状态出现的次数就好了。

考虑到这是一个树,每次记录当前节点对应在广义 SAM 的节点编号,回溯的时候,暴力的跳父亲的 SAM 节点,在 insert 即可。

Problem M

Solved by Weaver_zhu && Kilo_5723. 01:50 (+)

题意:定义 critical point 为树上点 $u, c(w) = \sum\limits_{v\in T}d(w,v), c(u) = min\{c(w)\}$,然后求有根树每个子树的 critical point

题解:critical point 就是重心,考虑当前重心,一定在孩子子树重心到自己的路径上,二分(二分一阶导数,也就是移动一格的代价,也就是子树大小和子树外大小)就完事了