Baudelaire is Programmer

Agri-Net

最小生成树问题。应用Prim算法或Kruskal算法。

/*
ID: huilong1
LANG: C++
TASK: agrinet
*/
#include<stdio.h>
#include<stdlib.h>

int N;
FILE *fin,*fout;
int map[100][100];
int dist[100];
bool had[100];

int main(){
	fin=fopen("agrinet.in","r");
	fout=fopen("agrinet.out","w");
	fscanf(fin,"%d",&N);
	int i,j;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			fscanf(fin,"%d",&map[i][j]);
	for(i=0;i<N;i++)dist[i]=map[0][i];
	had[0]=true;
	int res=0;
	for(i=1;i<N;i++){
		int min=0x7fffffff;
		int pmin;
		for(j=1;j<N;j++){
			if(!had[j]&&min>dist[j]){
				min=dist[j];
				pmin=j;
			}
		}
		res+=min;
		had[pmin]=true;
		for(j=1;j<N;j++){
			if(had[j])continue;
			if(map[pmin][j]<dist[j])
				dist[j]=map[pmin][j];
		}
	}
	fprintf(fout,"%d\n",res);
	//system("pause");
	return 0;
}

Score Inflation

动态规划，完全背包问题（参见《背包九讲》）。状态转移方程:

dp[n][m]=max{dp[n][m-time(n)]+score(n); dp[n-1][m]}

/*
ID: huilong1
LANG: C++
TASK: inflate
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int dp[10001];
int score[10001];
int time[10001];
int N,M;

int main(){
	int i,j;
	fin=fopen("inflate.in","r");
	fout=fopen("inflate.out","w");
	fscanf(fin,"%d %d",&M,&N);
	for(i=1;i<=N;i++)
		fscanf(fin,"%d %d",&score[i],&time[i]);
	for(j=0;j<=M;j++)dp[j]=0;
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++){
			if(j-time[i]>=0&&dp[j-time[i]]+score[i]>dp[j])
				dp[j]=dp[j-time[i]]+score[i];
		}
	fprintf(fout,"%d\n",dp[M]);
	//system("pause");
	return 0;
}

Humble Numbers

策略是按顺序生成所有Humble Numbers。因为一个humble number必定可由另一个较小humble number乘以S集合中的某素数来生成，我们求第n个humble number时只须用素数试乘然后找出比第n-1个humble number大的那些结果中最小的。参考关键词：二分查找，记录位置。

Shaping Regions

矩形切割问题。

/*
ID: huilong1
LANG: C++
TASK: rect1
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int A,B,N;

typedef struct{
	int ll[2];
	int ur[2];
	int c;
	bool exist;
}Rect;

Rect q[100000];
int tail;
int sum[2501];

int main(){
	fin=fopen("rect1.in","r");
	fout=fopen("rect1.out","w");
	fscanf(fin,"%d %d %d",&A,&B,&N);
	tail=0;
	q[0].c=1;
	q[0].ll[0]=0;
	q[0].ll[1]=0;
	q[0].ur[0]=A;
	q[0].ur[1]=B;
	q[0].exist=true;
	int i,j;
	int ll[2],ur[2],c;
	for(i=0;i<N;i++){
		fscanf(fin,"%d %d %d %d %d",
			&ll[0],&ll[1],&ur[0],&ur[1],&c);
		int newtail=tail;
		for(j=0;j<=tail;j++){
			if(!q[j].exist)continue;
			if(ll[0]>q[j].ur[0]||q[j].ll[0]>ur[0])continue;
			if(ll[1]>q[j].ur[1]||q[j].ll[1]>ur[1])continue;
			int x1,x2;
			int y1,y2;
			x1=ll[0]>q[j].ll[0]?ll[0]:q[j].ll[0];
			x2=ur[0]<q[j].ur[0]?ur[0]:q[j].ur[0];
			y1=ll[1]>q[j].ll[1]?ll[1]:q[j].ll[1];
			y2=ur[1]<q[j].ur[1]?ur[1]:q[j].ur[1];
			if(q[j].ll[0]<x1){
				newtail++;
				q[newtail].exist=true;
				q[newtail].c=q[j].c;
				q[newtail].ll[0]=q[j].ll[0];
				q[newtail].ll[1]=q[j].ll[1];
				q[newtail].ur[0]=x1;
				q[newtail].ur[1]=q[j].ur[1];
			}
			if(q[j].ur[0]>x2){
				newtail++;
				q[newtail].exist=true;
				q[newtail].c=q[j].c;
				q[newtail].ll[0]=x2;
				q[newtail].ll[1]=q[j].ll[1];
				q[newtail].ur[0]=q[j].ur[0];
				q[newtail].ur[1]=q[j].ur[1];
			}
			if(q[j].ll[1]<y1){
				newtail++;
				q[newtail].exist=true;
				q[newtail].c=q[j].c;
				q[newtail].ll[0]=x1;
				q[newtail].ll[1]=q[j].ll[1];
				q[newtail].ur[0]=x2;
				q[newtail].ur[1]=y1;
			}
			if(q[j].ur[1]>y2){
				newtail++;
				q[newtail].exist=true;
				q[newtail].c=q[j].c;
				q[newtail].ll[0]=x1;
				q[newtail].ll[1]=y2;
				q[newtail].ur[0]=x2;
				q[newtail].ur[1]=q[j].ur[1];
			}
			q[j].exist=false;
		}
		newtail++;
		q[newtail].exist=true;
		q[newtail].c=c;
		q[newtail].ll[0]=ll[0];
		q[newtail].ll[1]=ll[1];
		q[newtail].ur[0]=ur[0];
		q[newtail].ur[1]=ur[1];
		tail=newtail;
	}
	for(i=0;i<=tail;i++)
		if(q[i].exist)
			sum[q[i].c]+=(q[i].ur[0]-q[i].ll[0])*(q[i].ur[1]-q[i].ll[1]);
	for(i=1;i<=2500;i++)
		if(sum[i]>0)
			fprintf(fout,"%d %d\n",i,sum[i]);
	return 0;
}

Contact

从01序列中抓取每种长度的片段按二进制求值，哈希到一个数组进行统计。

Stamps

类似完全背包问题，但是对物品总数量有限制。

用dp[n][x]表示前n个面值的邮票凑成x最少要用多少张。

状态转移方程：

dp[n][x]=min{dp[n][x-value(n)]+1; dp[n-1][x]}

/*
ID: huilong1
LANG: C++
TASK: stamps
*/
#include<stdio.h>
#include<stdlib.h>

#define IMPOSSIBLE (201)

FILE *fin,*fout;
int N,K;
int value[51];
unsigned char dp[2000001];

int main(){
	fin=fopen("stamps.in","r");
	fout=fopen("stamps.out","w");
	fscanf(fin,"%d %d",&K,&N);
	int i;
	for(i=1;i<=N;i++)fscanf(fin,"%d",&value[i]);
	dp[0]=0;
	for(i=1;i<=2000000;i++)dp[i]=IMPOSSIBLE;
	int j;
	for(i=1;i<=N;i++)
		for(j=1;j<=2000000;j++)
			if(j-value[i]>=0&&dp[j-value[i]]!=IMPOSSIBLE)
				if(dp[j-value[i]]+1<dp[j]){
					dp[j]=dp[j-value[i]]+1;
					if(dp[j]>K)dp[j]=IMPOSSIBLE;
				}
	for(i=1;i<=2000000;i++)
		if(dp[i]==IMPOSSIBLE)break;
	fprintf(fout,"%d\n",i-1);
	//system("pause");
	return 0;
}

矩形切割

以下出自薛矛神牛的讲义：