[数据结构与算法]AtCoder Beginner Contest 243 补题题解

比赛传送门
官方题解

A - Shampoo

原题

#include<bits/stdc++.h>

using namespace std;

//const int N = 1;

#define int long long
#define x first
#define y second
#define ve vector<int>
#define PII pair<int, int>

int T, n, m;

void solve()
{
	int v1, v2, v3;
	cin>>n>>v1>>v2>>v3;
	if(n >= (v1 + v2 + v3)){
		int iu = n % (v1 + v2 + v3);
		if(iu >= v1 + v2){
			cout<<"T";
		}
		else if(iu >= v1){
			cout<<"M"<<endl;
		}
		else if(iu < v1){
			cout<<"F";
		}
	}
	else if(n >= (v1 + v2)){
		cout<<"T"<<endl;
	}
	else if(n >= v1){
		cout<<"M";
	}
	else if(n < v1){
		cout<<"F"<<endl;
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
//	cin>>T;
	T = 1;
	while(T -- ){
		solve();
	}
	return 0;
}

B - Hit and Blow

原题

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

#define int long long
#define x first
#define y second
#define ve vector<int>
#define PII pair<int, int>

int T, n, m;
int a[N], b[N];
int res1, res2;
map<int, bool>mp;
bool st[N];

void solve()
{
	cin>>n;
	for(int i = 0; i < n; i ++ ){
		cin>>a[i];
		mp[a[i]] = 1;
	}
	for(int i = 0; i < n; i ++ ){
		cin>>b[i];
		if(a[i] == b[i]){
			st[i] = 1;
			res1 ++ ;
		} 
		if(mp[b[i]] && !st[i]) res2 ++ ;
		
	} 
	cout<<res1<<endl;
	cout<<res2<<endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
//	cin>>T;
	T = 1;
	while(T -- ){
		solve();
	}
	return 0;
}

C - Collision 2

原题
比赛半天没写出来，太可惜了，又学到了一种元素的存取方式

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

#define int long long
#define x first
#define y second
#define ve vector<int>
#define PII pair<int, char>//一维表编号，二维表列数 
#define pb push_back

int T, n, m;
int a[N], b[N];
int res1, res2;
map<int, int>mp;
map<int, vector<int>>mp2;
int st[N];//记录第几行的面向 
string str;
vector<PII>v1[N];
PII r[N];
int idx;

void solve()
{
	
	cin>>n;
//	memset(h, -1, sizeof(h));
	for(int i = 0; i < n; i ++ ){
		cin>>a[i]>>b[i];
	}
	
	cin>>str;
	
	for(int i = 0; i < n; i ++ ){
		if(!mp[b[i]]){
			mp[b[i]] = idx;
			v1[idx].pb({a[i], str[i]});
			idx ++ ;
		}
		else{
			v1[mp[b[i]]].pb({a[i], str[i]});
		}
	}
	
	bool flag = true;
	for(int i = 0; i < idx; i ++ ){
		if(v1[i].size()){
			int l = 1e9, r = -1e9;
			for(auto op : v1[i]){
				if(op.y == 'L') r = max(r, op.x);
				else if(op.y == 'R') l = min(l, op.x);
				if(l < r) flag = false;
			}
		}
	}
	if(!flag) cout<<"Yes"<<endl;
	else if(flag) cout<<"No"<<endl;
	return;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
//	cin>>T;
	T = 1;
	while(T -- ){
		solve();
	}
	return 0;
}

D - Moves on Binary Tree

原题

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

#define int long long
#define x first
#define y second
#define ve vector<int>
#define PII pair<int, char>//一维表编号，二维表列数 
#define pb push_back

int T, n, m;
string str;

void solve()
{
	cin>>n>>m;
	cin>>str;
	ve v;
	while(m){
		v.pb(m % 2);
		m >>= 1;
	}
	
	reverse(v.begin(), v.end());//注意向量存取是从数的最后一位存的，所以需要翻转 
	
	for(int i = 0; i < n; i ++ ){
		if(str[i] == 'U' && !v.empty()){
			v.pop_back();
		}
		else if(str[i] == 'L'){
			v.pb(0);
		}
		else if(str[i] == 'R'){
			v.pb(1);
		}
	}
	
	for(auto op : v){
		m = m * 2 + op;
	}
	cout<<m<<endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
//	cin>>T;
	T = 1;
	while(T -- ){
		solve();
	}
	return 0;
}