首页 > 其他 > 详细

2016 ACM/ICPC Asia Regional Qingdao Online（2016ACM青岛网络赛部分题解）

时间：2017-01-14 07:22:09      阅读：271      评论：0      收藏：0      [点我收藏+]

2016 ACM/ICPC Asia Regional Qingdao Online（部分题解）

5878---I Count Two Three http://acm.hdu.edu.cn/showproblem.php?pid=5878

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1287    Accepted Submission(s): 604

Problem Description
I will show you the most popular board game in the Shanghai Ingress Resistance Team.
It all started several months ago.
We found out the home address of the enlightened agent Icount2three and decided to draw him out.
Millions of missiles were detonated, but some of them failed.

After the event, we analysed the laws of failed attacks.
It‘s interesting that the i-th attacks failed if and only if i can be rewritten as the form of 2a3b5c7d which a,b,c,d are non-negative integers.

At recent dinner parties, we call the integers with the form 2a3b5c7d "I Count Two Three Numbers".
A related board game with a given positive integer n from one agent, asks all participants the smallest "I Count Two Three Number" no smaller than n.
 

 

Input
The first line of input contains an integer t (1≤t≤500000), the number of test cases. t test cases follow. Each test case provides one integer n (1≤n≤109).
 

 

Output
For each test case, output one line with only one integer corresponding to the shortest "I Count Two Three Number" no smaller than n.
 

 

Sample Input
10 1 11 13 123 1234 12345 123456 1234567 12345678 123456789
 

 

Sample Output
1 12 14 125 1250 12348 123480 1234800 12348000 123480000
 
这题枚举一下四重循环打表，然后二分答案水过。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

int t,n,cnt;
long long st[500005],p,r;
long long p2[500005],p3[500005],p5[500005],p7[500005];

int main()
{
	scanf("%d",&t);
	r=1;
	p2[0]=r;
	for(int i=1;i;i++)
	{
		if(r>1e9)break;
		r*=2;
		p2[i]=r;
	}
	r=1;
	p3[0]=r;
	for(int i=1;i;i++)
	{
		if(r>1e9)break;
		r*=3;
		p3[i]=r;
	}
	r=1;
	p5[0]=r;
	for(int i=1;i;i++)
	{
		if(r>1e9)break;
		r*=5;
		p5[i]=r;
	}
	r=1;
	p7[0]=r;
	for(int i=1;i;i++)
	{
		if(r>1e9)break;
		r*=7;
		p7[i]=r;
	}
	cnt=0;
	for(int i=0;i<=31;i++)
	{
		for(int j=0;j<=19;j++)
		{
			for(int k=0;k<=12;k++)
			{
				for(int v=0;v<=11;v++)
				{
					p=p2[i]*p3[j];
					if(p>1e9)break;
					st[++cnt]=p;
					if(p<1e9)
					{
						p*=p5[k];
						if(p>1e9)break;
						st[++cnt]=p;
					}
					else break;
					if(p<1e9)
					{
						p*=p7[v];
						if(p>1e9)break;
						st[++cnt]=p;
					}
				}
			}
		}
	}
	sort(st+1,st+cnt+1);
	while(t--)
	{
		scanf("%d",&n);
		printf("%lld\n",*lower_bound(st+1,st+cnt+1,n));
	}
	return 0;
}

　　

5879---Cure http://acm.hdu.edu.cn/showproblem.php?pid=5879

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1783    Accepted Submission(s): 568

Problem Description
Given an integer n, we only want to know the sum of 1/k2 where k from 1 to n.
 

 

Input
There are multiple cases.
For each test case, there is a single line, containing a single positive integer n. 
The input file is at most 1M.
 

 

Output
The required sum, rounded to the fifth digits after the decimal point.
 

 

Sample Input
1 2 4 8 15
 

 

Sample Output
1.00000 1.25000 1.42361 1.52742 1.58044
 

 这题可以找规律发现到某一点往上至正无穷大，数值都不会变，然后就好做啦～只需要处理前几十万个。

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

string n;
long double sum[400005];

int main()
{
	sum[0]=(long double)0.0;
	for(int i=1;i<=400000;i++)
	{
		sum[i]=sum[i-1]+(long double)1.0/(long double)i/(long double)i;
	}
	while(cin>>n)
	{
		if(n[0]==‘-‘)n[0]=‘0‘;
		long long p=0;
		bool f=0;
		for(int i=0;i<n.size();i++)
		{
			p=p*10+n[i]-48;
			if(p>400000)
			{
				printf("%.5f\n",(double)sum[400000]);
				f=1;
				break;
			}
		}
		if(f==0)
		{
			printf("%.5f\n",(double)sum[p]);
		}
	}
	return 0;
}

　　

5882---Balanced Game  http://acm.hdu.edu.cn/showproblem.php?pid=5882

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 435    Accepted Submission(s): 377

Problem Description
Rock-paper-scissors is a zero-sum hand game usually played between two people, in which each player simultaneously forms one of three shapes with an outstretched hand. These shapes are "rock", "paper", and "scissors". The game has only three possible outcomes other than a tie: a player who decides to play rock will beat another player who has chosen scissors ("rock crushes scissors") but will lose to one who has played paper ("paper covers rock"); a play of paper will lose to a play of scissors ("scissors cut paper"). If both players choose the same shape, the game is tied and is usually immediately replayed to break the tie.

Recently, there is a upgraded edition of this game: rock-paper-scissors-Spock-lizard, in which there are totally five shapes. The rule is simple: scissors cuts paper; paper covers rock; rock crushes lizard; lizard poisons Spock; Spock smashes scissors; scissors decapitates lizard; lizard eats paper; paper disproves Spock; Spock vaporizes rock; and as it always has, rock crushes scissors.

Both rock-paper-scissors and rock-paper-scissors-Spock-lizard are balanced games. Because there does not exist a strategy which is better than another. In other words, if one chooses shapes randomly, the possibility he or she wins is exactly 50% no matter how the other one plays (if there is a tie, repeat this game until someone wins). Given an integer N, representing the count of shapes in a game. You need to find out if there exist a rule to make this game balanced.
 

 

Input
The first line of input contains an integer t, the number of test cases. t test cases follow.
For each test case, there is only one line with an integer N (2≤N≤1000), as described above.

Here is the sample explanation.

In the first case, donate two shapes as A and B. There are only two kind of rules: A defeats B, or B defeats A. Obviously, in both situation, one shapes is better than another. Consequently, this game is not balanced.

In the second case, donate two shapes as A, B and C. If A defeats B, B defeats C, and C defeats A, this game is balanced. This is also the same as rock-paper-scissors.

In the third case, it is easy to set a rule according to that of rock-paper-scissors-Spock-lizard.
 

 

Output
For each test cases, output "Balanced" if there exist a rule to make the game balanced, otherwise output "Bad".
 

 

Sample Input
3 2 3 5
 

 

Sample Output
Bad Balanced Balanced
 
傻逼的无脑题，直接判断奇偶性！简单说下吧，一个点是偶数可以连其余奇数条边，不可能满足50%，即BAD，反之同理。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;

int t,n;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		if(n%2==0)cout<<"Bad"<<endl; else cout<<"Balanced"<<endl;
	}
	return 0;
}

 

5883---The Best Path http://acm.hdu.edu.cn/showproblem.php?pid=5883

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1155    Accepted Submission(s): 515

Problem Description
Alice is planning her travel route in a beautiful valley. In this valley, there are N lakes, and M rivers linking these lakes. Alice wants to start her trip from one lake, and enjoys the landscape by boat. That means she need to set up a path which go through every river exactly once. In addition, Alice has a specific number (a1,a2,...,an) for each lake. If the path she finds is P0→P1→...→Pt, the lucky number of this trip would be aP0XORaP1XOR...XORaPt. She want to make this number as large as possible. Can you help her?
 

 

Input
The first line of input contains an integer t, the number of test cases. t test cases follow.

For each test case, in the first line there are two positive integers N (N≤100000) and M (M≤500000), as described above. The i-th line of the next N lines contains an integer ai(∀i,0≤ai≤10000) representing the number of the i-th lake.

The i-th line of the next M lines contains two integers ui and vi representing the i-th river between the ui-th lake and vi-th lake. It is possible that ui=vi.
 

 

Output
For each test cases, output the largest lucky number. If it dose not have any path, output "Impossible".
 

 

Sample Input
2 3 2 3 4 5 1 2 2 3 4 3 1 2 3 4 1 2 2 3 2 4
 

 

Sample Output
2 Impossible

 

裸的一笔画问题，判欧拉回路与欧拉通路两种与连通性。

欧拉通路没啥好说的，首尾点固定，路线固定。

欧拉回路，即环。值是不定的，要求最大，即将必须通过的点XOR，再枚举开头初始点，与之前ans进行XOR，比最值。

不是一笔画即Impossible。

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

int t,n,m,x,y,ans,p,cnt;
int a[100005],sum[100005],par[100005];

int find(int x)
{
	if(x==par[x])return x; else return par[x]=find(par[x]);
}

void unionx(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y)return ;
	par[x]=y;
}

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		for(int i=1;i<=n;i++)par[i]=i;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		memset(sum,0,sizeof(sum));
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			unionx(x,y);
			sum[x]++;
			sum[y]++;
		}
		cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(i==par[i] && sum[i]!=0)cnt++;
		}
		if(cnt>1)
		{
			cout<<"Impossible"<<endl;
			continue;
		}
		p=0;
		ans=0;
		for(int i=1;i<=n;i++)
		{
			if(sum[i]==0)continue;
			if(sum[i]%2==1)p++;
			ans^=(((sum[i]+1)/2)%2)*a[i]; 
		}
		if(p!=0 && p!=2)
		{
			cout<<"Impossible"<<endl;
			continue;
		}
		if(p==2)
		{
			printf("%d\n",ans);
			continue;
		}
		else
		{
			int anss=0;
			for(int i=1;i<=n;i++)
			{
				if(sum[i]==0)continue;
				anss=max(anss,ans^a[i]);
			}
			printf("%d\n",anss);
		}
	}
	return 0;
}

　　

先只看了几道通过率高的题A了，剩余的题如果还有A的，且心情好的话再补上。。。

毕竟之前两天辣么的题目都没挂上来。原因。。。文化课掉出年级250外了。。。

2016 ACM/ICPC Asia Regional Qingdao Online（2016ACM青岛网络赛部分题解）

原文：http://www.cnblogs.com/winmt/p/6284391.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！