AtCoder Beginner Contest 328) C、D 补题"/>
【刷题】(AtCoder Beginner Contest 328) C、D 补题
前言
第一次打 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;
}
总结
虽然库函数很好用 但遇到大的数据量的时候 还是要注意一些 很容易TLE
太痛苦了
结尾
AB没什么可说的 CD都是TLE E看了一眼 看到了图 不打算做了
第一次打atcoder 感觉还是不太好
菜就多练 以前是以前 现在是现在
我们下篇文章见
更多推荐
【刷题】(AtCoder Beginner Contest 328) C、D 补题
发布评论