Atcoder ABC 386

#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;
}

#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; 
}

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, k;
char s[N], t[N];
int dp[N][50];

int main(){
	scanf("%d", &k);
	scanf("%s", s); scanf("%s", t);
	
	n = strlen(s), m = strlen(t);
	if(abs(n - m) > 20) {
		puts("No");
		return 0;
	}
	
	memset(dp, 0x3f, sizeof dp);
	
	dp[0][20] = 0;
	
	for(int i = 0; i <= n; i++) // s的前i个字符 
		for(int d = 0; d <= 40; d++){// s的位置与t的位置的相对差值 
			int j = i + d - 20;// j表示在t中的前j个字符 
			if(j < 0 || j > m) continue;
			if(i >= 1 && j >= 1)
				dp[i][d] = min(dp[i][d], dp[i - 1][d] + (s[i - 1] != t[j - 1])); //修改 
			if(i >= 1)
				dp[i][d] = min(dp[i][d], dp[i - 1][d + 1] + 1); // 删除
			if(j >= 1) 
				dp[i][d] = min(dp[i][d], dp[i][d - 1] + 1); // 插入 
		}
	
	if(dp[n][m - n + 20] <= k)
		puts("Yes");
	else
		puts("No"); 
	return 0;
}