Educational Codeforces Round 177 (Rated for Div. 2)

2025-04-04

比赛链接: https://codeforces.com/contest/2086

A

题目问的是造 \(3n\) kg 需要多少，损耗为 \(\frac{1}{4}\) ，所以需要 \(4n\) kg的材料，也就是每种原料 \(2n\) kg。

void ChatGptDeepSeek()
{
    int n;
    cin>>n;
    //3n 2n?
    cout<<n*2<<'\n';
}

B

赛时题看错了耽误很久，这题只需要求满足条件的 \(l\) 的数量。我们可以找到最后一个满足条件的 \(l\) 输出就行，因为它前面的肯定都是满足的。

二分也行。

void ChatGptDeepSeek()
{
    int n, k;
    ll x;
    cin >> n >> k >> x;
    vector<int> a(n + 1);
    vector<ll> pre(n + 1), nxt(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    auto ask = [&](ll i)
    {
        return pre[n] * (i / n) + pre[i % n];
    };
    auto calc = [&](ll l, ll r)
    {
        return ask(r) - ask(l - 1);
    };

    ll lo=0,hi=1LL*n*k+1;
    while(lo<hi-1){
        ll mid=(lo+hi)>>1;
        if(calc(mid,1LL*n*k)>=x)
            lo=mid;
        else hi=mid;
    }
    cout<<lo<<'\n';
}

void ChatGptDeepSeek()
{
    int n, k;
    ll x;
    cin >> n >> k >> x;
    vector<int> a(n + 1);
    ll sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];
    if (x > k * sum)
    {
        cout << "0\n";
        return;
    }
    ll ned = x / sum * sum;
    // 完整的區間需要減去 x/sum 個，這部分的 sum 是 ned
    // 也許剛好整除了 那麽答案就是

    if (x % sum == 0)
    {
        cout << (k - x / sum) * n + 1 << '\n';
        return;
    }

    ll idx = 1LL * n * k - x / sum * n;

    // 我們找一個後綴 使得這個後綴的 sum 小於 x
    // 并且這個後綴 再多加一個數字 就會使得 sum 大於等於 x


    for (int i = n; i >= 1; i--)
    {
        if (ned + a[i] >= x)
        {
            cout << idx << '\n';
            return;
        }
        ned += a[i];
        idx--;
    }
}

C

需要对应的位置都修改。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<int> p(n + 1), d(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        r[p[i]] = i;
    }
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        // we can only change p[d[i]] to d[i]
        // so we should check d[i]
        // r[p[d[i]]] = 0;
        int x = p[d[i]];
        while (r[x])
        {
            ans++;
            r[x] = 0;
            x = p[x];
        }
        x = d[i];
        while (r[x])
        {
            ans++;
            r[x] = 0;
            x = p[x];
        }
        cout << ans << " \n"[i == n];
    }
}

D

求两个组合概率的乘积，这个值是一直不会变的。所以我们需要求出和为 \(\frac{n}{2}\) 的子集的数量，可以很简单地用 DP 求出。虽然赛时没想到。

那个概率公式，之前遇过一次。。理解了很久才勉强理解，，虽然现在感觉只要能记住公式就好。具体叫啥我忘了，就是每种数字可能有多个，然后求排列数。

constexpr int mod = 998244353;
constexpr int N = 5e5 + 114;
int f[N];

ll ksm(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
ll inv(ll x) { return ksm(x, mod - 2); }
void ChatGptDeepSeek()
{
    array<int, 26> c;
    int n = 0;
    for (int i = 0; i < 26; i++)
        cin >> c[i], n += c[i];
    vector<int> dp(n + 1);
    dp[0] = 1;
    for (int i = 0; i < 26; i++)
    {
        if (!c[i])
            continue;
        for (int j = n; j >= c[i]; j--)
            dp[j] = (dp[j] + dp[j - c[i]]) % mod;
    }
    ll ans = (dp[n / 2] * f[n / 2] % mod) * f[(n + 1) / 2] % mod;
    for (int i = 0; i < 26; i++)
        ans = ans * inv(f[c[i]]) % mod;
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    f[0] = 1;
    for (int i = 1; i < N; i++)
        f[i] = 1LL * f[i - 1] * i % mod;
    int T = 1;
    cin >> T;
    while (T--)
        ChatGptDeepSeek();
    return 0;
}