ABC458 A-E题解
2026-05-17 07:07:51
发布于:浙江
A
按照题目模拟,代码略。
B
同A
C
对于字符串每一个 ,向左右边同时移动同等数量时我们可以构造出满足题目条件的一种字串,对于每个 ,计算其左右边最多可以扩展多少格即可。
不要忘了加上形如 C 这类的字串。
signed main(){
cin>>s;
int ans=0;
for (int i=0;i<s.size();++i){
if (s[i]=='C'){
ans+=min(i,(int)s.size()-1-i)+1;
}
}
cout<<ans<<endl;
return 0;
}
D
孩子们直接平衡树平推即可。
代码略,具体请参考平衡树模板。
E
观察题目,可以发现序列不满足条件仅当存在有 和 相邻,于是我们可以考虑将 看做隔板,将数列分成以下形式:
然后因为 和 不能相邻,所以在每一段中要么连续的一段 或者连续的一段 ,直接处理过于麻烦,考虑容斥。
显然,要是没有” 和 不能相邻“这个条件,在 个段中插入 和 的组合分别为 ,然后我们假设存在 个段有问题,此时存在 钟选择问题段的方式,每个问题段至少有一个 和一个 ,于是我们在就可以所有问题段中取出 个 和 和 ,对于剩下的 个 和 个 进行重新排列,根据容斥原理,对于 来说,其贡献为:
所以答案即为:
用乘法逆元计算即可,代码略。
全部评论 2
不会连续段计数。气笑了。
昨天 来自 广东
0现在我和带 3 的都有仇,比如三个数,三个社团
昨天 来自 广东
0看懂的人这辈子有了
22小时前 来自 浙江
0
d
昨天 来自 浙江
0





















有帮助,赞一个