欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019牛客暑期多校训练营(第四场)K number(思维)

程序员文章站 2022-04-02 22:20:57
...

链接:https://ac.nowcoder.com/acm/contest/884/K

题意:给你一个全由数字字符组成的字符串,求出是300倍数的子串的个。0,00都算,并考虑前导零的情况。

思路:遍历一遍每次计算%3的值,如果本位和后一位都是0,把之前统计的num[mo]的个数加上,思想和https://blog.csdn.net/birdmanqin/article/details/97375159类似。注意0也算答案即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
char s[N];
int num[3],n,mo;
ll ans;
int main(void)
{
	while(~scanf("%s",s+1))
	{
		ans=0;
		n=strlen(s+1);
		num[0]=1;
		num[1]=num[2]=0;
		mo=0;
		for(int i=1;i<=n;i++)
		{
			mo=(mo*10+(s[i]-'0'))%3;
			
			if(s[i]=='0'&&s[i+1]=='0')
				ans+=num[mo];
			num[mo]++;
			if(s[i]=='0') ans++;
			
		}
		printf("%lld\n",ans);
	}
	
	return 0;	
} 

 

相关标签: 思维