526互联

2021 China Collegiate Programming Contest (CCPC) Guilin Site

发布时间 2023-10-13 16:55:23作者: PHarr

A. A Hero Named Magnus

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve(){
    int x;
    cin >> x;
    cout << 2ll * x - 1 << "\n";
    return ;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    for( cin >> T ; T ; T -- )
        solve();

    return 0;
}

B. A Plus B Problem

对于两个数的加法，一位最多只能被进位一次。

并且进位方式的情况一定是当前位\(i\)向右连续若干位（可以是 0 位）都是\(9\)，直到\(j\)第一个满足\(a_j+b_j\ne 9\)的情况下，判断\(a_j+b_j>=10\)即可知道当前位是否被进位。

而当前位进位向左可以进多少位呢？会进连续的\(a_j+b_j=9\)位，所以我们要早到第一个和不为 9 的位置。

所以我们要动态的维护所有和不等于 9 的位置，并且找到一个位置的前驱和后继，所以可以使用set来维护信息。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    string sa, sb;
    cin >> sa >> sb;
    vi a(n + 1), b(n + 1);
    set<int> s;
    for (int i = 1; i <= n; i++) {
        a[i] = sa[i - 1] - '0', b[i] = sb[i - 1] - '0';
        if (a[i] + b[i] != 9) s.insert(i);
    }
    for (int r, id, d, res, val, tmp; q; q--) {
        cin >> r >> id >> d;
        res = 2; // 至少有两位不同，剩下是进位造成的不同
        auto it = s.upper_bound(id);
        if (it == s.end()) { // 计算修改前的值
            val = a[id] + b[id];
        } else {
            int nxt = *(it);
            val = a[id] + b[id] + ((a[nxt] + b[nxt]) >= 10);
        }
        // 修改值
        if (r == 1) {
            if (d == a[id]) { // 没有变化
                cout << val % 10 << " 0\n";
                continue;
            }
            if (d + b[id] != 9) s.insert(id);
            else s.erase(id);
            a[id] = d;
        } else {
            if (d == b[id]) { // 没有变化
                cout << val % 10 << " 0\n";
                continue;
            }
            if (d + a[id] != 9) s.insert(id);
            else s.erase(id);
            b[id] = d;
        }
        // 重新计算值
        it = s.upper_bound(id);
        if (it == s.end()) {
            tmp = (a[id] + b[id]);
        } else {
            int nxt = (*it);
            tmp = a[id] + b[id] + ((a[nxt] + b[nxt]) >= 10);
        }
        cout << tmp % 10 << " ";
        if (tmp < 10 and val >= 10) { // 原本进位，现在不进位，要计算出原来进了多少位
            auto its = s.lower_bound(id);
            if (its != s.begin()) {
                its = prev(its), res += (id - (*its));
            } else res += id - 1;
        }else if ( tmp >= 10 and val < 10 ) { // 现在进位，原来不进位 ，要计算出现在进了多少位
            auto its = s.lower_bound(id);
            if (its != s.begin()) {
                its = prev(its), res += (id - (*its));
            } else res += id - 1;
        }
        cout << res << "\n";
    }
    return 0;
}

D. Assumption is All You Need

首先交换操作一定会使得逆序对的数量减少，所以\(A\)的逆序程度一定大于\(B\)的逆序程度，否则无解。

我们从左向右逐位判断，如果当前位\(i\) 满足前\(i-1\)位都合法，如果\(a_i< b_i\)则一定无解。反之我们要在后面找\(a_j=b_i\)然后交换过来。但是请注意，对于样例 3 就可以看出如果交换一步到位会使得\(A\)的逆序程度迅速减小，从而导致后续点无法交换，所以我们要使得每一次交换减小的逆序对数量最少。也即只要遇到\(a_j\)满足\(b_i\le a_j < a_i\)就把\(a_i,a_j\)交换。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve() {
    int n;
    cin >> n;
    vi a(n), b(n);
    for (auto &i: a) cin >> i;
    for (auto &i: b) cin >> i;
    vector<pii> res;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) continue;
        if (a[i] < b[i]) {
            cout << "-1\n";
            return;
        }
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[i] and a[j] >= b[i]) {
                res.emplace_back(i + 1, j + 1);
                swap(a[i], a[j]);
                if (a[i] == b[i]) break;
            }
    }

    cout << res.size() << "\n";
    for (auto [x, y]: res)
        cout << x << " " << y << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    for (cin >> T; T; T--)
        solve();

    return 0;
}

E. Buy and Delete

可以注意到是，Bob对于任意有向环，最多只需要两次就可以把所有的边全部删掉。

所以对于Alice来说，只要考考虑能不能买的起最小环，如果可以答案为 2。

如果不行，考虑能不能买得起最短边，如果可以，则答案为 1，反之为 0。

为什么两次一定可以把环全部删掉，很简单，对于有向边\((u,v)\)，第一次删除所有\(u<v\)的边，在删除所有\(u>v\)的边，即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;
using db = long double;

constexpr int inf = 1E18;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, c;
    cin >> n >> m >> c;
    vector<array<int, 3>> e(m);
    vector<vector<pii>> g(n + 1);

    int minEdge = inf, minCycle = inf;

    for (auto &[x, y, w]: e)
        cin >> x >> y >> w, g[x].emplace_back(y, w), minEdge = min(minEdge, w);

    vi dis;
    auto dij = [&dis, n, g](array<int, 3> ban) {
        dis = vi(n + 1, inf);
        dis[ban[1]] = 0;
        vi vis(n + 1, 0);
        priority_queue<pii, vector<pii>, greater<pii> > q;
        q.emplace(0, ban[1]);
        for (int u; !q.empty();) {
            u = q.top().second, q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (const auto &[v, w]: g[u]) {
                if (u == ban[0] and v == ban[1] and w == ban[2]) continue;
                if (dis[v] <= dis[u] + w) continue;
                dis[v] = dis[u] + w, q.emplace(dis[v], v);
            }
        }
    };

    for (auto edge: e) {
        dij(edge);
        minCycle = min(minCycle, edge[2] + dis[edge[0]]);
    }
    if (minCycle <= c)
        cout << "2\n";
    else if (minEdge <= c)
        cout << "1\n";
    else
        cout << "0\n";
    return 0;
}

G. Occupy the Cities

考虑二分答案，设二分的枚举值为\(x\)，对于\(i\)位置上的\(1\)，一定可以覆盖到\([i-x+1,i+x-1]\)，而对于\(i-x,i+x\)的覆盖只能二选一。

所以我们从左向后的遍历，维护上一个\(1\)覆盖到的位置，如果\(i-x\)被覆盖到了，则对于\(i\)来说覆盖\(i+x\)肯定更优，反之则覆盖\(i-x\)，但请注意如果\(i-x-1\)没有被覆盖到，则说明两个 1 的不能覆盖之间所有的 0，则当前\(x\)太小了。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    if( s == string( n , '1' )){
        cout << "0\n";
        return ;
    }

    auto check = [s, n](int x) {
        int lst = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') continue;
            if (lst < i - x) return false;
            else if (lst == i - x) lst = i + x;
            else lst = i + x + 1;
        }
        return lst >= n;
    };

    int l = 0, r = n, res = -1;
    for (int mid; l <= r;) {
        mid = (l + r) / 2;
        if (check(mid)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    for (cin >> T; T; T--)
        solve();
    return 0;
}

I. PTSD

最优解肯定是两个一组的分配

倒序维护一个计数器统计没有配对的人。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;
using vi = vector<int>;

void solve(){
    int n , cnt = 0 , res = 0;
    string s;
    cin >> n >> s;
    for( int i = n ; i >= 1 ; i -- ){
        if( s[i-1] == '0' ) cnt ++;
        else {
            if( cnt > 0 ) res += i , cnt --;
            else cnt ++;
        }
    }
    cout << res << "\n";
    return ;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    for( cin >> T ; T ; T -- )
        solve();
    return 0;
}