Educational Codeforces Round 181 (Rated for Div. 2) ABCD

目錄

• Educational Codeforces Round 181 (Rated for Div. 2) ABCD
• 目錄
  • A
  • B
  • C
  • D
  • E(TODO)

ABCD 偏簡單了

A

眾所周知，競賽可以用 \(s\) 字符串表示，該字符串由大寫拉丁字母組成，表示問題。我們還知道，如果競賽的連續子串中包含 "FFT "或 "NTT"，那么競賽就是有難度的。

你的任務是重新排列競賽 \(s\) 中的問題，使其不難。如果最初的競賽不難，您可以保持原樣。

眾所周知，一個競賽可以用一個字符串 \(s\) 表示，這個字符串由表示問題的大寫拉丁字母組成。我們還知道，如果競賽中包含 "FFT "或 "NTT "這樣的連續子串，那么這個競賽就是有難度的。你的任務是重新排列競賽 \(s\) 中的問題，使這個競賽不難。如果最初的競賽不難，您可以保持原樣。

直接排序即可實現，不過我寫煩了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    string s;
    cin >> s;
    int T = 0, N = 0, F = 0;
    for (char c : s)
    {
        if (c == 'T')
            T++;
        else if (c == 'N')
            N++;
        else if (c == 'F')
            F++;
        else
            cout << c;
    }
    while (T--)
        cout << 'T';
    while (N--)
        cout << 'N';
    while (F--)
        cout << 'F';
    cout << '\n';
}

B

在一個無限網格的 \((a,b)\) 單元中有一個機器人。米沙想要將它移動到 \((0,0)\) 單元。為此，他設定了一個整數 \(k\) 。

米沙可以執行以下操作：選擇兩個整數 \(dx\) 和 \(dy\)$ (均從 \(0\) 到 \(k\) 包括在內)，然后將機器人向左移動 \(dx\) 個單元格(沿 \(x\) 坐標遞減的方向)，向下移動 \(dy\) 個單元格(沿 \(y\) 坐標遞減的方向)。換句話說，將機器人從 \((x,y)\) 移動到 \((x - dx, y - dy)\) 。

操作成本為

• \(1\) ，如果首次使用所選的 \((dx,dy)\) 對；
• \(0\) ，如果之前已經選擇過一對 \((dx,dy)\) 。

注意，如果是 \(dx \ne dy\) ，則 \((dx, dy)\) 和 \((dy, dx)\) 會被視為不同的一對。

幫助米莎以最小的總成本將機器人帶到 \((0,0)\) 小區。請注意，您不必盡量減少操作次數。

看到 請注意，您不必盡量減少操作次數。 就可以猜到答案要么是1，要么是2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    ll a, b, k;
    cin >> a >> b >> k;
    ll ans = 0;
    ll sm = __gcd(a, b);
    a /= sm;
    b /= sm;
    if (a <= k and b <= k)
        ans = 1;
    else
        ans = 2;
    cout << ans << '\n';
}

C

質數是正好有兩個除數的正整數： \(1\) 和它本身。前幾個質數是 \(2, 3, 5, 7, 11, \dots\) 。

正整數的質因數化就是將正整數表示為質數的乘積。例如

• \(111\) 的質因數分解是 \(3 \cdot 37\) ；
• \(43\) 的質因數分解是 \(43\) ；
• \(12\) 的質因數分解是 \(2 \cdot 2 \cdot 3\) 。

對于每一個正整數，其質因數化都是唯一的（如果不考慮積中素數的順序）。

如果一個正整數的因式分解中的****素數都至少包含兩位數，我們就稱它為好。例如

• \(343 = 7 \cdot 7 \cdot 7\) 不是好整數；
• \(111 = 3 \cdot 37\) 不好；
• \(1111 = 11 \cdot 101\) 好；
• \(43 = 43\) 好。

您必須計算出從 \(l\) 到 \(r\) 的好整數個數（包括端點）。(包括端點）。

容斥
可以暴力求

4
0 210
0 420
0 95
0 305

這組，然后觀察發現可以分成長度為210的塊算，剩余的暴力算。
[l,r]內的xx個數是經典的套路
可以轉化成 前 N 個數的xx個數。

正解是容斥做，其實差不多

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll f(ll x)
{
    ll block = x / 210;
    ll ans = block * 48;
    ll rem = x % 210;
    for (ll i = 1; i <= rem; ++i)
    {
        if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
            continue;
        ++ans;
    }
    return ans;
}
void sol()
{
    // 2 3 5 7 -> 210
    ll l, r;
    cin >> l >> r;
    cout << f(r) - f(l - 1) << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--)
    {
        sol();
    }
    return 0;
}

D

有一個線性條帶，分為 \(m\) 個單元，從左到右編號為 \(1\) 至 \(m\) 。

你會得到 \(n\) 個區段。每個區段由四個數字定義： \(l\) 、 \(r\) 、 \(p\) 和 \(q\) --該區段包括從 \(l\) 到 \(r\) 的單元格，并且存在的概率為 \(\frac{p}{q}\) （獨立存在）。

您的任務是計算每個單元格僅被1個線段覆蓋的概率。

第一眼想用圖論做（）
但是應該用DP做
本質上區別不大
賽后寫了一個圖論的，因為有點丑，所以以下代碼經過gpt格式化。

#include <bits/stdc++.h>
using namespace std;
using namespace std;
 
const long long MOD = 998244353;
 
 
long long modexp(long long base, long long exp, long long mod = MOD)
{
    long long res = 1;
    base %= mod;
    while (exp > 0)
    {
        if (exp & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}
 
long long modinv(long long x, long long mod = MOD)
{
    return modexp(x, mod - 2, mod);
}
 
struct Edge
{
    int u, v;
    long long weight;
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
 
    vector<vector<Edge>> graph(m + 1);
 
    long long globalFactor = 1;
 
    for (int i = 0; i < n; i++)
    {
        int l, r, pi, qi;
        cin >> l >> r >> pi >> qi;
        long long p = pi % MOD, q = qi % MOD;

        long long r_prob = (p * modinv(q)) % MOD; 
        long long one_minus = (1 - r_prob + MOD) % MOD;

        globalFactor = (globalFactor * one_minus) % MOD;
 
        long long weight = (r_prob * modinv(one_minus)) % MOD;
 
        Edge e;
        e.u = l - 1;
        e.v = r;
        e.weight = weight;
        graph[e.u].push_back(e);
    }
 
    vector<int> indegree(m + 1, 0);
    for (int u = 0; u <= m; u++)
    {
        for (auto &edge : graph[u])
        {
            indegree[edge.v]++;
        }
    }
 
    vector<long long> ways(m + 1, 0);
    ways[0] = 1;
 
    queue<int> q;
    for (int i = 0; i <= m; i++)
    {
        if (indegree[i] == 0)
            q.push(i);
    }
 
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto &edge : graph[u])
        {
            int v = edge.v;
            ways[v] = (ways[v] + ways[u] * edge.weight) % MOD;
 
            indegree[v]--;
            if (indegree[v] == 0)
                q.push(v);
        }
    }
 
    long long ans = (globalFactor * ways[m]) % MOD;
    cout << ans % MOD << "\n";
 
    return 0;
}

E(TODO)

如果整數集 \(Q\) 可以通過以下操作得到，我們就稱它為互補和集：

• 選擇一個由 \(m\) 個正整數組成的數組 \(a\) ( \(m\) 是任意一個正整數)；
• 計算數組 \(a\) 中所有元素的和 \(s\) ；
• 對于數組中的每個元素 \(a_{i}\) ，將數字 \(s - a_{i}\) 加到集合中，更正式的集合是
  \( Q = {s - a_{i}}; 1 \le i \le m \)。

請注意， \(Q\) 不是一個多集合，也就是說其中的每個數字都是唯一的。例如，如果選擇數組 \(a = [1, 3, 3, 7]\) ，那么 \(s = 14\) 和 \(Q = \\{7, 11, 13\\}\) 。

你的任務是計算下列條件成立的互補和的不同集合的數目：

• 集合恰好包含 \(n\) 個元素；
• 集合中的每個元素都是一個從 \(1\) 到 \(x\) 的整數。

如果第一個集合中有一個元素沒有包含在第二個集合中，那么這兩個集合就被認為是不同的。

由于答案可能很大，因此輸出它取模 \(998,244,353\) 。