[SNCPC2019] 0689 题解

awesomegordon · 2023-09-22 10:09:38 · 题解

By awesomegordon.

题意

给定一个只由 0,6,8,9 组成的字符串 S，求将S的任意非空字串进行翻转后可得到多少新字串。

思路

最开始是很懵的，但是却想到既然不能求到合法子串数，那就求不合法字串数。其中不合法字串分三种：

1. 首，尾均为 0 的子串。

统计 0 字符数量 sum1，不合法子串数量为

2. 首，尾均为 8 的子串。

统计 8 字符数量 sum3，不合法子串数量为

3. 首，尾为 6,9 的字串。

统计 6,9 字符数量 sum2,sum4，不合法子串数量为 sum2 \times sum4。

注意一点：

如果有全为 6 或 全为 9 的字串，则答案减 1。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
int main(){
    //By awesomegordon 
    int T;
    cin>>T;
    while(T--){
        cin>>s;
        ll l=s.size();
        ll sum1=0,sum2=0,sum3=0,sum4=0;
        //统计数字量 
        for(int i=0;i<l;i++){
            if(s[i]=='0'){
                sum1++;
            }
            if(s[i]=='6'){
                sum2++;
            }
            if(s[i]=='8'){
                sum3++;
            }
            if(s[i]=='9'){
                sum4++;
            }
        }
        ll tsum=0;
        //tsum是不符合的数量 
        tsum+=sum1*(sum1+1)/2;
        tsum+=sum3*(sum3+1)/2;
        tsum+=sum2*sum4;
        if(sum2==l||sum4==l){
            tsum++;
            //特判没考虑到的
        }
        cout<<(l+1)*l/2-tsum+1<<"\n";
    }
    return 0;
}