当前位置：首页 > article >正文

AtCoder Beginner Contest （ABC）394(ABCD)

article 2025/2/23 6:52:56

前言

很激动啊！！ABC第一次在限定的时间内写出四个题！！虽然离大佬们还差很多，中间走了不少弯路，但还是很激动啊！！加油加油！！每天进步一点点！！后面补完题也许会把剩下的发上来。

这一篇主要是总结当时比赛时的心路历程，解析可能不会写得太详细。

一、A - 22222

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve()
{
	string s;
	cin>>s;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='2')
		{
			cout<<2;
		}
	}
}

int main()
{
	solve();
	
	return 0;
}

签到题，无需多言。枚举到2就输出即可。

二、B - cat

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve()
{
	int n;
	cin>>n;
	string s;
	map<int,vector<string> >mp;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		mp[s.length()].push_back(s);
	}
	
	string ans;
	for(map<int,vector<string> >::iterator iter=mp.begin();iter!=mp.end();iter++)
	{
		for(int i=0;i<iter->second.size();i++)
		{
			ans+=iter->second[i];
		}
	}
	cout<<ans;
}

int main()
{
	solve();
	
	return 0;
}

这个题当时是读完题脑子里就蹦出了可以用map的思路然后就直接写了，虽然感觉能优化。

就是用map来按长度排序，开个数组往长度对应下标存应该也行吧，题目好像说了长度都不相等。

三、C - Debug

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve()
{
	string s;
	cin>>s;
	for(int i=0,j;i<s.length()-1;i++)
	{
		if(s[i]=='W'&&s[i+1]=='A')
		{
			s[i]='A';
			s[i+1]='C';
			j=i-1;
			while(j>=0&&s[j]=='W')
			{
				s[j]='A';
				s[j+1]='C';
				j--;
			}
		}
	}
	cout<<s;
}

int main()
{
	solve();
	
	return 0;
}

这个题的思路就是顺序遍历，然后遇到WA就往前刷，就是纯暴力，不知道有没有别的办法。

四、D - Colorful Bracket Sequence

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

bool solve()
{
	string s;
	cin>>s;
	if(s.length()%2==1||s[0]==')'||s[0]==']'||s[0]=='>')
	{
		return false;
	}
	
	stack<int>stk;
	for(int i=0;i<s.length();)
	{
		stk.push(s[i++]);
		while((s[i]==')'&&stk.top()=='(')
            ||(s[i]==']'&&stk.top()=='[')
            ||(s[i]=='>'&&stk.top()=='<'))
		{
			stk.pop();
			i++;
		}
	}
	return stk.empty();
}

int main()
{
	cout<<(solve()?"Yes":"No");
	
	return 0;
}

这个题就花了不少心思，但回过头来想根本没那么复杂。

一开始我的思路也是直接暴力，就是一个一个删过去，然后喜提超时。

第二个思路是考虑嵌套类问题用递归解，具体可见我的这篇文章嵌套类问题的递归及N皇后问题，先不说由于本人太菜，递归写了好久才写出来，结果还是超时。（已红温）

最后才想到可以使用栈结构来维护前括号，这样只需要遍历一遍即可。