Codeforces Round #822 (Div. 2) A-F

2022-10-07 06:06:45

比賽連結

A

題解

知識點:貪心。

注意到任意三根木棍的相等最優解是最長減最小,因此從小到大排序,三個三個取,取最小值。

時間複雜度 \(O(n\log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll a[307];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    ll ans = a[3] - a[1];
    for (int i = 3;i <= n;i++) {
        ans = min(ans, a[i] - a[i - 2]);
    }
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

題解

知識點:構造。

注意到第 \(i\) 行的房間最多明亮值為 \(i\) ,又發現只需要兩側房間安排火把已經滿足一行最大值,因此直接兩側房間 \(1\) 其他都是 \(0\)

時間複雜度 \(O(n^2)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= i;j++) {
            if (j == 1 || j == i) cout << 1 << ' ';
            else cout << 0 << ' ';
        }
        cout << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

題解

知識點:貪心,數學。

從小到大,把每一個要刪除的數當作 \(k\) 列舉倍數,如果是要刪除的數花費一次 \(k\) 刪掉,如果已經刪過則無視,如果不是要刪除的數則停止換下一個 \(k\)

時間複雜度 \(O(n\log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int vis[1000007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        char c;
        cin >> c;
        vis[i] = c == '1';
    }
    ll sum = 0;
    for (int i = 1;i <= n;i++) {
        if (vis[i] == 1) continue;
        for (int j = i;j <= n;j += i) {
            if (vis[j] == 1) break;
            if (vis[j] == 0) {
                vis[j] = 2;
                sum += i;
            }
        }
    }
    cout << sum << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

題解

知識點:貪心,列舉。

先選擇一個方向直走,比如先走左側,走到不能再走為止,把盡頭的生命值 \(lnw\) 記錄下。

此時考慮回頭,但顯然在左側盡頭回頭不是一定最優的,應該在走左側過程中生命值和最大處回頭才是最優的,因為這樣在走右側時可以走最多的路,因此在走左側的過程中也要記錄左側的生命和最大值 \(lmx\)

同理從 \(lmx\) 回頭走右側時,也是走到盡頭記錄右側最大生命值 \(rmx\) 和盡頭生命值 \(rnw\) 。此時從 \(rmx\) 回頭走左側,應該直接從上一次的左側盡頭位置 \(lnw\) 繼續走。

如此來回往復,直到兩側不能繼續走或者到達兩端為止。

時間複雜度 \(O(n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[200007];
bool solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int i = k - 1, j = k + 1;
    ll lmx = 0, lnw = 0, rmx = 0, rnw = 0;
    while (1 <= i && j <= n) {
        bool ok = false;
        while (1 <= i) {
            if (a[k] + lnw + rmx + a[i] < 0) break;
            ok = true;
            lnw += a[i--];
            lmx = max(lmx, lnw);
        }
        while (j <= n) {
            if (a[k] + lmx + rnw + a[j] < 0) break;
            ok = true;
            rnw += a[j++];
            rmx = max(rmx, rnw);
        }
        if (!ok) break;
    }
    if (i == 0 || j == n + 1) cout << "YES" << '\n';
    else cout << "NO" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

E

題解

知識點:構造,數學。

注意到,

\[\begin{aligned} & & a_{i_1,j_1} + a_{i_2,j_2} \not \equiv a_{i_1,j_2} + a_{i_2,j_1} \pmod n\\ &\Leftrightarrow & a_{i_2,j_2} - a_{i_2,j_1} \not \equiv a_{i_1,j_2} - a_{i_1,j_1} \pmod n \end{aligned} \]

猜測一行元素具有線性關係,設 \(i_1\) 行線性係數為 \(k_1\)\(i_2\) 行線性係數為 \(k_2\) ,於是有:

\[\begin{aligned} &\Leftrightarrow & (j_2-j_1)\cdot k_2 \not \equiv (j_2-j_1)\cdot k_1 \pmod n \end{aligned} \]

根據定理:當 \(k > 0\) 時,若 \(kx \equiv ky \pmod n\) ,則 \(x \equiv y\pmod {\frac{n}{gcd(k,n)}}\)

於是有:

\[\begin{aligned} &\Leftrightarrow & k_2 \not \equiv k_1 \pmod n \end{aligned} \]

因此,只要每行之間的線性係數在 \(\mod n\) 意義下不同餘,且在 \((i,i)\) 處經過 \(b_i\) 即可。

顯然,\(i \in [1,n]\) 時即能保證互不同餘,可以當作係數,因此有公式 \(b_{i,j} = (i \cdot (j-i) + b_i) \mod n\)

時間複雜度 \(O(n^2)\)

空間複雜度 \(O(n^2)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[357][357], b[357];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> b[i];
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            a[i][j] = ((i * (j - i) + b[i]) % n + n) % n;
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

F

題解

知識點:記憶化搜尋,線性dp,數學,位運算。

先是一個結論:定義函數 \(parity(a)\) 表示 \(a\) 二進位制位 \(1\) 的個數的奇偶性(奇數返回 \(1\) ,偶數返回 \(0\)),那麼 \(S_i = parity(i)\)

證明非常簡單:

  1. 由於 \(S\) 的生成方法是每次都從原來的一份取反得到 \(S'\) 放到 \(S\) 末尾,所以第 \(k(k\geq 1)\) 次擴充套件後 \(S\) 的編號一定是 \([0,2^{k-1}]\)
  2. 對於第 \(k+1\) 次新生成的 \(S'\) 中的每一位編號 \(i'\) ,滿足 \(i’ = i + 2^k\) ,因為編號 \(i\) 的第 \(k\) 位之前一定是 \(0\),所以這次變換實際上是將編號 \(i\) 的第 \(k\) 位變為 \(1\) 作為編號 \(i'\)
  3. 顯然,所有數位都是從編號 \(0\) 開始數次變換得到的,每次變換都會將編號的一位 \(0\) 變為 \(1\) ,因此我們記錄二進位制 \(1\) 的數量就能得知這個編號從 \(0\) 變換了多少次。
  4. \(S_0 = 0\) ,所以編號 \(i\) 有偶數個 \(1\) 就是變了偶數次,故 \(S_i=0\) ,否則 \(S_i = 1\) 。即 \(S_i = parity(i)\)

有了這個結論,我們就可以對問題進行量化。記原問題答案為 \(f(n,m)\) ,有 \(f(n,m) = \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\)

\(m = 0\) 時,顯然有 \(f(n,0) = 0\)

\(m\) 為奇數時,先對末尾判斷再對 \(m-1\) 討論(偶數討論方便一點),有 \(f(n,m) = f(n,m-1) + [parity(i) \neq parity(n+i)]\)

\(m\) 為偶數時:

  • \(n\) 為偶數,有如下關係:

    \[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(2k+1) \neq parity(n+2k+1)\\ \end{aligned} \]

    因為偶數末尾總是 \(0\) ,加 \(1\) 不會影響其餘的二進位制位,所以 \(1\) 的數量明確加 \(1\) ,奇偶性一定同時改變。

    \[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(k) \neq parity(\frac{n}{2}+k) \end{aligned} \]

    因為偶數末尾總是 \(0\) ,刪去這個 \(0\) 後,數位奇偶性不變。

    那麼有如下公式:

    \[\begin{aligned} f(n,m) &= \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\\ &= 2\sum_{k = 0}^{\frac{m}{2}-1} [parity(2k) \neq parity(n+2k)]\\ &= 2\sum_{k = 0}^{\frac{m}{2}-1} [parity(k) \neq parity(\frac{n}{2}+k)]\\ &= 2f(\frac{n}{2},\frac{m}{2}) \end{aligned} \]

  • \(n\) 為奇數,有如下關係:

    \[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(2k) = parity(n+2k-1)\\ &\Leftrightarrow& &parity(k) = parity(\frac{n-1}{2}+k)\\ \end{aligned} \]

    以及,

    \[\begin{aligned} && &parity(2k+1) \neq parity(n+2k+1) \\ &\Leftrightarrow& &parity(2k) = parity(n+2k+1)\\ &\Leftrightarrow& &parity(k) = parity(\frac{n+1}{2}+k)\\ \end{aligned} \]

    證明同上。

    \[\begin{aligned} f(n,m) &= \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\\ &= \sum_{k = 0}^{\frac{m}{2}-1} ([parity(2k) = parity(n+2k-1)] + [parity(2k) = parity(n+2k+1)])\\ &= \sum_{k = 0}^{\frac{m}{2}-1} ([parity(k) = parity(\frac{n-1}{2}+k)] + [parity(k) = parity(\frac{n+1}{2}+k)])\\ &= m - f(\frac{n-1}{2},\frac{m}{2}) - f(\frac{n+1}{2},\frac{m}{2}) \end{aligned} \]

至此,我們就可以通過記憶化搜尋進行求解了。

時間複雜度 \(O(\log n \log m)\)

空間複雜度 \(O(\log n \log m)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool check(ll a, ll b) {
    return __builtin_parityll(a) != __builtin_parityll(b);
}

map<pair<ll, ll>, ll> mp;
ll f(ll n, ll m) {
    if (m == 0) return 0;
    if (mp.count({ n,m })) return mp[{n, m}];
    if (m & 1) return mp[{n, m}] = f(n, m - 1) + check(m - 1, n + m - 1);
    if (n & 1) return mp[{n, m}] = m - f(n / 2, m / 2) - f((n + 1) / 2, m / 2);
    else return mp[{n, m}] = 2 * f(n / 2, m / 2);
}

bool solve() {
    ll n, m;
    cin >> n >> m;
    cout << f(n, m) << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}