Atcoder AGC031B Reversi (DP計(jì)數(shù))

簡(jiǎn)單的計(jì)數(shù)題。（總算做出一道AGC的B題了，然而這場(chǎng)比賽我忘記打了233333）

題目鏈接: https://atcoder.jp/contests/agc031/tasks/agc031_b

題意: 有一個(gè)長(zhǎng)度為\(N\)的顏色序列，第\(i\)個(gè)位置初始顏色為\(a_i\), 可以執(zhí)行若干次操作，每次可以選擇兩個(gè)顏色一樣的位置，然后把這兩個(gè)位置中間的區(qū)間都刷成和兩端相同的顏色，問最后本質(zhì)不同的序列有多少種。

題解: 最重要的想法就是要深刻地理解本質(zhì)不同。

因?yàn)槲覀儾徽撊绾尾僮?#xff0c;最后得到的序列一樣就算一樣，所以假設(shè)\([l_1,r_1]\)和\([l_2,r_2]\)分別是先后兩次操作。

若前者和后者相交但不包含，若前后兩次刷成的顏色相同，我們可以等效成一次操作，操作區(qū)間為它們的并。（等效法？文化課走火入魔了吧）若前后兩次顏色不同，那么這種情況一定是不存在的，因?yàn)橄嘟坏话馕吨谝粋€(gè)區(qū)間的一個(gè)端點(diǎn)在第二個(gè)區(qū)間里，那這個(gè)端點(diǎn)在執(zhí)行完前面的操作之后就不再是顏色2而變成顏色1了。

若前者包含后者，則后者無(wú)用。

若后者包含前者，則前者無(wú)用。

若兩次區(qū)間不相交，則兩次都有用。

所以本題就是要求把長(zhǎng)度為\(N\)的序列內(nèi)取出若干不相交區(qū)間，每個(gè)區(qū)間兩端點(diǎn)顏色相同的方案數(shù)。

我們先對(duì)序列進(jìn)行如下處理: 把所有連續(xù)的顏色相同的區(qū)間縮成一個(gè)位置。例如122333441變成12341.

然后\(f_i\)表示前\(i\)個(gè)的方案數(shù)。

\(f_i=\sum_{j\le i, a_j=a_i} f_{j-1}\)

桶優(yōu)化。

時(shí)間復(fù)雜度\(O(n)\).

特發(fā)此文，假裝自己還沒AFO。

代碼

好長(zhǎng)啊，500多B.

#include<cstdio> #include<cstdlib> #include<cstring> #define llong long long using namespace std;const int N = 2e5; const int P = 1e9+7; int a[N+3],b[N+3]; llong f[N+3],g[N+3]; int n;int main() {scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%d",&a[i]);int m = 0; for(int i=1; i<=n; i++) if(i==0 || a[i]!=a[i-1]) {m++; b[m] = a[i];}n = m; for(int i=1; i<=n; i++) a[i] = b[i];f[0] = 1ll; g[a[1]] = 1ll;for(int i=1; i<=n; i++){f[i] = g[a[i]];g[a[i+1]] = (g[a[i+1]]+f[i])%P;}printf("%lld\n",f[n]);return 0; } 發(fā)表于 2019-03-17 00:01 suncongbo 閱讀(...) 評(píng)論(...) 編輯 收藏 刷新評(píng)論刷新頁(yè)面返回頂部

總結(jié)

以上是生活随笔為你收集整理的Atcoder AGC031B Reversi (DP计数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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