周练19.11.03/10

POJ3984

Description

定义一个二维数组：

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int mp[5][5];
int d[4][2] = {-1,0,0,-1,1,0,0,1};
struct node
{
	int x,y;
}now,nt,path[5][5];
void show(int x,int y)
{
    if(x==0&&y==0)
    {
        cout << "(0, 0)" << endl;
        return;
    }
    show(path[x][y].x,path[x][y].y);
    cout << "(" << x << ", " << y << ")" << endl;
}
int main()
{
	memset(mp,1,sizeof(mp));
	for(int i =0;i<5;++i)
	{
		for(int j =0;j<5;++j)
		{
			cin>>mp[i][j];
		}
	}
	//BFS
	queue<node> q;
	now.x = 0;
	now.y = 0;
	q.push(now);
	mp[now.x][now.y] = 1;
	while(!q.empty())
	{	
		now = q.front();
		q.pop();
		if(now.x==4&&now.y==4)
		{
			break;
		}
		for(int i =0;i<4;++i)
		{
			nt.x = now.x+d[i][0];
			nt.y = now.y+d[i][1];
			if(nt.x>=0 && nt.y>=0 && nt.x<5 && nt.y<5 &&mp[nt.x][nt.y]==0)
			{
				mp[nt.x][nt.y]=1;
				path[nt.x][nt.y].x = now.x;
				path[nt.x][nt.y].y = now.y;
				q.push(nt);
			}
		}
	}
	print(4,4);
	return 0;
 } 
 //

CodeForce

Harbin, whose name was originally a Manchu word meaning “a place for drying fishing nets”, grew from a small rural settlement on the Songhua River to become one of the largest cities in Northeast China. Founded in 1898 with the coming of the Chinese Eastern Railway, the city first prospered as a region inhabited by an overwhelming majority of the immigrants from the Russian Empire. Now, Harbin is the capital of Heilongjiang province and the largest city in the northeastern region of the People’s Republic of China. It serves as a key political, economic, scientific, cultural, and communications hub in Northeast China, as well as an important industrial base of the nation.

This year, a CCPC regional contest is going to be held in this wonderful city, hosted by Northeast Forestry University. To ensure the contest will be a success and enjoyed by programmers around the country, preparations for the event are well underway months before the contest.

You are the leader of a student volunteer group in charge of making banners to decorate the campus during the event. Unfortunately, your group made a mistake and misprinted one of the banners. To be precise, the word “harbin” is missing in that banner. Because you don’t have time to reprint it, the only way to fix it is to cut letters from some used old banners and paste them onto the misprinted banner. You have exactly six banners, and for some reason, you must cut exactly one letter from each banner. Then, you can arrange and paste the six letters onto the misprinted banner and try to make the missing word “harbin”. However, before you start cutting, you decide to write a program to see if this is possible at all.

Input

The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤50000)T (1≤T≤50000), the number of cases.

For each case, the input contains six lines. Each line contains a non-empty string consisting only of lowercase English letters, describing the letters on one of the old banners.

The total length of all strings in all cases doesn’t exceed 2⋅1062⋅106.

Output

For each case, print the string “Yes” (without quotes) if it is possible to make the word “harbin”, otherwise print the string “No” (without quotes).

Example

Input

2
welcome
toparticipate
inthe
ccpccontest
inharbin
inoctober
harvest
belong
ninja
reset
amazing
intriguing

Output

No
Yes

这道题比较简单，一开始用dfs搜图没搜出来，看了学长的代码，使用全排列写的，记录一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int main()
{
	int t,mp[6][30];
	scanf("%d",&t);
	while(t--)
	{
		memset(mp,0,sizeof mp);
		for(int i=0;i<6;i++)
		{
			char st[maxn];
			scanf("%s",st);
			int len=strlen(st);
			for(int j=0;j<len;j++)
				mp[i][st[j]-'a']++;
		}
		char s[10]={"abhinr"};//一定得字典序最小,不然有些情况便利不到 
		bool flag;
		do
		{
			flag=1;
			for(int i=0;i<6;i++)
				if(!mp[i][s[i]-'a'])
					flag=0;
			if(flag)
				break;
		}while(next_permutation(s,s+6));
		if(flag)
			puts("Yes");
		else
			puts("No");
	}
	return 0;
}

HDU6575

Avin’s company has many ongoing projects with different budgets. His company records the budgets using numbers rounded to 3 digits after the decimal place. However, the company is updating the system and all budgets will be rounded to 2 digits after the decimal place. For example, 1.004 will be rounded down to 1.00 while 1.995 will be rounded up to 2.00. Avin wants to know the difference of the total budget caused by the update.

Input

The first line contains an integer n (1 ≤ n ≤ 1, 000). The second line contains n decimals, and the i-th decimal ai (0 ≤ ai ≤ 1e18) represents the budget of the i -th project. All decimals are rounded to 3 digits.

Output

Print the difference rounded to 3 digits..

Sample Input

1
1.001
1
0.999
2
1.001 0.999

Sample Output

-0.001
0.001
0.000

自我感觉这道题太坑了，一开始用double，不行，换成float，WA，最后竟然要用字符串来做，傻眼了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
const int maxx=1e3+100;
string s;
int n;
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		double ans=0.0;
		int len;
		for(int i=1;i<=n;i++)
		{
			cin>>s;
			len=s.length();
             int x = s[len-1] - '0';
			if(x==0) continue;
			else if(x>=5&&x<=9) ans+=0.001*(10-x);
			else if(x<5&&x>0) ans-=0.001*x;
		}
		printf("%.3lf\n",ans);
	}
	return 0;
}

HDU6573

Avin is observing the cars at a crossroads. He finds that there are n cars running in the east-west direction with the i-th car passing the intersection at time ai . There are another m cars running in the north-south direction with the i-th car passing the intersection at time bi . If two cars passing the intersections at the same time, a traffic crash occurs. In order to achieve world peace and harmony, all the cars running in the north-south direction wait the same amount of integral time so that no two cars bump. You are asked the minimum waiting time.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 1, 000). The second line contains n distinct integers ai (1 ≤ ai ≤ 1, 000). The third line contains m distinct integers bi (1 ≤ bi ≤ 1, 000).

Output

Print a non-negative integer denoting the minimum waiting time.

Sample Input

1 1
1
1
1 2
2
1 3

Sample Output

1
0

这道题不难，但是读懂题很重要。

我语文是体育老师教的哈哈~

模拟一下就可以了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxx=5e3+100;
bool vis1[maxx];
bool vis2[maxx];
int a[maxx];
int b[maxx];
int n,m;

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(vis1,0,sizeof(vis1));
		memset(vis2,0,sizeof(vis2));
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis1[a[i]]=1;
		for(int i=1;i<=m;i++) scanf("%d",&b[i]);
		for(int t=0;t<=3008;t++)
		{
			memset(vis2,0,sizeof(vis2));
			for(int i=1;i<=m;i++)
			{
				vis2[b[i]+t]=1;//对南北方向进行标记
			}
			int flag=0; 
			for(int i=1;i<=t+100;i++)
			{
				if(vis1[i]&&vis2[i])//如何南北方向和东西方向同时有车通过，相撞
				{
					flag=1;
					break;
				}
			}
			if(flag==0)
			{
				printf("%d\n",t);
				break;
			}
		}
	}
}