題目地址：https://codeforces.com/contest/1920

Problems A. Satisfying Constraints

思路

題目給出若干約束，求符合要求的數(shù)字個數(shù)。

若為1，則大于等于該約束；若為2，則小于等于該約束；若為3，則不能等于該約束。

對于前兩種情況，統(tǒng)計最大左邊界和最小右邊界；對于第三種情況，存入數(shù)組中。然后統(tǒng)計在邊界內(nèi)的第三種情況的個數(shù)，最后用邊界內(nèi)數(shù)字個數(shù)減去區(qū)間內(nèi)第三種情況的個數(shù)即可。

標(biāo)程

void Solved() {
    int n; cin >> n;
    int mx = INF, mi = 0;
    vector<int> a;
    for(int i = 0; i < n; i ++ ) {
        int x, y; cin >> x >> y;
        if(x == 1) {
            mi = max(mi, y);
        } else if(x == 2) {
            mx = min(mx, y);
        } else {
            a.push_back(y);
        }
    }
    int sum = 0;
    for(auto i : a) {
        if(i >= mi && i <= mx) sum ++;
    }
    int res = mx - mi + 1 - sum;
    
    cout << max(res, 0) << endl;
}

Problems B. Summation Game

思路

簡單博弈，因為每人只操作一次，Bob希望結(jié)果數(shù)組之和最小，Bob會將前$x$大的數(shù)都變?yōu)樨?fù)，那么我們就只需要考慮Alice需要刪除多少數(shù)字才能讓結(jié)果數(shù)組之和最大。那么我們只需枚舉$k$次即可，對應(yīng)Alice刪除$\mathrm{0...}k$個數(shù)字，要使Bob取反后的數(shù)組之和最大，那么Alice刪除數(shù)字將會按照從大到小的順序。

標(biāo)程

#define int long long
void Solved() {
    int n, k, x; cin >> n >> k >> x;
    vector<int> a(n + 1), b(n + 1);
    int res = -INF;
 
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    sort(a.begin() + 1, a.end());
    for(int i = 1; i <= n; i ++ ) {
        b[i] = a[i] + b[i - 1];
    }
 
    for(int i = n; i >= n - k; i -- ) {
        int j = max(0ll, i - x);
        res = max(res, b[j] - (b[i] - b[j]));
    }
 
    cout << res << endl;
}

Problems C. Partitioning the Array

思路

本題是一道同余數(shù)論。給定長度為$n$的數(shù)組$a$，然后將數(shù)組均分為若干份，如果當(dāng)前分法可以找到每個子份對同一個數(shù)字取余后都相等，則分?jǐn)?shù)加一，問能加多少分？

1. 同余： 兩個整數(shù)，如果他們同時除以一個自然數(shù)$m$，所得的余數(shù)相同，則稱對于模$m$同余，記作$a\equiv b（mod.m）$
2. 關(guān)于將數(shù)組均分為若干份，我們可以直接枚舉即可。
3. 而判斷當(dāng)前所有組是否可以對同一個數(shù)字取余后相等，需要遍歷一遍數(shù)組。

標(biāo)程

void Solved() {
    int n; cin >> n;
    vector<int> a(n);

    for(auto &i : a) cin >> i;

    int res = 0;
    for(int i = 1; i <= n; i ++ ) {
        if(n % i == 0) {
            int g = 0;
            for(int j = i; j < n; j ++ ) {
                g = gcd(g, a[j] - a[j - i]);
            }
            res += (g != 1);
        }
    }
    
    cout << res << endl;   
}

Problems D. Array Repetition

思路

本題首先給出$n,q$，然后給出$n$次操作，每次操作有兩種：1. 在數(shù)組后面添上一個數(shù)字$x$，2. 將已有數(shù)組復(fù)制到數(shù)組后面$x$次。然后有$q$次查詢，每次查詢要求輸出數(shù)組當(dāng)前元素的值。

由于數(shù)組長度將會非常大，因此我們不能考慮模擬。

1. 我們可以記錄每次操作過后的數(shù)組長度。
2. 每次查詢是直接查詢數(shù)組下標(biāo)，因此我們可以找到第一個令數(shù)組長度大于該下標(biāo)的操作。
3. 注意當(dāng)數(shù)據(jù)比較大時會爆$longlong$，因此在讀入的時候要注意。
4. 如果將所有數(shù)據(jù)（操作、當(dāng)前數(shù)組長度）一起存，然后二分查找，這樣會導(dǎo)致超時。

我們可以在讀入的時候記錄該次操作后的數(shù)組長度，然后記錄該操作的$x$，用來最后輸出。每次查詢的時候找到對應(yīng)的操作，若是第二種操作，則將本次查詢的下標(biāo)對上一次操作的數(shù)組長度取模。最后必然找出的是第一次操作，輸出即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-797266.html

標(biāo)程

void solve(){
    int n, q; cin >> n >> q;

    ll dp[n + 1] = {};
    int lstAdd[n + 1] = {};
    vector<int> pos;

    for (int i = 1, doAdd = true; i <= n; i++){
        int a, v; cin >> a >> v;

        if (a == 1) {
            lstAdd[i] = v;
            dp[i] = dp[i - 1] + 1;
        } else {
            lstAdd[i] = lstAdd[i - 1];
            dp[i] = ((v + 1) > 2e18 / dp[i - 1]) ? (ll)2e18 : dp[i - 1] * (v + 1);

            if (doAdd) pos.push_back(i);
        }
        if (dp[i] == 2e18) doAdd = false;
    }
    while (q--){
        ll k; cin >> k;

        for (int i = pos.size() - 1; i >= 0; i--){
            int idx = pos[i];

            if (dp[idx] > k && dp[idx - 1] < k){
                if (k % dp[idx - 1] == 0){
                    k = dp[idx - 1]; break;
                }
                k %= dp[idx - 1];
            }
        }
        cout << lstAdd[lower_bound(dp + 1, dp + n + 1, k) - dp]<<" \n"[q == 0];
    }
}

超時代碼（思路較直觀）

#define int long long
struct arr{int x, y, z;};
arr a[N];
int n, q, sum;
 
int find(int m) {//找第一個大于m的a[i].z
    int l = 1, r = n, mid;
    while(l < r) {
        mid = (l + r) / 2;
        if(a[mid].z < m) l = mid + 1;
        else r = mid;
    }
    return l;
}
 
void Solved() {
    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i].x >> a[i].y;
        if(a[i].x == 1) a[i].z = a[i - 1].z + 1;
        else {
            if((a[i].y > 2e18 / a[i - 1].z) && !sum){
                a[i].z = 2e18;
                sum = i;
            } else {
                a[i].z = a[i - 1].z * (a[i].y + 1);
            }
        }
    }
    while(q -- ) {
        int m; cin >> m;
        int t = find(m);
        while(a[t].x == 2) {
            m %= a[t - 1].z;
            if(m == 0) m = a[t - 1].z;
 
            t = find(m);
        }
        cout << a[t].y << " ";
    }
    cout << endl;
}

到了這里，關(guān)于Codeforces Round 919 (Div. 2)（A-D)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！