模擬競賽 I 題解

2021 師大附中暑期資訊培訓

joylintp / WiwiHo

直播循環 (Cycle)

來源: Codeforces 1041C
測資: joylintp
題敘: joylintp

直播循環 - Subtask 1

\(r=0\)
→ 不用休息
→ 所有遊戲都可以在第一個循環直播
→ \(k=1,x_i=1\)

3 / 100

直播循環 - Subtask 3

\(n \le 10\)
→ 枚舉直播遊戲的順序
→ 盡量讓遊戲可以在同一個循環內直播
→ \(O(n! \times n)\)

9 / 100

直播循環 - Subtask 2

\(n = s\)
→ 每天都有一種遊戲要玩
→ 第一個循環玩第 \(1,1+r+1,1+2r+2,\dots\) 天的遊戲
→ 第二個循環玩第 \(2,2+r+1,2+2r+2,\dots\) 天的遊戲
→ \(O(n)\)

13 / 100

直播循環 - Subtask 2

貪心法

直播循環 - Subtask 4

每次盡量選擇還沒玩過的遊戲中 \(a_i\) 最小的
→ \(O(n)\) 迴圈尋找可玩的遊戲
→ 總複雜度 \(O(n^2)\)

18 / 100

直播循環 - Subtask 5

→ \(O(n)\) 迴圈尋找可玩的遊戲
→ set、priority_queue \(O(\log{n})\) 維護
→ 總複雜度 \(O(n\log{n})\)

100 / 100



































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

#define MP make_pair
#define F first
#define S second

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, d;
    cin >> n >> m >> d;

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i].F, a[i].S = i;
    sort(a.begin(), a.end());

    vector<int> ans(n);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < n; i++)
        if (pq.empty() || a[i].F - pq.top().F < d + 1)
            ans[a[i].S] = pq.size() + 1, pq.push(MP(a[i].F, pq.size() + 1));
        else
            ans[a[i].S] = pq.top().S, pq.pop(), pq.push(MP(a[i].F, ans[a[i].S]));

    cout << pq.size() << '\n';
    for (int i : ans)
        cout << i << ' ';

    return 0;
}

兔田彩券 (Lottery)

靈感來源: JOI 2021 Final Round pC
測資: WiwiHo
題敘: joylintp

題目大意

有 \(m\) 個 pair \((a_i,b_i)\)
對於每筆詢問 \((l_i,r_i,s_i,t_i)\)
求有幾個 \(j\) 滿足
\(l_i \leq a_j \leq r_i \land s_i \leq b_j \leq t_i\) 或
\(l_i \leq b_j \leq r_i \land s_i \leq a_j \leq t_i\)

Subtask 1

\(n,m,q \leq 500\)

對於每一個詢問
把所有 pair 檢查一次是否符合條件就好了

\(O(mq)\)

常見錯誤

  1. 同一個算到兩次
  2. 把「或」當成「且」

Subtask 2

\(n \leq 100\)，\(q \leq 10000\)

\(n\) 很小？
pair 只有 \(O(n^2)\) 種而已
數每一種 pair 出現了幾次
詢問的時候，找符合條件的 pair

\(O(m + n^2q)\)

Subtask 3

\(l_i \leq r_i < s_i \leq t_i\)

如果把每一種 pair 出現的數量存在一個表格上
那詢問其實是在問一個矩形區域的和

假設 \((i,j)\) 出現 \(c[i][j]\) 次
二維前綴和：\(sum[i][j]= \sum_{i'=1}^i \sum_{j'=1}^j c[i'][j']\)

\(\sum_{i=l}^{r} \sum_{j=s}^t c[i][j] = sum[r][t] \\ - sum[l-1][t] - sum[r][s-1] + sum[l-1][s-1]\)

預處理 \(sum\)，詢問只要 \(O(1)\) 的時間

\(O(m + n^2 + q)\)

Subtask 4

為什麼上一個 subtask 的 code 不能過這個？

因為會算到重複的
如果 \(l_i \leq a_j \leq r_i \land s_i \leq b_j \leq t_i\)
和 \(l_i \leq b_j \leq r_i \land s_i \leq a_j \leq t_i\)
同時滿足，\(j\) 就會被算到兩次

誰會被算到兩次？

\(\max(l_i,s_i) \leq a_j,b_j \leq \min(r_i,t_i)\)
\(j\) 就會被算到兩次
把這個區域扣掉就好














































#include <bits/stdc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

int main(){
    StarBurstStream

    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(n + 1));
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        if(u > v) swap(u, v);
        a[u][v]++;
        a[v][u]++;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) a[i][j] += a[i][j - 1];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) a[j][i] += a[j - 1][i];
    }

    auto calc = [a](int x1, int y1, int x2, int y2){
        return a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1];
    };

    int q;
    cin >> q;
    while(q--){
        int l, r, s, t;
        cin >> l >> r >> s >> t;
        int tl = max(l, s);
        int tr = min(r, t);
        int ans = calc(l, s, r, t);
        if(tl <= tr) ans -= calc(tl, tl, tr, tr) / 2;
        cout << ans << "\n";
    }

    return 0;
}

魔法師測驗 (Mage)
來源: CF 1101D
測資: joylintp
題敘: joylintp

魔法師測驗 - Subtask 1

\(m_1=m_2=\ldots=m_n\)
→ 若 \(m_1=1\) 則答案為 \(0\)（和諧度必為 \(1\)）
→ 若 \(m_1 \ne 1\) 則答案為樹直徑（和諧度必不為 \(1\)）

8 / 100

魔法師測驗 - Subtask 2, 6

\(n \le 1000\)
→ 枚舉起點
→ \(O(n)\) DFS 看能走多遠
→ 總複雜度 \(O(n^2)\)

(6 + 14) / 100

魔法師測驗

和諧度不為 \(1\)
→ 最大公因數大於 \(1\)
→ 所有數字至少有一個共同質因數

魔法師測驗 - Subtask 5

\(m_i \le 100\)
→ 枚舉質數（至多 \(25\) 個）
→ 對每個質數建出子圖
→ 找所有子圖中最長的樹直徑
→ 總複雜度 \(O(n \times 25)\)

16 / 100

魔法師測驗 - Subtask 7

\(m_i \le 2 \times 10^5\)
→ 質數有 \(17984\) 個
→ 對每個質數建出子圖
→ TLE

魔法師測驗 - Subtask 7

\(m_i \le 2 \times 10^5\)
→ \(2 \times 3 \times 5 \times 7 \times 11 \times 17 > 2 \times 10^5\)
→ 每個節點的相異質因數不會超過 \(5\) 個
→ 樹 DP

魔法師測驗 - Subtask 7

樹 DP

記錄

  • 每個節點回傳各質因數可往下延伸多長

轉移

  • 繼續延伸子節點質因數的長度
  • 將兩個子節點質因數的長度接起來

總複雜度 \(O(n\log^2{m})\)

100 / 100






















































































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

#define F first
#define S second

int ans;
vector<bool> pfac(200001, true), vis;
vector<int> prime, a;
vector<vector<int>> edge;

map<int, int> dfs(int u)
{
    vis[u] = true;

    map<int, int> sa;
    for (int i : prime)
    {
        if (i * i > a[u])
            break;
        while (a[u] % i == 0)
            sa[i] = 1, a[u] /= i;
    }

    if (a[u] != 1)
        sa[a[u]] = 1;

    map<int, pair<int, int>> sb;
    for (int i : edge[u])
        if (!vis[i])
        {
            map<int, int> mp = dfs(i);
            for (auto p : mp)
                if (sa.count(p.F))
                {
                    sa[p.F] = max(sa[p.F], p.S + 1);
                    if (p.S > sb[p.F].F)
                        sb[p.F].S = sb[p.F].F, sb[p.F].F = p.S;
                    else if (p.S > sb[p.F].S)
                        sb[p.F].S = p.S;
                    else;
                }
        }

    for (auto p : sa)
        ans = max(ans, p.S);
    for (auto p : sb)
        ans = max(ans, p.S.F + p.S.S + 1);

    return sa;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 2; i <= 200000; i++)
    {
        if (pfac[i])
            prime.push_back(i);
        for (int j : prime)
        {
            if (i * j > 200000)
                break;
            pfac[i * j] = false;
            if (i % j == 0)
                break;
        }
    }

    int n;
    cin >> n, vis.resize(n + 1), a.resize(n + 1), edge.resize(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int u, v;
    for (int i = 1; i < n; i++)
        cin >> u >> v, edge[u].push_back(v), edge[v].push_back(u);

    dfs(1);
    cout << ans << '\n';

    return 0;
}

刷怪塔 (Monster)

來源: Google Code Jam 2020 Round 2 pA
測資: joylintp
題敘: joylintp

刷怪塔 - Subtask 3

\(a,b \le 1000\)
→ 選擇刷怪塔的次數至多 \(\sqrt{a+b}\) 次
→ 模擬每次選擇刷怪塔
→ 總時間複雜度 \(O(T\sqrt{a+b})\)

12 / 100

刷怪塔 - Subtask 1

\(a=0\)
→ 只會打第二座刷怪塔的怪物
→ \(b \ge \frac{l(l+1)}{2}\)
→ 解不等式或二分搜最大值
→ 總時間複雜度 \(O(T)\) 或 \(O(T\log{b})\)

8 / 100

刷怪塔 - Subtask 2

\(a=b\)
→ 觀察到在怪物數量足夠的情況下，
奇數一定選擇第一座刷怪塔，偶數一定選擇第二座
→ \(a \ge 1+3+\ldots+(2k+1) = (k+1)^2\)
\(b \ge 2+4+\dots+(2k) = (k+1)^2 + k + 1\)
→ 解不等式或二分搜最大值
→ 總時間複雜度 \(O(T)\) 或 \(O(T\log{b})\)

21 / 100

刷怪塔 - Subtask 4

將較多的那座擊殺到怪物數量不超過另一座
接下來兩座刷怪塔必定會輪流使用
→ 作法類似 Subtask 2
→ 總時間複雜度 \(O(T)\) 或 \(O(T\log{b})\)

100 / 100













































































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

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        long long A, B;
        cin >> A >> B;

        bool swp = (A <= B);
        if (A < B)
            swap(A, B);

        long long l = 0, r = 2e9;
        while (l != r)
        {
            long long m = (l + r) / 2;
            if (m * (m + 1) / 2 > A - B)
                r = m;
            else
                l = m + 1;
        }

        A -= l * (l - 1) / 2;
        if (A > B || (A == B && !swp))
            swap(A, B), swp = !swp;

        long long x = l - 1;
        if (B < x + 1)
        {
            if (swp)
                swap(A, B);
            cout << x << ' ' << A << ' ' << B << '\n';
        }
        else if (A < x + 2)
        {
            B -= x + 1;
            if (swp)
                swap(A, B);
            cout << x + 1 << ' ' << A << ' ' << B << '\n';
        }
        else
        {
            l = x + 2, r = 2e9;
            long long Aa = A, Ba = B;
            while (l != r)
            {
                long long m = (l + r) / 2;

                long long Al = m, Bl = m;
                if (Al % 2 == x % 2)
                    Bl--;
                else
                    Al--;

                long long At = (Al + x + 2) * (Al - x) / 4, Bt = (Bl + x + 1) * (Bl - x + 1) / 4;
                if (A < At || B < Bt)
                    r = m;
                else
                    l = m + 1, Aa = A - At, Ba = B - Bt;
            }

            if (swp)
                swap(Aa, Ba);
            cout << l - 1 << ' ' << Aa << ' ' << Ba << '\n';
        }
    }

    return 0;
}

時空旅人之爭 (Time)

來源: 原創
測資: WiwiHo
題敘: joylintp

題目大意

給一棵樹，複製人大軍會從節點 1 開始擴散，每 2 秒擴散一個節點
有 \(Q\) 筆詢問，詢問求從入侵的時間點開始，從 \(s_i\) 走到 \(t_i\) 的路上
至少要經過幾個有複製人大軍的節點

顯然就是走得越快越好，所以直接走 \(s_i\) 到 \(t_i\) 的簡單路徑
Kronii 到達 \(v\) 的時間：\(dis(s_i, v)\)
複製人大軍到達 \(v\) 的時間： \(2 \times dis(1, v)\)
答案要求有幾個 \(v\) 滿足 \(dis(s_i,v) \geq 2 \times dis(i,v)\)

Subtask 1

\(n,q \leq 1000\)

暴力檢查

\(O(nq)\)

Subtask 2

\(\forall 1 \leq i < n, v_i = u_{i+1}\)

就是這個樹是一條鏈的意思

如果 \(s_i,t_i\) 都在 \(1\) 的同一側
那麼靠近 \(1\) 的那邊可能會有一段連續的符合條件的節點
也就是這條鏈上會有一邊符合條件、一邊不符合
二分搜找交界點

如果 \(s_i,t_i\) 在 \(1\) 的兩側
那麼符合條件的節點會是中間連續的一段
如果把 \(1\) 左右分開看
就和上一種狀況一樣了

\(O(n + q \log n)\)

Subtask 3

除了節點 1 以外，每個節點度數最多 2

也就是說這個樹是從 1 往外伸的一堆鏈

只看 \(s_i\) 和 \(t_i\) 所在的鏈
就跟 Subtask 2 一樣了

Subtask 4

Subtask 2,3 都是「把 \(s_i\) 到 \(t_i\) 的路徑，以最靠近 \(1\) 的節點為中心把這條路徑切成兩半」，而切出來的兩條路徑上，都是有一邊的點符合條件（靠近中心的那邊）、一邊不符合

\(s_i\) 到 \(t_i\) 的路徑上離 \(1\) 最近的點就是他們的 LCA
（以 \(1\) 為根）
然後就跟前面一樣了
可以用倍增法二分搜











































































































#include <bits/stdc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define eb(a) emplace_back(a)

using namespace std;

vector<vector<int>> g;
vector<int> in, out, dpt;
int ts = 0;
vector<vector<int>> anc;

void dfs(int now, int p, int d){
    in[now] = ts++;
    dpt[now] = d;
    anc[0][now] = p;
    for(int i : g[now]){
        if(i == p) continue;
        dfs(i, now, d + 1);
    }
    out[now] = ts++;
}

bool isAnc(int a, int b){
    return in[a] <= in[b] && out[a] >= out[b];
}

int getLCA(int a, int b){
    if(isAnc(a, b)) return a;
    if(isAnc(b, a)) return b;
    for(int i = 19; i >= 0; i--){
        if(!isAnc(anc[i][a], b)) a = anc[i][a];
    }
    return anc[0][a];
}

int getDis(int a, int b){
    int lca = getLCA(a, b);
    return dpt[a] + dpt[b] - 2 * dpt[lca];
}

bool check(int s, int now){
    return getDis(s, now) < dpt[now] * 2;
}

void solve(){
    int s, t;
    cin >> s >> t;
    int lca = getLCA(s, t);

    if(check(s, lca)){
        cout << "0\n";
        return;
    }

    int ans = 0;
    int now = s;
    for(int i = 19; i >= 0; i--){
        if(check(s, anc[i][now])) now = anc[i][now];
    }
    ans += dpt[now] - dpt[lca] + !check(s, s);
    now = t;
    for(int i = 19; i >= 0; i--){
        if(check(s, anc[i][now])) now = anc[i][now];
    }
    ans += dpt[now] - dpt[lca] + !check(s, t);
    ans--;
    cout << ans << "\n";
}

int main(){
    StarBurstStream

    int n;
    cin >> n;

    g.resize(n + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    dpt.resize(n + 1);
    anc.resize(20, vector<int>(n + 1));

    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }

    int q;
    cin >> q;

    dfs(1, 1, 0);

    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= n; j++){
            anc[i][j] = anc[i - 1][anc[i - 1][j]];
        }
    }

    for(int i = 0; i < q; i++){
        solve();
    }

    return 0;
}
Select a repo