K number（思维和后缀以及3的特性）（2019牛客暑期多校训练营（第四场））

示例1：

输入：600

输出：4

说明：'600', '0', '0', '00' are multiples of 300. (Note that '0' are counted twice because it appeared two times)

示例2：

输入：123000321013200987000789

输出：55

题意：给一个全由数字字符组成的字符串，求出是300倍数的子串的个数。0，00，000等都算，并考虑前导为0的情况。

题解：让求的是300的倍数，但是呢我们可以拆成既是3的倍数也是100的倍数
那么这样就可以找到一些规律：
1.对于3的倍数来说就是各个位上的数值加起来和对3取余答案是0
2.对于100的倍数来说就是要求后两位至少为0（来源：https://blog.csdn.net/c___c18/article/details/97561689）

所以我们需要循环将各个位数上的数字进行相加，如果是0和当前是0与上一位是0的情况进行特殊处理。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int inf=0x3f3f3f3f,maxn=1e5+;

 char str[maxn];

 long long summ,now,a[],len;

 int main()

 {

     scanf("%s",str);

     len=strlen(str);

     for(int i=len-;i>=;i--){

         now+=str[i]-'';

         now%=;

         if(str[i]=='')summ++;

         if(str[i]==''&&str[i+]==''&&i!=len-){

             a[now]++;

         }

         summ+=a[now];

     }

     printf("%lld\n",summ);

     return ;

 }

巴特西

K number（思维和后缀以及3的特性）（2019牛客暑期多校训练营（第四场））

最新文章

热门文章