题目描述：
沫沫非常喜欢看足球赛，但因为沉迷于射箭游戏，错过了最近的一次足球联赛。此次联 赛共N支球队参加，比赛规则如下：
(1) 每两支球队之间踢一场比赛。 (2) 若平局，两支球队各得1分。
(3) 否则胜利的球队得3分，败者不得分。 尽管非常遗憾没有观赏到精彩的比赛，但沫沫通过新闻知道了每只球队的最后总得分， 然后聪明的她想计算出有多少种可能的比赛过程。
譬如有3支球队，每支球队最后均积3分，那么有两种可能的情况。
请你计算出可能的比赛过程的数目，由于答案可能很大，你只需要输出答案对10^9+7取模的结果。
思路：
整体上：直接枚举每一场比赛，考虑平局和胜败局。最好是从前往后一个一个枚举，每次枚举出两支队伍比赛，这样比较方便。
剪枝或优化：
① 易知，一场胜败局对总分贡献3，所以 已经有的分数+剩余场数*3<总分，剪掉。
② 对于每一支队伍，同样有①。另外，已经有的分数+剩余场数*2>总分，剪掉。
③ 给定总分数后，可以求出总胜局和总平局，小优化。
④ 最主要的一点还是记忆化。考虑到每支队伍的得分情况构成的得分序列与 各队伍的具体情况无关，即顺序随意改变，只要序列一定，方案数一定。
那么我们可以考虑把其记录下来。实现的话用Hash，因为每支队伍最多得27分，所以看成一个28进制数，用 long long 存在map里就好了。
#include<bits/stdc++.h> #define RG register #define IL inline #define LL long long using namespace std; IL int gi () { RG int x=0,w=0; char ch=0; while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();} while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } const int N=11; const int P=28; const int Mod=1e9+7; map<LL,LL> hs; int n,tot,Asc,cntW,cntD,sco[N],now[N],ned[N]; IL bool cmp (int a,int b) {return a>b;} LL dfs (int x,int y,int CW,int CD) { RG LL sta=0; RG int ans=0,i; if (x==n) return 1; if (now[x]+3*(n-y+1)<sco[x]) return 0; if (y>n) { for (i=x+1;i<=n;++i) ned[i]=sco[i]-now[i]; sort (ned+x+1,ned+n+1,cmp); for (i=x+1;i<=n;++i) sta=sta*P+ned[i]; if (hs.find(sta)!=hs.end()) return hs[sta]; return hs[sta]=dfs(x+1,x+2,CW,CD); } if (now[x]<sco[x]&&now[y]<sco[y]&&CD<cntD) ++now[x],++now[y],ans+=dfs(x,y+1,CW,CD+1),--now[x],--now[y]; if (now[x]+3<=sco[x]&&CW<cntW) now[x]+=3,ans+=dfs(x,y+1,CW+1,CD),now[x]-=3; if (now[y]+3<=sco[y]&&CW<cntW) now[y]+=3,ans+=dfs(x,y+1,CW+1,CD),now[y]-=3; return ans%Mod; } int main () { RG int i; n=gi(),tot=n*(n-1)/2; for (i=1;i<=n;++i) Asc+=(sco[i]=gi()); cntW=Asc-tot*2,cntD=tot-cntW; sort(sco+1,sco+n+1,cmp); printf ("%lld ",dfs(1,2,0,0)); return 0; }
题目描述：
给定一个 n*m 的矩形色板，有 k 种不同的颜料，有些格子已经填上了某种颜色，现在 需要将其他格子也填上颜色，使得从左上角到右下角的任意路径经过的格子都不会出现两种 及以上相同的颜色。路径只能沿着相邻的格子，且只能向下或者向右。 计算所有可能的方案，结果对 1000000007 (10^9 + 7)求模。
思路：
n，m的范围很假，其实总共有n+m-1个格子会被经过，那么如果n+m-1>k，就输出0。
那么此时可以注意到，n,m被限制在较小的范围内，直接搜索。
剪枝：
① 如果到了一个点(x,y)，他走到终点的步数(n+m-x-y+1)>剩下的颜色数就可以减掉了。
② 类似记忆化的思想，注意到对于一个点而言，假设还能够填几种 整个棋盘之前没填过的颜色 。
那么于他们而言，不管谁先填，填的方案数是一定的。（注意：这里只对于之前没填过的成立，若之前填过的，则会受其他同颜色的位置的影响）
所以可以记录下来这个值，用于优化。
具体实现注意：因为只有10种颜色，可以用一个二进制数表示某个点可以染的色，再通过一些需要的位运算，取出要取得东西计算就好了。
#include<bits/stdc++.h> #define RG register #define IL inline #define LL long long using namespace std; IL int gi () { RG int x=0,w=0; char ch=0; while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();} while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } const int N=1010; const int Mod=1e9+7; int n,m,k,cnt,used[21],Lg[1<<12],a[N][N],f[20][20]; int dfs (int x,int y) { if (y==m+1) ++x,y=1; if (x==n+1) return 1; RG int i,id,now,fnow,cnt=0,ans=0,res=-1; now=f[x-1][y]|f[x][y-1];fnow=(~now)&((1<<k)-1); for (i=fnow;i;i^=i&(-i)) ++cnt; if (cnt<n+m-x-y+1) return 0; for (i=fnow;i;i^=i&(-i)) { id=Lg[i&(-i)]; if (a[x][y]==0||a[x][y]==id) { ++used[id],f[x][y]=now|(1<<(id-1)); if (used[id]==1) { if (res==-1) res=dfs(x,y+1); ans+=res; } else ans+=dfs(x,y+1); if (ans>=Mod) ans-=Mod; --used[id]; } } return ans; } int main () { int i,j; n=gi(),m=gi(),k=gi(); for (i=1;i<=n;++i) for (j=1;j<=m;++j) a[i][j]=gi(),used[a[i][j]]+=(a[i][j]>0); if (n+m-1>k) {putchar('0'); return 0;} for (i=1;i<=k;++i) Lg[1<<(i-1)]=i; printf("%d ",dfs(1,1)); return 0; }
题目描述：
黑白棋游戏的棋盘由4×4方格阵列构成。
棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。
思路：
感觉DFS其实不好下手（我太菜了），考虑BFS。
注意到其实，棋盘最多也就2^16=65536种不同的局面，所以只接爆搜就好了。
判重方面，可以用一个二进制数存下整个棋盘，直接O(1)的判就好了。。
小优化：上下左右完全没必要，只要两边就好了。
#include<bits/stdc++.h> #define RG register #define IL inline using namespace std; IL int gi () { RG int x=0,w=0; char ch=0; while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();} while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } char str[5]; int ans,To,Head,Tail,Apr[70000],a[5][5],b[5][5]; struct state {int stp,now,pre,dot[2][2];}s[70000],From; IL void Right_move (state x,int numb,int id) { if (id%4==0) return; RG int val=x.now,del,add; add=(((val>>(id-1))&1)<<id)+(((val>>id)&1)<<(id-1)); del=(((val>>(id-1))&1)<<(id-1))+(((val>>id)&1)<<id); val+=add-del; if (Apr[val]) return; Apr[val]=1,s[++Tail]=(state){x.stp+1,val}; s[Tail].pre=numb; s[Tail].dot[0][0]=(id-1)/4+1,s[Tail].dot[0][1]=id%4; s[Tail].dot[1][0]=(id-1)/4+1,s[Tail].dot[1][1]=s[Tail].dot[0][1]+1; } IL void Down_move (state x,int numb,int id) { if (id>12&&id<17) return; RG int val=x.now,del,add; add=(((val>>(id-1))&1)<<(id+3))+(((val>>(id+3))&1)<<(id-1)); del=(((val>>(id-1))&1)<<(id-1))+(((val>>(id+3))&1)<<(id+3)); val+=add-del; if (Apr[val]) return; Apr[val]=1,s[++Tail]=(state){x.stp+1,val}; s[Tail].pre=numb; s[Tail].dot[0][0]=(id-1)/4+1,s[Tail].dot[0][1]=(id%4==0)?4:id%4; s[Tail].dot[1][0]=(id-1)/4+2,s[Tail].dot[1][1]=s[Tail].dot[0][1]; } IL void Qcout (int id) { if (!s[id].pre) return; Qcout(s[id].pre); printf("%d%d%d%d ",s[id].dot[0][0],s[id].dot[0][1],s[id].dot[1][0],s[id].dot[1][1]); } IL void BFS () { Head=Tail=1; s[Tail]=From; while (Head<=Tail) { if (s[Head].now==To) { printf("%d ",s[Head].stp),Qcout(Head); exit(0); } RG int i; for (i=1;i<=16;++i) Right_move(s[Head],Head,i),Down_move(s[Head],Head,i); ++Head; } } int main () { RG int i,j; for (i=1;i<=4;++i) { scanf ("%s",str+1); for (j=1;j<=4;++j) a[i][j]=str[j]^48,From.now|=(a[i][j]<<((i-1)*4+j-1)); } for (i=1;i<=4;++i) { scanf ("%s",str+1); for (j=1;j<=4;++j) b[i][j]=str[j]^48,To|=(b[i][j]<<((i-1)*4+j-1)); } Apr[From.now]=1,BFS(); return 0; }
题目描述：略。
思路：
整体思路：枚举每一个字母对应的数值，依次判断。
剪枝：
① 最高位不能进位。（注意：可以有前导0）
② 对于某一位若三个式子都已经有值，可以直接判断（若(A+B)%n!=C&&(A+B+1)%n!=C，剪掉）。
③ 搜索顺序从上往下，从低位往高位搜，依次枚举。
然后，就差不多了，但不是很快。
#include<bits/stdc++.h> #define RG register #define IL inline using namespace std; IL int gi () { RG int x=0,w=0; char ch=0; while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();} while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } const int N=30; int n,nber[N],used[N]; char A[N],B[N],C[N]; IL bool judgement() { RG int i,ad=0,a,b,c; for (i=n;i>=1;--i) { a=A[i]-'A'+1,b=B[i]-'A'+1,c=C[i]-'A'+1; if (nber[a]!=-1&&nber[b]!=-1&&nber[c]!=-1) { if ((nber[a]+nber[b])%n!=nber[c]&&(nber[a]+nber[b]+1)%n!=nber[c]) return 0; } else continue; } return 1; } void dfs (int x,int y,int ad,int num) { RG int i,a=A[1]-'A'+1,b=B[1]-'A'+1,c=C[1]-'A'+1,res; if (nber[a]!=-1&&nber[b]!=-1&&nber[a]+nber[b]>=n) return; if (!judgement()) return; if (num==n) { for (i=1;i<=n;++i) printf("%d ",nber[i]); exit(0); } if (x==3) { a=A[y]-'A'+1,b=B[y]-'A'+1,c=C[y]-'A'+1; res=(nber[a]+nber[b]+ad)%n; if (nber[c]!=-1) if (res!=nber[c]) return; else dfs(1,y-1,(nber[a]+nber[b]+ad)/n,num); else if (used[res]) return; else { used[res]=1,nber[c]=res; dfs(1,y-1,(nber[a]+nber[b]+ad)/n,num+1); used[res]=0,nber[c]=-1; } } else { if (x==1&&nber[A[y]-'A'+1]!=-1) dfs(x+1,y,ad,num); else if (x==2&&nber[B[y]-'A'+1]!=-1) dfs(x+1,y,ad,num); else for (i=0;i<n;++i) { if (used[i]) continue; if (x==1) nber[A[y]-'A'+1]=i; else nber[B[y]-'A'+1]=i; used[i]=1,dfs(x+1,y,ad,num+1),used[i]=0; if (x==1) nber[A[y]-'A'+1]=-1; else nber[B[y]-'A'+1]=-1; } } } int main () { // freopen ("alpha.in","r",stdin); //freopen ("alpha.out","w",stdout); n=gi(); scanf("%s%s%s",A+1,B+1,C+1); memset (nber,-1,sizeof(nber)); dfs (1,n,0,0); return 0; }
五、P2750 [USACO5.5]贰五语言Two Five
题目描述：
有一种奇怪的语言叫做“贰五语言”。它的每个单词都由A～Y这25个字母各一个组成。但是，并不是任何一种排列都是一个合法的贰五语言单词。贰五语言的单词必须满足这样一个条件：把它的25个字母排成一个5*5的矩阵，它的每一行和每一列都必须是递增的。比如单词ACEPTBDHQUFJMRWGKNSXILOVY，它排成的矩阵如下所示：
A C E P T
B D H Q U
F J M R W
G K N S X
I L O V Y
因为它的每行每列都是递增的，所以它是一个合法的单词。而单词YXWVUTSRQPONMLKJIHGFEDCBA则显然不合法。 由于单词太长存储不便，需要给每一个单词编一个码。编码方法如下：从左到右，再从上到下，可以由一个矩阵的得到一个单词，再把单词按照字典顺序排序。比如，单词ABCDEFGHIJKLMNOPQRSTUVWXY的编码为1，而单词ABCDEFGHIJKLMNOPQRSUTVWXY的编码为2。
现在，你需要编一个程序，完成单词与编码间的转换。
思路 ：
单词转编号：
用一种类似求一个全排列编号的方法——逼近法。
具体而言，对于一个单词比如ACEPTBDHQUFJMRWGKNSXILOVY，那么它肯定在以AB，ACD，ACEF，ACEG...等为前缀的合法的串之后。
因此我们只要 分别求出这些的个数 加起来 的下一个 一定就是答案。
编号转单词：
同样用这种方法：一步步逼近，如果算得的总数已经超过n，则说明当前位已经确定；如果还不足n，说明需要枚举下一个前缀。
具体实现 求固定前缀的合法的串的个数 用记忆化搜索：
令f[a][b][c][d][e]表示第一行填了a个数，第二行填了b个数...第五行填了e个数的总方案。
为什么这样做是对的呢？
我的理解是：因为我们的采取填数的方法是从小到大依次枚举每个字母，且使它满足条件，那么已经填了的都小于没填的。
我们在保证仍然满足条件的前提下，交换已经填的两个字母，那么最终能产生的贡献仍然是之前那么多。这就是我们这里用记忆化来优化的原理。
然后注意下枚举字母填在哪一行时，需保证它的上一行已经填了数。
至于我们需要钦定的前缀，就另开一个数组存一下。我下面的程序应该还是会多跑一些冗余状态的，但还是挺快的。
#include<bits/stdc++.h> #define RG register #define IL inline using namespace std; IL int gi () { RG int x=0,w=0; char ch=0; while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();} while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } char op[2],str[30],ans[30]; int tot,f[6][6][6][6][6]; IL bool Judge(int x,int y) {return (!ans[x+1]||ans[x+1]==y+'A'-1);} int dfs (int a,int b,int c,int d,int e,int Alp) { if (Alp==26) return 1; RG int res=f[a][b][c][d][e]; if (res) return res; if (a<5&&Judge(a,Alp)) res+=dfs(a+1,b,c,d,e,Alp+1); if (b<a&&Judge(b+5,Alp)) res+=dfs(a,b+1,c,d,e,Alp+1); if (c<b&&Judge(c+10,Alp)) res+=dfs(a,b,c+1,d,e,Alp+1); if (d<c&&Judge(d+15,Alp)) res+=dfs(a,b,c,d+1,e,Alp+1); if (e<d&&Judge(e+20,Alp)) res+=dfs(a,b,c,d,e+1,Alp+1); return f[a][b][c][d][e]=res; } void WorkN () { RG int i,id=gi(),num; for (i=1;i<=25;++i) { for (ans[i]='A';;++ans[i]) { memset(f,0,sizeof(f)); num=dfs(0,0,0,0,0,1); if (num>=id) break; id-=num; } } for (i=1;i<=25;++i) printf("%c",ans[i]); } void WorkW () { scanf("%s",str+1); for (RG int i=1,num;i<=25;++i) for (ans[i]='A';ans[i]<str[i];++ans[i]) { memset(f,0,sizeof(f)); num=dfs(0,0,0,0,0,1); tot+=num; } printf("%d ",tot+1); } int main () { scanf("%s",op+1); op[1]=='N'?WorkN():WorkW(); return 0; }
题目描述：略
思路：
IDA*板子。
① 答案不超过15，很明显用迭代加深。
② 每次算出至少还要多少步，若大于剩余步数，剪掉。
#include<bits/stdc++.h> #define RG register #define IL inline using namespace std; IL int gi () { RG int x=0,w=0; char ch=0; while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();} while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } char s[6]; int a[6][6],dx[9]={0,-1,-2,-2,-1,1,2,2,1},dy[9]={0,-2,-1,1,2,2,1,-1,-2}; int b[6][6]= { {0,0,0,0,0,0}, {0,2,2,2,2,2}, {0,1,2,2,2,2}, {0,1,1,0,2,2}, {0,1,1,1,1,2}, {0,1,1,1,1,1} }; IL int A_star () { RG int i,j,cnt=0; for (i=1;i<=5;++i) for (j=1;j<=5;++j) if (a[i][j]!=b[i][j]) ++cnt; return cnt-1; } bool dfs (int x,int y,int dep) { RG int i,nx,ny,Ned=A_star(); if (Ned>dep) return 0; if (!dep) return 1; for (i=1;i<=8;++i) { nx=dx[i]+x,ny=dy[i]+y; if (nx<1||nx>5||ny<1||ny>5) continue; swap(a[nx][ny],a[x][y]); if (dfs(nx,ny,dep-1)) return 1; swap(a[nx][ny],a[x][y]); } return 0; } int main () { RG int i,j,sx,sy,fl,T=gi(); while (T--) { fl=0; memset(a,0,sizeof(a)); for (i=1;i<=5;++i) { scanf("%s",s+1); for (j=1;j<=5;++j) if (s[j]=='*') sx=i,sy=j; else a[i][j]=(s[j]^48)+1; } for (i=1;i<=15&&(!fl);++i) if (dfs(sx,sy,i)) {printf("%d ",i);fl=1;} if (!fl) puts("-1"); } return 0; }