首页 > ACM题库 > HDU-杭电 > hdu 2515 Yanghee 的算术-递推-[解题报告]C++
2014
02-09

hdu 2515 Yanghee 的算术-递推-[解题报告]C++

Yanghee 的算术

问题描述 :

Yanghee 是一个小学生。他的数学老师给全班同学布置了一道家庭作业,即根据

一张不超过5000的n(n<50)个正整数组成的数表,两两相加得到n(n-1)/2个和,然后把它们排序。例如,如果数表含有四个数1,3,4,9,那么正确答案是4,5,7,10,12,13。Yanghee 做完作业以后和小伙伴们出去玩了一下午,回家以后发现老师给的数表不见了,可是他算出的答案还在。你能帮助Yanghee根据他的答案计算出原来的数表吗?

输入:

输入第1行是1个正整数N,3<=n<50.然后有若干行,每行10个正整数,共计n(n-1)/2个数. 输入的数据有唯一解.

输出:

输入第1行是1个正整数N,3<=n<50.然后有若干行,每行10个正整数,共计n(n-1)/2个数. 输入的数据有唯一解.

样例输入:

15
3 4 5 6 7 8 9 10 11 12
13 14 15 16 5 6 7 8 9 10
11 12 13 14 15 16 17 7 8 9
10 11 12 13 14 15 16 17 18 9
10 11 12 13 14 15 16 17 18 19
11 12 13 14 15 16 17 18 19 20
13 14 15 16 17 18 19 20 21 15
16 17 18 19 20 21 22 17 18 19
20 21 22 23 19 20 21 22 23 24
21 22 23 24 25 23 24 25 26 25
26 27 27 28 29

样例输出:

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15

#include <iostream>
#include <algorithm>
using namespace std;

int Arr[100];						//Arr means the array
int Sum[2500];						//Sum means the Sum array
int sNum;							//Sum number
int aNum;							//Arr number
bool visited[2500];					//visited[i] means Sum[i] is visited

//to calc a1,a2,a3,before,of course sum1,sum2,sumk is certain,
//visited[1],visited[2],visited[k] is true(be visited)
//memset visited is false

bool isRebuild()
{
	int i, j = 3, v, p;
	for ( i = 4; i <= aNum; ++i )
	{
		while ( j <= sNum && visited[j] )
			++j;
		if( j > sNum )						//all visited
			return true;

		visited[j] = true;
		Arr[i] = Sum[j] - Arr[1];

		for( v = 2; v < i; ++v )
		{
			for ( p = j+1; p <= sNum; ++p )
			{
				if( !visited[p] && Arr[v] + Arr[i] == Sum[p] )
				{
					visited[p] = true;
					break;
				}
			}
			if( p > sNum )
				return false;
		}
	}
	return true;
}
int main()
{
	int i,j;
	while( cin >> aNum )
	{
		sNum = aNum * ( aNum - 1 ) >> 1;
		for( i = 1; i <= sNum; ++i )
			cin >> Sum[i];

		sort( Sum, Sum + sNum );

		for( i = 3; i <= sNum; ++i )
		{
			Arr[1] = ( Sum[1] + Sum[2] - Sum[i] ) >> 1;
			Arr[2] = Sum[1] - Arr[1];
			Arr[3] = Sum[2] - Arr[1];
			if( Arr[2] + Arr[3] != Sum[i] )
				continue;

			memset( visited, false,sizeof(visited) );
			visited[i] = true;

			if( isRebuild() )
			{
				for( j = 1; j <= aNum; ++j )
					cout << Arr[j] << endl;
				break;
			}
		}
	}
}
#include<iostream>
using namespace std;

//visited[i]=true表示sum[i]已经被算过一遍,对于数据量小,
//这种办法省空间,也可以visited[sum[i]],这种数据量小且数据跨度大时费空间

bool visited[10010];
int vex[1000];
int sum[10010];
int vexNum,Num;

/*调用之前需要先算出vex[1],vex[2],vex[3]
	a1+a2=sum1
	a1+a3=sum2
	a2+a3=sumk,3<=k<=Num
visited[i]置为false
其中visited[1]=visited[2]=visited[k]=true*/

bool isRebuild() //判断是否可以重建数表
{
	int index = 3, i, k, p;
	for( i = 4; i<=vexNum; ++i )
	{
		while( index <= Num && visited[index] )//找未被算过的和数(sum),越过已算过的sum
			++index;
		if( index > Num )//所有都已经算出来,返回真
			return true;

		visited[index] = true;
		vex[i] = sum[index] - vex[1]; // 找未被访问过的第一个值

		//判断vex[i]+vex[k]==sum[p]是否成立,2<=k<i,index+1<=p<=Num,如果成立说明ok,否则出错
		for( k = 2; k < i; ++k )
		{
			for( p = index + 1; p <= Num; ++p )
			{
				if ( !visited[p] && vex[k] + vex[i] == sum[p] )
				{
					visited[p] = true;
					break;
				}
			}
			if( p > Num ) //不存vex[i]+vex[k] == sum[p],则说明有两个vex[i],vex[k]之和并不在sum中,出错!
				return false;
		}
	}
	return true;
}
int main()
{
	int i,j;
	while( cin >> vexNum && vexNum != 0 )
	{
		Num = vexNum*(vexNum-1) / 2;
		for(i=1; i<=Num; ++i)
			cin >> sum[i];
		//memset(visited,false,sizeof(bool)*(Num+1));
		//a1+a2=sum1
		//a1+a3=sum2
		//a2+a3=sumk,3<=k<=Num
		for(i=3; i<=Num; ++i)
		{
			vex[1]=(sum[1]+sum[2]-sum[i])/2;
			vex[2]=sum[1]-vex[1];
			vex[3]=sum[2]-vex[1];
			if(vex[2]+vex[3] != sum[i])
				continue;
			memset(visited,false,sizeof(visited));
			visited[i] = true;
			if(isRebuild())
			{
				for(j=1; j<vexNum; ++j)
					cout << vex[j] <<' ';
				cout << vex[j] << endl;
				break;
			}
		/*  else
			{
				cout << "Are you kidding me?" << endl;
			}											*/
		}
	}
}

解题转自:http://blog.csdn.net/linraise/article/details/17243567


  1. 至死不渝?马丹我都不知道你们什么时候发的…无限治疗说是用金山游侠改的,想想看估计CE也行,备不住变速齿轮那会都能改CD。

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  3. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  5. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }