9
24
2012
7

USACO 3.1

 

Section 3.1 DONE 2012.09.20 TEXT Minimal Spanning Trees
DONE 2012.09.20 PROB Agri-Net [ANALYSIS]
DONE 2012.09.21 PROB Score Inflation [ANALYSIS]
DONE 2012.09.23 PROB Humble Numbers [ANALYSIS]
DONE 2012.09.23 PROB Shaping Regions [ANALYSIS]
DONE 2012.09.23 PROB Contact [ANALYSIS]
DONE 2012.09.20 PROB Stamps [ANALYSIS]

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

矩形切割

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

 

 

Category: USACO | Tags: usaco | Read Count: 1127
7 dollar essay revie 说:
2019年9月06日 11:44

Very helpful material for all the people who wanted to become developers they can grab here information about. The data structure subject update pretty informative for the programmers. Keep it up with your good quality updates please do share more.

Jumper Jacket 说:
2019年10月08日 05:20

Articles that have significant and savvy remarks are more agreeable, at any rate to me. It’s fascinating to peruse what other individuals thought and how it identifies with them or their customers, as their point of view could help you later on.

Jumper Jacket 说:
2019年10月08日 05:20

@Jumper Jacket: Articles that have significant and savvy remarks are more agreeable, at any rate to me. It’s fascinating to peruse what other individuals thought and how it identifies with them or their customers, as their point of view could help you later on.

mariakim 说:
2019年10月19日 09:20

I found this blog. Much appreciation to you for offering to us everything considered, find some new data from your post. to a cerebrum boggling degree satisfying and I to an amazing degree like your <a href="https://www.essaysolution.co.uk/write-my-essay">write an essay for me</a>

mariakim 说:
2019年10月19日 09:21

I found this blog. Much appreciation to you for offering to us everything considered, find some new data from your post. to a cerebrum boggling degree satisfying and I to an amazing degree like your [url=https://www.essaysolution.co.uk/write-my-essay]write an essay for me[/url]

 

 

write an essay for m 说:
2019年10月19日 09:22

I found this blog. Much appreciation to you for offering to us  everything considered, find some new data from your post. to a cerebrum boggling degree satisfying and I to an amazing degree like your article a commitment of Thankfulness  is everything

Buy Sheepskin Coat O 说:
2019年10月19日 09:22

Really appreciate this wonderful post that you have provided for us.Great site and a great topic as well i really get amazed to read this. Its really good site able to provide you with the writing help you have been looking for also get result in any time. 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com