2014
02-09

# Yanghee 的算术

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

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

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;
}											*/
}
}
}

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，也要很久才能得出结果，本人亲测

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;
}