Difference between revisions of "ICPC 2019 Xuzhou Online Contest"
Line 35: | Line 35: | ||
Solved by Kilo_5723. 01:43 (+) | Solved by Kilo_5723. 01:43 (+) | ||
− | 题意:给出一个父串 $T$,给出 $n$ 个子串 $S_i$,求 $T$ 和每个 $S_i$ 的包含关系。保证 $\sum_{i=1}^{n}(|T|+|S_i|)\ | + | 题意:给出一个父串 $T$,给出 $n$ 个子串 $S_i$,求 $T$ 和每个 $S_i$ 的包含关系。保证 $\sum_{i=1}^{n}(|T|+|S_i|)\le 10^7$。 |
题解: | 题解: |
Revision as of 06:37, 10 September 2019
Problem A
Solved by Kilo_5723 && Weaver_zhu. 03:40 (+)
题意:用同余式给出 $n$,有 $n$ 个石子,第一个人可以拿任意多但不能全拿走,之后每个人可以拿 $1$ 到前一个人拿取石子总数两倍的石子,取光石子的人获胜,求先手必胜还是后手必胜。
题意:第一部分是 CRT,第二部分是斐波那契博弈,当且仅当 $n$ 在斐波那契数列里出现过时后手必胜。
Problem B
Solved by Xiejiadong. 03:23 (+5)
题意:支持两个操作:
- 删掉一个数
- 询问一个数之后没被删掉的第一个数
题解:询问的位置之后,连续的一段被删掉的是会被影响的。
可以发现,答案只会是所有询问和修改位置,或者他们 $+1$ 位置,离线以后离散,用并查集维护即可。
死于 C++14 跑的比 C++11 慢。
Problem C
Solved by Xiejiadong. 00:14 (+1)
傻逼签到题。
死于出题人的英语水平。
Problem D
Solved by Kilo_5723. 01:43 (+)
题意:给出一个父串 $T$,给出 $n$ 个子串 $S_i$,求 $T$ 和每个 $S_i$ 的包含关系。保证 $\sum_{i=1}^{n}(|T|+|S_i|)\le 10^7$。
题解:
Problem E
Solved by Weaver_zhu. 00:51 (+1)
Problem F
Unsolved.
Problem G
Solved by Xiejiadong. 01:18 (+2)
题意:询问所有回文子串的价值,一个字符串的价值定义为包含的不同字母数量。
题解:利用 pam 建出所有回文串。
在见串的同时保存被一个状态所包含的不同字母数量,暴力加上当前转移边上的字母。
答案就是所有状态出现的次数 * 所有状态包含的不同字母数量。
Problem H
Unsolved.
Problem I
Solved by Xiejiadong && Kilo_5723. 01:55 (+)
题意:给出一个排列,每次求一个排列的区间中有多少数对满足 $min(x,y)=gcd(x,y)$ 。
题解:很容易发现, $min(x,y)=gcd(x,y)$ 等价于 $x|y$ 或者 $y|x$ ,而因为保证了给出的是一个排列,所以整除关系总数是 $nlogn$ 的。
于是,可以利用筛法,如果 $x|y$ ,我们就把 $(x,y)$ 这个点加入平面,询问就变成了询问一个正方形区域内点的数量。
离线,树状数组维护二维数点即可。
Problem J
Solved by Kilo_5723. 02:49 (+)
Problem K
Solved by Kilo_5723. 02:06 (+2)
Problem L
Solved by Kilo_5723 && Xiejiadong. 04:43 (+)
Problem M
Solved by Weaver_zhu. 02:30 (+)