HPU第二次积分赛

题目链接

题目链接

A. 再战斐波那契

单点时限: 1.0 sec

内存限制: 512 MB

小z 学会了斐波那契和 gcd 后，老师又给他出了个难题，求第N个和第M个斐波那契数的最大公约数，这可难倒了小z ，不过在小z 的再三请求下，老师又告诉他了个条件，gcd(N,M)∈[1,90]。

可是，笨拙的小z 还是不会，于是请求你帮他解答这个问题。

已知:

F i b o n a c c i [ i ] = = { i x&lt;=1 F i b o n a c c i [ i − 1 ] + F i b o n a c c i [ i − 2 ] x&gt;1 Fibonacci[i]== \begin{cases} i&amp; \text{x&lt;=1}\\ Fibonacci[i−1]+Fibonacci[i−2]&amp; \text{x&gt;1} \end{cases} Fibonacci[i]=={iFibonacci[i−1]+Fibonacci[i−2]​x<=1x>1​

输入格式

输入包括 T 组，T∈[1,10].

接下来 T 行,每行两个整数 N,M, 表示斐波那契的第 N 项和第 M 项，(N,M∈[1,1018]).

输出格式

输出包含 T 行,每行输出一个整数.

样例

Input

3

1 2

2 3

3 4

Output

1

1

1

这个题比赛时想了一会我去咋这么难，第一题就要用大数？？？结果发现我真的傻逼了，这个规律题真的还不错斐波那契的第N项和第M项的gcd就等于N和M的gcd的那一项对应的斐波那切数比如第4(3)项和第8(21)项的的gcd就等于gcd(4,8)的那一项也就是第2项3；

另外注意 long long 好像可以存到92项，unsigned long long可以存到93项

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[100];
int main()
{
	ios::sync_with_stdio(false);
	a[0]=0;a[1]=1;
	for(int i=2;i<94;i++)
	   a[i]=a[i-1]+a[i-2];
	   ll t,x,y;
	   while(cin>>t)
	  {
	  	while(t--)
	  	{
	  		cin>>x>>y;
	  		cout<<a[__gcd(x,y)]<<endl;
		}
	  }
	return 0;
}
           

B. 恐怖的怪物

单点时限: 5.0 sec

内存限制: 512 MB

一天早上，Dicer一觉醒来，发现自己来到了MineCraft的世界里面，身为MineCraft游戏爱好者的他欣喜不已，于是他在地下挖了一片长方体的空间作为秘密基地，可是他发现光照亮度小于等于7时，会有恐怖的怪物出现，并且他通过查阅资料发现光源方块产生光照每一米（方格）衰减1光照等级。

 此规律在坐标轴的3个方向上（东西、南北、上下）均成立。换句话来说，对角线方向的光照衰减依照“曼哈顿距离”（两个点在坐标系上的绝对轴距总和）计算。这意味着，假如地上插着一支火把（光照等级14），则在水平面上与火把相邻的4个方向的方格上光照等级均为13，而在水平面上与火把对角的4个方格上光照等级均为12（譬如，西北方格的光照等级为14-向西1级-向北1级）。

 上述这种衰减特性会在光源周围产生菱形的照明。该效果会在光源周围的光源扩散呈钻石状。如果被不透明方块阻挡，光照也可以沿着复杂而弯曲的路径扩散。

如下图所示，红色为光源（亮度等级为14）,黑色为秘密物品，其余各个位置光照强度如图所示。

 秘密基地为N∗M的空间，不考虑高度，初始地面光照强度为0。为了不生成恐怖的怪物，Dicer布置了一些光源，但他不知道是否仍会生成怪物，现在请你帮助Dicer判断。

**注：**光源及秘密物品均为不透明方块，且其上方均不会生成怪物。

输入格式

第一行是一个T。（1≤T≤100）

接下来有T组数据，每一组第一行是N,M,（1≤N,M≤1000）,接下来有N行，每行M个字符，代表秘密基地地面放置的方块，0代表空气，#代表秘密物品，Y代表萤石(光照等级为15)，H代表火把(光照等级为14)，F代表附魔台(光照等级为12)，R代表激活的红石火把(光照等级为7)。

输出格式

输出包含T行，每行如果仍会生成怪物，输出”Yes”,否则输出”No”

样例

Input

2
2 3
0Y0
00#
3 4
R00#
00R0
0R00
           

Output

No

Yes

Input

2
1 5
0Y0R0
2 4
Y#0R
0000
           

Output

Yes

No

Input

1
5 4
Y0F0
0000
0000
0000
0000
           

Output

No

这道题看着我都头痛补都不想补！比赛的时候看见了感觉就是跑bfs但是发自内心的不想写，唉！以后要改改这个坏毛病了不能再这样了！不过这个题也要注意！光源，神秘物体是不能透过光的所以一遇到不是“0”的都不能放进队列里面，队列还要用优先队列！真是麻烦GYH学长真毒瘤！！！

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<math.h>
using namespace std;
typedef long long ll;
typedef unsigned long long  ull;

const int maxn=1e5+10;
const int mod=1e9+7;

char mmp[2000][2000];//存图
int mp[2000][2000];//存光照强度
bool flag[2000][2000];//作为标记
struct pe{
	int x,y;
	int s;
	bool friend operator < (pe x,pe y)//规定一下排列顺序
	{
		return x.s<y.s ;
	}
}cc,c;
int t,n,m;
int dir[4][2]={1,0,0,1,-1,0,0,-1};

priority_queue<pe>q;

bool bfs()
{
	c=q.top() ;
	
	while(!q.empty() )
	{
		c=q.top() ;q.pop() ;
		if(mp[c.x][c.y]==8) break;
		for(int i=0;i<4;i++)
		{
			int x=c.x+dir[i][0] ;int y=c.y+dir[i][1] ;
	//注意这里只有mmp[x][y]=='0'；才能放入队列；		
			if(x>=0&&x<n&&y>=0&&y<m&&!flag[x][y]&&mmp[x][y]=='0'&&mp[x][y]<c.s)
			{
				flag[x][y]=1;
				mp[x][y]=c.s -1;
				cc.x =x;cc.y =y;cc.s =c.s -1;
				q.push(cc); 
			}	
		}	
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(mmp[i][j]=='0'&&mp[i][j]<=7)//判断是不是满足条件
			return 0;
		}
	}
	return 1;
}

int main()
{
	ios::sync_with_stdio(false);
	while(cin>>t)
	{
		while(t--)
		{
			cin>>n>>m;
			memset(mp,0,sizeof mp);
			memset(flag,0,sizeof flag);
			for(int i=0;i<n;i++)
			{
				cin>>mmp[i];
				for(int j=0;j<m;j++)//存图并且提前判断一下光照强度标记光源和记录强度
				{
					if(mmp[i][j]=='Y') {
						mp[i][j]=15;//flag[i][j]=1;
						c.x=i;c.y=j;c.s =15;
						q.push(c); 
					}
					else if(mmp[i][j]=='H'){
					  mp[i][j]=14;	//flag[i][j]=1;
						c.x=i;c.y=j;c.s =14;
						q.push(c); 
					} 
					else if(mmp[i][j]=='R') 
					{
						mp[i][j]=7;//flag[i][j]=1;
						c.x=i;c.y=j;c.s =7;
						q.push(c); 
					}
					else if(mmp[i][j]=='F')
					{
						mp[i][j]=12;//flag[i][j]=1;
						c.x=i;c.y=j;c.s =12;
						q.push(c); 
					}
					 	
				}
			}
			if(bfs()) cout<<"No"<<endl;
			else cout<<"Yes"<<endl;
		}
	}
	return 0;
}

           

C. 连连看

单点时限: 3.0 sec

内存限制: 512 MB

 众所周知，《连连看》是一个老少皆宜的游戏。

《连连看》是由黄兴武创作的一款PC端益智类游戏，只要将相同的两张牌用三根以内的线段连在一起就可以消除，规则简单容易上手。

 现在呢，Boctorio学长突然想玩连连看了，但不是单纯的玩游戏，他想自己出一局连连看。

由于Boctorio学长是一个蒟蒻，他不知道自己出的连连看是否符合能够通过多次操作将其全部消除，所以想要你帮他检查一下他出的连连看是否符合规则。

输入格式

第一行输入个T,表示T组数据（1≤t≤100）

每组数据第一行两个数 n,m ,表示连连看棋盘的长和宽（1≤n,m≤100）

接下来 n 行，每行输入 m 个正整数aij，表示 m 个棋子 (1≤aij≤n∗m)。

每种棋子只会出现一对，因此数据保证只有一种有效结果。

输出格式

每组数据输出一行。

如果棋盘符合规定，输出”Yes”，否则，输出”No”（不包括引号）。

样例

Input

3
2 2
1 2
2 1
3 4
1 6 2 3
4 5 3 1
4 2 6 5
4 4
1 2 3 6
8 4 7 8
5 6 5 7
1 2 3 4
           

Output

No

No

Yes

emmmmm这个题之前写过一个简单的但是现在还是不会以后再补吧…

D. Points in rectangle

单点时限: 2.0 sec

内存限制: 512 MB

 在二维平面中有一个矩形，它的四个坐标点分别为(0,a),(a,0),(n,n−a),(n−a,n)。你现在有m个点，现在你想知道有多少个点是在这个矩形内的(边上的也算)。

输入格式

第一行输入n,a(1≤a<n≤103)。

第二行一个正整数m(1≤m≤103),代表你拥有的点的个数，接下来m行，每行一个点的坐标xi,yi(1≤xi,yi≤103)。

输出格式

第一行输出在矩形内的点的个数，然后输出在矩形内点的坐标，横坐标大的优先，如果横坐标相同，则纵坐标大的优先。如果没有，输出−1。

样例

Input

6 1
5
1 2
1 3
2 3
3 4
4 5
           

Output

4
4 5
3 4
2 3
1 2
           

这个题看上去很难但是仔细想想画画图也就那么回事，不过我很傻逼的吧x.x!=y.x打成 y.y了Wa了一发感觉也是个水题。。。还是自己太菜了

#include<queue>
#include<string>
#include<queue>
#include<stack>
#include<string.h>
#include<set>
#include<map>
#include<algorithm>
#include<iostream>
#include<stdio.h>

using namespace std;
typedef pair<int,int> pa;
typedef long long ll;

const int maxn=1e5+10;
const int mod=1e9+7;
struct pe{
	int x,y;
}S[5000];
bool cmp(pe x,pe y){
	if(x.x !=y.x ) return x.x >y.x ;
	else return x.y >y.y ;
}
int n,m,k;
int x,y;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
		cin>>k;
		int bb=2*n-m;
		int t=0;
		for(int i=0;i<k;i++)
		{
			cin>>x>>y;
			int w=y-x-m,q=y-x+m;
			int r=y+x-m,s=y+x-bb;
			if((q>=0&&w<=0)&&(r>=0&&s<=0))
			{
				S[t].x =x;
				S[t++].y=y;
			}
		}
		if(!t) cout<<-1<<endl;		
		else
		{	
		sort(S,S+t,cmp);
			cout<<t<<endl;
			for(int i=0;i<t;i++)
			{
				cout<<S[i].x <<" "<<S[i].y<<endl;
			}
		}
	return 0;
}
           

E. Numbers of interval

单点时限: 2.0 sec

内存限制: 512 MB

现在有一个数组，请计算有多少的区间 [l,r] (l≤r)满足 a[i] ∑ l r \sum_l^r ∑lr​>i ≥k;

输入格式

第一行输入n,k(1≤n,k≤106).

接下来输入n个数，第i个数为ai(1≤ai≤103).

输出格式

输出满足条件的区间个数

样例

Input

3 5
2 3 5
           

Output

4

这个题我感觉是这次出的最有意思的题！这个思路是用sum一直加，一旦结果大于等于K；ant=n-i那就从对一项减，如果sum还大于K那就再加；接着减，记得不能回头减，如果这次减到第二项了，那么下次一定要从第三项开始

#include<queue>
#include<string>
#include<queue>
#include<stack>
#include<string.h>
#include<set>
#include<map>
#include<algorithm>
#include<iostream>
#include<stdio.h>

using namespace std;
typedef pair<int,int> pa;
typedef long long ll;
const int maxn=1e6+1000;
const int mod=1e9+7;
int a[maxn];

int main()
{
	ios::sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
	memset(a,0,sizeof a);
	ll sum=0;
	ll ast=0;//初始化，记录有几种方案
	ll k=0;
		for(ll i=0;i<n;i++)
		{
			cin>>a[i];
			sum+=a[i];//前几项的累加
			if(sum>=m)//如果大于m就开始减；
			{
			   ast+=n-i;
			for(;k<=i;)//最多减到当前位置；
			 {
			 	sum-=a[k++];
				if(sum>=m) ast+=n-i;//如果依旧满足条件那么就一直加；
				else break;
			 }
			}
		}	
		cout<<ast<<endl;
	return 0;
}
           

I. Same String

单点时限: 2.0 sec

内存限制: 512 MB

 有两个只由小写字母组成的长度为n的字符串s1,s2和m组字母对应关系，每一组关系由两个字母c1和c2组成，代表c1可以直接变成c2,你需要判断s1是否可以通过这m组关系转换为s2。

输入格式

第一行输入一个n(1≤n≤100)，代表字符串的长度。

第二行和第三行输入两个字符串s1,s2。

第四行输入一个m(1≤m≤325)，代表有m组关系。

接下来m行，第i行两个字符ui,vi,代表ui可以直接变为vi。

输出格式

如果s1可以通过这些m组关系转化变为s2，输出”YES”，否则输出”NO”。

样例

Input

6
aabbcc
cdbcad
4
a c
c a
a d
b c
           

Output

YES

提示

可以转换多次，比如a可以转换为b，而b可以转换为c，则a可以转换为c。

样例一：aabbcc->cabbcc->cdbbcc->cdbccc->cdbcac->cdbcaa->cdbcad

这个题我看见的第一反应是直接暴力因为按最坏的复杂度也不会TLE于是就直接莽了一发！结果还真过了！！！

#include<queue>
#include<string>
#include<queue>
#include<vector>
#include<string.h>
#include<set>
#include<map>
#include<algorithm>

#include<stdio.h>

using namespace std;
typedef pair<int,int> pa;
typedef long long ll;

const int maxn=1e5+10;
const int mod=1e9+7;

char a[200],aa[200];
vector<int> v[30];
bool flag[30];
bool bfs(int x,int y)
{//每次都要初始化！！！
	memset(flag,0,sizeof(flag));
	queue<int>q;
	q.push(x);
	flag[x]=1; 
	while(!q.empty() )
	{
		int xx=q.front() ;q.pop() ;
		if(xx==y){
			return 0;
		}
		else{
			for(int i=0;i<v[xx].size() ;i++)
			{
				int qq=v[xx][i];
				if(!flag[qq])
				{
					q.push(qq);
					flag[qq]=1; 
				}
			}
		}
	}
	return 1;
}

int main()
{
//	ios::sync_with_stdio(false);
	int n,m;
	char x,y;
	scanf("%d",&n);
	scanf("%s",a);
	scanf("%s",aa);
	scanf("%d",&m);
	getchar();
	for(int i=0;i<m;i++)
	{
		scanf("%c %c",&x,&y);
		getchar();
		int A=x-'a';int B=y-'a';
		v[A].push_back(B); //存入邻接表
	}
	int fa=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]!=aa[i])
		{
			if(bfs(a[i]-'a',aa[i]-'a')){//每次判断
				fa=1;
				break;
			}
		}
	}
	if(fa) puts("NO");
	else puts("YES");
	return 0;
}
           

//这里附加一份华佬的代码，用了另一个算法，还是比较巧的，华佬真强！！！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
string s1,s2;
char c,d;
int ma[330][330];
int main(){
	ios::sync_with_stdio(0);
	cin >> n >> s1 >> s2 >> m;
	for(int i = 0; i < m; i++){
		cin >> c >> d;
		ma[c][d] = 1;
	}
	for(int i = 'a'; i <= 'z'; i++){
		for(int j = 'a'; j <= 'z'; j++){
			if(ma[j][i]){
				for(int k = 'a'; k <= 'z'; k++){
					ma[j][k] = ma[j][k] || ma[i][k];
				}
			}
		}
	}
	for(int i = 0; i < n; i++){
		if(s1[i] != s2[i]){
			if(!ma[s1[i]][s2[i]]) {
				cout << "NO\n";
				return 0;
			}
		}
	}
	cout <<"YES\n";
	

	return 0;
}