比賽連結

A

題意

給一串只包含 \(1,2\) 的數，找到最小的 \(k\) 使得 \(\prod_{i=1}^k a_i = \prod_{i=k+1}^n a_i\) 。

題解

知識點：列舉。

因為只有 \(1,2\) ，所以考慮左右兩邊 \(2\) 的個數即可。

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

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

程式碼

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

int a[1007];
bool solve() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 1;i <= n;i++) cin >> a[i], cnt += a[i] == 2;
    if (cnt & 1) return false;
    int cntt = 0;
    for (int i = 1;i <= n;i++) {
        cntt += a[i] == 2;
        if (cntt == cnt - cntt) {
            cout << i << '\n';
            break;
        }
    }
    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

題意

給定 \(n\) ，找到 \(a,b\) 滿足 \(a+b = n\) 且 \(a,b\) 各自數位之和相差不超過 \(1\) 。

題解

知識點：構造。

我們對 \(n\) 的每位數拆分，若為偶數直接對半分，若為奇數則對半分後交替取大小部分。

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

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

程式碼

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

bool solve() {
    int n;
    cin >> n;
    int a = 0, b = 0;
    bool f = 0;
    int base = 1;
    while (n) {
        int val = n % 10;
        int x = val / 2, y = val - val / 2;
        if (x != y) {
            if (f) swap(x, y);
            f ^= 1;
        }
        a += x * base;
        b += y * base;
        n /= 10;
        base *= 10;
    }
    cout << a << ' ' << b << '\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

題意

將長為 \(2n\) 的排列中的數，兩兩配對 \(\{(a_1,b_1),\cdots ,(a_n,b_n)\}\)，使得 \(\{ a_1+b_1,\cdots , a_n+b_n \}\) 滿足從小到大排序後是連續上升的整數。

題解

知識點：構造。

\(\sum_{i=1}^{2n} i = n(2n+1)\) ，構造 \(n\) 對後平均值是 \(2n+1\) ，為了保證數對是連續上升的，一定從 \(2n+1\) 開始兩側同時擴充套件。

\(n\) 為偶數時，一共有偶數對無法做到兩側同時擴充套件的，所以無解。

\(n\) 為奇數時，只需構造 \((1,2n),\cdots (n,2n-\left\lfloor \dfrac{n}{2} \right\rfloor)\) 以及 \((2,2n-\left\lfloor \dfrac{n}{2} \right\rfloor - 1),\cdots ,(n-1,2n - 2\left\lfloor \dfrac{n}{2} \right\rfloor)\) 即可。

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

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

程式碼

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

bool solve() {
    int n;
    cin >> n;
    if (!(n & 1)) return false;
    cout << "YES" << '\n';
    for (int i = 1;i <= n;i += 2) cout << i << ' ' << 2 * n - i / 2 << '\n';
    for (int i = 2;i <= n;i += 2) cout << i << ' ' << 2 * n - n / 2 - i / 2 << '\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 << "NO" << '\n';
    }
    return 0;
}

D

題意

給定座標軸上 \(n\) 個點，座標為 \(x_i\) ，選中不少於 \(2\) 個點，可以進行一場遊戲。

對於一場遊戲，每個點在開始前會固定移動方向，移動方向為離自己最近的另一個點的方向，若兩個方向最近的點距離一樣，則往左邊走。遊戲開始後，每個點在碰到另一個點後會立刻停止。一場遊戲的價值為，遊戲最後存在點的不同的座標個數。

問，對於所有選點方案，都進行一場遊戲後的價值總和。

題解

知識點：列舉，組合數學。

每個貢獻一定由一組相鄰的且開始後相互靠近的點對產生，對於不相鄰的點對他們不會產生任何貢獻。因此，考慮列舉所有點對，計算滿足相鄰且開始後會相互靠近的方案數，求和便是答案。

對於一組點對 \((i,j)\) ，令 \(d = x_j - x_i\) ，可以用二分計算出最後一個小於 \(x_i-d\) 的位置 \(l\) ，和第一個大於等於 \(x_j+d\) 的位置 \(r\) ，於是 \([1,l],[r,n]\) 的點能保證 \((i,j)\) 兩點相互靠近產生一次貢獻，這些點可選可不選，共計產生 \(2^{l+n-r+1}\) 的貢獻。

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

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

程式碼

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

const int P = 1e9 + 7;
int x[3007];
int p[3007];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> x[i];
    p[0] = 1;
    for (int i = 1;i <= n;i++) p[i] = 2LL * p[i - 1] % P;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            int d = x[j] - x[i];
            int l = lower_bound(x + 1, x + n + 1, x[i] - d) - x - 1;
            int r = lower_bound(x + 1, x + n + 1, x[j] + d) - x;
            (ans += p[l + n - r + 1]) %= P;
        }
    }
    cout << ans << '\n';
    return 0;
}

E

題意

給定一個陣列 \(a_i\) 。設段的集合 \(S\) 滿足：

1. 元素形式為段 \([x,y]\) ，其中 \(1\leq x\leq y\leq n\) 。
2. 所有段沒有交集，即任意兩個段 \(A ,B\) 不存在 \(x\) 滿足 \(x \in A\) 且 \(x \in B\) 。
3. 所有段 \([x,y]\) 滿足 \(\sum_{i=x}^y a_i \geq 0\) 。

一個段集合 \(S\) 的價值為，所有其中元素段長度的和，即 \(\sum_{[x,y] \in S} (y-x+1)\) 。

求對於陣列 \(a_i\) 所有可能的 \(S\) 的價值最大值。

題解

知識點：線性dp，樹狀陣列，離散化。

設 \(s_i\) 為 \(\sum_{j=1}^i a_j\) 。

設 \(f_i\) 為 \([1,i]\) 中 \(S\) 價值的最大值。有轉移方程：

1. 若不選 \(a_i\) ，則 \(f_i = \max(f_i,f_{i-1})\) 。
2. 若選 \(a_i\) ，則考慮 \(j \in [0,i-1]\) 滿足 \(s_i - s_j \geq 0\) 中找到 \(f_j + i -j\) 的最大值。

對於2，樸素遞推是 \(O(n^2)\) 的，考慮用資料結構優化。

注意到 \(f_j + i - j\) 中 \(i\) 是定值，我們只需要知道滿足 \(s_j \leq s_i\) 的 \(j\) 中 \(f_j-j\) 的最大值即可。為了方便找到 \(s_j \leq s_i\) ，我們可以用一個以 \(s_i\) 作為下標，能查詢字首最大值的資料結構，樹狀陣列和權值線段樹都可以。其中，因為我們要求的是最大值，所以對於不同的 \(j\) 若有相同的 \(s\) ，我們取最大的 \(f_j-j\) 作為 \(s\) 對應的值不影響結果。

這裡值域太大了但個數不多，可以離散化處理一個值的排名到值的對映，就可以利用排名作為下標。

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

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

程式碼

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

template<class T>
struct Fenwick {
    int n;
    vector<T> node;

    Fenwick(int _n = 0) { init(_n); }
    void init(int _n) {
        n = _n;
        node.assign(n + 1, T::e());
    }

    void update(int x, T val) {
        for (int i = x;i <= n;i += i & -i)
            node[i] += val;
    }

    T query(int x) {
        T ans = T::e();
        for (int i = x;i >= 1;i -= i & -i)
            ans += node[i];
        return ans;
    }
};

struct T {
    int val;
    static T e() { return { (int)-1e9 }; }
    T &operator+=(const T &x) { return val = max(val, x.val), *this; }
};

template<class T>
struct Discretization {
    vector<T> uniq;
    Discretization() {}
    Discretization(const vector<T> &a) { init(a); }
    void init(const vector<T> &a) {
        uniq = a;
        sort(uniq.begin() + 1, uniq.end());
        uniq.erase(unique(uniq.begin() + 1, uniq.end()), uniq.end());
    }
    int get(T x) { return lower_bound(uniq.begin() + 1, uniq.end(), x) - uniq.begin(); }
};

ll s[200007];
int dp[200007];
int pos[200007];

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> s[i], s[i] += s[i - 1];

    Discretization<ll> dc(vector(s, s + n + 2));
    for (int i = 0;i <= n;i++) pos[i] = dc.get(s[i]);

    Fenwick<T> fw(dc.uniq.size() - 1);
    dp[0] = 0;
    fw.update(pos[0], { dp[0] - 0 });
    for (int i = 1;i <= n;i++) {
        dp[i] = max(dp[i - 1], fw.query(pos[i]).val + i);
        fw.update(pos[i], { dp[i] - i });
    }
    cout << dp[n] << '\n';
    return 0;
}