Codeforces1142D

做法：構(gòu)建一個可以識別出合法串的自動機(jī)，然后就可以想辦法在上邊 dp 出答案。 首先，按照最直觀的思路畫一畫這個自動機(jī)，找到每一個狀態(tài)s如何推出它的后繼t，然后通過狀態(tài)的轉(zhuǎn)移方式，找到等價的狀態(tài)，想辦法壓縮這個自動機(jī)。我們令x的位數(shù)是d，ax是比x小的合法的數(shù)的數(shù)目，bx是位數(shù)是d的合法數(shù)中比x小的數(shù)的數(shù)目，cx是位數(shù)是d的合法數(shù)的數(shù)目。那么如果在x后添加一個數(shù)字s構(gòu)成一個數(shù)字y，\(ay = ax - bx + cx + cal(ax-bx+1,bx) + s\), \(cal(a,b)\)是從a開始到b在%11下循環(huán)求和。 這個式子的\(ax-bx+cx\)就是在計算x的這種位數(shù)中最后一個數(shù)字的編號，\(cal(ax-bx+1,bx) + s\)就是當(dāng)前層比y小的數(shù)的個數(shù)，那么有\(by = cal(ax-bx+1,bx) + s\)，\(cy = cal(ax-bx+1,cx)\)。觀察這個轉(zhuǎn)移的式子，如果 ax+11 會導(dǎo)致 ay + 11，by， cy，如果 bx+11 會導(dǎo)致 ay - 11 + 55, by + 55, cy 如果cx + 11 會導(dǎo)致 ay + 11， by，cy + 55。觀察可以知道 (ax,bx,cx) 在 %11 意義下等價，后繼的數(shù)量種類也一致，轉(zhuǎn)移是有等價性的，于是對于這個三元組(ax,bx,cx)我們建出11 * 11 * 11的狀態(tài)轉(zhuǎn)移圖，而一個子串如果可以在這個圖上完成匹配，他就是合法的。顯然，對于個位置i如果它的最長匹配距離是A，那么答案加A，設(shè)\(dp[i][j]\)表示以字符串的第i個位置為起點(diǎn)，自動機(jī)的節(jié)點(diǎn)j為起點(diǎn)，最長的匹配長度。就有\(dp[i][j] = dp[i+1][nxt(j,s[i+1])] + 1\)，其中 \(nxt(s,c)\) 指狀態(tài)s后添加一個字符c走到的新狀態(tài)，需要注意的一點(diǎn)是，對于任意一種串的位置i和狀態(tài)s，dp[i][s]至少為1！！復(fù)雜度\(O(11^3 N)\)求解過程中需要理性取模。注意常數(shù)

#include <bits/stdc++.h> #define rep(i,a,b) for(int i = (a); i <= (b); ++i) #define per(i,a,b) for(int i = (a); i >= (b); --i) #define pb push_back #define Pll pair<ll,ll> #define Pii pair<int,int> #define Plp pair< ll,Pii > #define Pip pair< int,Pii > #define Ppp pair< Pii,Pii > #define x first #define y second typedef long long ll; const int N = 100100;using namespace std; int cal(int a, int n) {return (( (a+a+n-1)*n/2 )%11+11)%11; } int n, dp[2][11][11][11]; char s[N]; ll ans;int main() {scanf(" %s",s+1); n = strlen(s+1);int f = 0;per(i, n, 1) {int now = s[i] - '0', nx = s[i+1] - '0';rep(a, 0, 10) rep(b, 0, 10) rep(c, 0, 10) {dp[f][a][b][c] = 1;if(i == n) continue;if( (a+1)%11 <= nx ) continue;int ta = (a - b + 11 + c + cal(a-b+1,b) + nx) % 11;int tb = (cal(a-b+1,b) + nx) %11 ;int tc = cal(a-b+1,c);dp[f][a][b][c] = dp[f^1][ta][tb][tc] + 1;}if(now) ans += dp[f][now-1][now-1][9];f ^= 1;}printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/10668310.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces1142D的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。