AtCoder Grand Contest 013D: Piling Up 题解

题意简化:

[luogu] Piling Up

一开始有n个颜色为黑白的球，但不知道黑白色分别有多少，m次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球，最后拿出的球按顺序排列会形成一个颜色序列，求颜色序列有多少种
n,m小于等于3000 答案对1e9+7取膜

一些乱七八糟的东西

这个题还是 Power_Leo101 同学教我做的, 自己太弱了,完全不会
这是菊队ppt里推荐的题, 这个学期过了, 学长们就毕业了, 菊队也不再会给我们讲课了
虽然陈菊开学长讲课的画风毒瘤, ppt毒瘤

题解

对于每一次操作,其实是可以看成一次染色的,因为总数总是不变,而颜色却会变化
所以对于每一次染色,即有四种情况: 嘿嘿 黑黑 , 白白, 黑白,白黑
按照常规思路:
我们不妨设 f[i][j] 表示当前进行第i次操作, 还剩下 j 个白球 (其实颜色没影响)
所以对于每一个当前状态则是可以有之前的状态,通过上面列举的四种操作得到
即

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]; //是黑白和黑黑两种情况

但是

这连样例都跑不过!!!

没想到吧

这是为什么呢???

再通过观察, 可以发现题目要求的是取出的球的不同顺序方案,而在我们的处理中有了很多重复的
因为它要求的只是顺序, 还在序列中的黑白球的数量并不重要!
所以求出所有的方案数之后,我们只需将 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; }

嗯, 就这样,这是蒟蒻的第一篇正式题解了

转载于:https://www.cnblogs.com/yzhx/p/10611041.html

总结

以上是生活随笔为你收集整理的AtCoder Grand Contest 013D: Piling Up 题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。