Codeforces Round #753 (Div. 3) 【C++】

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

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

∑ i = 1 n − 1 ∣ s z [ s i ] − s z [ s i − 1 ] ∣ sum_{i = 1}^{n-1} lvert sz[s_i] - sz[s_{i-1}] rvert i=1∑n−1​∣sz[si​]−sz[si−1​]∣

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

#include
#include 
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;
}

要点: 映射 模拟

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

1. 当前 x x x 是奇数， x = x + d x = x + d x=x+d
2. 当前 x x x 是偶数， x = x − d x = x - d x=x−d

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

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

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

1. n ≡ 0 m o d    4 n equiv 0 mod{4} n≡0mod4 时： x x x
2. n ≡ 1 m o d    4 n equiv 1 mod{4} n≡1mod4 时： x + n x + n x+n (奇数)，否则 x − n x - n x−n (偶数)
3. n ≡ 2 m o d    4 n equiv 2 mod{4} n≡2mod4 时： x − 1 x - 1 x−1 (奇数)，否则 x + 1 x + 1 x+1 (偶数)
4. n ≡ 3 m o d    4 n equiv 3 mod{4} n≡3mod4 时： x − n − 1 x - n - 1 x−n−1 (奇数)，否则 x + n + 1 x + n + 1 x+n+1 (偶数)

#include
#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;
}

要点: 分类讨论 找规律

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

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

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

这种思路下算法的时间复杂度为 O ( n   ⋅ l o g 2 n ) O(n cdotp log_2^n) O(n ⋅log2n​)， 2   ⋅ 1 0 5 2 cdotp 10^5 2 ⋅105的数据范围内可用。

#include
#include
#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;
}

要点：思维 懒标记

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

1. 如果 s i s_i si​ = ‘B’， a i = a i − 1 a_i = a_i - 1 ai​=ai​−1
2. 如果 s i s_i si​ = ‘R’， a i = a i + 1 a_i = a_i + 1 ai​=ai​+1

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

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

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

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

#include
#include
#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;
}

要点： 贪心