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 序上的矩形不能取到点,二分扫描线就做完了,好像很难写。
标签:字符,相等,赛时,航电,最大值,多校,Alice,2024,序列 From: https://www.cnblogs.com/eastcloud/p/18312513