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。
B
队友写了
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。
假如你现在在一棵值域线段树上面,你知道左儿子和右儿子的信息。那么对于你这个节点,多出来的就是跨越你这个点的信息。这实际上就是 右边的平方和 * 左边的个数 - 右边的和 * 左边的和。线段树合并一下,做完了。
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]。
朴素的转移就是枚举上一个状态,可以用高维前缀和优化。
2024“钉耙编程”中国大学生算法设计超级联赛(1)