HPU第二次积分赛

题目链接

A. 再战斐波那契

单点时限: 1.0 sec
内存限制: 512 MB

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

已知:
$$Fibonacci[i]==
\begin{cases}
i& \text{x<=1}\
Fibonacci[i−1]+Fibonacci[i−2]& \text{x>1}
\end{cases}$$
输入格式
输入包括 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]$\sum_l^r$>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;
}

 上一篇
POJ-2585-Window Pains POJ-2585-Window Pains
POJ-2585-Window Pains Window Pains Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2915 Accepted: 1
2019-07-28
下一篇 
树的直径 树的直径
我真的是好惨一男的呀!今天又被吊打一天好不容易搞懂树的直径了,又遇见树形dp!好惨呀!还有dfs!希望到时候有一个大佬可以带我飞!!!
2019-07-25
  目录