2008 ACM-ICPC世界总决赛试题分析8-11

8

#include<stdio.h>
#include<time.h>
#include<string.h>
#include<utility>
#include<algorithm>
#include<set>
#include<math.h>
#include<stdlib.h>
#include<iostream>
#define X first
#define Y second
using namespace std;
const int MAXN=300110;
const int MAXM=900110;
const long double PI=3.1415926535898;
const long double EPS=1e-9;
typedef pair<long double,long double> Tpoint;
Tpoint a[MAXM][3];
int n;
pair<int,int> b[MAXM];
int f[MAXN],d[MAXN];
long double tmp;

struct Tnode
{
	long double p,v;
	int t,pos;
	inline bool operator==(const Tnode &x)
	{
		return (x.t==t) && (x.pos==pos);
	}
	inline long double value()
	{
		return (p+v*tmp);
	}
};

inline bool operator < (const Tnode &y,const Tnode &x)
{
	return (y.p+y.v*tmp<x.p+x.v*tmp-EPS)||(((fabs(y.p+y.v*tmp-x.p-x.v*tmp)<EPS)&&(y.t<x.t)));
}

inline bool equal(long double x,long double y)
{
	return fabs(x-y)<EPS;

}

int cmp(const void *a,const void *b)
{
	return (*(long double *)a > *(long double *)b ? 1 : -1);
}

inline bool cmp2(const pair<int,int>&x,const pair<int,int>&y)
{
	return a[x.X][x.Y].X<a[y.X][y.Y].X;
}

inline void rorate(Tpoint &a,long double alpha)
{
	long double x,y;
	x=a.X*cos(alpha) - a.Y*sin(alpha);
	y=a.X*sin(alpha) + a.Y*cos(alpha);
	a.X=x;
	a.Y=y;
}

int getf(int p)
{
	if(p==-1)
		return 1;
	else if(d[p]!=-1)
		return d[p];
	else
		return d[p]=getf(f[p])+1;
}


void init()
{
	int i,j,k,l;
	int tx,ty;
	for(i=0;i<n;++i)
		for(j=0;j<3;++j)
		{
			scanf("%d %d",&tx,&ty);
			a[i][j].X=tx;
			a[i][j].Y=ty;
		}
	long double alpha=rand()%30000/30000.0*PI;
	for(i=0;i<n;++i)
	{
		for(j=0;j<3;++j)
			rorate(a[i][j],alpha);
		qsort(a[i],3,sizeof(long double)*2,cmp);
		b[3*i].X=b[3*i+1].X=b[3*i+2].X=i;
		b[3*i].Y=0;
		b[3*i+1].Y=1;
		b[3*i+2].Y=2;
	}
	sort(b,b+3*n,cmp2);
}

void solve()
{
	int i,j,k,l;
	Tnode t1,t2,t3;
	long double td;
	set<Tnode> t;
	set<Tnode> :: iterator i1,i2,i3;
	t.clear();
	bool ok=1;
	memset(f,0xff,sizeof(f));
	for(i=0;ok&&(i<3*n);++i)
	{
		j=b[i].X;
		k=b[i].Y;
		tmp=a[j][k].X;
		if(k==0)
		{
			t1.v=(a[j][1].Y - a[j][0].Y)/(a[j][1].X - a[j][0].X);
			t1.p=a[j][0].Y-a[j][0].X*t1.v;
			t2.v=(a[j][2].Y - a[j][0].Y)/(a[j][2].X - a[j][0].X);
			t2.p=a[j][0].Y-a[j][0].X*t2.v;
			t1.pos=t2.pos=j;
			if(t1.v>t2.v)
			{
				t3=t1;
				t1=t2;
				t2=t3;
			}
			t1.t=0;
			t2.t=1;
			i1=t.lower_bound(t1);
			t3=(*i1);
			if((i1!=t.end())&&equal(t3.value(),t1.value()))
			{
				ok=false;
				break;
			}
			t.insert(t1);
			t.insert(t2);
			i1=t.find(t1);
			if(i1==t.end())
			{
				ok=false;
				break;
			}
			if(i1!=t.begin())
			{
				i1--;
				if(i1->t==1)
					f[j]=f[i1->pos];
				else
					f[j]=i1->pos;
			}
		}
		else if(k==1)
		{
			if((a[j][1].Y-a[j][0].Y)/(a[j][1].X-a[j][0].X)<(a[j][2].Y-a[j][0].Y)/(a[j][2].X-a[j][0].X))
				l=0;
			else
				l=1;
			t1.v=(a[j][1].Y - a[j][0].Y)/(a[j][1].X - a[j][0].X);
			t1.p=a[j][0].Y-a[j][0].X*t1.v;
			t1.pos=j;
			t1.t=l;
			td=t1.value();
			i1=t.find(t1);
			if(i1==t.end())
			{
				ok=false;
				break;
			}
			if(i1!=t.begin())
			{
				i1--;
				t3=(*i1);
				if(td<=t3.value()+EPS)
				{
					ok=false;
					break;
				}
				i1++;
			}
			i1++;
			if(i1!=t.end())
			{
				t3=(*i1);
				if(td>=t3.value()-EPS)
				{
					ok=false;
					break;
				}
			}
			t.erase(t1);
			t1.v=(a[j][2].Y - a[j][1].Y)/(a[j][2].X - a[j][1].X);
			t1.p=a[j][1].Y-a[j][1].X*t1.v;
			t.insert(t1);
		}
		else
		{
			if((a[j][1].Y-a[j][0].Y)/(a[j][1].X-a[j][0].X)>=(a[j][2].Y-a[j][0].Y)/(a[j][2].X-a[j][0].X))
			{
				t1.v=(a[j][2].Y - a[j][0].Y)/(a[j][2].X - a[j][0].X);
				t1.p=a[j][0].Y-a[j][0].X*t1.v;
			}
			else
			{
				t1.v=(a[j][2].Y - a[j][1].Y)/(a[j][2].X - a[j][1].X);
				t1.p=a[j][1].Y-a[j][1].X*t1.v;
			}
			t1.pos=j;
			t1.t=0;
			i2=t.find(t1);
			i1=i2++;
			if((i1==t.end())||(i2==t.end())||(i2->pos!=j)||(i2->t!=1))
			{
				ok=false;
				break;
			}
			td=t1.value();
			i3=i2++;
			t.erase(i3);
			if(i2!=t.end())
			{
				t3=(*i2);
				if(t3.value()<=EPS+td)
				{
					ok=false;
					break;
				}
			}
			i3=i1--;
			if(i3!=t.begin())
			{
				t3=(*i1);
				if(t3.value()>=td-EPS)
				{
					ok=false;
					break;
				}
			}
			t.erase(i3);
		}
	}
	if(!ok)
	{
		printf("ERRORn");
		return;
	}
	int ans=1;
	memset(d,0xff,sizeof(d));
	for(i=0;i<n;++i)
		ans=max(ans,getf(i));
	printf("%d shadesn",ans);
}

int main()
{
	srand(time(NULL));
	int CASE=0;
	while((scanf("%d",&n)!=EOF)&&(n!=-1))
	{
		init();
		printf("Case %d: ",++CASE);
		solve();
	}
	return 0;
}

9

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct info
{
	int P;
	int next[26];
};
const int MaxN=25;
const int MaxM=10;
const int MaxL=10;
const int MaxOut=42;
char word[MaxM][MaxL+1],list[MaxOut+1][MaxN+1];
long long ans,list_num;
int cases,n,m,c,sum;
info prefix[MaxM*MaxL+1];
long long f[MaxN+1][1<<MaxM][MaxM*MaxL+1];
int tmp[MaxOut+1];
void refresh(int x)
{
	memset(prefix[x].next,0,sizeof(prefix[x].next));
	prefix[x].P=0;
}

int check(int s)
{
	int i,now;
	now=1;
	for(i=s;i<=tmp[0];i++)
		if(prefix[now].next[tmp[i]]>0)
			now=prefix[now].next[tmp[i]];
		else
			return 0;
	return now;
}

void work(int x)
{
	int i,j,k;
	tmp[0]++;
	for(i=0;i<26;i++)
		if(prefix[x].next[i]>0)
		{
			tmp[tmp[0]]=i;
			work(prefix[x].next[i]);
		}
		else
		{
			tmp[tmp[0]]=i;
			for(j=1;j<=tmp[0]+1;j++)
			{
				k=check(j);
				if(k!=0)
				{
					prefix[x].next[i]=k;
					break;
				}
			}
		}
		tmp[0]--;
}

bool cmp(int x,int y)
{
	return (strcmp(list[x],list[y])<0);
}

void rework(int Len,int l,int now)
{
	int i,L,k;
	if(f[Len][l][now]==0)
		return;
	if(Len==0)
	{
		list_num++;
		for(i=0;i<n;i++)
			list[list_num][i]=tmp[i+1]+'a';
		list[list_num][n]='';
		return;
	}
	for(L=0;L<26;L++)
		for(i=1;i<=sum;i++)
			if(prefix[i].next[L]==now)
			{
				tmp[Len]=L;
				rework(Len-1,l,i);
				if(prefix[now].P)
					rework(Len-1,l-(1<<(prefix[now].P-1)),i);
			}
}


bool init()
{
	int i,j,k,now,l,t;
	scanf("%d %d",&n,&m);
	if(n==0)
		return true;
	for(i=1;i<=m;i++)
		scanf("%s",word[i]);
	for(i=m;i>=1;i--)
		for(j=1;j<=m;j++)
			if(strlen(word[j])>=strlen(word[i])&&i!=j)
			{
				for(k=0;k<=strlen(word[j]-strlen(word[i]));k++)
				{
					t=0;
					for(l=0;word[i][l]!='';l++)
						if(word[i][l]!=word[j][l+k])
							t=1;
					if(t==0)
						break;
				}
				if(t==0)
				{
					for(k=i+1;k<=m;k++)
					{
						for(l=0;'a'<=word[k][l]&&word[k][l]<='z';l++)
							word[k-1][l]=word[k][l];
						word[k-1][l]='';
					}
					m--;
					break;
				}
			}
			sum=1;refresh(1);
			for(i=1;i<=m;i++)
			{
				now=1;
				for(j=0;'a'<=word[i][j]&&word[i][j]<='z';j++)
				{
					if(prefix[now].next[word[i][j]-'a']==0)
					{
						sum++;
						refresh(sum);
						prefix[now].next[word[i][j]-'a']=sum;
					}
					now=prefix[now].next[word[i][j]-'a'];
				}
				prefix[now].P=i;
			}
		tmp[0]=0;
		work(1);
		memset(f,0,sizeof(f));
		f[0][0][1]=1;
		return false;
}

void DP()
{
	int i,j,k,c;
	for(i=0;i<n;i++)
		for(j=0;j<(1<<m);j++)
			for(k=1;k<=sum;k++)
				if(f[i][j][k])
					for(c=0;c<26;c++)
						f[i+1][j|(1<<(prefix[prefix[k].next[c]].P-1))][prefix[k].next[c]]+=f[i][j][k];
}

void write()
{
	int i;
	ans=0;
	for(i=1;i<=sum;i++)
		ans+=f[n][(1<<m)-1][i];
	printf("Case %d: %lld suspectsn",++cases,ans);
	if(ans<=MaxOut)
	{
		list_num=0;
		for(i=1;i<=sum;i++)
			if(f[n][(1<<m)-1][i]>0)
				rework(n,(1<<m)-1,i);
		for(i=1;i<=ans;i++)
			tmp[i]=i;
		sort(tmp+1,tmp+ans+1,cmp);
		for(i=1;i<=ans;i++)
			printf("%sn",list[tmp[i]]);
	}
}

int main()
{
	while(1)
	{
		if(init())
			break;
		DP();
		write();
	}
	return 0;
}

10

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=111;
const int maxpoints=11111;
const double eps=1e-9;
int n,i,j,points,id[maxpoints],cases;
double x[maxn],h[maxn],b[maxn],point[maxpoints],left,right,mid,top,side,k,height,len;

void addpoints(double z)
{
	point[points]=z;
	id[points]=points;
	points++;
}

void cross(double xa,double xb,double yb,double xc,double xd,double yd)
{
	double va,vc,t;
	va=(xb-xa)/yb;vc=(xd-xc)/yd;
	if(fabs(va-vc)<1e-9)
		return;
	t=(xc-xa)/(va-vc);
	if(t>0&&t<yb&&t>yd)
		addpoints(xa+va*t);
}

bool cmp(int i,int j)
{
	return point[i]<point[j];
}

int main()
{
	while(scanf("%d",&n)&&n)
	{
		points=0;
		for(i=0;i<n;i++)
		{
			scanf("%lf%lf%lf",&x[i],&h[i],&b[i]);
			b[i]/=2;
			addpoints(x[i]-b[i]);
			addpoints(x[i]);
			addpoints(x[i]+b[i]);
			for(j=0;j<i;j++)
			{
				cross(x[i]-b[i],x[i],h[i],x[j]-b[j],x[j],h[j]);
				cross(x[i]+b[i],x[i],h[i],x[j]-b[j],x[j],h[j]);
				cross(x[i]-b[i],x[i],h[i],x[j]+b[j],x[j],h[j]);
				cross(x[i]+b[i],x[i],h[i],x[j]+b[j],x[j],h[j]);
			}
		}
		sort(id,id+points,cmp);
		len=0;
		for(i=1;i<points;i++)
		{
			left=point[id[i-1]];
			right=point[id[i]];
			mid=(left+right)/2;
			if(right-left>eps)
			{
				top=-2;
				for(j=0;j<n;j++)
				{
					side=x[j]-b[j];
					if(side<mid&&x[j]>mid)
					{
						height=h[j]*(mid-side)/b[j];
						if(height>top)
						{
							top=height;
							k=h[j]/b[j];
						}
					}
					side=x[j]+b[j];
					if(x[j]<mid&&side>mid)
					{
						height=h[j]*(side-mid)/b[j];
						if(height>top)
						{
							top=height;
							k=h[j]/b[j];
						}
					}
				}
				if(top>-1)
					len+=(right-left)*sqrt(1+k*k);
			}
		}
		printf("Case %d: %dnn",++cases,((int)((len+0.5)*10))/10);
	}
	return 0;
}

11

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct info
{
	int x,y,kind,T;
};

const int MaxN=100;
const int MaxM=100;
const int change[4][2]={1,0, 0,1, -1,0, 0,-1};
int n,m,i,j,k,sum,cases;
info st,ed,s;
info heap[5*MaxN*MaxM];
int position[MaxN+1][MaxM+1][5];
int Time[MaxN+1][MaxM+1][4];

void up(int x)
{
	int k;
	while(x>1&&heap[x].T<heap[x/2].T)
	{
		k=x/2;
		heap[0]=heap[k];
		heap[k]=heap[x];
		heap[x]=heap[0];
		position[heap[k].x][heap[k].y][heap[k].kind]=k;
		position[heap[x].x][heap[x].y][heap[x].kind]=x;
		x=k;
	}
}

void down(int x)
{
	int k;
	while((x+x<=sum&&heap[x+x].T<heap[x].T)||(x+x<sum&&heap[x+x+1].T<heap[x].T))
	{
		if(x+x==sum||heap[x+x].T<heap[x+x+1].T)
			k=x+x;
		else
			k=x+x+1;
		heap[0]=heap[k];
		heap[k]=heap[x];
		heap[x]=heap[0];
		position[heap[k].x][heap[k].y][heap[k].kind]=k;
		position[heap[x].x][heap[x].y][heap[x].kind]=x;
		x=k;
	}
}

bool init()
{
	scanf("%d %d %d %d %d %d",&n,&m,&st.x,&st.y,&ed.x,&ed.y);
	if(n==0)
		return true;
	memset(heap,0,sizeof(heap));
	memset(Time,0,sizeof(Time));
	memset(position,0,sizeof(position));
	for(i=1;i<=n;i++)
	{
		for(j=1;j<m;j++)
		{
			scanf("%d",&k);
			Time[i][j][1]=Time[i][j+1][3]=k;
		}
		if(i<n)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&k);
				Time[i][j][0]=Time[i+1][j][2]=k;
			}
	}
	return false;
}

int main()
{
	cases=0;
	while(true)
	{
		if(init())
			break;
		sum=1;
		position[st.x][st.y][4]=1;
		heap[1].x=st.x;
		heap[1].y=st.y;
		heap[1].kind=4;
		heap[1].T=0;
		while(sum>0)
		{
			if(heap[1].x==ed.x&&heap[1].y==ed.y&&heap[1].kind==4)
				break;
			if(heap[1].kind==4)
			{
				for(i=0;i<4;i++)
					if(Time[heap[1].x][heap[1].y][i]!=0)
					{
						s.x=heap[1].x+change[i][0];
						s.y=heap[1].y+change[i][1];
						s.T=heap[1].T+Time[heap[1].x][heap[1].y][i]*2;
						s.kind=4;
						if(position[s.x][s.y][s.kind]==0)
						{
							sum++;
							heap[sum]=s;
							position[s.x][s.y][s.kind]=sum;
							up(sum);
						}
						else if(position[s.x][s.y][s.kind]>0)
						{
							k=position[s.x][s.y][s.kind];
							if(heap[k].T>s.T)
							{
								heap[k].T=s.T;
								up(k);
							}
						}
						s.kind=i;
						if(position[s.x][s.y][s.kind]==0)
						{
							sum++;
							heap[sum]=s;
							position[s.x][s.y][s.kind]=sum;
							up(sum);
						}
						else if(position[s.x][s.y][s.kind]>0)
						{
							k=position[s.x][s.y][s.kind];
							if(heap[k].T>s.T)
							{
								heap[k].T=s.T;
								up(k);
							}
						}
					}
			}
			else if(Time[heap[1].x][heap[1].y][heap[1].kind]!=0)
			{
				s.x=heap[1].x+change[heap[1].kind][0];
				s.y=heap[1].y+change[heap[1].kind][1];
				s.kind=4;
				s.T=heap[1].T+Time[heap[1].x][heap[1].y][heap[1].kind]*2;
				if(position[s.x][s.y][s.kind]==0)
				{
					sum++;
					heap[sum]=s;
					position[s.x][s.y][s.kind]=sum;
					up(sum);
				}
				else if(position[s.x][s.y][s.kind]>0)
				{
					k=position[s.x][s.y][s.kind];
					if(heap[k].T>s.T)
					{
						heap[k].T=s.T;
						up(k);
					}
				}
				s.kind=heap[1].kind;
				s.T=heap[1].T+Time[heap[1].x][heap[1].y][heap[1].kind];
				if(position[s.x][s.y][s.kind]==0)
				{
					sum++;
					heap[sum]=s;
					position[s.x][s.y][s.kind]=sum;
					up(sum);
				}
				else if(position[s.x][s.y][s.kind]>0)
				{
					k=position[s.x][s.y][s.kind];
					if(heap[k].T>s.T)
					{
						heap[k].T=s.T;
						up(k);
					}
				}
			}
			position[heap[1].x][heap[1].y][heap[1].kind]=-1;
			heap[1]=heap[sum];
			position[heap[1].x][heap[1].y][heap[1].kind]=1;
			sum--;
			down(1);
		}
		if(sum>0)
			printf("Case %d: %dn",++cases,heap[1].T);
		else
			printf("Case %d: Impossiblen",++cases);
	}
	return 0;
}

最后

以上就是痴情墨镜为你收集整理的2008 ACM-ICPC世界总决赛试题分析8-11的全部内容，希望文章能够帮你解决2008 ACM-ICPC世界总决赛试题分析8-11所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。