codeforces周赛div3#855记录

总结

真羡慕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;
}