内蒙古大学第十五届程序设计大赛(春季赛) 题解

发布于 2019-05-19  422 次阅读


这次校赛的题目总体上来说是比较简单的,出题中途怕大家做不出来,多次对题目降低了难度,其中最难的三题是改自省赛题,难度也就省赛简单点。不过本次题目没有水的数据,去年出题数据出太水了,结果好多人都是水过= =

A.qhq&php

这题题意很明显,就是查找最大的两个值。不过这题输入量不确定(且限制了内存),无法使用sort进行排序。此外还需要注意对字符串的处理。还有要注意收益k的取值范围,k是无法用int存下的。

标程(from jasonczc)

#include <string>
#include <iostream>
using namespace std;
bool cmp(string a,string b){
    if(a.length()!=b.length()) return a.length()>b.length();
    return a>b;
}
int main(){
    string ansa,ansb,ansa1,ansb1,a,b,tmp;
    while(getline(cin,tmp)){
        long long int start=tmp.length()-1,length=0;
        while(tmp[start]!=' ') start--,length++;
        a = tmp.substr(0,start);
        b = tmp.substr(start+1,length);
        if(cmp(b,ansb1)){
            if(cmp(b,ansb)){
                ansb1=ansb;
                ansa1=ansa;
                ansb = b;
                ansa = a;
            }else{
                ansb1 = b;
                ansa1 = a;
            }
        }
    }
    cout << ansa <<  endl << ansa1;
}

B.可怜的qhq

这题改自前年的省赛题。这题在思考上有些难度,但是出题后降低了难度,直接在提示中告知了本题的做法。首先正反面肯定要先计算一次,然后正反面整理完后,就相当求逆序对数了。求逆序对数可以使用归并,也可以使用树状数组。

标程

#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
int a[100000+5],idx;
int bit[100000+5];
int sum(int i)
{
    int s=0;
    while(i>0)
    {
        s+=bit[i];
        i-=i&-i;
    }
    return s;
}
void add(int i,int x)
{
    while(i<=idx)
    {
        bit[i]+=x;
        i+=i&-i;
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        int ans1=0,t;
        memset(bit,0,sizeof(bit));
        idx=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&t);
            if(!(i&1))
            {
                if(!(t&1))ans1++;
                a[idx++]=(t+1)/2;
            }
        }
        long long ans2=0;
        for(int i=0;i<idx;i++)
        {
            ans2+=i-sum(a[i]);
            add(a[i],1);
        }
        printf("%lld\n",ans1+ans2);
    }
}

C.qhq的服务器

改自今年省赛热身赛的题目,二分即可,注意本题的数据范围。

标程

#include <bits/stdc++.h>
using namespace std;
long long a[100010],tmp;
int t,n,m;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        for(int i = 1;i<=n;i++){
            scanf("%lld",a+i);
            a[i]+=a[i-1];
        }
        for(int i = 1;i<=m;i++){
            scanf("%lld",&tmp);
            long long p = lower_bound(a+1,a+1+n,tmp)-(a+1);
            printf("%lld %lld\n",p+1,tmp-a[p]);
        }
    }
}

D.qhq的神奇表

改自某年的noip题,推出公式即可

标程

#include<cstdio>
#include<math.h>
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        int a=(-1.0+sqrt(1+8*(n-1)))/2+2;
        int b=(a-2)*(1+a-2)/2;
        if(a&1)
        {
            printf("%d/%d\n",n-b,a-(n-b));
        }
        else
        {
            printf("%d/%d\n",a-(n-b),n-b);
        }
    }
}

E.新的主角~皮神,登场!

Hello world,直接输出即可

标程

#include<cstdio>
int main()
{
printf("                    _0&                                                                                                      \n                    000                                                                                                      \n                   0000                                                                                                      \n                  j0000f                                                                                                     \n                 ]00000&                                                                                                     \n                 000000&                                                                                                     \n                j000000#                                                                                                     \n                00000000                                                                                                     \n               j00000M^]                                                                                                     \n               0000~   ]                                                                                                     \n              ]00M     ]                                                                                                     \n              #0&      ]                                                                                                     \n              0'       l                                                                                                     \n             ]'        !                                                                                                     \n             l         f                                                                                                     \n             I                                                                                                               \n             A                                                                                                               \n             H        ]                                                                                                      \n             -        [                            __,,aa-----* ..__                                                         \n             c        '         __,,____    _,.**~^                  \"\"-w_                                                   \n             U             ,-:~         `7*^                              0Mg,                                               \n             6       ?  ,\"                                              ,000000gg                                            \n             !       L/`                                              _g0000000000g,                                         \n             |     _/`                                              _p000000000000000r                                       \n             ]     `                               Y+*:,__        gM00000000000000MM^                                        \n                                                    1      ``~~\"\"~~~~~~~~~~``                                                \n              f '                                                                                                            \n              l[                                                                                                             \n                                           _gg_      f                                                                       \n              i                           pF`M0&     1                                                                       \n              !                           0g _00&    ]             q /f                                                      \n              L      __                   000000#     t         ,/^ ^ \"\"                                                     \n              L    g0M~Qp                 ^00000'     ]      ,*^        `                                                _, ,\n              !   q00  ]0                   ~M~       _1   x^           \",                                        _,a*\"~   _ \n              l   400&g00       _g                  jD00_x^            _/'                                  _,a=~`         } \n              ]   \"00000#        `                 ]0#MMI              '                                ,a+~`                \n                   ^M00M          _____  ,'        0NQ#gH             )                            _,-\"`                  1  \n                               _p0N0M0000#        _0000g#                                      _,+\"                          \n               _          -..pg##M000M#000        \"M000gV            f                      ,*\"                          !   \n              ]M#g           M000N0MM0NR00         0000K6           J                   _.*`                            w    \n    ^\\.a---*+*400#&           400NN0QK0###         M000#           y                 _/~                                I    \n V``          ]KAQ0L           #M0N@^`#IFM          `\"4                           ,/~                                        \n,\"             ##Q0d            #NN:{E-T-j           y~           '            _/'                                     ?     \n`1             \"#M04             Q: m S,n!          ,            '                                                           \n7                &0I              Y@^:G%,\"         )           y'                                                     J      \n                  \",               \\ , w7        _/           p'              ]                                       '      \n  w*(               *,              'q_W         ^           v                ]                                      j       \n     *,               ~m_                                   /                 |                                      f       \n       \\_                +v_                              $^ `                I                             ___,x.m/*        \n         \\,                 \"*                                \\               P                __,/***\"\"~~`                  \n           *q                                                  t              6       _,m+-~~^`                              \n             ~\\,                                               \"              W      !                                       \n                ~*._                                 ___        l                    6                                       \n                    ~**Q_                         ,*`   `~<      Y                                                           \n                                             _   /         >.    ]           ]      4                                        \n                        6                   pwT>f                 1     a,,,,J      l                                        \n                        f                   i] Y \\                ]   ]             I                                        \n                        ~                    q\\ ( `.                  ]_                                                     \n                                              c\\ \\  \\      -       f  l#   Y--**vL,_                                         \n                                              ] \\    '             $g_]0NXgI                                                 \n                                              ]`,                  #M000##Mf                                                 \n                        n                     \" ^,                 BM0N00001                                                 \n                        6                      1 \"q      /        _0N0N0&0MI                                                 \n                        t                      \",  \\     l        Q0# ~M0M01                                                 \n                        f                       ^}  >,   ~W      _N0       `                                                 \n                        n                        \"c   *,  l     y&Mf                                                         \n                                                        \"*'    7~`                                                           \n                       ]                                    _+`                                                              \n                       |                                 ,+~                                                                 \n                       ]                             _)\"                                                                     \n                       ]                           W~                                                                        \n                        _                        )^                                                                          \n                        ]                      p'                                                                            \n                         \\                    /                                                                              \n                          \\                p/                                                                                \n                           ^v            ,~                                                                                  \n                             R*g_____.*\"                                                                                     \n                             5\\   `j                                                                                         \n                               x r/!                                                                                         \n                            ]  / \\\\                                                                                          \n                            ]  >  J                                                                                          \n                            ]Q   ^'                                                                                          \n                            ]]  \\7                                                                                           \n                             j \"_                                                                                            \n                             0  ^                                                                                            \n                              V^                                                                                             ");
}

F.逃げる!电気石の洞穴

改自今年省赛热身赛,最最基础的搜索入门题。注意审题,终点可能有多个。

标程

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
char maze[205][205];
int flag[205][205];
int d[4][2]={0,1,1,0,0,-1,-1,0};
struct point{
    int x,y,t;
    point(int _x,int _y,int _t){x=_x;y=_y;t=_t;}
};
int main()
{
    int t,n,m,sx,sy;
    scanf("%d",&t);
    while(t--)
    {
        memset(flag,0,sizeof(flag));
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
        {
            getchar();
            for(int j=0;j<m;j++)
            {
                scanf("%c",&maze[i][j]);
                if(maze[i][j]=='R')
                {
                    sx=i;
                    sy=j;
                }
            }
        }
        queue<point> q;
        point s(sx,sy,0);
        q.push(s);
        flag[sx][sy]=1;
        int f=1;
        while(!q.empty())
        {
            point p=q.front();
            q.pop();
            if(maze[p.x][p.y]=='F')
            {
                printf("%d\n",p.t);
                f=0;
                break;
            }
            for(int i=0;i<4;i++)
            {
                int nx=p.x+d[i][0];
                int ny=p.y+d[i][1];
                if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]!='#'&&!flag[nx][ny])
                {
                    flag[nx][ny]=1;
                    point s(nx,ny,p.t+1);
                    q.push(s);
                }
            }
        }
        if(f)printf("Poor Pikachu.\n");
    }
}

G.皮卡丘的精灵图鉴

并查集。注意对字符串的处理。

标程(from jasonczc)

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
unordered_map<string,string> m;
string& find(string &t){
    if(m.find(t)==m.end()){
        return t;
    }else{
        string st = m[t];
        if(st==t) return t;
        else return m[t]=find(st);
    }
}
void merge(string &a,string &b){
    string fa=find(a),fb=find(b);
    if(fa!=fb) m[fa]=fb;
}
int main(){
    int k;cin >> k;
    while(k--){
        int a,b;
        cin >> a >> b;
        string sa,sb;
        while(a>0){
            cin >> sa >> sb;
            merge(sa,sb);
            a--;
        }
        while(b>0){
            cin >> sa >> sb;
            cout << ((find(sa)==find(sb))?"Y":"N")<< endl;
            b--;
        }
        m.clear();
    }
}

H.自闭了

博弈水题,只要n>2,都是pkq赢

标程

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n&&n)
    {
        if(n<=2)cout<<"qhq"<<endl;
        else cout<<"pkq"<<endl;
    }
}