action=problem&type=show&id=13303&courseid=0
题意：给你一个字符串,由数字和其它字符组成,问有多少个子串,使得子串里面的数字和为3的整数倍(子串必须连续,并且里面不能有其它字符)。
分析：开3个数组,dp0[i],dp1[i],dp2[i]。dp0[i]表示从字符串的最后一个位置到位置i有多少个字符串的和是0的倍数,dp1[i],dp2[i]类似。
从后往前推,那么假如当前位置为i,（str[i]-'0'）%3==1,dp0[i]=dp2[i+1],。。。。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e6+10;
char str[maxn];
long long dp0[maxn],dp1[maxn],dp2[maxn];
int main()
{
int len,i,j,x;
long long ans,Sum;
while(scanf("%s",str)!=EOF)
{
len=strlen(str);
memset(dp0,0,sizeof(dp0[0])*(len+2));
memset(dp1,0,sizeof(dp0[0])*(len+2));
memset(dp2,0,sizeof(dp0[0])*(len+2));
ans=0;
for(i=len-1;i>=0;i--)
{
if(str[i]>='0' && str[i]<='9')
{
x=(str[i]-'0')%3;
if(x==1)
{
ans+=dp2[i+1];
dp0[i]=dp2[i+1];
dp1[i]=dp0[i+1];
dp2[i]=dp1[i+1];
dp1[i]++;
}
else if(x==2)
{
ans+=dp1[i+1];
dp0[i]=dp1[i+1];
dp1[i]=dp2[i+1];
dp2[i]=dp0[i+1];
dp2[i]++;
}
else
{
ans+=dp0[i+1]+1;
dp0[i]=dp0[i+1];
dp1[i]=dp1[i+1];
dp2[i]=dp2[i+1];
dp0[i]++;
}
}
else
{
dp0[i]=dp1[i]=dp2[i]=0;
}
}
cout<<ans<<'
';
}
return 0;
}