2024 CCPC第五届辽宁省程序设计竞赛 集训1

A. 左移

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        string s;
        cin >> s;
        int ans = -1;
        if(s.front() == s.back()) ans = 0;
        else
        {
            for(int i = 0; i < s.size() - 1; i ++)
                if(s[i] == s[i + 1])
                {
                    ans = i + 1;
                    break;
                }
        }
        cout << ans << '\n';
    }
}

B. 矩阵

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// #define int long long
#define endl '\n'
#define all(_x) _x.begin(), _x.end()
#define range(_x, _st, _ed) (_x.begin() + _st), (_x.begin() + _ed)
#define rep(_x, _y, _z) for (int _x = _y; _x <= _z; _x++)
#define matrix(_x, _y, _z) vector<vector<int>>(_x, vector<int>(_y, _z))
#define debug(_x) cout << #_x << '=' << _x << endl
using i64 = long long;
using i128 = __int128;
using pii = pair<int, int>;
using mat = vector<vector<int>>;
using u64 = unsigned long long;
constexpr int N = 2e5 + 10;
// dont use umap!!!

signed main()
{
    IOS;
    int n;
    cin >> n;
    auto ans = matrix(n, n, 0);
    int idx = 1;
    for(int i = 0; i < n - 2; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            ans[i][j] = idx;
        }
        idx++;
    }
    for(int i = 0; i < n - 2; i ++)
    {
        ans[n - 2][i] = idx;
        ans[n - 1][i] = idx++;
    }
    ans[n-2][n-2] = idx++, ans[n-2][n-1] = idx++;
    ans[n-1][n-2] = idx++, ans[n-1][n-1] = idx++;
    cout << "Yes\n";
    for(auto i : ans)
    {
        for(auto j : i) cout << j << ' ';
        cout << '\n';
    }
    return 0;
}

C. 打印机

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// #define int long long
#define endl '\n'
#define all(_x) _x.begin(), _x.end()
#define range(_x, _st, _ed) (_x.begin() + _st), (_x.begin() + _ed)
#define rep(_x, _y, _z) for (int _x = _y; _x <= _z; _x++)
#define matrix(_x, _y, _z) vector<vector<int>>(_x, vector<int>(_y, _z))
#define debug(_x) cout << #_x << '=' << _x << endl
using i64 = long long;
using i128 = __int128;
using pii = pair<int, int>;
using mat = vector<vector<int>>;
using u64 = unsigned long long;
constexpr int N = 2e5 + 10;
// dont use umap!!!

void solve()
{
    int n;
    i64 k;
    cin >> n >> k;
    vector<array<i64, 3>> a(n);
    for(auto &[t,l,w] : a)
    {
        cin >> t >> l >> w;
    }
    auto check = [&](i64 mid)
    {
        i128 sum = 0;
        for(auto [t, l, w] : a)
        {
            sum += mid / (t * l + w) * l + min(mid % (t * l + w) / t, l);
        }
        return sum >= k;
    };
    i64 l = 0, r = 2e18;
    while(l < r)
    {
        i64 mid = l + r >> 1ll;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << '\n';
}

signed main()
{
    IOS;
    int _ = 1;
    cin >> _;

    while (_--) solve();

    return 0;
}

D. 多彩的线段II

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
const int mod = 998244353;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<array<int, 2>> a(n);
    for(auto &[l,r] : a)
    {
        cin >> l >> r;
    }
    sort(a.begin(), a.end());
    priority_queue<int, vector<int>, greater<int>> heap;
    i64 ans = 1;
    for(auto [l, r] : a)
    {
        while(heap.size() and heap.top() < l) heap.pop();
        ans = ans * (k - heap.size()) % mod;
        heap.push(r);
    }
    cout << ans << '\n';
}

int main()
{
    cin.tie(0) -> sync_with_stdio(0);
    int T;
    cin >> T;
    while(T--) solve();
}

E. 分割序列

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// #define int long long
#define endl '\n'
#define all(_x) _x.begin(), _x.end()
#define range(_x, _st, _ed) (_x.begin() + _st), (_x.begin() + _ed)
#define rep(_x, _y, _z) for (int _x = _y; _x <= _z; _x++)
#define matrix(_x, _y, _z) vector<vector<int>>(_x, vector<int>(_y, _z))
#define debug(_x) cout << #_x << '=' << _x << endl
using i64 = long long;
using i128 = __int128;
using pii = pair<int, int>;
using mat = vector<vector<int>>;
using u64 = unsigned long long;
constexpr int N = 2e5 + 10;
// dont use umap!!!

void solve()
{
    int n;
    cin >> n;
    vector<i64> suf(n);
    for(int i = 0; i < n; i ++) cin >> suf[i];
    for(int i = n - 2; i >= 0; i --)
    {
        suf[i] += suf[i + 1];
    }
    sort(suf.begin() + 1, suf.end(), greater<int>());
    i64 ans = suf[0];
    cout << ans << ' ';
    for(int i = 1; i < n; i ++)
    {
        ans += suf[i];
        cout << ans << ' ';
    }
    cout << '\n';
}

signed main()
{
    IOS;
    int _ = 1;
    cin >> _;

    while (_--) solve();

    return 0;
}

F. 多彩的生成树

#include <bits/stdc++.h>
using namespace std;

int n;
int c[1010], f[1010];
int a[1010][1010];

int find(int x)
{
    return x == f[x] ? x : f[x] = find(f[x]);
}

void solve()
{
    cin >> n;
    iota(f, f + n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    vector<array<int, 3>> edges;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
        {
            edges.push_back({i, j, a[i][j]});
        }
    sort(edges.begin(), edges.end(), [&](array<int, 3> p1, array<int, 3> p2)
         { return p1[2] < p2[2]; });
    long long ans = 0;
    for (auto [u, v, w] : edges)
    {
        if (u == v)
        {
            ans += (long long)(c[u] - 1) * w;
            c[u] = 1;
        }
        else
        {
            int fu = find(u), fv = find(v);
            if (fu != fv)
            {
                ans += (long long)(c[u] + c[v] - 1) * w;
                c[u] = c[v] = 1;
                f[fu] = fv;
            }
        }
    }
    cout << ans << '\n';
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--)
        solve();
}

G. 王国英雄

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// #define int long long
#define endl '\n'
#define all(_x) _x.begin(), _x.end()
#define range(_x, _st, _ed) (_x.begin() + _st), (_x.begin() + _ed)
#define rep(_x, _y, _z) for (int _x = _y; _x <= _z; _x++)
#define matrix(_x, _y, _z) vector<vector<int>>(_x, vector<int>(_y, _z))
#define debug(_x) cout << #_x << '=' << _x << endl
using i64 = long long;
using i128 = __int128;
using pii = pair<int, int>;
using mat = vector<vector<int>>;
using u64 = unsigned long long;
constexpr int N = 2e5 + 10;
// dont use umap!!!

void solve()
{
    i64 p, a, b;
    cin >> p >> a >> b;
    i64 q, c, d;
    cin >> q >> c >> d;
    i64 m, t;
    cin >> m >> t;
    while(t > b + d)
    {
        i64 x = m / p;
        if(x == 0) break;
        i64 L = (p * (x + 1) - m + (q - p) * x - 1) / ((q - p) * x);
        L = min(L, t / ((a + c) * x + b + d));
        if(L == 0)
        {
            L = 1;
            x = (t - b - d) / (a + c);
        }
        if(x == 0) break;
        m += L * (q - p) * x;
        t -= L * ((a + c) * x + b + d);
    }
    cout << m << '\n';
}

signed main()
{
    IOS;
    int _ = 1;
    cin >> _;

    while (_--) solve();

    return 0;
}