題意:一個01序列,長度1e6,問有多少子串十進制是3的倍數

題解:DP[i][j]代表前i個并且以i為結尾,且十進制%3==j的串的個數

#include<bits/stdc++.h> #define maxn 1001000 using namespace std; char s[maxn]; long long dp[maxn][3], sum; int main(){while(~scanf("%s", s+1)){sum = 0;int l = strlen(s+1);for(int i=1;i<=l;i++){if(s[i] == '0'){dp[i][0] = dp[i-1][0]+1;dp[i][2] = dp[i-1][1];dp[i][1] = dp[i-1][2];}else{dp[i][0] = dp[i-1][1];dp[i][1] = dp[i-1][0]+1;dp[i][2] = dp[i-1][2];}sum += dp[i][0];}cout<<sum<<endl;}return 0; }

?

轉載于:https://www.cnblogs.com/Noevon/p/8902576.html

總結

以上是生活随笔為你收集整理的nowcoderD Xieldy And His Password的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。