AtCoder Beginner Contest 372(C++实现)
AtCoder Beginner Contest 372(C++实现)
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一定是由许多不同的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
问题陈述
给你一个长度为
的字符串
。同时还给了你
个查询，你应该按顺序处理这些查询。
-th 查询如下：
- 给定一个整数
和一个字符
，用
替换
中的
-th 字符。然后，打印字符串 ABC 作为子串出现在
中的次数。
这里，
的子串是指从
的开头删除零个或多个字符，从结尾删除零个或多个字符后得到的字符串。
例如，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
问题陈述
有
幢楼房，依次为
幢、
幢、
幢、
幢。
号楼的高度为
。
的高度为
.。
求每个
的整数
的个数。
满足下列条件：
- 在建筑物
和
之间没有比建筑物
高的建筑物。
思路
要求为建筑物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;
}腾讯云开发者
