航电多校 2024 笔记

01

写点赛时不会的。难绷场，可能因为是 01 所以比较水，就只有最后一个能放省选模拟 T1，以及一堆原神题。

T5 hdu7434 博弈

小马给出了一个可重小写字符集合 \(S\)。Alice 初始时有空串 \(A\)，Bob 初始时有空串 \(B\)。两人轮流等概率取出集合 \(S\) 中的一个字符 \(c\)，将它拼接到自己的字符串的后面，直至 \(S\) 为空，每个字符只能被取一次，Alice 先手。如果最终 \(A\) 的字典序严格大于 \(B\)，则 Alice 胜利，求其获胜的概率，答案对 \(998244353\)​ 取模。

赛时发现了对于字符集大小为偶数的情况，我们只用算二者字符串相等的情况，不相等的话交换的两种情况构成双射，因此概率相等，字符串相等的情况数组合数随便算算就行。

对于奇数，其实你只用考虑前面 \(\frac{n-1}{2}\) 个字符是否相同，然后就跟上面一样，而且最后一个字符如果相同也只有一种取值，也就是字符数量为奇数的那种。

T6 hdu7435 序列幻方

给定长度为 \(N\) 的序列 \(a\)。一个序列有很多个子序列，每个子序列在序列中出现了若干次。小马想请你输出序列 \(a\) 每个非空子序列出现次数的立方值的和，答案对 \(998244353\) 取模。

这种次方和的常见转化方法是计数可重多元组，这里怎么算呢？赛时想的是在第一个不同的位置算，但是很难，其实直接记三个维度 dp 然后前缀和优化就做完了，这里前缀和是三维了，可以分别转移。

T7 hdu7436 三元环

给定数组 \(f\) 和 \(g\)，如果有 \(f_i<f_j\)，\(g_i<g_j\) 和 \(i<j\) 则有边 \(i \rightarrow j\)，否则反向，计数三元环个数。

突然想起来我好像在哪里见过类似的容斥思路，好像是在某个模拟赛里，总之难绷，容斥，找不是三元环的点对，有且仅有一个点度数为 2，在这里算，变成数点。

T9 hdu7438 数位的关系

题面

不想看了，数位 dp 题。

T10 hdu7439 众数

题面

绷，你发现这是随机的，所以答案不会离最大值太远，如果离很远就说明所有值分布都远离中心，概率很低，然后相当于拉若干个数出来算一算比一比，所有需要拉出来的区间很少，具体实现可以考虑区间 \(k\) 大+超级钢琴，每次把一个最大值最大的区间拿出来算贡献再分裂，如果最大值不算就不管了。

T11 hdu7440 树上的 mex

问所有链 mex 的 max，但是对于每种点权一定存在一条链完全包含这种权的所有点。

赛时想的淀粉质，但是其实可以从每种颜色身上考虑，一条链如果要包含这种颜色得满足什么条件，把链看作端点二元组 \((x,y)\)，不难发现每种颜色其实划定了有常数倍该颜色点数的 dfs 序上的矩形不能取到点，二分扫描线就做完了，好像很难写。