07.07NOIP模拟赛
考中
考试时不知道自己在想啥。。
拿到第一题：woc组合数学，第二题：woc组合数学，第三题，woc组合数学。
然后开始认真读题……
我tm真是闲的。。。
第一题是15年山东省选题，感觉暴力搜索都没法打。一秒pass掉。
（吹一波天皇大神，天皇想出正解少打一个if语句45分，赛后加上秒A。
天皇大神级人物！）
看起来第二题是个软柿子，捏捏看。
然后手折了……눈_눈
后来一查，第二题是APIO2016……我……眼瞎了。
打了两个小时的第二题，最后只打出来一个dfs。
开始想的是dp，但状态转移方程推崩了。（好吧我连状态表示都没想出来。。。）TLE0。
第三题放棋子想了二十分钟，码了个暴力（连暴力都算不上）然后连样例都没测就交了。
完了这把凉了
还剩半小时，开始打第一题。
又读了一边题，脑海里灵光一现，蹦出一个名词：逆序对。
然后我就想怎么求逆序对。
树状数组好像能求，但是谁还记得咋打……
然后我就打了归并排序 /糊脸
竟然输出了样例真是意料之外。
撇了一眼其他人，看见富豪大神正在交代码，我就顺手提交了第一题，
正准备把另外两道题交上去，
考试结束了……woc我只交了一道题……
赶紧交另外两道题，发现就第一题拿了5分。
我真tm走了*运……
我还是太弱了啊啊啊
第一名64分。鲁迅：救救孩子……
好吧。老师你够狠。。。
改题去……
改题
新专题开了。我放弃了继续改题……我不是好孩子
T1：[SDOI2015]排序
好题……一道我连暴力都不会打的好题……（我还是太菜了啊QAQ）
好吧一开始看错题了……以为T2是水题只给T1剩下了不到30分钟。
dfs加判定（类似于二分？？）
详细题解不说了网上有（懒）
就是说一说改题的历程。
我的八个swap参数写错位卡了我一个多小时……
没别的了……（我就是这么菜鸡）
为了清晰我甚至加了分界线……
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define int long long using namespace std; int n,a[4500],fac[4500],f2[15]; int ans=0; inline bool check(int x,int k) { for(register int i=1;i<f2[k];i++) if(a[x+i]!=a[x+i-1]+1) return 0; return 1; } inline void swp(int x,int y,int l) { for(register int i=0;i<l;++i) swap(a[x+i],a[y+i]); return ; } inline void dfs(int x,int now)//n^x { int h=0,hh=0; if(x==n+1){ans+=fac[now];return ;} for(register int i=1;i<=f2[n];i+=f2[x])//i即位置 if(!check(i,x)) { if(!h)h=i; else if(!hh)hh=i; else return ; } if(!h&&!hh)dfs(x+1,now); else if(h&&!hh)//有一个不合法，交换它下辖的两个段 { swp(h,h+f2[x-1],f2[x-1]); dfs(x+1,now+1); swp(h,h+f2[x-1],f2[x-1]); } else//两个不合法，交换四次尝试行不行 { swp(h,hh,f2[x-1]); if(check(h,x)&&check(hh,x)) dfs(x+1,now+1); swp(h,hh,f2[x-1]); /*-------------交-换-分-界-线------------------*/ swp(h,hh+f2[x-1],f2[x-1]); if(check(h,x)&&check(hh,x)) dfs(x+1,now+1); swp(h,hh+f2[x-1],f2[x-1]); /*-------------交-换-分-界-线------------------*/ swp(h+f2[x-1],hh,f2[x-1]); if(check(h,x)&&check(hh,x)) dfs(x+1,now+1); swp(h+f2[x-1],hh,f2[x-1]); /*-------------交-换-分-界-线------------------*/ swp(h+f2[x-1],hh+f2[x-1],f2[x-1]); if(check(h,x)&&check(hh,x)) dfs(x+1,now+1); swp(h+f2[x-1],hh+f2[x-1],f2[x-1]); } } inline void getchart() { fac[0]=fac[1]=f2[0]=1; for(register int i=2;i<=12;++i) fac[i]=fac[i-1]*i; for(register int i=1;i<=12;++i) f2[i]=f2[i-1]*2; return ; } signed main() { scanf("%lld",&n); getchart(); for(register int i=1;i<=(1<<n);++i) scanf("%lld",&a[i]); dfs(1,0); cout<<ans<<endl; }
T3：[CQOI]放棋子
错在没特判。
多谢wba巨佬提供的优质题解！
就是没看清所谓的小容斥部分。
g数组的转移不能由它本身转移而来……
我……是*吧……
真tm五颜六色
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #define mod 1000000009 using namespace std; long long g[35][35][1005],f[35][35][15],a[15]; long long C[1005][1005]; long long n,m,c; long long ms=0; inline void get_g() { C[0][0]=1; for(register int i=1;i<=n*m;++i) { C[i][0]=1; for(register int j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; } for(register int k=1;k<=c;++k) for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) { if(a[k]>i*j)continue; long long cnt=0; for(register int l=1;l<=i;++l) { for(register int r=1;r<=j;++r) { if(l<i||r<j) { cnt+=g[l][r][a[k]]*C[i][l]%mod*C[j][r]%mod; cnt%=mod; } } } g[i][j][a[k]]=(C[i*j][a[k]]-cnt+mod)%mod; } return ; } int main() { scanf("%lld %lld %lld",&n,&m,&c); for(register int i=1;i<=c;++i) { scanf("%lld",&a[i]); // ms=ms<a[i]?a[i]:ms; } if(c>min(n,m)) { cout<<"0"<<endl; return 0; } // cout<<ms<<endl; get_g(); // for(register int i=1;i<=n;++i) // for(register int j=1;j<=m;++j) // for(register int k=1;k<=c;++k) // cout<<g[i][j][a[k]]<<endl; f[0][0][0]=1; for(register int k=1;k<=c;++k) for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) for(register int l=0;l<i;++l) for(register int r=0;r<j;++r) { f[i][j][k]+=((((f[l][r][k-1]*C[n-l][i-l]%mod)*C[m-r][j-r])%mod)*g[i-l][j-r][a[k]])%mod; //(f[i][j][k]+=C[n-l][i-l]*C[m-r][j-r]%mod*f[l][r][k-1]%mod*g[i-l][j-r][a[k]]%mod)%=mod; f[i][j][k]%=mod; // cout<<f[i][j][k]<<endl; } long long ans=0; for(register int i=1;i<=n;++i) for(register int j=1;j<=m;++j) ans=(ans+f[i][j][c])%mod; cout<<(ans+mod)%mod<<endl; return 0; }