《算法竞赛入门经典训练指南》问题求解常见策略2

9月 16

问题求解常见策略(2)

例题12 组装电脑（Assemble，LA3971，POJ3497）

简单二分

POJ 3497 - Assembleview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

struct prog{
	char type[25];
	char name[25];
	int price;
	int quality;
}com[1010];
bool compare_type(prog a,prog b)
{
	if(strcmp(a.type,b.type)==0)
	{
		if(a.quality==b.quality)
			return a.price<b.price;
		return a.quality<b.quality;
	}
	if(strcmp(a.type,b.type)>0)
		return 1;
	return 0;
}
int com_start[1010];
int com_type;
int n,b;
int erfen(int s,int t)
{
	if(s==t)
		return s;
	int m=(s+t)/2+1;
	int i,j;
	int sum=0;
	for(i=0;i<com_type;i++)
	{
		int less=1000000;
		for(j=com_start[i];j<com_start[i+1];j++)
		{
			if(com[j].quality>=m)
			{
				less=min(less,com[j].price);
			}
		}
		sum+=less;
	}
	if(sum<=b)
		return erfen(m,t);
	else
		return erfen(s,m-1);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int i,j,k;
		scanf("%d%d",&n,&b);
		int max_quality,min_quality;
		max_quality=0;
		min_quality=1000000000;
		for(i=0;i<n;i++)
		{
			scanf("%s%s%d%d",&com[i].type,&com[i].name,&com[i].price,&com[i].quality);
			max_quality=max(max_quality,com[i].quality);
			min_quality=min(min_quality,com[i].quality);
		}
		sort(com,com+n,compare_type);

		com_start[0]=0;
		for(j=1,i=1;i<n;i++)
		{
			if(strcmp(com[i].type,com[i-1].type))
				com_start[j++]=i;
		}
		com_type=j;
		com_start[j]=n;
		printf("%d\n",erfen(min_quality,max_quality));
	}
    return 0;
}

例题13 派（Pie，LA3635，POJ3211）

二分题，和上题类似，注意精度问题

POJ 3211 - Pieview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const double pi=3.14159265359;
const double inf=0.00001;
double area[10005];
int n,f;

double erfen(double s,double t)
{
	double m=(s+t)/2+inf;
	if(fabs(s-t)<inf)
		return s;
	int i,j;
	int sum=0;
	for(i=0;i<n;i++)
	{
		sum+=(int)(area[i]/m);
	}
	if(sum>=f)
		return erfen(m,t);
	else
		return erfen(s,m-inf);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&f);
		f++;
		int i,j;
		double sum=0.0;
		for(i=0;i<n;i++)
		{
			int r;
			scanf("%d",&r);
			area[i]=pi*r*r;
			sum+=area[i];
		}
		printf("%.4lf\n",erfen(0,sum/f));
	}
    return 0;
}

例题14 填充正方形（Fill the Square，Uva11520）

水题

Uva 11520 Fill the Squareview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

char mat[15][15];
int main()
{
	int T,cas=1;
	scanf("%d",&T);
	while(T--)
	{
		int n,i,j;
		scanf("%d",&n);
		memset(mat,'.',sizeof(mat));
		for(i=1;i<=n;i++)
			scanf("%s",mat[i]+1);
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(mat[i][j]=='.')
				{
					for(char c='A';c<='Z';c++)
					{
						if(c!=mat[i][j-1]&&c!=mat[i][j+1]&&c!=mat[i-1][j]&&c!=mat[i+1][j])
						{
							mat[i][j]=c;
							break;
						}
					}
				}
			}
		}
		printf("Case %d:\n",cas++);
		for(i=1;i<=n;i++)
			printf("%s\n",mat[i]+1);
	}
    return 0;
}

例题15 网络（Network，LA3902）

深搜的题，看着白书过的

LA 3902 Networkview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

const int maxn=1000+10;
vector<int>link[maxn],node[maxn];
bool vis[maxn];
int fa[maxn];
int n,s,k;
void init()
{
	for(int i=0;i<=n;i++)
	{
		link[i].clear();
		node[i].clear();
	}
}
void build(int root,int father,int dep)
{
	int i,j;
	fa[root]=father;
	if(link[root].size()==1&&dep>k)
		node[dep].push_back(root);
	for(i=0;i<link[root].size();i++)
	{
		int knode=link[root][i];
		if(knode!=father)
		{
			build(knode,root,dep+1);
		}
	}
}
void dfs(int root ,int fat,int dep)
{
//	cout<<root<<' '<<dep<<endl;
	vis[root]=true;
	if(dep==k)
		return ;
	for(int i=0;i<link[root].size();i++)
	{
		int knode=link[root][i];
		if(knode!=fat)
		{
			dfs(knode,root,dep+1);
		}
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&s,&k);
		int i,j;
		init();
		for(i=1;i<n;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			link[a].push_back(b);
			link[b].push_back(a);
		}
		build(s,-1,0);
		int ans=0;
		zero(vis);
		for(i=n-1;i>k;i--)
		{
			for(j=0;j<node[i].size();j++)
			{
				int knode=node[i][j];
				if(vis[knode])
					continue;

				for(int d=0;d<k;d++)
				{
					knode=fa[knode];
				}

				dfs(knode,-1,0);
				ans++;
			}
		}
		printf("%d\n",ans);
	}
    return 0;
}

例题16 长城守卫（Beijing Guards，LA3177）

二分，当n为偶数时，很容易输出答案，唯一麻烦的就是n为基数的情况，详看白书

LA 3177 Beijing Guardsview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

int n;
const int maxn=100000+10;
int r[maxn];
int erfen(int a,int c)
{
	int b=(a+c)/2;
	if(a==c)
		return a;
	int i,j;
	int left,right;
	left=right=0;
	left=r[0];
	for(i=1;i<n-1;i++)
	{
		if(i%2==0)
		{
			right=b-r[0]-right;
			if(right>r[i])
			{
				right=r[i];
				left=0;
			}
			else
			{
				left=r[i]-right;
			}
		}
		else
		{
			left=r[0]-left;
			if(left>r[i])
			{
				left=r[i];
				right=0;
			}
			else
			{
				right=r[i]-left;
			}
		}
	}
//	cout<<left<<' '<<right<<' '<<b<<endl;
	int all=r[0]+right+r[n-1];
	if(all>b)
	{
		return erfen(b+1,c);
	}
	else
	{
		return erfen(a,b);
	}
}
int main()
{
	while(scanf("%d",&n),n)
	{
		int i,j;
		int l,m;
		for(i=0;i<n;i++)
			scanf("%d",&r[i]);
		if(n==1)
		{
			printf("%d\n",r[0]);
			continue;
		}
		l=m=0;
		for(i=0;i<n;i++)
		{
			l=max(l,r[i]+r[(i+1)%n]);
			m=max(m,3*r[i]);
		}

		if(n%2==0)
		{
			printf("%d\n",l);
		}
		else
		{
			printf("%d\n",erfen(l,m));
		}

	}
    return 0;
}