TCO19 SRM 740 Div1 解题记录

### Easy RainForecast
题意：$n$个人依次传递一个布尔变量，第$i$个人有$p_i$的概率传错，问最后结果正确的概率是多少。$n\le 50$

题解：简单的$O(n)$的$DP$，记$f(i,0/1)$即可。但是光是这样就是在水博客了，不行的。这题让人不禁发现一个有趣的性质：要想最终正确概率为$50\%$一定得有一个人的$p_i=50\%$！想一想，为什么？

### Medium DieDesign
题意：没题面，喵喵喵？？？？
发现statistics抽风了，上Arena就有了题面。
两个人玩投色子游戏，$A$有一个色子，$B$有一个每一个面没有点数的色子，每个色子都有$n$面。现在已知$A$的色子，$B$可以把每一个面填上点数，点数总和和$A$的一样，要输出一种填点数的方案让$B$赢得概率最大。平局算$A$赢。赢指的是$B$点数严格大于$A$。$n\le 30,每面已知点数\le 5000$

题解：不难发现实际上就是要构造数列$b$使得$|b|=n$且最大化：
$$\sum_i\sum_j[a_i<b_j]$$
考虑将$a$排序，按照贪心策略，我们设计$DP$如下：$f(i,j,k)$表示现在处理到第$i$大的$a$，剩下$j$的总和可用，$b$当前长度为$k$的最优策略。那么我们每一次从小到大的考虑$b$，一定是卡着某一个$a_i+1$最优，那么就可以从小到大地用$a$来填$b$。总的时间复杂度$O(n^4Max_A)$不是很能过。
但是转过来一想，发现$\sum_i\sum_j[a_i<b_j]$的值却是$O(n^2)$的，考虑记$f(i,j,k)$表示处理到第$i$大的$a$，答案是$b$，$b$长度为$k$的最小总和。
这样总复杂度就变成了$O(n^4)$，每一次直接考虑往下填一个或者保持当前大小不变。总的来说还是小清新而简单的。

### Hard LongPalindromes

题意：给你一个串$s$，问它循环$r$次后形成的串有多少个子序列是回文的。$|s|\le 50,r\le 10^9$

题解：乍一看很恐怖，实际上仔细分析发现还是很恐怖……
~~泄！~~
题解告诉我们，直接魔改原始的$dp$就可以，本来设$f(i,j)$表示$i-j$这一段字符串的回文子序列个数。转移为：
$$f(i,j)=f(i+1,j)+f(i,j-1)-[s[i]!=s[j]]f(i+1,j-1)$$
因为这样不含两头的串本来就会多算一遍，不一样就需要减去。
我们把这个区间$dp$写成$f(l,i)$的形式，用$l$表示它的长度，$i$一样。
$$f(l,i)=f(l - 1, i + 1)+f(l - 1, i)-[s[i] != s[l - i + 1]]f(l-2,i+1)$$
利用重复的性质，上面就等价于：
$$f(l,i)=f(l - 1, (i + 1)\%n)+f(l - 1, i\%n)-[s[(i)\%n] != s[(l - i + 1)\%n]]f(l-2,(i+1)\%n)$$
发现$f_l$的计算只需要$f_{l-1},f_{l-2}$
并且我们只需要维护$i\in[0,n-1]$，太爽了！
眼看着就要可以矩阵快速幂了，但是有个问题：
$$[s[(i)\%n] != s[(l - i + 1)\%n]]$$
这个东西蛋疼啊！和$l$有关！
不过没关系，发现因为$\% n$，所有矩阵只可能有$n$种，并且是轮流着乘的。
那么我们可以大小步，先把$n$种矩阵乘一轮的矩阵算出来倍增，然后剩下的残缺的一轮暴力。
总复杂度$O(n^4+n^3\log r)$

Rockdu's Blog

导航

最近发表

大佬们的友链