自动搬运

查看原文

来自洛谷，原作者为

	BJpers2 **

搬运于2025-08-24 21:46:44，当前版本为作者最后更新于2018-10-04 20:50:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑最暴力的方法，我们依次枚举$n(n-1)/2$场比赛的结果，按照$1V2,1V3...1Vn,2V3...2Vn...n-1Vn$d的顺序枚举。最后判断解是否可行

接下来上剪枝

剪枝们：

1. 考虑到最后再来判太浪费，索性在搜索时就限制每人的得分不超过总分。

2. 如果对于一个人u来说，他赢下所有以后的比赛也打不出自己的总分，剪枝。（最后分数也需等于总分）

3. 以上两条剪枝都是很弱智的。考虑$Sx$表示分出胜负的总场数，$Sy$表示平局的总场数,$Su$表示所有队总得分。那么显然有：$$Sx+Sy=n(n-1)/2$$且$$3Sx+2Sy=Su$$ 由此可以解出$Sx$,$Sy$。在搜索时，在可利用其限制胜利场次。

4. 此题中心方法楼上已经说的很清楚了，大致利用的是人数为$X$,分数集合为$A[]$的比赛方案数一定，它与某人具体的得分是无关的。因此可以利用记忆化搜索（这好像不能叫剪枝）。把最后几个人剩余的分数哈希起来存就好了。

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef unsigned long long ll;
const ll B=28,P=1e9+7;
const int N=1000;
int n,a[N],b[N],s[N],su,sx,sy; 
map<ll,ll>h;
bool cmp(int x,int y){return x>y;}
ll dfs(int u,int v){
	ll ret=0;
	if(u==n) return 1;
	if(a[u]+3*(n-v+1)<s[u]) return 0;//保证u打满了总分
	if(v>n){
		FOR(i,u+1,n) b[i]=s[i]-a[i];
		sort(b+u+1,b+n+1);
		ll sta=0;
		FOR(i,u+1,n) sta=sta*B+b[i];//hash
		if(h.find(sta)!=h.end()) return h[sta];
		else return h[sta]=dfs(u+1,u+2);
	}
	if(a[u]+3<=s[u] && sx) 
		a[u]+=3,sx--,ret+=dfs(u,v+1),a[u]-=3,sx++; //u win
	if(a[u]+1<=s[u] && a[v]+1<=s[v] && sy) 
		a[u]++,a[v]++,sy--,ret+=dfs(u,v+1),a[u]--,a[v]--,sy++;//draw
	if(a[v]+3<=s[v] && sx) 
		a[v]+=3,sx--,ret+=dfs(u,v+1),a[v]-=3,sx++;//v win
	return ret%P;
}//一场u-v的比赛 
int main(){
	scanf("%d",&n);
	FOR(i,1,n) scanf("%d",&s[i]),su+=s[i];
	sx=su-n*n+n;sy=(su-3*sx)>>1;//算出sx,sy
	sort(s+1,s+n+1,cmp);
	printf("%lld",dfs(1,2)%P);
}