Difference between revisions of "2019 ICPC Xuzhou Onsite"
Xiejiadong (talk | contribs) (Created page with "== Replay == Xiejiadong: * 垃圾键盘，无数次 想打 “\n” 直接回车就下去了。 * 热身赛感觉是办给主办方的。开始时间延迟将近一小时，...") |
Xiejiadong (talk | contribs) |
||
| (14 intermediate revisions by 3 users not shown) | |||
| Line 3: | Line 3: | ||
Xiejiadong: | Xiejiadong: | ||
| − | * | + | * 银川以后整个队伍就有一种任务达成的迹象。整个训练的状态极差。 |
| − | * | + | * 开局前半小时甚至提交都没有。第一发提交 A 还 wa 了，第二发提交 A 又 wa 了，而且此时 Kilo 和 Weaver 在 A 和 C 疯狂交互上机，手里握着一个 F ，感觉这把要打 Cu 滚回去了。 |
| − | * | + | * 可喜的是，前期三题过去以后，基本都是 1A 到了中后场，算是挽救了一把。 |
| − | * | + | * 总算做到了一道纯字符串题。 |
| − | * | + | * 左手东华，右手上大，上海三连坐。 |
| − | * | + | * 完成了 “不丢脸” 的小目标。 |
| − | * | + | * 恭喜蔡队出线。 |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Kilo_5723: | Kilo_5723: | ||
| − | * | + | * 做了一道只有自己没见过的原题。 |
| − | |||
| − | |||
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 就是重心，考虑当前重心，一定在孩子子树重心到自己的路径上，二分（二分一阶导数，也就是移动一格的代价，也就是子树大小和子树外大小）就完事了