2022 CCPC网络赛几句话题解

2022 CCPC网络赛解题报告

rank40

A. Doubt VS Lie

模拟打牌题。随便模拟几下

B. Degree

还没补

C. Guess

队友做的，没有看题

D. Pointer Sequence

还没补

E. Substring Match

状态$f[i][j]$表示$s$中第$i$个字母，匹配到$t$中第$j$个大写字母的最长匹配，然后DP一下。要么$s$和$t$中大写字母进行匹配，直接判断做；要么和中间的小写字母匹配，字符串哈希判断。

F. Xor Circle

还没补

G. Name the Puppy

使用$n$个字符串进行任意拼接（可以用多次），使得前缀的翻转等于后缀的长度最大。

把前缀和后缀独立拼接，对所有字符串建一个Trie，对所有字符串的翻转再建一个Trie。前缀和后缀分开进行搜索。如果搜索到重复状态则返回 INF

感觉是假了，可能通过不同路径搜索到相同状态。下面这个样例竟然会输出 INF

6
ab
aab
cdefgh
dcba
dcbaa
fe

H. Mutiple Set

给出$L,R,K$，求$\sum_{i = \lceil \frac{L}{x} \rceil}^{\lfloor \frac{R}{x} \rfloor} i * x \times 2^{\lfloor \frac{R}{x} \rfloor - \lceil \frac{L}{x} \rceil} = K$的条件下，所有的$x$。

对$\lceil \frac{L}{x} \rceil$ 和 $\lfloor \frac{R}{x} \rfloor$做整除分块就好了。

I. Transport Plan

还没补

J. Count Permutation

显然如果我们构造出一个模$n$意义下的等差数列$p$，$w(p)$一定等于2，因为相邻两个差一定是公差或者是$n$减去公差。
然后考虑哪些公差能够遍历$[1,n]$所有的数。通过简单的数论原理可知$gcd(n, d) =1$的情况下满足。
最后考虑题目给出的限制$p_1 = s, p_m = t$，显然$(m-1)\times d = t - s\pmod{n}$。那么只需要求出满足两个条件的$d$的个数即可。通过莫比乌斯的容斥，枚举$n$的约数来求解。

可惜在比赛中队友给错了题意，都已经推完两个条件了，不然还能再冲一题。

K. Roulette

交互题。 我有无穷的本金，希望获取$y$的利润，每次如果投注$x$(自己选定)元，有一定概率赚$x$，有一定概率亏$x$。

只需要第一次投$y$元，第二次投$2y$，第三次投$4y$，直到赢为止。

“我可以输很多次，但只要赢一次就够了。”

L. Tree Division

不会写，队友搞了个$O(N\sqrt{N logN}$的做法，最后WA了

M. Count Permutation 2

傻逼题，队友直接写了