链接：https://ac.nowcoder.com/acm/contest/884/K?&headNav=acm&headNav=acm 来源：牛客网
题目描述
300iq loves numbers who are multiple of 300.
One day he got a string consisted of numbers. He wants to know how many substrings in the string are multiples of 300 when considered as decimal integers.
Note that leading and trailing zeros are allowed (both in original string and substrings you chose) and the same substring appearing in different places can be counted multiple times.
输入描述:
A single line consisting a string consisted of characters '0' to '9'.输出描述:
The number of substrings that are multiples of 300 when considered as decimal integers.示例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备注:
let the string in the input be s, 1≤∣s∣≤1051 \leq |s| \leq 10^51≤∣s∣≤105.
题意：
给你一个字符串，问能否找到可以整除300的子串？
比如：600
满足题意的有：0 0 00 600
分析：
这题的简单方法：
O（n）
我们处理0 00的情况后，相当于找出前面有多少个被3整数的子串。状态只有0 1 2
具体是实现看一下代码
我的方法：
其实差不多，但当时每有想到可以这么优化
一开始想的是最暴力的解法，预处理里出来0个数的区间，比如1230012300
v[1].l=3,v[1].r=4
v[2].l=8,v[2].r=9
暴力循环v：
对v[i].l前面的数字，暴力求前缀和，sum+=3 sum+=2 sum+=1
如果前面sum%3==0，用一个num计数。
ans+=num*（后面0的个数-1）（300 12300， 0的个数如果为3个，可以增大3000 123000）
ans+=n*（n+1）/2 （n为0的个数，即有0产生的可行解，比如0000, 则0 0 0 0 00 00 00 000 000 0000）
但这样做法会T（具体看一下代码就懂了）
然后我想着因为我每一次都需要往前扫到0，所以T是很正常的，所以我想就是保存前面的状态，因为%3他就有三个状态0，1，2
，
dp1[sta]保存当前从v[i].l的逆着到v[i-1].l的前缀和sum1%3=sta的个数。
dp2[sta]保存从从v[i-1].l的逆着到0的前缀和sum1%3=sta的个数
如何更新从v[i].l的逆着到0的前缀和sum%3=sta的个数dp[sta]，
可以到达的状态（sum+j）%3的个数为dp2[j]
如下：
for(int j=0; j<3; j++)
{ if(dp2[j]!=0)
dp[(j+sum)%3]+=dp2[j];
} for(int j=0; j<3; j++)
{
dp[j]+=dp1[j];
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
string s;
LL dp[3];
int main()
{
cin>>s;
int len=s.size();
LL ans=0;
for(int i=0; i<len; i++)
{
if(s[i]=='0')
{
ans++;
if(i+1<len&&s[i+1]=='0')
{
ans++;
ans+=dp[0];
}
}
int temp=(s[i]-'0')%3;
int dp1[3];
for(int j=0;j<3;j++) //这个是关键，求以s[j]逆着的前缀和
{
dp1[(j+temp)%3]=dp[j];
}
dp1[temp]++;
for(int j=0;j<3;j++)
{
dp[j]=dp1[j];
}
//cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
string s;
struct Node
{
int l,r;
int num;
} a;
vector<Node> v;
#define N 100
LL dp[N],dp1[N],dp2[N];
int main()
{
cin>>s;
int len=s.size();
a.l=0;
a.r=-1;
v.push_back(a);
for(int i=0; i<len; i++)
{
if(s[i]=='0')
{
a.l=i;
int j;
for(j=i; j<len; j++)
{
if(s[j]!='0')
{
break;
}
}
a.r=j-1;
i=j-1;
v.push_back(a);
}
}
int n=v.size();
LL ans=0;
LL sum=0;
for(int i=1; i<n; i++)
{
ans+=(v[i].r-v[i].l+1)*(v[i].r-v[i].l+2)/2;
for(int j=0; j<3; j++)
{
dp1[j]=0;
dp2[j]=dp[j];
dp[j]=0;
}
sum=0;
LL num=0;
for(int j=v[i].l-1; j>=v[i-1].l; j--)
{
sum+=s[j]-'0';
sum%=3;
dp1[sum]++;
}
if(i!=1)
for(int j=0; j<3; j++)
{
if(dp2[j]!=0)
dp[(j+sum)%3]+=dp2[j];
}
for(int j=0; j<3; j++)
{
dp[j]+=dp1[j];
}
if(v[i].r-v[i].l+1>=2)
ans+=(v[i].r-v[i].l)*dp[0];
}
cout<<ans;
return 0;
}
/*
123000321013200987000789
3 5
10
9 9
11
13 14
23
18 20
55
55
*/T了的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
string s;
struct Node
{
int l,r;
int num;
} a;
vector<Node> v;
int main()
{
cin>>s;
int len=s.size();
for(int i=0; i<len; i++)
{
if(s[i]=='0')
{
a.l=i;
int j;
for(j=i; j<len; j++)
{
if(s[j]!='0')
{
break;
}
}
a.r=j-1;
i=j-1;
v.push_back(a);
}
}
int n=v.size();
LL ans=0;
for(int i=0; i<n; i++)
{
cout<<v[i].l<<" "<<v[i].r<<endl;
ans+=(v[i].r-v[i].l+1)*(v[i].r-v[i].l+2)/2;
//cout<<ans<<" "<<endl;
if(v[i].r-v[i].l+1>=2)
{
//cout<<v[i].r<<" "<<v[i].l<<endl;
LL sum=0;
LL num=0;
for(int j=v[i].l-1; j>=0; j--)
{
sum+=s[j]-'0';
if(sum%3==0)
{
//cout<<i<<"#"<<s[i]<<"#"<<sum<<" ";
num+=1;
// }
}
// cout<<endl;
ans+=num*(v[i].r-v[i].l);
cout<<num<<"&";
}
cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}