比賽連結

A

題意

給 \(n\) 個正整數，找到三個數，使得他們的和為奇數，輸出他們的下標。

題解

知識點：貪心。

找到三個奇數或者一個奇數兩個偶數即可，其他情況無解。

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

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

程式碼

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

bool solve() {
    int n;
    cin >> n;
    vector<int> v1, v2;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        if (x & 1) v1.push_back(i);
        else v2.push_back(i);
    }
    if (v1.size() >= 3) {
        cout << "YES" << '\n';
        cout << v1[0] << ' ' << v1[1] << ' ' << v1[2] << '\n';
    }
    else if (v1.size() >= 1 && v2.size() >= 2) {
        cout << "YES" << '\n';
        cout << v1[0] << ' ' << v2[0] << ' ' << v2[1] << '\n';
    }
    else return false;
    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 << "NO" << '\n';
    }
    return 0;
}

B

題意

給 \(n\) 個正整數 \(a_i\) 。選擇一個 \(k>1\) ，隨後將 \(a_i\) 分成 \(k\) 個連續非空段，使得每段的和 \(b_i\) 的最大公約數 \(\gcd(b_1,\cdots,b_k)\) 最大。

題解

知識點：數論，貪心。

對於任意 \(k\) 的任意劃分有答案 \(\gcd(b_1,\cdots,b_k)\) ，根據 \(\gcd(a,b) = \gcd(a+b,b)\) ，即 \(a\) 和 \(b\) 的最大公因數一定也是 \(a+b\) 的因子，那麼 \(\gcd(b_1+b_2,b_3,\cdots,b_k) \geq \gcd(b_1,\cdots,b_k)\) ，所以任意兩段合併代替合併前的兩段不會讓答案變差，因此最好的情況一定出現在只分為兩段的情況。

因此，我們只要求出 \(\max_\limits{1\leq i \leq n-1}\gcd(a[1,i],a[i+1,n])\) 即可。

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

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

程式碼

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

ll a[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i], a[i] += a[i - 1];
    ll ans = 1;
    for (int i = 1;i <= n - 1;i++) {
        ans = max(ans, gcd(a[i], a[n] - a[i]));
    }
    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;
}

C

題有問題。

D

題意

有一個數位 \(n \in[1,10^9]\) ，告訴你 \(n\) 的二進位制位 \(1\) 的個數 \(cnt\)。

隨後可以執行不超過 \(30\) 次操作：選擇一個 \(x\) ，使得 \(n\) 減去 \(x\) ，得到新的 \(n\) 的二進位制位 \(1\) 的個數 \(cnt\) 。

最後，你需要猜出 \(n\) 是多少。

題解

知識點：位運算，列舉。

由於 \(n\) 最多會有 \(30\) 個 \(1\) ，我們可以探測每一位是否為 \(1\) 。

具體的說，我們探測第 \(i\) 位是否為 \(1\) ，可以減去 \(2^{i-1}\) 。如果這位是 \(1\) ，那麼新的個數 \(cnt' = cnt-1<cnt\) ，否則一定有 \(cnt'\geq cnt\) 。但是，這個結論的前提是，我們是對原本的 \(n\) 做減法。考慮到操作會改變 \(n\) ，因此我們第 \(i-1\) 位探測完後，第 \(i\) 位的探測減去的應該是 \(2^{i-1} - 2^{i-2}\) ，這樣可以抵消上一次操作，等效於對原來的 \(n\) 減去 \(2^{i-1}\) 。

要注意的是，如果減的數超過 \(n\) 那麼也會錯，即我們不能探測超過 \(n\) 最高位二進位制的數。為了防止超出，我們可以記錄探測為 \(1\) 的位數 \(tot\) ，如果 \(tot = cnt\) 那麼可以立刻停止，因為此時答案已經滿足要求了。

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

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

程式碼

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

int query(int x) {
    int cnt;
    cout << "- " << x << endl;
    cin >> cnt;
    return cnt;
}

void answer(int n) {
    cout << "! " << n << endl;
}

bool solve() {
    int cnt;
    cin >> cnt;
    int ans = 0, tot = 0;
    if (query(1) < cnt) ans += 1, tot++;
    for (int i = 1;i < 30 && tot < cnt;i++) {
        if (query((1 << i) - (1 << (i - 1))) < cnt) ans += 1 << i, tot++;
    }
    answer(ans);
    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

題意

給定一個區間 \([L,R]\) ，求 \(\gcd(i,j)\) 的種類，其中 \(i,j\in[L,R]\) 。

題解

知識點：整除分塊。

設 \(\gcd(i,j) = d\) 我們考慮討論 \(d\) 的大小：

1. 當 \(\left\lfloor \dfrac{R}{2} \right\rfloor + 1 \leq d\) ，那麼對於最小的倍數 \(2d\) ，也一定有 \(2d > R\) ， 所以不存在 \([L,R]\) 的數滿足這個範圍的 \(d\) 。
2. 當 \(L \leq d \leq \left\lfloor \dfrac{R}{2} \right\rfloor\) ，我們一定可以構造 \(\gcd(d,2d) = d\) ，其中 \(L \leq d < 2d \leq R\) 。
3. 當 \(d \leq L - 1\) ，我們嘗試構造大於等於 \(L\) 的最小的一組數 \(L \leq d \cdot \left\lceil \dfrac{L}{d} \right\rceil < d \cdot \left( \left\lceil \dfrac{L}{d} \right\rceil +1\right)\) ，這兩個數滿足 \(d \cdot \left\lceil \dfrac{L}{d} \right\rceil < d \cdot \left( \left\lceil \dfrac{L}{d} \right\rceil +1\right) \leq R\) ，則 \(d\) 是合法的，否則一定不合法。

對於前兩類我們可以輕易求出個數，但第三類，顯然我們不可能一個一個列舉 \(d\in[1,L-1]\) 。

實際上，我們發現會存在許多連續區間的 \(d\) ，其 \(\left\lceil \dfrac{L}{d} \right\rceil\) 的值是一樣的，大約有 \(\sqrt L\) 個。假設 \([l,r]\) 區間的 \(d\) 滿足 \(\left\lceil \dfrac{L}{d} \right\rceil = \left\lceil \dfrac{L}{l} \right\rceil\) ，那麼若 \(d\) 滿足 \(l \leq d \leq \min \left(r,\left\lfloor \dfrac{R}{\left\lceil \dfrac{L}{d} \right\rceil + 1} \right\rfloor \right)\) 則構造的數不會超 \(R\) ，是合法的。

那麼這個問題現在就變成一個整除分塊問題，為了方便，我們把取上整都轉化為取下整，即 \(\left\lceil \dfrac{L}{d} \right\rceil = \left\lfloor \dfrac{L-1}{d} \right\rfloor + 1\) 。已知左端點 \(l\) 和 \(\left\lfloor \dfrac{L-1}{l} \right\rceil = k\) ，求最大的右端點 \(r\) 滿足 \(\left\lfloor \dfrac{L-1}{i} \right\rfloor = k,i \in [l,r]\) 。為了在 \(l\) 的基礎上將 \(i\) 向上逼近，我們將整除等式轉化一個不等式 \(i \cdot k \leq L-1\) ， \(r\) 即為 \(i\) 的最大值 \(\left\lfloor \dfrac{L-1}{k} \right\rfloor\) 。

現在我們就可以從 \(d = 1\) 開始列舉，每次可以列舉一個區間。

時間複雜度 \(O(\sqrt{L})\)

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

程式碼

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

bool solve() {
    ll L, R;
    cin >> L >> R;
    ll ans = max(0LL, R / 2 - L + 1);
    for (int l = 1, r;l < L;l = r + 1) {
        int k = (L - 1) / l;
        r = (L - 1) / k;
        ans += max(0LL, min((ll)r, R / (k + 2)) - l + 1);
    }
    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;
}