AtCoder Beginner Contest 372(C++实现)

比赛链接：Tasks - UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372)

A-delete

问题陈述

给你一个由小写英文字母和 . 组成的字符串 SS 。请找出从 SS 中删除所有 . 后得到的字符串。

思路

创建一个字符串来存储输入信息，在再创建一个字符串来存储除字符.外的所有字符。

代码

#include <iostream>
#include <string>
using namespace std;

int main()
{
	string s;
	cin >> s;
	string ans;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] != '.') {
			ans += s[i];
		}
	}
	cout << ans;
	return 0;
}

B - 3^A

问题陈述

给你一个正整数 $M$ 。求满足以下所有条件的正整数 $N$ 和非负整数序列 $A=(A_1,A_2,\dots ,A_N)$ ：

• $1\le N\le 20$
• $0\le A_i\le 10$ $(1\le i\le N)$
• $\sum _{i=1}^N{3}^{A_i}=M$

可以证明，在约束条件下，总是存在至少一对满足条件的 $N$ 和 $A$ 。

思路

因为M一定是由许多不同的3的幂得到的，也就说明了M一定是3的倍数，然后我们又可以知道，3的1次方会等于，3个3的0次方，以此往后类推，我们就可以得到，3的n次方会等于3个3的n-1次方。这就告诉了我们应该尽量去求3的高次幂，也就是贪心，我们从3的高次幂来往前推。
如果M可以由这个3的幂组成，就把该幂次存入数组。反之就降低幂次。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int m;
int main()
{
	cin >> m;
	//N [1,20];
	//a [0,10]
	//逆向思维
	int num = m;
	int ans_n = 0;
	vector<int> ans_v;
	int x = 10;
	while (num > 0) {
		int tmp = num - pow(3, x);
		if (tmp >= 0){
			ans_n += 1;
			ans_v.push_back(x);
			num = tmp;
		}
		else {
			if(x!=0)
				x -= 1;
		}
	}
	//因为我们是从后往前求，所以需要逆置一下
	reverse(ans_v.begin(), ans_v.end());
	cout << ans_n << endl;
	for (int i = 0; i < ans_v.size(); ++i) {
		cout << ans_v[i] << ' ';
	}
	return 0;
}

C - Count ABC Again

问题陈述

给你一个长度为 $N$ 的字符串 $S$ 。同时还给了你 $Q$ 个查询，你应该按顺序处理这些查询。

$i$ -th 查询如下：

• 给定一个整数 $X_i$ 和一个字符 $C_i$ ，用 $C_i$ 替换 $S$ 中的 $X_i$ -th 字符。然后，打印字符串 ABC 作为子串出现在 $S$ 中的次数。

这里， $S$ 的子串是指从 $S$ 的开头删除零个或多个字符，从结尾删除零个或多个字符后得到的字符串。
例如，ab是abc的子串，但ac不是abc的子串。

思路

因为要求的是字串而且还固定了，那么求子串的操作就很简单了。直接遍历字符串，每次往取3个字符进行比较就可以了，这样的话，我们就求出了最初版本的字串数量num了。
不过这题的重点肯定不是求字串。因为字符串每次都会变一个字符，每次都重新求的话，程序会超时的。为了防止超时，肯定要做一些策略。
可以知道的是，每一次都只会改变一个，那么这个字符影响的范围就固定了，取极限情况，该字符会影响的范围，只要它的前两个字符和后两个字符。也就是说，加上自己该字符会影响5个字符的范围，为此我们每次只需要检查这5个字符。如果改变字符导致目标子串出现j就让num+1,反之num-1，就考虑到越界情况，加个判断就可以了。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n, t;
int func(string& s, const string& tmp) {
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (s.substr(i, 3) == tmp) {
			ans += 1;
		}
	}
	return ans;
}
int main()
{
	cin >> n >> t;
	string s;
	cin >> s;
	int num = func(s, "ABC");
	while (t--) {
		int x;
		char c;
		string tmp = s;
		cin >> x;
		x -= 1;
		cin >> c;
		s[x] = c;
		for (int i = 0; i <= 2 && x - i >= 0; ++i) {
			if (s.substr(x - i, 3) == "ABC" && tmp.substr(x - i, 3) != "ABC") {
				num += 1;
			}
			else if (s.substr(x - i, 3) != "ABC" && tmp.substr(x - i, 3) == "ABC") {
				num -= 1;
			}
		}
		for (int i = 1; i <= 2 && x + i < n; ++i) {
			if (s.substr(x + i, 3) == "ABC" && tmp.substr(x + i, 3) != "ABC") {
				num += 1;
			}
			else if (s.substr(x + i, 3) != "ABC" && tmp.substr(x + i, 3) == "ABC") {
				num -= 1;
			}
		}
		cout << num << endl;
		
	}
	return 0;
}

D - Buildings

问题陈述

有 $N$ 幢楼房，依次为 $1$ 幢、 $2$ 幢、 $\dots$ 幢、 $N$ 幢。 $i$ 号楼的高度为 $(1\le i\le N)$ 。 $(1\le i\le N)$ 的高度为 $H_i$.。

求每个 $i=1,2,\dots ,N$ 的整数$j$ $(i<j\le N)$ 的个数。$(i<j\le N)$ 满足下列条件：

• 在建筑物 $i$ 和 $j$ 之间没有比建筑物 $j$ 高的建筑物。

思路

要求为建筑物i和j间没有比建筑物j高的建筑物数量(不包括i)，为此我们可以用单调栈来解决问题。创建一个栈，从后往前遍历数组，不过是从倒数第2个元素开始，因为最后一个元素对应的值一定是0。但是我们比较时要让i+1。
这样的话，算法的逻辑就出来了，当栈不为空时，就循环比较，如果栈顶元素小于v[i+1]就出栈。如此一来就可以保证i到j内的数没有比v[j]大的元素。循环结束后要让v[i+1]入栈，因为出了最后一个元素，其他的每个元素保底都有一个相邻的元素满足条件。最后每个v[i]对应的答案就是当前栈中元素的个数。

代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> v(n+1);
	for (int i = 1; i <= n; ++i) {
		cin >> v[i];
	}
	//要求为建筑物i和j间没有比建筑物j高的建筑物数量
	//单调栈？
	stack<int> st;
	vector<int> ans(n + 1);
	for (int i = n - 1; i >= 1; --i) {
		while (!st.empty() && v[st.top()] < v[i + 1]) {
			st.pop();
		}
		st.push(i + 1);
		ans[i] = st.size();
	}
	for (int i = 1; i <= n; ++i) {
		cout << ans[i]<<' ';
	}
	return 0;
}