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

【刷题】(AtCoder Beginner Contest 328) C、D 补题

news 2025/8/19 18:31:02

前言

第一次打 a了两道 C、D都是TLE 看了其他人的题解之后有一些想法所以发一篇博客

C

题干

题目链接

我的思路及做题过程

我的思路是输入left、right 再在这个区间内计算字母相同的对数

代码是：

#include<iostream>
#include<cmath>
#include<algorithm>using namespace std;int main()
{int n, q, le, ri, _max = 0;string str;cin >> n >> q >> str;for (int i = 0; i < q; i++) {cin >> le >> ri;int num = 0;for (int j = le - 1; j < ri - 1; j++) {if (str[j] == str[j + 1]) {num++;}}cout << num << endl;}return 0;
}

tle了

优化

其实在每一个小的区间里 对数是不变的
所以我们可以先遍历字符串找到每个小的区间内的对数
再根据输入的left和right输出相应区间内的对数

遍历

遍历的过程是下面这样

for (int i = 1; i <= n; i++)
{if (str[i] == str[i - 1]){t++;num[i] = t;}else{num[i] = t;}
}

输出

		cout << num[right - 1] - num[left - 1] << endl;

思考

写题要有自己的思考不要题目说什么就写什么
不然简单题也会吃亏

D

题干

题目链接

我的思路及做题过程

使用find函数和erase函数
find函数查找”ABC“ erase函数删除”ABC“

但是TLE了

我在想是不是数据量大的时候库函数太慢了

就只用循环和判断语句来写了

#include<iostream>using namespace std;char a[200100];
string s;
int main() {cin >> s;int left = 0;int right = 0;while (left < s.size()) {right++;a[right] = s[left];//赋值给另一个数组if (right >= 3) {if (a[right] == 'C' && a[right - 1] == 'B' && a[right - 2] == 'A') {//满足条件 就减少输出的范围 即rightright -= 3;}}left++;}for (int k = 1; k <= right; k++)cout << a[k];return 0;
}