Educational Codeforces Round 170 (Rated for Div.2)

10月14日 Codeforces 实战记录。

比赛跳转：Educational Codeforces Round 170 (Rated for Div.2)

题解

A. Two Screens

输出：两序列长度 - 开头重复序列 + 是否有重复。

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

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    string a, b; cin >> a >> b;
    int res = 0;
    for(int i = 0; i < a.length(); i++){
        if(a[i] == b[i]) res++;
        else break;
    } 
    res = a.length() + b.length() - res + (res > 0);
    cout << res << '\n';
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

B. Binomial Coefficients, Kind Of

每一列长这样 1 2 4 8 16 … 1，找出规律快速幂直接输出即可。

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

const int mod = 1e9 + 7;

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

signed main(){
    int t = read();
    vector<int>n(t), k(t);
    for(int i = 0; i < t; i++) cin >> n[i];
    for(int i = 0; i < t; i++) cin >> k[i];
    
    for(int i = 0; i < t; i++){
        if(k[i] == n[i]){
            cout << 1 << '\n';
            continue;
        }
        cout << qmi(2, k[i], mod) << '\n';
    }
    
    return 0;
}

C. New Game

把能相邻的块聚集到一起，对每个块取滑动窗口即可。

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

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

void solve(){
    int n = read(), k = read();
    vector<int>v(n);
    for(auto &i : v) cin >> i;
    sort(v.begin(), v.end());
    
    vector<vector<int>> q;
    
    int last = -1;
    vector<int>tmp;
    for(int i = 0; i < n; i++){
        if(v[i] == last){
            tmp.back()++;
        }
        else if(v[i] == last + 1){
            tmp.emplace_back(1);
            last = v[i];
        }
        else{
            q.emplace_back(tmp);
            tmp.clear();
            tmp.emplace_back(1);
            last = v[i];
        }	
    }
    q.emplace_back(tmp);

    
    int res = 0;
    for(auto &u : q){
        int sum = 0, mxsum = 0;
        if(u.size() <= k){
            for(auto &i : u) sum += i;
            res = max(res, sum);
        }
        else{
            for(int i = 0; i < k; i++){
                sum += u[i];
            }
            mxsum = sum;
            
            for(int i = 0; i + k < u.size(); i++){
                sum += u[i + k];
                sum -= u[i];
                mxsum = max(mxsum, sum);
            }
            
            res = max(res, mxsum);
        }
    }
    cout << res << '\n';
}

signed main(){
    int t = read();
    while(t--) solve();
    return 0;
}

D. Attribute Checks

差分优化dp。
转移：r = 0 时，每一项与前一项取最大值
r > 0 时，[r, op] 区间+1
r < 0 时，[0, op + r] 区间+1

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

inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int n, m, c[5010];
int op = 0;

int main(){
    n = read(), m = read();
    
    while(n--){
        int x = read();
        if(x == 0){
            op++;
            for(int i = 1; i <= op; i++) {
                c[i] += c[i - 1];
            }
            for(int i = op; i >= 1; i--){
                c[i] = max(c[i], c[i - 1]);
            }
            for(int i = op; i >= 1; i--){
                c[i] -= c[i - 1];
            }
        }
        else if(x > 0){
            if(x > op) continue;
            c[x]++, c[op + 1]--;
        }
        else{
            if(-x > op) continue;
            c[0]++, c[op + x + 1]--;
        }
    }
        
    int res = 0, sm = 0;
    for(int i = 0; i <= op; i++){
        sm += c[i];
        res = max(res, sm);
    }
    cout << res;
    return 0;
}