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;
}