Blog - Floating Ocean
0%

Codeforces - Round 855 Div 3

发表于 更新于
本文字数： 5.8k 阅读时长 ≈ 10 分钟
阅读次数： Valine：

Contestant(alt). Rank 3678. Rating +62(+262 -200).

A. Is It a Cat?

题意

给定一个字符串，转化为小写字母后，判断其是否由 组成，四个字母可以出现重复多个，但顺序不能改变，且每一个字母必须出现至少一次。如 。

思路

如题，我们只需用一个变量存储当前遍历到了哪个字母，若比较到某一个字母的时候，遍历的下标越界，那么输出 。否则，在最后判断一下四个字母是否都出现了至少一次，若满足那么 ，否则 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int tp = 0;
        char up[4] = {'M', 'E', 'O', 'W'}, lo[4] = {'m', 'e', 'o', 'w'};
        bool ok[4] = {false};
        bool f = true;
        for(int i=0;i<n;i++){
            while(tp < 4 && s[i] != up[tp] && s[i] != lo[tp]) tp ++;
            if(tp >= 4){
                f = false;
                break;
            }
            ok[tp] = true;
        }
        cout << (ok[0] && ok[1] && ok[2] && ok[3] && f ? "YES\n" : "NO\n");
    }
}

瞎模拟即可

B. Count the Number of Pairs

题意

给定一个字符串以及一个整数 ，规定同一个字母的大写和小写可以进行配对，一个字符只能出现在一对数中。定义一次操作为选择一个字符改变它的大小写，输出在小于等于 次的操作后，最多有多少对数。

思路

我们用两个数组解决这个问题：

  1. 令小写字母对应权值为 ，大写字母对应权值为 ，那么加权后每种字母的总和的绝对值可以表征配对了多少对。我们记它为 。

  2. 统计每一种数出现的次数 。

那么，在不进行操作的前提下，我们易得最后的答案为 。

若可以进行操作，那么对于一个字母剩余的数 ，我们可以配对 个。

因此，最后的答案即为 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int cnt[26]{}, ans[26]{};
        for(int i=0;i<n;i++){
            if(s[i] >= 'a' && s[i] <= 'z') {
                cnt[s[i] - 'a'] ++;
                ans[s[i] - 'a'] ++;
            }else{
                cnt[s[i] - 'A'] ++;
                ans[s[i] - 'A'] --;
            }
        }
        int res = 0, left = 0;
        for(int i=0;i<26;i++){
            res += (cnt[i] - abs(ans[i])) / 2;
            left += abs(ans[i]) / 2;
        }
        cout << res + min(k, left) << '\n';
    }
}

总感觉类似的题哪里做过

C1. Powering the Hero (easy version)

详见C2，区别是C1的数据量更小一点

C2. Powering the Hero (hard version)

题意

给定 个卡牌对应的数字，从前向后遍历，若数字不为 ，那么可以选择是否将该数放在堆顶，或者将其丢弃。对于所有为 的数字，从堆顶拿出一个牌作为这个 的加分值，并将这两个牌丢弃，若堆为空则不考虑。输出最后加分的最大值。

思路

既然可以选择放或不放，那么我们一定可以让后面的 个 拿到前面的前 大的数。

因而，我们直接用优先队列即可。

有趣的是，困难版的数据量也无碍。

时间复杂度：最坏

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        priority_queue<int> q;
        int ans = 0;
        for(int i=0;i<n;i++) {
            int cur;
            cin >> cur;
            if(cur != 0) q.push(cur);
            else if(!q.empty()) ans += q.top(), q.pop();
        }
        cout << ans << '\n';
    }
}

赛时贪错了，吃了WA

D. Remove Two Letters

题意

给定一个字符串，输出去掉连续的两个字母后，得到的所有字符串中不同的字符串的个数。

思路

我们不妨取补集：

对于一个序列，若要出现重复的子串，那么需要满足 ，这样的话，去掉 和去掉 就是等价的了。

因而，我们统计出对数，用 减去即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans = 0, cnt = 1;
        char pre0 = s[0], pre1 = s[1];
        for(int i=1;i<n-1;i++){
             char cur0 = s[i], cur1 = s[i + 1];
             if((pre0 == cur0 && pre1 == cur1) || pre0 == cur1 && pre1 == cur0){
                 cnt ++;
             }else{
                 ans += cnt - 1;
                 cnt = 1;
                 pre0 = cur0, pre1 = cur1;
             }
        }
        cout << n - (ans + cnt - 1) - 1 << '\n';
    }
}

赛时的代码居然还写的麻烦了一点（（

E1. Unforgivable Curse (easy version)

详见E2，区别是本题k=3

E2. Unforgivable Curse (hard version)

题意

给定两个长度相等的字符串 ，定义操作为交换 或 上的数，在任意数量的操作后，输出是否可以将 更改为 。

思路

首先，我们只需进行下面的操作即可将相邻数交换：

因而，只要可以进行上面的操作（或者向左），那么我们只需进行一定的操作，肯定可以将其换到我们需要的为止。

那么，我们也不难发现，若要向右交换，那么 ，若要想左交换，那么 。

因而，只要 内的字符相等，就一定有解。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int a[N];

void solve(){
    int n, k;
    cin >> n >> k;
    string s, t;
    cin >> s >> t;
    if(n <= k) cout << (s == t ? "YES\n" : "NO\n");
    else{
        bool f = true;
        if(2 * k > n){
            for(int i=n-k;i<k;i++)
                if(s[i] != t[i]) f = false;
        }
        if(f){
            sort(s.begin(), s.end());
            sort(t.begin(), t.end());
            f = s == t;
        }
        cout << (f ? "YES\n" : "NO\n");
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while(t --) solve();
}

比赛快结束的时候就懒得写了（其实还挺好写的

F. Dasha and Nightmares

题意

给定 个字符串，输出有多少对字符串，满足下面的条件：

  1. 两个字符串的长度总和为奇数；

  2. 不同字母的个数为 ；

  3. 每种字母出现的次数为奇数。

思路

首先，第一个条件可以忽略，因为偶数个奇数相加，一定是奇数。

其次，第二个条件即为排除掉一个字母，需要其余的字母均出现。

考虑到 足够小，我们不妨用状压。

更具体地说，我们枚举不出现的字母 ，然后枚举所有字符串，对于字符串 ，它的所有字母的出现次数均可以预处理。但，因为我们只需考虑奇偶性，所以我们不妨令奇数状态为 ，偶数状态为 ，按照字母表顺序构建一个 位二进制字符串，便可以得到这个字符串的”哈希”值。

那么，考虑到异或的可逆性，对于一个排除掉 的拼接后的字符串，它的哈希值一定为形如 ， 位即为 。那么，对于这个 ，我们可以将其和 的哈希值进行异或，得到需要和其配对的字符串的哈希值。

显然，对于第 个字符串，我们只需遍历前 个字符串是否可以与其配对即可。那么，我们可以用 存储一个哈希值对应的字符串有多少个，最后统计总和即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 5e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

int odd[N], num[N];

void solve(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        string cur;
        cin >> cur;
        for(char e : cur){
            odd[i] ^= (1 << (e - 'a'));
            num[i] |= (1 << (e - 'a'));
        }
    }
    int ans = 0;
    for(int i=0;i<26;i++){ //不选i
        map<int, int> cnt;
        int tot = ((1 << 26) - 1) ^ (1 << i);
        for(int j=0;j<n;j++){
            if(!(num[j] & (1 << i))){
                ans += cnt[tot ^ odd[j]];
                cnt[odd[j]] ++;
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

我好若，居然想不到状压