2019夏季SOJ编程比赛题解

5) 删除字符串中所有相邻得重复项[栈]

题意:删除重复项的两个字母,反复执行,直到无法删除为止.

题解:基于栈的实现,如果下一个字母与栈顶的字母一样,就出栈,否则就入栈.

#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
 
const int N=8e4+5;
const int mod=998244353;
stack<char> q;
char a[N];
int main(){
    string s;
    cin>>s;
    int sz=s.size();
    for(int i=0;i<sz;i++){
        if(q.empty()||q.top()!=s[i]) q.push(s[i]);
        else q.pop();
    }
    int cnt=0;
    while(!q.empty()){
        a[++cnt]=q.top();
        q.pop();
    }
    for(int i=cnt;i>=1;i--) putchar(a[i]);
    puts("");
    return 0;
}

6)有界机器人[瞎搞\玄学]

题意:机器人按指令走是否一直在循环

题解:每循环完一次指令后,判断是否到(0,0)这个点,即返回原点.如果一直都没有返回原点,这就难搞了,那我们可以假设一下循环了MAX次后,如果还没有返回原点,我们就认为是不循环的(当然这就很玄学了).

#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
 
const int N=2e5+5;
const int mod=998244353;
string s;
int dir[4][2]={0,1,-1,0,0,-1,1,0};
int main(){
    cin>>s;
    P now;
    int sz=s.size();
    now.fir=0;
    now.sec=0;
    int t=0;
    int f=0;
    int cnt=0;
    int ans=0;
    while(f!=1){
        if(cnt>=1000){ans=1;break;}
        for(int i=0;i<sz;i++){
            if(s[i]=='G') now.fir+=dir[t][0],now.sec+=dir[t][1];
            else if(s[i]=='L') t=(t+1)%4;
            else t=(t-1+4)%4;
        }
        if(now.fir==0&&now.sec==0) f=1;
        cnt++;
    }
    if(ans) puts("false");
    else puts("true");
    return 0;
}

7)无邻花种植(搜索)

题意:这个无向图的每个节点与相邻的其他节点的值都不能相同.

题解: BFS搜索,枚举每个节点,遍历所有的相邻节点,找出还能种的花.

#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
 
const int N=4e4+5;
const int mod=998244353;
vector<int> v[N];
int vis[N];
void bfs(int now){
    map<int,int> m;
    for(unsigned i=0;i<v[now].size();i++){
        m[vis[v[now][i]]]=1;
    }
    for(int i=1;i<=4;i++) if(m[i]==0){vis[now]=i;break;}
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++) bfs(i);
    for(int i=1;i<=n;i++) printf("%d%c",vis[i],i==n?'\n':' ');
    return 0;
}

8)网格照明

题意:

• 点灯:灯所在的x轴,y轴,对角线都会被点亮
• 关灯:询问的点的八个方向如果有灯就关灯.

题解:这题题目有提醒了,和八皇后问题的方法类似.(啥是八皇后问题可以百度)

x[],y[]数组来标记x轴和y轴是否有灯照亮

对角线的话,可以枚举所有亮着的灯,如果查询的点abs(qx-x)==abs(qy-y)相等的话,说明他们在同一个对角线上.

tips:注意数据范围

#include <bits/stdc++.h>
typedef long long ll;
#define P pair<ll,ll>
//#define fir first
//#define sec second
using namespace std;
 
const int N=8e4+5;
const int mod=998244353;
struct node{
    ll fir,sec;
}a[N];
map <ll,int> x;
map <ll,int> y;
int dir[8][2]={-1,0,-1,-1,0,-1,1,-1,1,0,1,1,0,1,-1,1};
ll n;
int q,l;
int main(){
    scanf("%lld%d%d",&n,&q,&l);
    for(int i=1;i<=q;i++){
        scanf("%lld%lld",&a[i].fir,&a[i].sec);
        x[a[i].fir]=1;
        y[a[i].sec]=1;
    }
    ll v,w;
    for(int i=1;i<=l;i++){
        scanf("%lld%lld",&v,&w);
        int ans=0;
        if(x[v]==1) ans=1;
        else if(y[w]==1) ans=1;
        else{
            for(int j=1;j<=q;j++){
                if(abs(a[i].fir-v)==abs(a[i].sec-w)){
                    ans=1;
                    break;
                }
            }
        }
        ll hh,jj;
        for(int j=0;j<8;j++){
            hh=v+dir[j][0];
            jj=w+dir[j][1];
            if(hh>=0&&jj>=0&&hh<n&&jj<n&&x[hh]==1&&y[jj]==1) x[hh]=0,y[jj]=0;
        }
        printf("%d%c",ans,i==l?'\n':' ');
    }
    return 0;
}