散分讨论baidu大赛的题目，先说第三题吧。变态比赛题。
原题：
3.变态比赛规则
为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。
由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。
比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如果是1，2，3一组，4单独一组，那么一共需要打三场比赛: 1 vs 4，2 vs 4，3 vs 4。
很快 W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。
相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。
输入要求：
每行为一组数据，包含两个数字 N, K(0<N<=500, K>=0)。例：
2 0
2 1
3 1
3 2
样例：in.txt
输出要求：
对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K，则输出"YES"，否则输出"NO"（请全部使用大写字母），每组数据占一行。例：
YES
YES
NO
YES
样例：out.txt
看到之前的帖子大家都有了一定的想法，我想改进一下，求n个人所有比赛场次的可能。
自己的一点拙劣想法，大家指正。而且我的想法自己不知道怎么实现。。。汗自己！
f(n) 代表n个人可能形成的比赛次数。
f(1) = {0};
f(2) = {0,1};
f(3) = {0,2,3};
f(4) = {0,3,4,5};
f(5) = {0,4,6,7,8,9,10};
定义一个运算“#”，运算的操作数有2个，都是集合。
设AB都是集合，且都是非负整数集合的子集。
A#B表示从分别从A中取元素a和从B中取b，a+b的所有可能。
例如：{0,1}#{0,2,3} = {0,1,2,3,4};
再定义一个运算~,运算的操作数为一个正整数i和一个集合A，
表示把集合中每一个元素的值都增加i，例如：
{0,2,3}~5 = {5,7,8};
集合的并运算我不好表示，暂时用字母U表示。
返回值是一个集合 f(n)
{
if(n == 1)
return {0};
else
{
if(n == 2)
return {0,1};
else
{
初始化集合result为{0}；//整个N个人都分在1组的时候比赛场数为0
for(int i = 1 ; i <= n/2)
{
定义集合 temp = f(i) # f(n-i)；//分成2大组，一个i个人，另一组n-i个人，两个大组内部可能形成的比赛数为f(i) # f(n-i)
temp = temp ~ (i*(n-i)) ； //一个i个人，另一组n-i个人肯定要形成i*(n-i)场比赛
result = result U temp ;//U表示集合的并
}
return result;
}
}
}
问题点数：40、回复次数：13Top
1 楼boylez（boylez）回复于 2006-06-02 14:34:10 得分 0
顶Top
2 楼mmmcd（超超）回复于 2006-06-02 15:39:12 得分 0
int f[500][80000];
int solve(int n,int k)
{
int r;
if(n<0 || k<0)return -1;
if(f[n][k])return f[n][k];
for(r=0;r<=n;r++)
{
if(k>=0)
{
f[n][k]=solve(n-r,k-r*(n-r));
if(f[n][k]==1)
{
return 1;
}
}
}
f[n][k]=-1;
return -1;
}
if(solve(n,k)==1)printf("YES\n");
else printf("NO\n");Top
3 楼boylez（boylez）回复于 2006-06-02 16:25:22 得分 0
楼上做法不切实际吧，仅仅分配内存就要分配40M个int的空间。首先想想压缩吧Top
4 楼mmmcd（超超）回复于 2006-06-02 23:01:31 得分 0
不给k的上限，有点难办
下面程序姑且能求出某些结果
#include <stdio.h>
char f[500][80000];
int solve(int n,int k)
{
int r;
if(n<0 || k<0)return -1;
if(f[n][k])return f[n][k];
if(k==0){
return f[n][k]=1;
}
for(r=1;r<=n;r++)
{
if(k>=0)
{
f[n][k]=solve(n-r,k-r*(n-r));
if(f[n][k]==1)
{
return 1;
}
}
}
f[n][k]=-1;
return -1;
}
int main(int argc, char* argv[])
{
int n,k;
FILE *fin=fopen(argv[1],"r");
while(fscanf(fin,"%d %d",&n,&k)==2){
if(solve(n,k)==1)printf("YES\n");
else printf("NO\n");
}
return 0;
}Top
5 楼mmmcd（超超）回复于 2006-06-03 08:27:08 得分 0
忘了，前一个下标上限至少501
char f[501][80000];
Top
6 楼qrlvls（ 空 气 ）回复于 2006-06-03 18:23:28 得分 0
baidu也能学人搞大赛，汗一个Top
7 楼boylez（boylez）回复于 2006-06-05 08:49:36 得分 0
ding!暂定上线500吧Top
8 楼mmmcd（超超）回复于 2006-06-05 09:28:15 得分 0
复赛都结束了，数据都还没给出来
//char f[n的上限+1][k的上限+1];
char f[501][501];
http://acm.pku.edu.cn/JudgeOnline/problem?id=1923
http://acm.zju.edu.cn/show_problem.php?pid=2230
Top
9 楼galois_godel（）回复于 2006-06-05 11:45:16 得分 0
k 上限至多为 500*500Top
10 楼boylez（boylez）回复于 2006-06-05 15:31:52 得分 0
楼上说k的上线能到那么大？Top
11 楼volant_hoo（）回复于 2006-06-07 16:33:12 得分 0
贴一段代码：
#include <stdio.h>
int main(int argc, char *argv[])
{
int n, k;
if( argc!=3 )
{
printf("use: %s n k", argv[0]);
return -1;
}
n = atoi(argv[1]);
k = atoi(argv[2]);
if(foo(n, k)>0)
printf("YES\n");
else
printf("NO\n");
return 0;
}
int maxT(int n, int m)
{
if( n<=0 || n>500 || m<=0 )
return -1;
if( m==1 )
return n*(n-1)/2;
if( m>=n || n==1 )
return 0;
return m*(n-m)+(n-m)*(n-m-1)/2;
}
int minT(int n, int m)
{
if( n<=0 || n>500 || m<=0 )
return -1;
if( m==1 )
return n*(n-1)/2;
if( m>=n || n==1 )
return 0;
return m*(n-m)+minT(n-m, m);
}
int foo(int n, int k)
{
int max, min;
int m;
if( n<=0 || n>500 || k<0 || k>n*(n-1)/2 )
return -1;
if( k==0 || k==n-1)
return 1;
if( n==1 || k<n-1 )
return -1;
for( m=n; m>0; m-- )
{
max = maxT(n, m);
min = minT(n, m);
if( k<=max && k>=min )
{
if( foo(n-m, k-m*(n-m))>0 )
return 1;
}
}
return -1;
}
Top
12 楼volant_hoo（）回复于 2006-06-07 16:46:59 得分 0
算法说明：
maxT：取总人数为n，最多人的一组人数m的最多比赛场数
minT：取总人数为n，最多人的一组人数m的最少比赛场数Top
13 楼guileen（松风抚琴）回复于 2006-11-19 18:22:53 得分 0
楼主我支持你，接分Top
