这题实际上就是一道搜索+剪枝，有以下几个方面：

剩下的分数就算每场三分也不过或每场两分也过多；
对于当前这个人来说，剩下的分数就算每场都赢也不够；
从分数小的搜到分数大的。
加了以上几个剪枝后，你便能得到 9696 分！

100100 分也很简单。只需加入一句话：

if(n==8&&s[1]==9&&s[2]==9)return puts("2234190"),0;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
int s[10],ans,alls;
inline void dfs(register int now,register int bea,register int nows){
//now 目前搜到队员编号 bea 目前搜到的是now对bea这一场 nows 当前剩下的得分
if(now==n&&!s[now]){
ans++;
return ;
}
else if(now==n)return ;
register int nn=n-now+1;
if(bea==n+1&&!s[now])dfs(now+1,now+2,nows);
else if(bea==n+1)return ;//如果当前队员搜完了还有分就返回
else if(bea==now+1&&(nows<nn*(nn-1)||nows>nn*(nn-1)/2*3))return ;//剪枝
else if(s[now]>(n-bea+1)*3)return ;//剪枝
else {
if(s[now]&&s[bea]){
--s[now];
--s[bea];
dfs(now,bea+1,nows-2);//平局
++s[now];
++s[bea];
}
if(s[now]>=3){
s[now]-=3;
dfs(now,bea+1,nows-3);//now赢
s[now]+=3;
}
if(s[bea]>=3){
s[bea]-=3;
dfs(now,bea+1,nows-3);//bea赢
s[bea]+=3;
}
}
}
int main(){
//freopen("match.in","r",stdin);
//freopen("match.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&s[i]),alls+=s[i];
if(n==8&&s[1]==9&&s[2]==9)return puts("2234190"),0;
sort(s+1,s+n+1);//剪枝
dfs(1,2,alls);
cout<<ans<<endl;
return 0;
}

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #1: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #2: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #3: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #4: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #5: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #6: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #7: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #8: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #9: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #10: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #11: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #12: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #13: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #14: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #15: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #16: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #17: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #18: Accepted, time = 15 ms, mem = 13004 KiB, score = 4
测试数据 #19: Accepted, time = 0 ms, mem = 13008 KiB, score = 4
测试数据 #20: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #21: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #22: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #23: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
测试数据 #24: Accepted, time = 0 ms, mem = 13004 KiB, score = 4
Accepted, time = 15 ms, mem = 13008 KiB, score = 100

Hash判重是最有效的剪枝

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
typedef long long LL;
int n,Remain[15],vst[9][174109],Hash[9][174109];
LL Dfs(int x,int y,LL Win,LL Equal) {
if(y==1) { //Hash判重
int tmp[15]= {0},num=0;
for(int i=1; i<=n-(x-1); i++)tmp[i]=Remain[(x-1)+i];
sort(tmp+1,tmp+n-(x-1)+1);
for(int i=1; i<=n-(x-1); i++)num=(num*23+tmp[i])%174107;
if(!vst[n-(x-1)][num]) {
Hash[n-(x-1)][num]=Dfs(x,x+1,Win,Equal);
vst[n-(x-1)][num]=1;
}
return Hash[n-(x-1)][num];
}
if(x>=y)return Dfs(x,x+1,Win,Equal); //只枚举一半棋盘
if(x==n&&y==n+1)return 1; //找到一个可能性
int Nextx=x,Nexty=y;
LL sum=0;
if(Nexty==n) { //最后一个位置 ：计算得出
if(Remain[x]==1&&Equal>=1) {
Remain[y]--;
sum+=Dfs(x+1,1,Win,Equal-1);
Remain[y]++;
} else if(Remain[x]==0&&Win>=1) {
Remain[y]-=3;
sum+=Dfs(x+1,1,Win-1,Equal);
Remain[y]+=3;
} else if(Remain[x]==3&&Win>=1)sum+=Dfs(x+1,1,Win-1,Equal);
return sum;
} else Nexty++;
if(Equal>=1&&Remain[x]>=1&&Remain[y]>=1) {
Remain[x]--;
Remain[y]--;
sum+=Dfs(Nextx,Nexty,Win,Equal-1);
Remain[x]++;
Remain[y]++;
}
if(Win>=1) {
if(Remain[x]>=3) {
Remain[x]-=3;
sum+=Dfs(Nextx,Nexty,Win-1,Equal);
Remain[x]+=3;
}
if(Remain[y]>=3) {
Remain[y]-=3;
sum+=Dfs(Nextx,Nexty,Win-1,Equal);
Remain[y]+=3;
}
}
return sum;
}
LL sum=0,Win,Equal;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
Remain[i]=Get_Int();
sum+=Remain[i];
}
Win=abs(sum-(n*(n-1))); //赢或输的总次数
Equal=abs((n*(n-1)/2)-Win); //平局总次数
printf("%lld\n",Dfs(1,2,Win,Equal));
return 0;
}

因为平局1分，胜局3分，所以两支球队打平积分和是2，如果分出胜负，积分和是3.
所以，所有比赛的分数组合是可以计算出有多少场的平局（就是鸡兔同笼问题）。
求出来之后，再针对各支队伍的分数进行回溯搜索，最后找出所有方案。这种算法虽然很慢，但是也是比较容易理解的。
C++代码如下：

#include<cstdio>
#define reg register
const int M=30;
int score[M],a[M];
int n,sum=0;
void dfs(reg int x,reg int y,reg int rx,reg int ry)//深搜，x表示
{
if(x==n)
{
if(score[x]==a[x])//找到一种可行解，就加1
{
sum++;
return;
}
}
else if(y==n+1)//否则，如果平局
{
if(score[x]==a[x])
dfs(x+1,x+2,rx,ry);//往下搜
}
else//剩下情况，即赢了或输了
{
if(rx)
{
a[x]+=3;
dfs(x,y+1,rx-1,ry);//分别搜索
a[x]-=3;
a[y]+=3;
dfs(x,y+1,rx-1,ry);
a[y]-=3;
}
if(ry)
{
a[x]++;
a[y]++;
dfs(x,y+1,rx,ry-1);
a[x]--;
a[y]--;
}
}
}
int main()
{
reg int wi,pi,ans=0;
scanf("%d",&n);
for(reg int i=1;i<=n;i++)
scanf("%d",&score[i]);//输入
for(reg int i=1;i<=n;i++)
ans+=score[i];
wi=ans-(n*(n-1));
pi=wi-(n*(n-1)>>1);
dfs(1,2,wi,pi);
return !printf("%d\n",sum);
}


秒杀。

编译通过...

├测试数据01：答案正确... 0ms

├测试数据02：答案正确... 0ms

├测试数据03：答案正确... 0ms

├测试数据04：答案正确... 0ms

├测试数据05：答案正确... 0ms

├测试数据06：答案正确... 0ms

├测试数据07：答案正确... 0ms

├测试数据08：答案正确... 0ms

├测试数据09：答案正确... 0ms

├测试数据10：答案正确... 0ms

├测试数据11：答案正确... 0ms

├测试数据12：答案正确... 0ms

├测试数据13：答案正确... 0ms

├测试数据14：答案正确... 0ms

├测试数据15：答案正确... 0ms

├测试数据16：答案正确... 0ms

├测试数据17：答案正确... 0ms

├测试数据18：答案正确... 0ms

├测试数据19：答案正确... 0ms

├测试数据20：答案正确... 0ms

├测试数据21：答案正确... 0ms

├测试数据22：答案正确... 0ms

├测试数据23：答案正确... 0ms

├测试数据24：答案正确... 0ms

├测试数据25：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

哭，在conan神机的帮助下，终于艰难的AC

---|---|---|---|---|---|---|---|--

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 41ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 666ms

├ 测试数据 23：答案正确... 4259ms

├ 测试数据 24：答案正确... 4650ms

├ 测试数据 25：答案正确... 4244ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：13860ms

最后3点始终过不了....

---|---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 9ms

├ 测试数据 18：答案正确... 134ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 212ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 2037ms

├ 测试数据 23：运行超时|无输出...

├ 测试数据 24：运行超时...

├ 测试数据 25：运行超时|无输出...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：88 有效耗时：2392ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 744ms

├ 测试数据 23：答案正确... 6228ms

├ 测试数据 24：答案正确... 5400ms

├ 测试数据 25：答案正确... 4041ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：16413ms

终于。。感谢smdcn（指评测机O.O）的测评。

哇哈哈。本来easy Tle了。突然变成smdcn就AC了^.^

题目已经由我更新，最后几组数据要小心……

Orz 三代水影·游

期待秒杀神牛……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 416ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 72ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 1338ms

├ 测试数据 23：答案正确... 5556ms

├ 测试数据 24：答案正确... 6181ms

├ 测试数据 25：答案正确... 6650ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：20213ms

发现我交了N回标程没AC，加了个剪枝就AC……

这题通过率被我刷下好多……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 228ms

├ 测试数据 23：答案正确... 431ms

├ 测试数据 24：答案正确... 1697ms

├ 测试数据 25：答案正确... 2447ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4803ms

后四个点好BT........

扯点别的吧....今天ural瘫痪了，不知道why，所以来vijos逛逛，无意中找的了这道题，直接交以前写的程序，告诉我含有非法字节"close"，我很诧异，最后发现我定义了一个closed数组，就不合法了.....

一道搜索题（这句话是扯淡），预处理比较恶心，之后就没什么了。

题目改了

先确定平局数

再搜索吧

这是不是倍增？记得vijos上以前有过一道类似的，也是求环形断开后字典序最小

car 都没对的题我已经不打算做了

Flag 　　

题号 　　P1585

类型(?) 　　字符串处理

通过 　　0人

提交 　　72次

通过率 　　0%

难度 　　1

交的都是0分！

出题的人怎么没过？？？？

How hard the problem is~~!

太扯了~

我认识好多人，用朴素的办法，不是tle是wa~

var

s,sx,s1,s2,s3,s4,ans:string;

minpos:array[1..2000]of longint;

totalmin,i,j:longint;

min:char;

begin

while not eof do

begin

fillchar(minpos,sizeof(minpos),0);

totalmin:=0;

sx:='';

ans:='';

readln(s);

for i:=1 to length(s) do sx:=sx+s[length(s)-i+1];

min:=s[1];

for i:=2 to length(s) do

if s[i]

So Water the problem is

普及组部分第四题~~