2022 China Collegiate Programming Contest (CCPC) Guilin Site

今天药忘吃喽~ 2024-02-17 12:48 38阅读 0赞

## A.Lily ##

[Problem - A - Codeforces][]

题意

![67b42e3098944de79be6bba455d7bc29.png][]

思路

数所有周围没L的格子

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    constexpr int N = 2e5 + 10;
    constexpr int mod = 1e9 + 7;
    constexpr int Inf = 0x3f3f3f3f;
    constexpr double eps = 1e-10;
    
    std::string s;
    
    int n;
    
    void solve() {
        std::cin >> n >> s;
        s = " " + s;
        for (int i = 1; i <= n; i ++) {
            if (s[i] == 'L') continue;
            if (i == 1) {
                if (s[i + 1] != 'L') {
                    s[i] = 'C';
                }
            }else if (i == n) {
                if (s[i - 1] != 'L') {
                    s[i] = 'C';
                }
            }else {
                if (s[i - 1] != 'L' && s[i + 1] != 'L') {
                    s[i] = 'C';
                }
            }
        }
        std::cout << s.substr(1, n) << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        while(t --) {
            solve();
        }
        return 0;
    }

## M. Youth Finale ##

[Problem - M - Codeforces][]

题意

给定一个排列，每次可以翻转这个排列，或者循环往左一个单位，给定操作序列，问操作之后给序列做冒泡排序的操作次数

思路

冒泡排序的操作次数其实就是逆序对的对数，那就是求操作之后的逆序对有多少

考虑DS的思想，我们对它的逆序对统计，考虑两次操作对逆序对的贡献

第一种就是逆序对个数 = 长度 - 逆序对个数

对于第二种，考虑操作一下，变化量就是 cur - pre

cur就是原序列中比操作数大的数

pre就是原序列中比操作数小的数

减一下就行

然后发现需要维护操作数，那就拿个 idx 维护即可，发现第一种操作会让方向反向，因此维护 x 方向

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    #define lowbit(x) (x & (- x))
    
    constexpr int N = 1e6 + 10;
    constexpr int mod = 1e9 + 7;
    constexpr int Inf = 0x3f3f3f3f;
    constexpr double eps = 1e-10;
    
    std::string s;
    
    int n, m;
    int p[N];
    int tr[N];
    
    void add(int x, int k) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += k;
    }
    int query(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
    void solve() {
        std::cin >> n >> m;
        for (int i = 1; i <= n; i ++) std::cin >> p[i];
        std::cin >> s;
        s = " " + s;
    
        int cur = 0;
        for (int i = 1; i <= n; i ++) {
            cur += query(n) - query(p[i]);
            add(p[i], 1);
        }
        std::cout << cur << "\n";
    
        int idx = 1, x = 1;
        for (int i = 1; i <= m; i ++) {
            if (s[i] == 'S') {
                cur = cur - (p[idx] - 1) + (n - (p[idx] + 1) + 1);
                idx = idx + x;
                if (idx == n + 1) idx = 1;
                else if (idx == 0) idx = n;
            }else {
                cur = n * (n - 1) / 2 - cur;
                idx = idx - x;
                if (idx == 0) idx = n;
                else if (idx == n + 1) idx = 1;
                x = -x;
            }
            std::cout << cur % 10;
        }
        std::cout << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        while(t --) {
            solve();
        }
        return 0;
    }

## E. Draw a triangle ##

题意

![7df1220fe9d7444e924272c367a77e62.png][]

思路

![d49010f8b94e43059048aacc0bfe6e75.png][]

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    #define lowbit(x) (x & (- x))
    
    constexpr int N = 1e6 + 10;
    constexpr int mod = 1e9 + 7;
    constexpr int Inf = 0x3f3f3f3f;
    constexpr double eps = 1e-10;
    
    int a, b, c, d;
    int v, u;
    
    int exgcd(int a, int b, int &v, int &u) {
        if (!b) {
            v = 1, u = 0;
            return a;
        }
        int gcd = exgcd(b, a % b, u, v);
        u -= (a / b) * v;
        return gcd;
    }
    void solve() {
        std::cin >> a >> b >> c >> d;
        int x = c - a;
        int y = d - b;
        int gcd = exgcd(x, -y, v, u);
        std::cout << a + u << " " << b + v << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        std::cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

## C. Array Concatenation ##

题意

![6e171f5dfaeb489285f6b8a4ad3edff8.png][]

![7f0e3aa24c664731973b8ff72f087a2a.png][]

#include <iostream>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    #define int long long
    typedef long long lld;
    const int N = 100005;
    const lld p = 1000000007;
    lld sum[N], a[N], tot[N];
    lld powe(lld a, lld b) {
    	lld base = 1; 
    	while(b) {
    		if(b & 1) base = base * a % p;
    		a = a * a % p; b >>= 1;
    	}
    	return base;
    }
    lld pos_t = 0, neg_t = 0, squ = 0;
    lld ans1 = 0, ans2 = 0;
    signed main() {
    	int n, m; scanf("%lld%lld", &n, &m);
    	for(int i = 1; i <= n; i++) {
    		scanf("%lld", &a[i]);
    		squ += a[i]; squ %= p;
    	}
    	for(int i = 1; i <= n; i++) {
    		sum[i] = (sum[i - 1] + a[i]) % p;
    		pos_t = (pos_t + sum[i]) % p;
    	}
    	for(int i = n; i >= 1; i--) {
    		tot[i] = (tot[i + 1] + a[i]) % p;
    		neg_t = (neg_t + tot[i]) % p;
    	}
    	squ = squ * n % p;
    	ans1 = ans2 = squ * powe(2, m - 1) % p * (powe(2, m) - 1 + p) % p; 
    	ans1 = (ans1 + powe(2, m - 1) * pos_t % p) % p;
    	ans1 = (ans1 + powe(2, m - 1) * neg_t % p) % p;
    	ans2 = (ans2 + powe(2, m) * pos_t % p) % p;
    	printf("%lld", max(ans1, ans2)); 
    	return 0;
    }

[Problem - A - Codeforces]: https://codeforces.com/gym/104008/problem/A
[67b42e3098944de79be6bba455d7bc29.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/f0036d81ea0f474bbba05430692c9360.png
[Problem - M - Codeforces]: https://codeforces.com/gym/104008/problem/M
[7df1220fe9d7444e924272c367a77e62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/09fe421f954f4b60a9015dfec8bfe9a0.png
[d49010f8b94e43059048aacc0bfe6e75.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/78f02de0a9874b8681d3f282507d6665.png
[6e171f5dfaeb489285f6b8a4ad3edff8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/6793b178e39c44aaae3eb58cdbe3298c.png
[7f0e3aa24c664731973b8ff72f087a2a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/89e9327fe07c45ed84fc058b72fc16cc.png