[C++知识库]Codeforces Round #753 (Div. 3) 【C++】

Codeforces Round #753 (Div. 3)。当作记事本，简单写点题解，当是为自己留下纪念。

A. Linear Keyboard

问题描述：

$t$ 组数据，每组有一个长度是 $26$ 的字符串 $p$，和一个长度是 $1$ 到 $50$ 的字符串 $s$。$p$，$s$ 只包含从 $a$ 到 $z$ 的小写拉丁字母，$p$ 是拉丁字母的某种排列，定义数组$sz$，满足$sz[p[i]]=i+1(0\le i<26)$，求如下：

$$\sum _{i=1}^{n?1}|sz[s_i]?sz[s_{i?1}]|$$

问题思路：

数据量允许 $O(n)$ 时间复杂度，所以照着上面的公式直接模拟即可。

实现代码：

#include<iostream>
#include<cmath> 
int t;
std::string s;
int a[26];
 
int main(){
    std::cin >> t;
    while(t--){
        std::cin >> s;
        for(int i = 0; i < 26; i++){
            a[s[i]-'a'] = i + 1;
        }
        
        std::cin >> s;
        int ans = 0;
        for(int i = 1, j = s.size(); i < j; i++){
            ans += abs(a[s[i]-'a'] - a[s[i-1]-'a']);
        }
        std::cout << ans << std::endl;
    }
    return 0;
}

要点: 映射 模拟

B. Odd Grasshopper

问题描述：

$t$ 组数据，每组给两个整数 $x$，$n$，$x$ 表示初始值，$n$ 表示要执行的操作数。记 $d$ 为：当前是第 $d$ 次操作 $(1\le d\le n)$，操作如下：

1. 当前 $x$ 是奇数，$x=x+d$
2. 当前 $x$ 是偶数，$x=x?d$

求执行 $n$ 次操作后，$x$ 的值。

问题思路：

题目要求非常明确，第一反应是按照题意模拟，但是 $n$ 的数据范围高达 $10^{14}$，所以必须找规律。
我们对 $x$ 的奇偶性分类讨论，找前 $8$ 轮 $x$ 值变化的规律，得到下表：

通过上表，可以总结如下：

1. $n\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}4$ 时：$x$
2. $n\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}4$ 时：$x+n$ (奇数)，否则 $x?n$ (偶数)
3. $n\equiv 2\mathrm{m}\mathrm{o}\mathrm{d}4$ 时：$x?1$ (奇数)，否则 $x+1$ (偶数)
4. $n\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}4$ 时：$x?n?1$ (奇数)，否则 $x+n+1$ (偶数)

实现代码：

#include<iostream>
#define ll long long
 
int t;
ll n, x;
 
int main(){
    std::cin >> t;
    while(t--){
        std::cin >> x >> n;
        ll b = n % 4;
        
        if(x & 1){
            if(b == 0){
                std::cout << x << std::endl;
            }else if(b == 1){
                std::cout << x + n << std::endl;
            }else if(b == 2){
                std::cout << x - 1 << std::endl;
            }else{
                std::cout << x - 1 - n << std::endl;
            }
        }else{
            if(b == 0){
                std::cout << x << std::endl;
            }else if(b == 1){
                std::cout << x - n << std::endl;
            }else if(b == 2){
                std::cout << x + 1 << std::endl;
            }else{
                std::cout << x + 1 + n << std::endl;
            }
        }
        
    }
    return 0;
}

要点: 分类讨论 找规律

C. Minimum Extraction

问题描述：

$t$ 组数据，每组给长度 $n$ 的整数数组 $a$，在数组长度 $>1$的前提下，可以执行0或者多次如下操作：选择数组中最小值，删除它，并将数组中所有值减去这个值。现在要求执行任意次操作后，使得数组中最小值尽可能大，并打印这个最小值。

问题思路：

执行 $0$ 次操作，最小值就是原数组的最小值。可以发现，因为每次操作都会对数组中所有元素减去同一个值，元素的相对大小不变，所以执行 $n$ 次操作(包括 $0$ 次)，输出 $n$ 个最小值的顺序和升序排序后的原数组是一一对应的。我们最多操作 $n$ 次(包括 $0$ 次)，要求最小值的最大可能，可以直接枚举 $0$ 到 $n?1$ 次操作后的最小值，然后选择最大的即可。

我们将原数组升序排序，从 $0$ 开始枚举。现在关键的问题是，每个删掉的最小值都会对原数组进行更改，这里我们没必须用线段树对区间做减法。可以用 $off$，来表示偏移量，将前 $i$ 个 $a[i]$ 的真值进行累加，代表执行 $i+1$ 次操作 $(0\le i<n?1)$，那么最小值 $a[i+1]$ 的真值就是 $a[i+1]?sum$，最终维护最大的 $a[i+1]?sum$ 即可。

这种思路下算法的时间复杂度为$O(n?lo{g}_2^n)$，$2?10^5$的数据范围内可用。

实现代码：

#include<iostream>
#include<algorithm>
#define ll long long

int t;
int n;
ll a[200009];
int main(){
    std::cin >> t;
    while(t--){
        std::cin >> n;
        for(int i = 0; i < n; i++)
            std::cin >> a[i];
        std::sort(a, a+n);
        ll ans = a[0], sum = 0;
        for(int i = 0; i < n - 1; i++) {
            sum += a[i] - sum;
            ans = std::max(ans, a[i + 1] - sum);
        }
        std::cout << ans << std::endl;
    }
    return 0;
}

要点：思维 懒标记

D. Blue-Red Permutation

问题描述

$t$ 组数据，每组给一段长度 $n$ 的整数数组 $a$，和同等长度的字符串 $s$。可以执行任意次如下操作：

1. 如果 $s_i$ = ‘B’，$a_i=a_i?1$
2. 如果 $s_i$ = ‘R’，$a_i=a_i+1$

现在问，是否存在执行任意次操作使得数组 $a$ 的值构成一个从 $1$ 到 $n$ 的某种排列

问题思路

先将不同颜色的元素分开，得到放’B’的数组 $b$，和放’R’的数组 $r$。从全排列着手，枚举 $i$ $1\le i\le n$，判断 $i$ 能否通过数组 $b$ 或者 $r$ 中某个数得到。我们从小到大枚举 $i$，对于每一个 $i$ 进行分类讨论：

1. 如果存在’B’和’R’可以覆盖 $i($ 也就是存在$b_i\ge i$ 且 $r_i\le i)$，那么是选择’B’还是’R’?因为 $i$ 是递增的，如果使用’R’可能会出现 $i+1$ 且‘B’不能覆盖；但是选择’B’，至少这个可能存在的 $i+1$ 是可以被这个’R’给解决掉的。故有‘B’用’B’。
2. 如果只存在’B’可以覆盖 $i($也就是存在 $b_i\ge i)$，那么选择 $b_i$大的还是小的呢？还是因为 $i$ 是递增的，用掉大的 $b_i$ 可能导致后续小的 $b_i$ 无法够到大的 $i$。故从小到大选 $b_i$。
3. 如果只存在’R’可以覆盖 $i($也就是存在 $ri\le i)$，那么选择 $r_i$ 大的还是小的呢？首先 $i$ 是递增的，因为不管小的 $r_i$ 还是大的 $r_i$ 都 $\le i$，所以用掉其中一个，可能存在的 $i+1$ 依旧可以被另一个捕获。因此$r_i$大小选择无所谓。
4. 如果不存在’B’或者’R’可以覆盖 $i$，那么无法构成全排列。

综上，我们先对数组 $b$，$r$ 升序排列，然后遍历 $i$ 从 $1$ 到 $n$。因为 $b$，$r$ 都是有序的，所以我们可以使用双指针 $O(n)$ 判断 $i$ 点能否被覆盖，如果某次 $b$、$r$ 的指针都走到头了，那么无法构成；其他可以构成。

代码实现

#include<iostream>
#include<algorithm>
#define ll long long

int t;
int n, r[200009], b[200009], sr, sb;
std::string s;

void slv(){
    std::cin >> n;
    for(int i = 0; i < n; i++)
        std::cin >> b[i];
    std::cin >> s;
    sr = sb = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'R') r[sr++] = b[i];
        else b[sb++] = b[i];
    }        
    
    std::sort(b, b + sb);
    std::sort(r, r + sr);
    int pr = 0, pb = 0;
    
    for(int i = 1; i <= n; i++){
        // 先用B，没办法用A
        while(pb < sb && b[pb] < i){
            pb++;
        }
        
        if(pb < sb){
            pb++;
            continue;
        }
        
        while(pr < sr && r[pr] > i){
            pr++;
        }
        
        if(pr < sr){
            pr++;
            continue;
        }
        std::cout << "NO" << std::endl;
        return;
    }
        
    std::cout << "YES" << std::endl;
}

int main(){
    std::cin >> t;
    while(t--) slv();
    return 0;
}

要点： 贪心