Atcoder ABC 386

compaq · 2024-12-30 09:33:36 · 题解

D - Diagonal Separation

是否所有黑色块都在白色块的上方或者左方。

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
struct node{
    int x, y;
    char val;
}mp[N];
bool cmp(node x, node y){
    return x.x == y.x ? x.y < y.y : x.x < y.x;
} // 先按x排，再按y排 
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> mp[i].x >> mp[i].y >> mp[i].val;

    sort(mp + 1, mp + m + 1, cmp);

    int now = n; // 表示当前最小的W的边界 

    for(int i = 1; i <= m; i++){ // x以保证有序，维护当前最小的y 
        if(mp[i].val == 'W') 
            now = min(now, mp[i].y - 1);
        else{
            if(mp[i].y > now){ // 破坏性的'B' 
                cout << "No";
                return 0;
            }
        }
    }
    cout<<"Yes";
    return 0;
}

E - Maximize XOR

题目保证了\dbinom{N}{K}\leq 10^6,所以可以爆搜所有情况，然后取max。

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

typedef long long LL;

const int N = 2e5 + 5;
int n, k;
LL a[N], ans;

void dfs(int k, int i, LL cur) {
    if (k + i > n + 1) return;
    if (k == 0) {
        ans = max(ans, cur);
        return;
    }
    dfs(k - 1, i + 1, cur ^ a[i]);
    dfs(k, i + 1, cur);
}
int main() {
    cin >> n >> k;
    LL base = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], base ^= a[i];
    if (k + k > n) k = n - k; else base = 0;
    // k+k>n 相当于再base中去掉n-k个数 
    dfs(k, 1, base);
    cout << ans << endl;
    return 0; 
}

F - Operate K

经典动归，字符串编辑距离的改编。

设S的前i个字符，T的前j个字符相等的最少操作次数。