自动搬运

查看原文

来自洛谷，原作者为

	awesomegordon 曼巴洲际！！！

搬运于2025-08-24 22:50:21，当前版本为作者最后更新于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;
}