A. 再战斐波那契
单点时限: 1.0 sec
内存限制: 512 MB
小z 学会了斐波那契和 gcd 后，老师又给他出了个难题，求第N个和第M个斐波那契数的最大公约数，这可难倒了小z ，不过在小z 的再三请求下，老师又告诉他了个条件，gcd(N,M)∈[1,90]。
可是，笨拙的小z 还是不会，于是请求你帮他解答这个问题。
已知:
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] ∑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;
}
京公网安备 11010502036488号