codeforces周赛div3#855记录

目录

总结

一，A. Is It a Cat?

二，B. Count the Number of Pairs

三，C1. Powering the Hero (easy version)

四，C2. Powering the Hero (hard version)

---

总结

真羡慕ACM校队的同学，能AC七八题，甚至ak

可能别人从div4一道题都做不对，到div3，AC 九题，只需要几个月的时间😲

那么从div3AK到div2AK他们又需要多久呢？也许是半年？

div2AK的实力，拿铜牌是否有希望呢，观望大佬成长

对于字符串，vector, queue的常用函数的使用还很生疏，所幸经过这次锻炼，下次应该可以AC同类型的题

因为不熟练，浪费了接近一半的时间在百度搜vector和queue的用法，以及字符串常用函数

知识点

1，字符串常用函数

头文件#include<cstring>

1，截取子串

s.substr(i)从下标i开始截取到结尾，s.substr(i, j)从下标i开始截取j个字符

2，替换子串

s.replace(i, j, s1)用s1替换s中从下标i开始的j个字符

3，查找子串

s.find(s1) 查找s1在s中第一次出现的下标

s.rfind(s1) 查找s1在s中最后一次出现的下标

4，删除子串

s.erase(i, j)删除从下标i开始的j个字符

关于s.find()补充

#include<iostream>
#include<cstring>
using namespace std;int main()
{string s1 = "babajiaoni";string s2 = "bajiao";string s3 = "babb";if(s1.find(s3) == string::npos) //找不到子串cout<<"找不到子串"<<endl;if(s1.find(s2) != string::npos) //能找到子串cout<<"能找到子串";return 0;
}

找不到子串
能找到子串

2，queue

→ (2条消息) C++优先队列priority_queue详解_priority_queue头文件_是一只派大鑫的博客-CSDN博客

→ 

(5条消息) C++队列queue用法详解（超详细）_轻松学C语言的博客-CSDN博客

3，vector

→ (5条消息) c++ vector详解_~不羁的博客-CSDN博客

反思

只过了2题，第三题一开始尝试vector + priority_queue，但是写了70多行，非常混乱，写写改改，最后还是没过

今早补题，才发现想复杂了，臆想多了一个限制条件，但是样例并没有体现我这个思路的错误

后来拿第三题(easy version)AC的代码提交第四题(hard)，发现第四题也直接过了

一，A. Is It a Cat?

Problem - A - Codeforces

标签：模拟，字符串

这个思路不是很清晰，写写改改才AC，代码非常臃肿

用了字符串函数中的s.find()和s.rfind()，头文件是#include<cstring>

关键是，现在codeforces不知道为什么禁止中文注释了，说我不符合utf-8标准。。。。

这里又浪费了10分钟。。

AC  代码

#include<iostream>
#include<cstring> //s.find(s1)
using namespace std;
int main()
{int t, n;string s;cin>>t;while(t--) {int flag = 1;cin>>n;cin>>s;for(int i = 0; i < n; ++i)if(s[i] == 'M' || s[i] == 'E' ||s[i] == 'O' || s[i] == 'W')s[i] += 32;if(s.find('w') == string::npos || s.find('o') == string::npos|| s.find('e') == string::npos || s.find('m') == string::npos) {cout<<"NO"<<endl;continue;}else if(s.find('w') < s.find('o') || s.find('o') < s.find('e')|| s.find('e') < s.find('m')) {cout<<"NO"<<endl;continue;}else if(s.rfind('m') + 1 != s.find('e') ||s.rfind('e') + 1 != s.find('o') ||s.rfind('o') + 1 != s.find('w')) {cout<<"NO"<<endl;continue;}for(int i = 1; i <= s.rfind('m'); ++i)if(s[i] != s[i - 1]) {flag = 0;cout<<"NO"<<endl;break;}for(int i = s.find('e') + 1; i <= s.rfind('e'); ++i)if(s[i] != s[i - 1]) {flag = 0;cout<<"NO"<<endl;break;}for(int i = s.find('o') + 1; i <= s.rfind('o'); ++i)if(s[i] != s[i - 1]) {flag = 0;cout<<"NO"<<endl;break;}for(int i = s.find('w') + 1; i < n; ++i)if(s[i] != s[i - 1]) {flag = 0;cout<<"NO"<<endl;break;}if(flag)cout<<"YES"<<endl;}return 0;
}

二，B. Count the Number of Pairs

Problem - B - Codeforces 

标签：贪心，字符串

 

 初始思路不是很清晰，写了50多行才AC

AC  代码

#include<iostream>
#include<cstring>
using namespace std;
int a[26], b[26];
int main()
{int t, n, k, ans;string s;cin>>t;while(t) {t--;memset(a, 0, sizeof(a));memset(b, 0, sizeof(b));ans = 0;cin>>n>>k;cin>>s;for(int i = 0; i < n; ++i) {if(s[i] >= 'a' && s[i] <= 'z')a[s[i] - 'a']++;if(s[i] >= 'A' && s[i] <= 'Z')b[s[i] - 'A']++;}for(int i = 0; i < 26; ++i) {if(a[i] >= b[i]) {ans += b[i];a[i] -= b[i];b[i] = 0;}else {ans += a[i];b[i] -= a[i];a[i] = 0;}}for(int i = 0; i < 26; ++i) {if(a[i] >= 2)while(k > 0 && a[i] >= 2) {ans += 1;k--;a[i] -= 2;}else if(b[i] >= 2)while(k > 0 && b[i] >= 2) {ans += 1;k--;b[i] -= 2;}if(k == 0) break;}cout<<ans<<endl;}return 0;
}

三，C1. Powering the Hero (easy version)

Problem - C1 - Codeforces

标签：数据结构，贪心 

 

 这题臆想多了一个限制条件，多做了很多无用功，最后还不符合题意

简单的queue使用，其他都不需要了

30行优先队列能搞定的，我一开始愣是结合vector写了70行 

AC  代码

#include<iostream>
#include<queue>
#include<cstdio> //scanf()
using namespace std;
int main()
{int t, n;scanf("%d", &t);while(t) {t--;scanf("%d", &n);long long ans = 0, m;priority_queue<int>q;for(int i  = 0; i < n; ++i) {scanf("%lld", &m);if(m != 0) {q.push(m);}if(m == 0)if(!q.empty()) {ans += q.top();q.pop();}}cout<<ans<<endl;}return 0;
}

四，C2. Powering the Hero (hard version)

标签：数据结构，贪心

同第三题，只是数据量不同，第三题AC  代码提交，也能过

AC  代码

同第3

#include<iostream>
#include<queue>
#include<cstdio> //scanf()
using namespace std;
int main()
{int t, n;scanf("%d", &t);while(t) {t--;scanf("%d", &n);long long ans = 0, m;priority_queue<int>q;for(int i  = 0; i < n; ++i) {scanf("%lld", &m);if(m != 0) {q.push(m);}if(m == 0)if(!q.empty()) {ans += q.top();q.pop();}}cout<<ans<<endl;}return 0;
}