Codeforces 1269 #Codeforces

1269A.cpp

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void solve() {
    int n;
    cin >> n;
    int base = (n&1)?9:8;
    cout << base + n << " " << base << endl;
}

signed main() {
    Android;
    solve();
}

1269B.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)
#define print(s) std::cout << s << std::endl

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 2000 + 100;
int n, m, unqA = 0, unqB = 0;
int valA[maxn], valB[maxn];
int cntA[maxn], cntB[maxn];

void solve() {
    cin >> n >> m;
    F(i, n) cin >> valA[i];
    F(i, n) cin >> valB[i];
    sort(valA, valA+n);
    sort(valB, valB+n);
    cntA[0] = cntB[0] = 1;
    for(int i=1; i<n; i++){
        if(valA[i] != valA[i-1]) unqA++;
        cntA[unqA]++;
    }
    for(int i=1; i<n; i++){
        if(valB[i] != valB[i-1]) unqB++;
        cntB[unqB]++;
    }
    unique(valA, valA+n);
    unique(valB, valB+n);
    ll min_ans = 0x3f3f3f3f3f3f3f3f;
    unqA++;
    for(int i=0; i<unqA; i++){
        ll diff = (valB[0] - valA[i] + m) % m;
        bool success = true;
        for(int k=0; k<unqA; k++){
            int l = (i+k)%unqA, r = k%unqA;
            if(cntA[l] != cntB[r]) success=false;
            if((valA[l] + diff) % m != valB[r]) success = false; 
        }
        if(success) min_ans = min(min_ans, diff);
        
    }
    cout << min_ans << endl;
}

signed main() {
    Android;
    solve();
}

1269C.cpp

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

const int maxn = 3e5 + 100;
char buffer[maxn];

void solve() {
    int n, k;
    cin >> n >> k >> buffer;
    bool check_loop = true;
    for(int i=k; i<n && check_loop; i++) 
        if(buffer[i] > buffer[i%k]) check_loop = false;
        else if(buffer[i] < buffer[i%k]) break; // !!!!!
    if(!check_loop){
        buffer[k-1] += 1;
        for(int i=k-1; i>0; i--){
            if(buffer[i] > '9') {
                buffer[i-1]++;
                buffer[i] -= 10;
            }else{
                break;
            }
        }
    }
    cout << n << '\n';
    for(int i=0; i<n; i++) cout << buffer[i%k];
    cout << endl;
}

signed main() {
    Android;
    solve();
}

1269D.cpp

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

const int maxn = 3e5 + 100;
ll h[maxn];

void solve() {
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> h[i];
    ll white = 0, black = 0;
    for(int i=1; i<=n; i++){
        ll div = h[i] / 2;
        white += div, black += div;
        if(h[i] & 1){
            if(i & 1) white++;
            else black++;
        }
    }
    cout << min(white, black) << endl;
}

signed main() {
    Android;
    solve();
}

1269E.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)
#define print(s) std::cout << s << std::endl

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 100;
ll bit_pos[maxn] = {0}, bit_presum[maxn] = {0};
int val_pos[maxn];
int n;

ll calc(ll v){
    return (v + 1) * v / 2;
}

void add(ll * arr, int pos, ll val){
    for(int i=pos; i<=n; i+=(-i)&i) arr[i] += val;
}

ll query(ll * arr, int pos){
    ll ret = 0;
    for(int i=pos; i>0; i-=(-i)&i) ret += arr[i];
    return ret;
}

void solve() {
    cin >> n;
    int tmp;
    for(int i=1; i<=n; i++){
        cin >> tmp;
        val_pos[tmp] = i;
    }

    int le = val_pos[1], re = val_pos[1]; // 使用二分来找中位
    ll ans, cnt_inv = 0;
    for(int k=1; k<=n; k++){
        le = min(le, val_pos[k]);
        re = max(re, val_pos[k]);
        add(bit_pos, val_pos[k], 1);
        add(bit_presum, val_pos[k], val_pos[k]);
        cnt_inv +=  k - query(bit_pos, val_pos[k]); // 逆序对数量
        ans = cnt_inv;
        int l = le, r = re, mid;
        while(l < r){
            mid = (l + r) >> 1;
            if(query(bit_pos, mid) * 2 < k){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        ll l_pre = query(bit_presum, l), l_cnt = query(bit_pos, l);
        ans += l_cnt * l - l_pre - calc(l_cnt - 1);
        ans += (query(bit_presum, re) - l_pre) - (k - l_cnt) * l - calc(k - l_cnt);
        cout << ans << " ";
    }
    cout << endl;
}

signed main() {
    Android;
    solve();
}