Codeforces Round #851 (Div. 2)

A. One and Two

比较两边 \(2\) 的个数即可。

#include <bits/stdc++.h>
using namespace std;
int n, T, prefix[1111], suffix[1111], ans, a[1111];
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n), prefix[0] = 0, suffix[n+1] = 0, ans= -1;
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), prefix[i] = prefix[i-1] + (a[i] == 2);
        for(int i = n; i >= 1; i --) suffix[i] = suffix[i+1] + (a[i] == 2);
        for(int i = n-1; i >= 1; i --) if(prefix[i] == suffix[i+1]) ans = i;
        printf("%d\n", ans);
    }
    return 0;
}

B. Sum of Two Numbers

#include <bits/stdc++.h>
using namespace std;
int T, n, total, A, B;
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n); A = B = 0; int wei = 1, fir = 0;
        while(n){
            int x = n % 10;
            A += wei * (x>>1), B += wei * (x>>1);
            if(x%2){if(fir) A += wei; else B += wei; fir ^= 1;}
            wei *= 10, n /= 10;
        }
        printf("%d %d\n", A, B);
    }
    return 0;
}

C. Matching Numbers

#include <bits/stdc++.h>
using namespace std;
int T, n;
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        if(n % 2 == 0) puts("No");
        else{
            puts("Yes");
            for(int i = 1; i <= n/2+1; i ++) printf("%d %d\n", i, 2*n-i*2+2);
            for(int i = 1; i <= n/2; i ++) printf("%d %d\n", i+n/2+1, 2*n-2*i+1);
        }
    }
    return 0;
}

D. Moving Dots

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e3+11;
const ll mod = 1e9+7;
int n, a[N]; ll ans, pows[N];
int main(){
    pows[0] = 1, scanf("%d", &n); for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), pows[i] = pows[i-1] * 2 % mod;
    for(int i = 1; i <= n; i ++) for(int j = i + 1; j <= n; j ++){
        int dist = a[j] - a[i];
        int l = lower_bound(a+1, a+n+1, a[i] - dist) - a-1;
        int r = lower_bound(a+j+1, a+n+1, a[j]+dist) - a;
        // printf("%d %d %d %d\n", i, j, l, r);
        ans = (ans + pows[n-r+l+1]) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

E. Sum Over Zero

#include <bits/stdc++.h>
using namespace std;
const long long N = 4e5+11;
long long n, a[N];
long long preffix[N], f[N], vec[N];
struct Fenwick{
    long long c[N], total;
    long long lb(long long x){return x & (-x);}
    void modify(long long x, long long y){
        for(; x <= total; x += lb(x)) c[x] = max(c[x], 1ll*y);
    }
    long long query(long long x){
        long long cur = -1111111;
        while(x) cur = max(cur, c[x]), x -= lb(x);
        return cur;
    }
    void clear(int num){
        total = num+11;
        for(long long i = 0; i <= total; i ++) c[i] = -1111111;
    }
}tree;
int main(){
    scanf("%lld", &n);
    for(long long i = 1; i <= n; i ++)
        scanf("%lld", &a[i]),
        vec[i] = preffix[i] = 1ll * a[i] + preffix[i-1];
    sort(vec+1, vec+n+1);
    long long m = unique(vec+1, vec+n+1)-vec-1;
    for(long long i = 0; i <= n; i ++)
        preffix[i] = lower_bound(vec+1, vec+m+1, preffix[i])-vec;
    f[0] = 0; tree.clear(m+11);
    tree.modify(preffix[0], 0);
    for(long long i = 1; i <= n; i ++){
        f[i] = max(f[i-1], 1ll*i + tree.query(preffix[i]));
        tree.modify(preffix[i], f[i]-i);
        // printf("%d\n", f[i]);
    }
    printf("%lld\n", f[n]);
    return 0;
}

F. XOR, Tree, and Queries

#include <bits/stdc++.h>
using namespace std;
const int N = 2.5e5+11;
vector< pair<int, int> > e[N];
vector< pair<int, int> > edge(N+1);
int n, q, Xor[N], sz[N], top[N], ans;
bool visited[N];
void dfs(int u, int rt){
    top[u] = rt, visited[u] = 1;
    if(sz[u]) ans ^= Xor[u];
    for(auto link : e[u]){
        if(visited[link.first]){
            if(link.second != (Xor[u] ^ Xor[link.first])){
                puts("No"); exit(0);
            }
            continue;
        }
        Xor[link.first] = Xor[u] ^ link.second;
        dfs(link.first, rt);
        sz[u] ^= sz[link.first];
    }
}
int main(){
    scanf("%d %d", &n, &q);
    for(int i = 1; i < n; i ++){
        scanf("%d %d", &edge[i].first, &edge[i].second);
        sz[edge[i].first] ^= 1, sz[edge[i].second] ^= 1;
    }
    for(int i = 1; i <= q; i ++){
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        e[x].push_back(make_pair(y, z)), e[y].push_back(make_pair(x, z));
    }
    for(int i = 1; i <= n; i ++) if(visited[i] == false) dfs(i, i);
    for(int i = 1; i <= n; i ++){
        if(top[i] == i && sz[i] != 0){
            for(int j = 1; j <= n; j ++) if(top[j] == i) Xor[j] ^= ans;
            break;
        }
    }
    puts("Yes");
    for(int i = 1; i < n; i ++)
        printf("%d ", (Xor[edge[i].first]^Xor[edge[i].second]));
    return 0;
}