2023 Hubei Provincial Collegiate Programming Contest题解 C F H I J K M

发布于 2023-05-02  645 次阅读


补题链接:https://codeforces.com/gym/104337

原文链接:https://www.eriktse.com/algorithm/1136.html

M. Different Billing

签到题,写几个柿子然后枚举B或C即可。

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

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int x, y;cin >> x >> y;
    for(int c = 0;c <= x; ++ c)
    {
        int b = (y - 2500 * c) / 1000;
        if(b < 0 || 1000 * b + 2500 * c != y)continue;

        int a = x - b - c;

        if(a >= 0)
        {
            cout << a << ' ' << b << ' ' << c << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    return 0;
}

C. Darkness I

这题是对Minecraft中无限水的拓展过程为背景的一道思维题。

先考虑一下n, m均为奇数的情况:

然后从这种情况开始,增加一列,或者增加一行,都需要多加一个黑棋子,如果同时增加一行一列,那也是只需要增加一个棋子,增加到右下角的位置即可。

所以我们按照这种构造方法输出答案即可。

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


signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;cin >> n >> m;
    int res = (n + 1) / 2 + (m + 1) / 2 - 1;
    if(n % 2 == 0 || m % 2 == 0)res ++;
    cout << res << '\n';
    return 0;
}

J.Expansion

这题可以转化为以下题意:

一开始身上资源为0,从1号点走到n号点,每个点上有一些资源(可能为负数),每秒钟可以选择走或者不走,且每秒会得到当前点上的资源(此时的资源已经做了前缀和),为了保证每时每刻身上的资源都不为负数,请问从1走到n所需的最小时间。

我们模拟一下这个过程,如果到了某个点发现如果在当前点停留1秒会使得资源变为负数,就说明“我应该在左边的某个正数点多停留一会儿”,而为了使得停留时间最少,我会选择最大的点进行停留。

注意一些特判,题意需要保证最后在n一直停留都不会使得资源为负数,所以prefix[n]需要大于等于零,还有为了使得可以走到n,需要保证第一个非0的数为正数。

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

const int N = 1e6 + 9, p = 998244353;

int a[N], prefix[N];

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;cin >> n;
    for(int i = 1;i <= n; ++ i)cin >> a[i];
    for(int i = 1;i <= n; ++ i)prefix[i] = prefix[i - 1] + a[i];

    if(prefix[n] < 0)
    {
        cout << -1 << '\n';
        return 0;
    }
    //遇到的第一个是负数
    for(int i = 1;i <= n; ++ i)
    {
        if(prefix[i] != 0)
        {
            if(prefix[i] < 0)
            {
                cout << -1 << '\n';
                return 0;
            }
            break;
        }   
    }

    int ans = 0, res = 0, mx = 0;
    //前面一步步推进
    for(int i = 1;i <= n; ++ i)
    {
        mx = max(mx, prefix[i]);
        res += prefix[i];
        ans ++;//走一秒
        if(res < 0)//说明走快了,应该在前面多停留一段时间的
        {
            //补几秒钟
            int ti = (-res + mx - 1) / mx;
            ans += ti;
            res += ti * mx;
        }
    }
    cout << ans << '\n';
    return 0;
}

H.Binary Craziness

赛时卡这道题了,一直在想拆位的做法(形成惯性思维了......糟糕)。

其实这题我们可以这样想,最多m条边,也就是所有点的出度之和一定是2m,然后我们最多n个点,也就是说出度的种类数不会超过 $\sqrt{2m}$ 种。因为如果要使得种类数最多,那么就是每一种都只有一个,且从小到大,出度数组排序后(长度为t)将会是1, 2, 3, 4, 5, ...其和为$\frac{t(t + 1)}{2} \le 2m$,所以长度t不会很大。

我们就可以根据这个原理做一个桶记录一下某个数字出现的次数,然后直接双重循环暴力写!

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

const int N = 1e6 + 9, p = 998244353;

int cnt[2 * N], a[N];

int f(int x, int y)
{
    return (x ^ y) * (x | y) * (x & y);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;cin >> n >> m;

    for(int i = 1;i <= m; ++ i)
    {
        int x, y;cin >> x >> y;
        a[x] ++, a[y] ++;
    }
    for(int i = 1;i <= n; ++ i)cnt[a[i]] ++;

    vector<int> v;
    for(int i = 1;i <= 2 * m; ++ i)if(cnt[i])v.push_back(i);
    int res = 0;
    for(int i = 0;i < v.size(); ++ i)
    {
        for(int j = i + 1;j < v.size(); ++ j)
        {
            res = (res + cnt[v[i]] * cnt[v[j]] % p * f(v[i], v[j]) % p) % p;
        }
    }
    cout << res << '\n';

    return 0;
}

F.Inverse Manacher

这题甚至不需要会马拉车。

题目给定一个“回文半径”的数组,要你还原还原出一种可能的字符串(仅包含ab)。数据保证至少存在一种解。

只需要理解回文半径的含义即可。

当我们走到i时,如果a[i] > 1,说明我们要把i左边的一部分堆成到右边去,为了优化复杂度,我们可以用双指针,r表示此时b数组(也就是答案数组)的大小,也就是我们更新到的右端,当r < i + a[i] - 1时,我们就拓展得到b[r],如果此时i > r,再根据一些情况来确定b[i]即可(交替的取a, b)。

注意数组开大一点,马拉车一般是两倍空间。

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

const int N = 3e6 + 9;

int a[N];

char b[N];

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;cin >> n;
    for(int i = 0;i <= 2 * n + 1; ++ i)cin >> a[i];

    char ch = 'a';

    for(int i = 0, r = 0;i <= 2 * n + 1; ++ i)
    {
        while(i + a[i] - 1 > r)++ r, b[r] = b[2 * i - r];
        if(i == 0)b[i] = '&';
        else if(i & 1)b[i] = '|';
        else if(b[i] == 0)b[i] = ch, ch = (ch == 'a' ? 'b' : 'a');
    }
    for(int i = 2;i <= 2 * n + 1;i += 2)cout << b[i];
    return 0;
}

K.Dice Game

这题主要难在分析出n个事件相互独立。

x确定时,对于n个人当中的某一个人,他胜利的概率是$p = \frac{m-x}{m-1}$,这个有两种理解,第一个感性的理解就是,当投出y = x是没有意义的,所以有效的y一共是m个,其中m - x个是可以赢的。

数学的理解是,这个人可能在第一次赢,也可能第二次赢,也可能第三次赢...,设平局概率为t,胜利概率为q

$$ p= q + t * q + t^{2} * q + .... + t^{inf} * q $$

其中$t=\frac{1}{m}$, $q = \frac{m-x}{m}$。

根据等比数列求和我们可以知道:

$$p = \frac{m-x}{m-1}$$

然后对于某个x,一共有n个人,那么答案就是$p^n = (\frac{m-x}{m-1}) ^ n$。

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

const int N = 1e6 + 9, p = 998244353;

int qmi(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1)res = res * a % p;
        a = a * a % p, b >>= 1;
    }
    return res;
}

int inv(int x){return qmi(x, p - 2);}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;cin >> n >> m;
    int res = 1;
    for(int i = 1;i <= m; ++ i)
    {
        cout << qmi((m - i) * inv(m - 1) % p, n) << ' ';
    }

    return 0;
}

I.Step

已知$2t | k(k+1)$,求最小的$k$,其中$t=lcm(p_1,p_2...,p_n)$。

不妨设$2t=a*b$,且$a|k,b|(k+1)$,且$ax=k,by=(k+1)$,那么我们可以得到:

$$ax+1=by$$

转换一下得到:

$$a(-x)+by=1$$

枚举a,可以算出b,然后exgcd搞出最小的x,即得到了k=ax答案。

现在问题是如何枚举a,我们看这个exgcd式子可以发现我们需要保证gcd(a, b) = 1,且有2t = a * b,所以我们可以对2t进行唯一分解,然后选取不同质因子种类分配给ab

分配方案可以通过二进制直接做。

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

const int N = 1e6 + 9, inf = 8e18;

int p[N];

int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}
int lcm(int a, int b){return a / gcd(a, b) * b;}


map<int, int> mp;
vector<int> v;

void func(int x)
{
    for(int i = 2;i <= x / i; ++ i)
    {
        if(x % i)continue;
        v.push_back(i);
        mp[i] = 1;
        while(x % i == 0)mp[i] *= i, x /= i;
    }
    if(x > 1)v.push_back(x), mp[x] = x;
}

int exgcd(int a, int b, int &x, int &y)
{
    if(!b)return x = 1, y = 0, a;
    int d = exgcd(b, a % b, y , x);
    y -= a / b * x;
    return d;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;cin >> n;
    for(int i = 1;i <= n; ++ i)cin >> p[i];
    int lc = p[1];
    for(int i = 2;i <= n; ++ i)lc = lcm(lc, p[i]);

    //对2 * lc进行质因数分解
    func(2 * lc);
    int res = inf;
    for(int i = 0;i < (1ll << v.size()); ++ i)
    {
        //根据i得到a
        int a = 1;
        for(int j = 0;j < v.size(); ++ j)
            if(i >> j & 1)a = a * mp[v[j]];

        int b = 2 * lc / a;
        int x, y, d = exgcd(a, b, x, y);
        x = -x;
        x = (x % (b / d) + (b /  d)) % (b / d);
        if(a * x)res = min(res, x * a);
        //cout << "a = " << a << ' ' << "ax = " << a * x << '\n';
    }

    cout << res << '\n';

    return 0;
}