AtCoder ABC248 A-D题解

比赛链接:ABC348

Problem A:

签到。

#include <bits/stdc++.h>
using namespace std;
int main(){
	int N;
	cin>>N;
	for(int i=1;i<=N;i++){
		if(i%3==0)
			cout<<'x'<<endl;
		else
			cout<<'o'<<endl;
	}
	return 0;
}

Problem B:

枚举即可。

#include <bits/stdc++.h>
using namespace std;
int X[maxn],Y[maxn];
int main(){
	int N;
	cin>>N;
	for(int i=0;i<N;i++)
		cin>>X[i]>>Y[i];
	for(int i=0;i<N;i++){
		int mx=0,ans=0;
		for(int j=0;j<N;j++){
			int dis=(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
			if(dis>mx){
				mx=dis;
				ans=j+1;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Problem C:

直接暴力开桶显然不可取，，所以用map记录。

#include <bits/stdc++.h>
using namespace std;
int A[maxn],C[maxn];
int main(){
	int N;
	cin>>N;
	map<int,int> beans;
	for(int i=1;i<=N;i++){
		cin>>A[i]>>C[i];
		if(beans.find(C[i])==beans.end())
			beans[C[i]]=INT_MAX;
		beans[C[i]]=min(beans[C[i]],A[i]);
	}
	int ans=-1;
	for(int i=1;i<=N;i++)
		ans=max(ans,beans[C[i]]);
	cout<<ans<<endl;
	return 0;
}

Problem D:

看起来有点唬人。

bfs即可。表示图上的能量值，是走到的能量。

#include <bits/stdc++.h>
using namespace std;
const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
char A[MAX][MAX];
int energy[MAX][MAX],cnt[MAX][MAX];
int main(){
	int H,W;
	cin>>H>>W;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++)
			cin>>A[i][j];
	}
	int N;
	cin>>N;
	for(int i=0;i<N;i++){
		int R,C,E;
		cin>>R>>C>>E;
		R--;
		C--;
		energy[R][C]=E;
	}
	memset(cnt,-1,sizeof(cnt));
	queue<pair<int,int>> que;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(A[i][j]=='S'){
				que.push(make_pair(i,j));
				cnt[i][j]=0;
			}
		}
	}
	while(!que.empty()){
		pair<int,int> u=que.front();
		que.pop();
		if(A[u.first][u.second]=='T'){
			cout<<"Yes"<<endl;
			return 0;
		}
		cnt[u.first][u.second]=max(cnt[u.first][u.second],energy[u.first][u.second]);
		for(int i=0;i<4;i++){
			int nx=u.first+dx[i];
			int ny=u.second+dy[i];
			if(0<=nx && nx<H && 0<=ny && ny<W && (cnt[u.first][u.second]-1)>cnt[nx][ny] && A[nx][ny]!='#'){
				cnt[nx][ny]=cnt[u.first][u.second]-1;
				que.push(make_pair(nx,ny));
			}
		}
	}
	cout<<"No"<<endl;
	return 0;
}

其实que可以写一个结构体。

好了，以上就是本期的全部内容了。我们下期再见！\(^o^)/~

友情提醒:本期的所有代码都有问题，请勿无脑Ctrl C+Ctrl V