題意簡化:

[luogu] Piling Up

一開始有n個顏色為黑白的球，但不知道黑白色分別有多少，m次操作，每次先拿出一個球，再放入黑白球各一個，再拿出一個球，最后拿出的球按順序排列會形成一個顏色序列，求顏色序列有多少種
n,m小于等于3000 答案對1e9+7取膜

一些亂七八糟的東西

這個題還是 Power_Leo101 同學(xué)教我做的, 自己太弱了,完全不會
這是菊隊ppt里推薦的題, 這個學(xué)期過了, 學(xué)長們就畢業(yè)了, 菊隊也不再會給我們講課了
雖然陳菊開學(xué)長講課的畫風(fēng)毒瘤, ppt毒瘤

題解

對于每一次操作,其實是可以看成一次染色的,因為總數(shù)總是不變,而顏色卻會變化
所以對于每一次染色,即有四種情況: 嘿嘿 黑黑 , 白白, 黑白,白黑
按照常規(guī)思路:
我們不妨設(shè) f[i][j] 表示當前進行第i次操作, 還剩下 j 個白球 (其實顏色沒影響)
所以對于每一個當前狀態(tài)則是可以有之前的狀態(tài),通過上面列舉的四種操作得到
即

if (j>0)f[i][j] = f[i][j] + f[i-1][j] + f[i-1][j-1]; //是白白和白黑兩種情況if (j<n)f[i][j] = f[i][j] + f[i-1][j] + f[i-1][j+1]; //是黑白和黑黑兩種情況

但是

這連樣例都跑不過!!!

沒想到吧

這是為什么呢???

再通過觀察, 可以發(fā)現(xiàn)題目要求的是取出的球的不同順序方案,而在我們的處理中有了很多重復(fù)的
因為它要求的只是順序, 還在序列中的黑白球的數(shù)量并不重要!
所以求出所有的方案數(shù)之后,我們只需將 n=n-1 再跑一遍
然后用第一次的答案減去第二次的答案,就是真正的答案了. (想想為什么)

代碼 (沒有注釋,不要槍斃我)

#include<bits/stdc++.h> using namespace std; #define re register #define ll long long #define get getchar() #define in inline #define db double in int read() {int t=0; char ch=get;while(ch<'0' || ch>'9') ch=get;while (ch<='9' && ch>='0') t=t*10+ch-'0', ch=get;return t; } const int _=3010; const int mod=1e9+7; ll n,m,f[_][_]; int main() {n=read(),m=read();for (re int i=0;i<=n;i++)f[0][i]=1;ll ans=0;for (re int i=1; i<=m; i++)for (re int j=0; j<=n; j++){if(j>0)f[i][j]=(f[i][j]+f[i-1][j-1]+f[i-1][j])%mod;if(j<n)f[i][j]=(f[i][j]+f[i-1][j+1]+f[i-1][j])%mod;}for (re int i=0; i<=n; i++) ans=(ans+f[m][i])%mod;ll ans1=0;memset(f,0,sizeof(f));for (re int i=0;i<=n-1;i++)f[0][i]=1;for (re int i=1; i<=m; i++)for (re int j=0; j<=n-1; j++){if(j>0)f[i][j]=(f[i][j]+f[i-1][j-1]+f[i-1][j])%mod;if(j<n-1)f[i][j]=(f[i][j]+f[i-1][j+1]+f[i-1][j])%mod;}for (re int i=0; i<=n-1; i++) ans1=(ans1+f[m][i])%mod;cout<<((ans-ans1)+mod)%mod;return 0; }

嗯, 就這樣,這是蒟蒻的第一篇正式題解了

轉(zhuǎn)載于:https://www.cnblogs.com/yzhx/p/10611041.html

總結(jié)

以上是生活随笔為你收集整理的AtCoder Grand Contest 013D: Piling Up 题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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