11年の成都ネット試合

今日は去年の成都のネット試合をしましたが、去年は問題ができませんでした。今も大変です。まだいくつかの問題があります。時間があったらまた見に来てください。
Attack
http://acm.hdu.edu.cn/showproblem.php?pid=4031
ツリー配列、このツリー配列ノードnに記録されているのはwall[n]とwall[n-1]の砲撃の差です。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define N 20050
int len,Q,T;
int sum[N],deftime[N],defnum[N];
struct cam
{
	int l,r;
}attack[N];
int lowbit(int x)
{
	return x&(-x);
}
void update(int p,int x)
{
	while(p<=len)
	{
		sum[p]+=x;
		p+=lowbit(p);
	}
}
int getsum(int p)
{
	int ans=0;
	while(p>0)
	{
		ans+=sum[p];
		p-=lowbit(p);
	}
    return ans;
}
int main()
{
	char str[50];
	int k,t,cnt,pos,i;
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		printf("Case %d:
",k);
		cnt=0;
		memset(sum,0,sizeof(sum));
		memset(deftime,0,sizeof(deftime));
		memset(defnum,0,sizeof(defnum));
		scanf("%d%d%d",&len,&Q,&T);
		while(Q--)
		{
			scanf("%s",str);
			if(str[0]=='A')
			{
				cnt++;
				scanf("%d %d",&attack[cnt].l,&attack[cnt].r);
				update(attack[cnt].l,1);
				update(attack[cnt].r+1,-1);
			}
			else
			{
				scanf("%d",&pos);
				for(i=deftime[pos];i<=cnt;i++)
				if(attack[i].l<=pos&&pos<=attack[i].r)
				{
					defnum[pos]++;
					deftime[pos]=i+T;
					i+=T-1;
				}
				printf("%d
",getsum(pos)-defnum[pos]);
			}
		}
	}
	return 0;
}

Reglar Polygon
http://acm.hdu.edu.cn/showproblem.php?pid=4033
問題は、点から各頂点までの距離を与え、これらの頂点が正の多角形、二分辺の長さを構成できるかどうかを見ることです。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
double map[110][2];
const double eps=1e-10;
const double pi=acos(-1.0);
int n;
int sol(double mid)
{
	int i;
	double sum,temp;
	sum=0.0;
	for(i=0;i<n;i++)
	{
		if(mid>(map[i][0]+map[i][1])-eps)  return 1; //   
		if(mid<fabs(map[i][0]-map[i][1])+eps) return -1; //   
		temp=(map[i][0]*map[i][0]+map[i][1]*map[i][1]-mid*mid)/(2*map[i][0]*map[i][1]);
		sum+=acos(temp);
	}
	if(sum>2*pi+eps) return 1; //   
	if(sum<2*pi-eps) return -1;  //   
	return 0;
}
int main()
{
	int k,t,i,ans,flag;
	double low,high,mid;
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%lf",&map[i][1]);
			map[i+1][0]=map[i][1];
		}
		printf("Case %d: ",k);
		map[0][0]=map[n][0];
		flag=1;
		low=0;
		high=20000;
		flag=0;
		while(high-low>eps)
		{
			mid=(low+high)/2;
			ans=sol(mid);
			if(ans==0)
			{
				flag=1;
				break;
			}
			else if(ans==1)
			high=mid;
			else
			low=mid;
		}
		if(!flag)
		printf("impossible
");
		else
		printf("%.3lf
",mid);
	}
	return 0;
}

Graph
http://acm.hdu.edu.cn/showproblem.php?pid=4034
逆のfolyd

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int map[110][110];
int sign[110][100];
int n;
int judge()
{
    int i,j,k;
	for(k=0;k<n;k++)
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	if(map[i][k]+map[k][j]<map[i][j])
    return 0;
	return 1;
}
void sol()
{
	int i,j,k;
	for(k=0;k<n;k++)
	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
	if(map[i][k]+map[k][j]==map[i][j]&&i!=j&&i!=k&&j!=k)
	sign[i][j]=1;
}
int main()
{
	int t,k,i,j,ans;
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		scanf("%d",&map[i][j]);
		printf("Case %d: ",k);
		if(!judge())
		{
			printf("impossible
");
			continue;
		}
		ans=0;
		memset(sign,0,sizeof(sign));
		sol();
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			if(!sign[i][j]&&map[i][j])
			ans++;
		}
		printf("%d
",ans);
	}
	return 0;
}

Rolling Hongshu
http://acm.hdu.edu.cn/showproblem.php?pid=4036
sweet potatoのポテンシャルエネルギーと運動エネルギーの和がbitter potatosより大きいのでさえすれば、bitter potatosはsweet potatoに追いつけません。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
double a[1005][2];
int main()
{
	int t,k;
	int n1,n2,m,i,j;
	double st,ans,highnew;
	double aa,b,c,cur,res,high;
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d%d%d",&n1,&n2,&m);
		high=-100000000;
		for(i=0;i<n1;i++)
		{
			scanf("%lf%lf",&a[i][0],&a[i][1]);
			if(a[i][1]>high)
			high=a[i][1];
		}
		ans=m*20*high;
		st=m*20*a[0][1];
		while(n2--)
		{
			scanf("%lf %lf %lf",&aa,&b,&c);
			for(i=1;i<n1;i++)
			if(a[i-1][0]<=aa&&aa<=a[i][0])
			{
				highnew=(a[i][1]-a[i-1][1])/(a[i][0]-a[i-1][0])*(aa-a[i-1][0])+a[i-1][1];
				res=m*20*highnew+0.5*m*b*b;
				if(res>ans)
				ans=res;
				break;
			}
		}
		printf("Case %d: ",k);
		printf("%.2lf
",sqrt(2*(ans-st)/m));
	}
	return 0;
}

The Social Network
http://acm.hdu.edu.cn/showproblem.php?pid=4039
文字列のシミュレーションは、対応する下付き文字に変換すればいいです。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define N 2500
char name[N][20],out[N][20];
int map[N][N],num[N];
int ans;
int cmp(const void *a,const void *b)
{
	return strcmp((char *)a,(char *)b);
}
int find(char str[20])
{
	int i;
	if(ans==-1)
	{
		strcpy(name[0],str);
		ans=0;
		return 0;
	}
	for(i=0;i<=ans;i++)
	if(strcmp(name[i],str)==0)
	return i;
	ans++;
	strcpy(name[ans],str);
	return ans;
}
int querry(int x)
{
	int i,j;
	int mm;
	mm=0;
	for(i=0;i<=ans;i++)
    if(map[x][i])
	{
		for(j=0;j<=ans;j++)
		{
			if(x!=j&&map[i][j]&&map[x][j]==0)
			{
				num[j]++;
			    if(num[j]>mm)
			    mm=num[j];
			}
		}
	}
	return mm;
}
int main()
{
	int t,k;
	int n1,n2;
	int a,b,cur,len,i,Max;
	char str1[20],str2[20],str3[20];
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d%d",&n1,&n2);
		ans=-1;
		memset(map,0,sizeof(map));
        while(n1--)
		{
			scanf("%s %s",str1,str2);
			a=find(str1);
			b=find(str2);
		    map[a][b]=1;
			map[b][a]=1;
		}
		printf("Case %d:
",k);
		while(n2--)
		{
			scanf("%s",str3);
            memset(num,0,sizeof(num));
			cur=find(str3);
			Max=querry(cur);
			if(Max==0)
			printf("-
");
			else
			{
				len=0;
				for(i=0;i<=ans;i++)
				if(num[i]==Max)
				strcpy(out[len++],name[i]);
				qsort(out,len,sizeof(out[0]),cmp);
				for(i=0;i<len;i++)
				{
					if(i==len-1)
					printf("%s
",out[len-1]);
					else
					printf("%s ",out[i]);
				}
			}
		}
	}
	return 0;
}