HPU第二次积分赛

某些人

发布于 2020-04-09 11:36:45

4220

发布于 2020-04-09 11:36:45

文章被收录于专栏：一Wa哇一天

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

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

Output

这个题看上去很难但是仔细想想画画图也就那么回事，不过我很傻逼的吧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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-07-28，如有侵权请联系 cloudcommunity@tencent.com 删除

海外加速

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

海外加速

登录后参与评论

0 条评论

热度