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?'
':' ');
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?'
':' ');
}
return 0;
}