P9183 [USACO23OPEN] FEB
一道规律题$.....$
说在前面的
写这一道题,首先要知道一个东西:
如果$A$的取值为($1,3,5$)中的一种,$B$的取值为($0,2,4$)中的一种,
则$A+B$的取值为($1,3,5,7,9$)中的一种.
如果$A$的取值为($1,2,3$)中的一种,$B$的取值为($0,2,4$)中的一种,
则$A+B$的取值为($1,2,3,4,5,6,7$)中的一种.
那么:如果$A$的取值为一个等差数列$l_a-r_a$(公差为$k_a$)中的一种,$B$的取值为等差数列$l_b-r_b$(公差为$k_b$)中的一种,
则$A+B$的取值为等差数列$(l_a+l_b)-(r_a+r_b)$(公差为$\min(k_a,k_b))$中的一种.
Solution
题意再次并不赘述,总答案为已知的字符所产生的贡献$+$字符$F$所产生的贡献
由眼可得 仔细观察,可发现$F$在字符串中只有三种可能
- 形如$...BFFFB...$或$...EFFFE...$ 即一段连续$F$的两头相连的已知字符相同。
- 形如$...BFFFE...$或$...EFFFB...$ 即一段连续$F$的两头相连的已知字符不相同。
- 形如$FFF...$或$...FFF$ 即一段连续的$F$在字符串的开头或结尾
这时,可以考虑找不同情况下$F$的贡献,然后将每一段$F$的贡献合并起来,加上已知字符的贡献,便是本题答案。
第一种情况时:
- $...BFB...$ 的贡献为 $0,2$
- $...BFFB...$ 的贡献为 $1,3$
- $...BFFFB...$ 的贡献为 $0,2,4$
- $...BFFFFB...$ 的贡献为 $1,3,5$
- $......$
第二种情况时:
- $...BFE...$ 的贡献为 $1$
- $...BFFE...$ 的贡献为 $0,2$
- $...BFFFE...$ 的贡献为 $1,3$
- $...BFFFFE...$ 的贡献为 $0,2,4$
- $......$
第三种情况时:
- $F...$ 的贡献为 $0,1$
- $FF...$ 的贡献为 $0,1,2$
- $FFF...$ 的贡献为 $0,1,2,3$
- $FFFF...$ 的贡献为 $0,1,2,3,4$
- $......$
所以,不同情况下的$F$的贡献都是等差数列,判断$F$的种类,合并答案便可
标签:字符,Feb,...,贡献,一种,取值,等差数列 From: https://www.cnblogs.com/cutemush/p/17399000.html