ABC394 A,B,C,D题题解
2025-02-23 11:13:07
发布于：广东
21阅读
3回复
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;
}
时间复杂度：。
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;
}
时间复杂度：。
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;
}
时间复杂度：。
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;
}
时间复杂度：。
最后我说一下 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;
}
有帮助，赞一个