E - Maximize XOR
题目大意
给出 \(n\) 个数，要选 \(k\) 个使异或和最大。
\(n\leq 2\times10^5,k\leq n\)
\(C_n^k\leq10^6\)
思路
由于那个组合数的性质，发现应该是直接深搜就可以的。可是发现 T 了。发现如果 \(k\) 很大那么还是不好处理。但是发现搜 \(k\) 个数和搜 \(n-k\) 个数是一样的，只不过第二种得到的值要用 \(n\) 个数的总异或值再异或一次。然后又因为 \(C_n^k=C_n^{n-k}\) 所以时间复杂度就是 \(O(C_n^k)\)。
代码
// Problem: E - Maximize XOR
// Contest: AtCoder - AtCoder Beginner Contest 386
// URL: https://atcoder.jp/contests/abc386/tasks/abc386_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;
ll n,k,a[MAXN];
ll ans,ma;
ll Val=0;
void dfs(ll x,ll num,ll val){
if(num>k||x>n+1){
return;
}
if(num==n-k){
ans=max(ans,Val^val);
return;
}
if(num==k){
ans=max(ans,val);
return;
}
dfs(x+1,num+1,val^a[x]);
dfs(x+1,num,val);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a[i];
ma=max(ma,a[i]);
Val^=a[i];
}
dfs(1,0,0);
cout<<ans<<endl;
return 0;
}
F - Operate K
题目大意
判断字符串 \(s\) 是否可以在 \(k\) 个编辑距离内变成 \(t\)。
一个编辑距离指进行下列三个操作之一：
- 将 \(s_i\) 改为 \(c\)。
- 删除 \(s_i\)。
- 在 \(s_i\) 和 \(s_{i+1}\) 之间新增字符 \(c\)。
\(|s|,|t|\leq 5\times10^5,k\leq20\)
思路
首先对于编辑距离有朴素 \(O(|s|\cdot|t|)\) 动规。设 \(f_{i,j}\) 表示当前从 \(s_1\) 到 \(s_i\) 在最小位 \(f_{i,j}\) 个编辑距离内匹配到了 \(t_1\) 到 \(t_j\)。
所以对于 \(f_{i,j}\) 有三种更新方式：
- \(f_{i,j}\leftarrow f_{i-1,j}+1\) 表示在 \(s_{i-1}\) 后新添一个 \(t_j\) 的字符完成匹配。
- \(f_{i,j}\leftarrow f_{i,j-1}+1\) 表示删除 \(s_i\)。
- \(f_{i,j}\leftarrow f_{i-1,j-1}+[s_i\neq t_j]\) 表示如果一样就直接继承，否则将 \(s_i\leftarrow t_j\)。
三种操作取最小值即可。初始化显然有 \(f_{0,i}=f_{i,0}=i\)。
考虑优化。发现 \(k\) 很小，所以编辑距离很大的状态可以直接剪枝掉。所以对于每一个 \(i\)，最极端的情况就是 \(j=i-k\) 或 \(j=i+k\) 了。即长度为 \(k+1\) 的区间。所以对于每一个 \(i\) 只转移 \(j\in[\max(1,i-k),\min(|t|,i+k)]\) 的区间即可。
时间复杂度 \(O(|s|k)\)
代码
// Problem: C - Operate 1
// Contest: AtCoder - AtCoder Beginner Contest 386
// URL: https://atcoder.jp/contests/abc386/tasks/abc386_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e5 + 5;
string s1, s2;
unordered_map<ll, ll> dp[MAXN];
ll gt(ll i, ll j) {
if (dp[i].count(j)) {
return dp[i][j];
}
return 1e9;
}
int main() {
ll k;
cin >> k;
cin >> s1 >> s2;
ll l1 = s1.size(), l2 = s2.size();
s1 = " " + s1;
s2 = " " + s2;
if (abs(l2 - l1) > k) {
cout << "No" << endl;
return 0;
}
for (int i = 0; i <= k; ++i) {
dp[i][0] = i;
}
for (int i = 0; i <= k; ++i) {
dp[0][i] = i;
}
for (int i = 1; i <= l1; ++i) {
for (int j = max(1ll, i - k); j <= min(l2, i + k); ++j) {
dp[i][j] = min({gt(i - 1, j) + 1, gt(i, j - 1) + 1,
gt(i - 1, j - 1) + (s1[i] != s2[j])});
// cout << i << " " << j << " " << dp[i][j] << " " << gt(i - 1, j) + 1 <<
// " "<< gt(i, j - 1) + 1 << " " << gt(i - 1, j - 1)<< endl;
}
}
cout << (dp[l1][l2] <= k ? "Yes" : "No") << endl;
return 0;
}