其实我现在挺想哭的 ，本来我就不是一个很勤奋的人，之前好几次都有写随笔，每次都半途而废，这次好不容易打了第一题，上午一个手贱按掉了呜呜呜
先讲讲50~60分的做法
思路：（标签：搜索）
1.有推理可知，要知道一整个队伍的得分情况，我们需要知道1+2+……+n（即n(n-1)/2）次队伍之间的得分情况，那么我们所有搜索的对象也就出来了，就是每个队伍和他的编号后面的队伍的比赛情况
2.我们枚举每次得分，将其记录，当搜索了这么多队伍时，我们就可以check一下，看符不符合，不符合就回溯
tips：在给队伍编号前sort一下(虽然我不知道为什么)，这可以减少你T掉的点
再来讲讲100分的做法（from GQL）
思路：（标签：记忆化搜索+剪枝）
1.剪枝技巧:
我们可以用数学方法计算出它胜利的场数和平局场数(这个条件可以用来剪枝),然后根据枚举是否满足条件,再去搜索下一
还有一个,就是在每次确定一个时,检验它是不是可行
e.g
如果这个数确定后,在胜利场数允许的情况下,后面所有场数都赢也无法达到相应的分数,那么我们就要return
2.记忆化
记忆化的话我们可以用map,我们记录每一个之前已经搜到过的可行情况,由于情况太多,我们要用hash储存,然后由于map有find功能,我们可以在其中寻找我们是否记录过这个值.
如果记录过就返回相应的值;
如果没有的话,我们就要继续搜下去,去寻找答案.
3.搜索
搜索的话我们可以采用四个变量进行传递,两个用来记录PK的队伍,一个用来记录赢的场数,一个用来记录平局的场数
代码的话我主要是多打了注释(代码大部分都是借鉴来的~~~~(>_<)~~~~,我就不说是借鉴GQL的了)
#include<bits/stdc++.h> using namespace std; int n,m,tot,sum,aver,wnn; int cs[100]; map<int,int> hs; const int P=28,Mod=1e9+1,N=11; int now[N],ned[N]; int scan() { int as=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') { as=(as<<3)+(as<<1)+c-'0'; c=getchar(); } return as; } inline bool cmp(int a,int b){return a>b;}; int dfs(int x,int y,int w,int p)//x,y代表哪个队对哪个队，w代表赢的场数， //p代表平局的场数 { int str=0,ans=0; if(x==n) return 1; if(now[x]+3*(n-y+1)<cs[x]) return 0;//也算一个剪枝 if(y>n) { for(int i=x+1;i<=n;i++) { ned[i]=cs[i]-now[i]; } sort(ned+x+1,ned+n+1,cmp);//再次排序 for(int i=x+1;i<=n;i++) { str=str*P+ned[i];//hash } if(hs.find(str)!=hs.end()) return hs[str];//如果搜到了,就不返回 //end,如果没有,则返 //回end如果是出现过的,说明 //之前就搜到了这种情 //况了,直接加上就好了 return hs[str]=dfs(x+1,x+2,w,p); } if(now[x]<cs[x]&&now[y]<cs[y]&&p<aver)++now[x],++now[y],ans+=dfs(x,y+1,w,p+1),--now[x],--now[y]; if(now[x]+3<=cs[x]&&w<wnn) now[x]+=3,ans+=dfs(x,y+1,w+1,p),now[x]-=3; if(now[y]+3<=cs[y]&&w<wnn) now[y]+=3,ans+=dfs(x,y+1,w+1,p),now[y]-=3; return ans%Mod; } int main() { n=scan(); tot=n*(n-1)/2; for(int i=1;i<=n;i++) { sum+=(cs[i]=scan()); } wnn=sum-tot*2;aver=tot-wnn;//设简便的为X，求出它的值 sort(cs+1,cs+n+1,cmp); printf("%d ",dfs(1,2,0,0)); return 0; }