程序猿的垃圾桶

How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We're assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + ... + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.

• in each test case there is exactly one best player and at least one second best player,
• each weekly ranking consists of M distinct player identifiers.

1. At the beginning of the game, the player picks K stones and puts them all in one bucket.
2. At each step of the game, the player can pick one stone from the bucket and put it on any empty leaf.
3. When all of the r immediate children of a node p each has one stone, the player may remove all of these r stones, and put one of the stones on p. The other r - 1 stones are put back into the bucket, and can be used in the later steps of the game.

#include<iostream>
using namespace std;

struct node{
	int Childnum;
	int* Child;
	int minstone;
};

int CalculateMinStone(int x,node* Array){
	node* cur=Array+x;
	if (cur->Childnum ==0){
		cur->minstone=1;
		return 1;
	}

        int i;

	for (i=0;i<cur->Childnum;i++){
		if(Array[cur->Child[i]].minstone==-1)
			Array[cur->Child[i]].minstone=CalculateMinStone(cur->Child[i],Array);
	}
	int* temp=new int[cur->Childnum+5];
	for (i=0;i<cur->Childnum;i++){
		temp[i]=Array[cur->Child[i]].minstone;
	}
	int t;
	for(i=0;i<cur->Childnum;i++){
		int largest=i;
		for(int j=i+1;j<cur->Childnum;j++){
			if (temp[largest]<temp[j]){
				largest=j;
			}
		}			
		t=temp[largest];
		temp[largest]=temp[i];
		temp[i]=t;
	}
	int max=temp[0];
	for (i=1;i<cur->Childnum;i++){
		if (temp[i]+i>max){
			max=temp[i]+i;
		}
	}
	return max;
}

int main(){
	int time;
	node *Array;
	cin>>time;
	while(time--){
		int n;
		int x,NumOfChild;
		scanf("%d",&n);
		Array=new node[n+5];
		int i,j;
		for(i=0;i<n;i++){
			cin>>x>>NumOfChild;
			Array[x].Childnum=NumOfChild;
			Array[x].Child=new int[NumOfChild+5];
			for (j=0;j<NumOfChild;j++){
				cin>>Array[x].Child[j];
			}
			Array[x].minstone=-1;
		}
		cout<<CalculateMinStone(1,Array)<<endl;
	}
	return 0;
}

#include<iostream>
using namespace std;
const int maxS=1000+1;
int Matrix[maxS][maxS];
int sum=0;
int n;
int Temp[maxS];
bool b[maxS];

void PrimBuild()
{
	int max,j,index,i;
	memset(b,0,n);
	b[0]=1;

	for(i=0;i<n;i++){
		if(Matrix[0][i]!=-1)
			Temp[i]=Matrix[0][i];
		else
			Temp[i]=-1;
	}
	for(i=0;i<n-1;i++)
	{
		max=-1;
		index=0;
		for(j=1;j<n;j++){
			if(max<Temp[j] && b[j]==0){	//找到与当前树中结点相连的最大的一条边
				index=j;				//记录地址
				max=Temp[j];			//记录长度
			}
		}
		if(Temp[index]==-1){			//没有这样的点，数据有误，跳出
			sum=-1;
			return;
		}
		b[index]=1;				//选定该结点
		sum=sum+max;
		for(j=0;j<n;j++)		//更新Temp数组
		{
			//当且仅当这个结点存在，未被标记过，且有价值（插入后比原先权重大）
			if(Matrix[index][j]!=-1&&b[j]==0&&Matrix[index][j]>Temp[j])
				Temp[j]=Matrix[index][j];
		}
	}
}

int main()
{
	int m,x,y;
	scanf("%d %d",&n,&m);
	int i;
	for(i=0;i<n;i++)
		memset(Matrix[i],-1,n*sizeof(int));
	int temp;
	for(i=0;i<m;i++)		//输入数据		
	{
		scanf("%d %d %d",&x,&y,&temp);
		if (Matrix[x-1][y-1]<temp){
			Matrix[x-1][y-1]=temp;
			Matrix[y-1][x-1]=temp;
		}
	}
	PrimBuild();
	printf("%d\n",sum);
	return 0;
}

    a   a   a   a

   /   /     \   \

  b   b       b   b

 /     \     /     \

c       c   c       c

• Source Code

#include<iostream>
using namespace std;

const int MSoE=12;
const int MAX=40+1;
bool Cake[MAX][MAX]={0};
int SoE[MSoE+1]={0};
int currentmax=MSoE;

int s,nn;
bool sta=0;

void set(int i,int j,int len){
	for (int ii=i;ii<i+len;ii++){
		for (int jj=j;jj<j+len;jj++){
			Cake[ii][jj]=1;
		}
	}
}

void putback(int i,int j,int len){
	for (int ii=i;ii<i+len;ii++){
		for (int jj=j;jj<j+len;jj++){
			Cake[ii][jj]=0;
		}
	}
}

bool check(int i,int j,int len){
	for (int jj=j;jj<len+j;jj++){
		if (Cake[i][jj]==1)return 0;
	}
	return 1;
}

void put(){
	if (nn==0){sta=1;return;}
	int i,j;
	for (i=0;i<s;i++){
		for(j=0;j<s;j++){
			if (Cake[i][j]==0){
				int len=currentmax;
				while(SoE[len]==0){len--;}
				while(len){	
					if(SoE[len]==0||j+len>s||i+len>s||!check(i,j,len)){len--;continue;}
					set(i,j,len);
					SoE[len]--;
					nn--;
					put();
					if (sta==1)return;
					putback(i,j,len);
					SoE[len]++;
					nn++;
					len--;
				}
				if (Cake[i][j]==0)return;
			}
		}
	}
}

int main(){
	int t,n;
	scanf("%d",&t);
	while(t--){
		int i;
		for (i=0;i<s;i++){
			memset(Cake[i],0,s);
		}
		for (i=0;i<MSoE;i++){
			SoE[i]=0;
		}
		currentmax=MSoE;
		scanf("%d %d",&s,&n);
		nn=n;
		int size;
		int space=0;
		while(n--){
			scanf("%d",&size);
			SoE[size]++;
			space+=size*size;
		}
		if (space!=s*s){
			printf("HUTUTU!\n");
			continue;
		}
		while(SoE[currentmax]==0){
			currentmax--;
		}
		put();
		if (sta==1){
			printf("KHOOOOB!\n");
		}		
		else printf("HUTUTU!\n");
		sta=0;
	}
	return 0;
}