2024“钉耙编程”中国大学生算法设计超级联赛（1）

比赛链接

补题链接

Problems	AC
1001. 循环位移	○
1002. 星星	○
1003. 树	⊕
1004. 传送	待补
1005. 博弈	⊕
1006. 序列立方	⊕
1007. 三元环	三维偏序 弃疗
1008. 位运算	○
1009. 数位的关系
1010. 众数
1011. 树上的 mex
1012. 并	待补

1001 循环位移 hash

定义字符串 $S=S_0+\cdots+S_{n-1}$ 循环位移 $k$ 次为 $S(k)=S_{k \bmod n}+\cdots+S_{n-1}+$ $S_0+\cdots+S_{(k-1) \bmod n \circ}$

定义 $[A]={A(k), k \in \mathbb{N}}$.
给出 $T$ 组串 $A, B$, 询问 $B$ 有多少个子串在 $[A]$ 中。

倍长一遍，然后把 n 个同构的 hash 值预处理出来丢进 map。

Code

B

队友写了

Code

1003 树 线段树合并 / DSU on Tree

给一棵根为 1 的有根树, 点 $i$ 具有一个权值 $A_i$ 。
定义一个点对的值 $f(u, v)=\max \left(A_u, A_v\right) \times\left|A_u-A_v\right|$ 。
你需要对于每个节点 $i$, 计算 $a n s_i=\sum_{u \in \text { subtree }(i), v \in \text { subtree }(i)} f(u, v)$, 其中 subtree $(i)$表示 $i$ 的子树。

请你输出 $\oplus\left(a n s_i \bmod 2^{64}\right)$, 其中 $\oplus$ 表示 XOR。

这个 f 函数其实就是 max * max - max * min。

假如你现在在一棵值域线段树上面，你知道左儿子和右儿子的信息。那么对于你这个节点，多出来的就是跨越你这个点的信息。这实际上就是 右边的平方和 * 左边的个数 - 右边的和 * 左边的和。线段树合并一下，做完了。

Code

1005 博弈

小马给出了一个可重小写字符集合 $S$ 。

Alice 初始时有空串 $A$, Bob 初始时有空串 $B$ 。

两人轮流等概率取出集合 $S$ 中的一个字符 $c$, 将它拼接到自己的字符串的后面, 直至 $S$为空, 每个字符只能被取一次, Alice 先手。

如果最终 $A$ 的字典序严格大于 $B$, 则 Alice 胜利, 求其获胜的概率, 答案对 998244353 取模。

其实，只要算下平局的概率就好了，由于对称性，减去平局的概率再除 2 就是答案。

如果出现次数为奇数的字符个数大于等于 2 的时候，必然无法平局。答案就是 1/2。

如果只有 1 个的话，算出去掉一个那个字符后平局的概率，

1006 序列立方 思维 / DP

给定长度为 $N$ 的序列 $a$

一个序列有很多个子序列，每个子序列在序列中出现了若干次。

小马想请你输出序列 $a$ 每个非空子序列出现次数的立方值的和，答案对 998244353​ 取模。

$1 \le a_i, N \le 250$

巧妙的转化 Trick，出现次数的三次方 = 同样的序列出现三次。

设 f[i][j][k] 代表现在选了三个序列，最后一位分别是 a[i], a[j], a[k]。需要满足 a[i] = a[j] = a[k]。

朴素的转移就是枚举上一个状态，可以用高维前缀和优化。

Code