8.15 米哈游服务器开发笔试投票 + 全A代码

我投的服务器端开发，三道算法题，分别是ab凑字符数，周期数组，排雷，总体来说还是比较简单的，算法岗应该和我的题目不一样。。。

A 其实ab就相当于左右括号，这题就是判断括号是否合法，用个类似栈的结构判断即可

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        string str;
        cin>>str;
        int left = 0;
        int len = str.length();
        bool succ = true;
        for(int i=0;i<len;i++){
            if(str[i] =='a')
                left++;
            else{
                if(left == 0)
                    succ = false;
                else
                    left--;
            }
        }
        if(succ&&left == 0)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}

B 这个题最终形态就是奇数位都是一样的数字，偶数位也是一样的数字，我只要找到奇数偶数位各自出现次数最多的数，那么这个数组的最终形态就是这两个最多的数字

#include <bits/stdc++.h>

using namespace std;
map<int,int>id;
int cnt[50005];
int num[100005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);

    int now = 0;
    for(int i=1;i<=n;i+=2){
        int d = id[num[i]];
        if(d == 0)
        {
            id[num[i]] = ++now;
            d = now;
        }
        cnt[d]++;
    }
    int large = 0;
    for(int i=1;i<=now;i++)
        large = max(large,cnt[i]);
    int ans = n/2 - large;
    if(n%2 == 1)
        ans++;
    memset(cnt,0,sizeof(cnt));
    id.clear();

    now = 0;
    for(int i=2;i<=n;i+=2){
        int d = id[num[i]];
        if(d == 0)
        {
            id[num[i]] = ++now;
            d = now;
        }
        cnt[d]++;
    }
    large = 0;
    for(int i=1;i<=now;i++)
        large = max(large,cnt[i]);
    ans = ans + (n/2 - large);
    printf("%d\n",ans);
    return 0;
}

C 几乎是bfs裸题，判断一下当前点是否可以排雷即可，也就是向八个方向走能否走到地雷上

#include <bits/stdc++.h>

using namespace std;

char road[105][105];
int vis[105][105];
int dirx[4] = {0,0,1,-1};
int diry[4] = {1,-1,0,0};
int judgex[8] = {0,0,1,-1,-1,-1,1,1};
int judgey[8] = {1,-1,0,0,-1,1,-1,1};
queue<pair<int,int>>q;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m,x1,y1,x2,y2;
        scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                cin>>road[i][j];
        }
        memset(vis,0,sizeof(vis));
        while(!q.empty())
            q.pop();
        q.push(pair<int,int>(x1,y1));
        vis[x1][y1] = 1;
        int small = 0x3f3f3f3f;
        while(!q.empty()){
            pair<int,int>now = q.front();
            q.pop();
            for(int i=0;i<8;i++){
                int nx = now.first + judgex[i];
                int ny = now.second + judgey[i];
                if(nx<=0||ny<=0||nx>n||ny>m||road[nx][ny]=='#')
                    continue;
                if(nx == x2&&ny == y2){
                    small = vis[now.first][now.second];
                    break;
                }
            }
            if(small != 0x3f3f3f3f)
                break;
            for(int i=0;i<4;i++){
                int nx = now.first + dirx[i];
                int ny = now.second + diry[i];
                if(nx<=0||ny<=0||nx>n||ny>m||road[nx][ny]=='#'||vis[nx][ny]!=0)
                    continue;
                vis[nx][ny] = vis[now.first][now.second] + 1;
                q.push(pair<int,int>(nx,ny));
            }
        }

        if(small == 0x3f3f3f3f)
            printf("-1\n");
        else
            printf("%d\n",(x1*x2)^(small-1)^(y1*y2));
    }
    return 0;
}

#米哈游笔试##笔试题目##米哈游#