Difference between revisions of "ICPC 2019 Nanchang Online Contest"
Line 3: | Line 3: | ||
Solved by Kilo_5723. 02:26 (+1) | Solved by Kilo_5723. 02:26 (+1) | ||
− | 题意:给出一段长度为 $100$ 的数列,判断其是否为 $\ | + | 题意:给出一段长度为 $100$ 的数列,判断其是否为 $\varphi(i)$ 中的连续一段。 |
题解:通过实验可以发现,$\phi(i)$ 的序列在 $[1,1.5\cdot 10^8)$ 中不存在 $x_i=x_j,x_{i+23}=x_{j+23},x_{i+46}=x_{j+46},x_{i+69}=x_{j+69},i\neq j$。因此,预处理每个 $(\phi(23\cdot k),\phi(23\cdot (k+1)),\phi(23\cdot (k+2)),\phi(23\cdot(k+3))$,其中 $\phi(23*p)$ 可以从 $phi(p)$ $O(1)$ 得到,因此可以线性筛出 $phi(i)(i \in [1,7 \cdot 10^6])$,再以此推出所有需要的 $\phi(23*p)$。接下里,只要枚举数列中第一个是 $23$ 倍数的位置,寻找符合要求的四元组。如果符合要求,用区间筛 | 题解:通过实验可以发现,$\phi(i)$ 的序列在 $[1,1.5\cdot 10^8)$ 中不存在 $x_i=x_j,x_{i+23}=x_{j+23},x_{i+46}=x_{j+46},x_{i+69}=x_{j+69},i\neq j$。因此,预处理每个 $(\phi(23\cdot k),\phi(23\cdot (k+1)),\phi(23\cdot (k+2)),\phi(23\cdot(k+3))$,其中 $\phi(23*p)$ 可以从 $phi(p)$ $O(1)$ 得到,因此可以线性筛出 $phi(i)(i \in [1,7 \cdot 10^6])$,再以此推出所有需要的 $\phi(23*p)$。接下里,只要枚举数列中第一个是 $23$ 倍数的位置,寻找符合要求的四元组。如果符合要求,用区间筛 |
Revision as of 12:06, 11 September 2019
Problem A
Solved by Kilo_5723. 02:26 (+1)
题意:给出一段长度为 $100$ 的数列,判断其是否为 $\varphi(i)$ 中的连续一段。
题解:通过实验可以发现,$\phi(i)$ 的序列在 $[1,1.5\cdot 10^8)$ 中不存在 $x_i=x_j,x_{i+23}=x_{j+23},x_{i+46}=x_{j+46},x_{i+69}=x_{j+69},i\neq j$。因此,预处理每个 $(\phi(23\cdot k),\phi(23\cdot (k+1)),\phi(23\cdot (k+2)),\phi(23\cdot(k+3))$,其中 $\phi(23*p)$ 可以从 $phi(p)$ $O(1)$ 得到,因此可以线性筛出 $phi(i)(i \in [1,7 \cdot 10^6])$,再以此推出所有需要的 $\phi(23*p)$。接下里,只要枚举数列中第一个是 $23$ 倍数的位置,寻找符合要求的四元组。如果符合要求,用区间筛
Problem B
Solved by Xiejiadong. 01:06 (+)
题意:求一个点到其他点的最大距离 $/C$ 和好多个点到其他所有点最大距离比较。
题解:多源最短路,合并路径 max 即可。
注意不要去除 $C$ ,会发生各种问题,用多个点的距离乘 $C$ 即可。
Problem C
Solved by Xiejiadong. 04:52 (+)
题意:求删掉最小的字符,使得包含子串 $9102$ 而不包含子串 $8102$ 。
题解:倒过来处理比较方便处理末位的情况。
维护每一个区间内的转移。区间内的转移为 $f[i][j]$ ,表示状态 $i$ 到状态 $j$ 所需要删除的最少字符数量。
状态一共五个,分别是空和依次 $2$ 、 $20$ 、 $201$ 、 $2019$ 。
用线段树维护区间,每次合并区间的时候,可以发现是矩阵乘法。
线段树支持区间查询即可。
Problem D
Solved by Weaver_zhu. 04:25 (+2)
Problem E
Solved by Xiejiadong && Kilo_5723. 02:33 (+)
题意:反向约瑟夫问题,询问一个位置第几个被删除。
题解:大力模拟的复杂度是 $n+\frac{9}{10}n+\frac{81}{100}n+\cdots =10n$ 。
直接用数组模拟即可。内存可能不够开三个数组,直接复用当前数组即可。
Problem F
Unsolved.
Problem G
Solved by Xiejiadong. 00:06 (+)
温暖的签到。
Problem H
Solved by Weaver_zhu. 01:34 (+)
Problem I
Unsolved.