ICPC 6823 Counting substhreengs

本文主要是介绍ICPC 6823 Counting substhreengs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求出满足要求的子串个数，要求是：子串都是数字，并且能被3整除。

做法：动态规划的思想。弄一个数组记录当前选定值之前的情况，num[0]记录余数为0的个数。假设选定当前值作为数字的最后一个位数，如果当前值mod3等于1，那么前面num[2]的数加上当前值都能变成余数0，所以num[0]=num[2].以此类推......

不用long long 会wa。

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{string s;while(cin >> s){long long num[4] = {0};long long ans = 0;for(long long i=0;i<s.length();i++){if(s[i]>='0'&&s[i]<='9'){long long x = (s[i]-'0')%3;long long x1,x2,x3;if(x==0){x1 = num[0]+1;x2 = num[1];x3 = num[2];}else if(x==1){x1 = num[2];x2 = num[0]+1;x3 = num[1];}else if(x==2){x1 = num[1];x2 = num[2];x3 = num[0]+1;}num[0] = x1;num[1] = x2;num[2] = x3;ans+=num[0];}else{num[0] = 0;num[1] = 0;num[2] = 0;}}cout<<ans<<endl;}return 0;
}

这篇关于ICPC 6823 Counting substhreengs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---