ABC394 A,B,C,D题题解

cjdst

2025-02-23 11:13:07

发布于：广东

24阅读

0回复

0点赞

A

遍历字符串中每个字符，有 2 的就输出 2。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	for(char c:s) if(c == '2') cout << '2';

	return 0;
}

时间复杂度： $O(|S|)$ 。

B

按照题意排序，输出即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
string a[105];
bool cmp(string &a, string &b){
	return a.length() < b.length();
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1, cmp);
	for(int i = 1; i <= n; i++) cout << a[i];

	return 0;
}

时间复杂度： $O(N\log N)$ 。

C

根据样例可以发现，WW...WA 在经历若干次操作后最终会变为 ACC...C。

所以我们可以记录连续的 W 的位置，再判断它后面紧跟着的是否是 A，如果是，就把这一连段字符串修改为 ACC...C。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	int l = -1, r = -1;
	for(int i = 0; i < s.length(); i++){
		if(s[i] == 'W'){//记录连续的W
			if(l == -1) l = r = i;
			r++;
		}else{
			if(s[i] == 'A'){
				if(l == -1) continue;
				s[l] = 'A';
				for(int j = l + 1; j <= r; j++){//修改
					s[j] = 'C';
				}
			}
			l = r = -1;//修改成-1，以便重新记录
		}
	}
	cout << s;

	return 0;
}

时间复杂度： $O(|S|)$ 。

D

括号匹配板子题，不做详细解释。

#include <iostream>
#include <cstdio>
#include <stack>
#include <unordered_map>
using namespace std;
stack <char> a;
unordered_map <char, char> mp;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	mp['('] = ')';//记录与之匹配的字符
	mp['['] = ']';
	mp['<'] = '>';
	string s;
	cin >> s;
	for(char c:s){
		if(!a.empty() && mp[a.top()] == c) a.pop();//如果与之匹配就弹出栈中元素
		else a.push(c);
	}
	cout << (a.empty() ? "Yes" : "No");
	
	return 0;
}

时间复杂度： $O(|S|)$ 。

最后我说一下 F 题的思路：记录下度数大于等于4的点，如果这些点之间有边相连就连，最后拓扑排序。

在最后一步有点问题，能不能帮忙改一下QWQ

//1.找到度大于等于4的 
//2. ???
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>
#include <memory.h>
#include <algorithm>
using namespace std;
vector <int> v[200005];
vector <int> v2[200005];
vector <int> sz[200005];

int cur[200005];
int in[200005];
set <int> deg4;
int n, ct;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i = 1; i <= n; i++){
		if(v[i].size() >= 4) deg4.insert(i); 
	}
	if(deg4.empty()){
		cout << -1;
		return 0;
	}
	for(int i:deg4){
		for(int j:v[i]){
			if(deg4.find(j) != deg4.end()){
				v2[i].push_back(j);
				in[j]++;
			}
		}
	}
	queue <int> q;
	int ctnum = 0;
	for(int i = 1; i <= n; i++){
		if(v2[i].size()) ctnum++;
		if(in[i] == 1) in[i] = 0, cur[i] = 3, q.push(i);
	}
	if(ctnum == 0){
		cout << 5;
		return 0;
	}
	if(ctnum == 2){
		cout << 8;
		return 0;
	}
	while(!q.empty()){
		int head = q.front();
		cout << head << ' ' << cur[head] << '\n';
		q.pop();
		for(int i:v2[head]){
			sz[i].push_back(cur[head] + 1);
			if(!(--in[i])){
				sort(sz[i].begin(), sz[i].end(), greater <int>());
				for(int j = 0; j < sz[i].size() && j < 3; j++) cur[i] += sz[i][j];
				if(sz[i].size() < 3) cur[i] += 3 - sz[i].size();
				q.push(i);
			}
		}
	}
	int mx = 0;
	for(int i = 1; i <= n; i++){
		mx = max(mx, cur[i]);
	}
	cout << mx + 1;

	return 0;
}