CF1721.

A. Image

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int t;
void solve() {
	string a, b;
	cin>>a>>b;
	a+=b;
	vector<int> c(30);
	int ans=0;
	for(auto x:a) if(++c[x-'a'+1]==1) ++ans;
	printf("%lld\n",ans-1);
}
signed main() {
	t=read();
	while(t--) solve();
}

B. Deadly Laser

最优解一定是 \((1,1) \rightarrow (1,m) \rightarrow (n,m)\) 或者 \((1,1) \rightarrow (n,1) \rightarrow (n,m)\)。

前者距离 \((s_x,s_y)\) 最近的距离是 \(\min(s_x-1,m-s_y)\)，后者是 \(\min(s_y-1,n-s_x)\)。

如果二者都小于等于 \(d\)，那么无解。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int t, n, m, x, y, d;
void solve() {
	n=read(), m=read(), x=read(), y=read(), d=read();
	if(min(x-1,m-y)<=d&&min(y-1,n-x)<=d) puts("-1");
	else printf("%lld\n",n+m-2);
}
signed main() {
	t=read();
	while(t--) solve();
}

C. Min-Max Array Transformation

对于 \(a_i\)，\(d_i\) 最小值显然是大于 \(a_i\) 的最小的 \(b_i\) 与它的差。

最大值则要复杂一些。例如样例 4 中，如果 \(d_1\) 取 \(45\)，那么 \(40\) 就没有合法决策了。而其它的数字，无论怎么选，都一定存在合法决策，贪心地取了最大的 \(33\)。

由于 \(a\)，\(b\) 都是有序的，所以从 \(n\) 到 \(1\) 考虑。\(40\) 只能变成 \(55\) 是因为前面所有的 \(b_i\) 都小于 \(40\)，而后面的数的决策区间也因此不包含 \(55\)。

维护最大值决策 \(j\)，初始化为 \(n\)，显然 \(j\) 是单调不增的。对于 \(a_i\)，当 \(b_1 \sim b_{i-1}\) 都小于 \(a_i\) 时，\([1,i-1]\) 必然不能取 \(j \in [i,n]\)，否则由于数字是一一对应的，\(a_i\) 将无法决策。所以只要第一个大于等于 \(a_i\) 的是 \(b_i\) 的话，那么令 \(j = i-1\)，否则 \(d_i = b_j - a_i\) 一定是最大决策。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=2e5+5;
int t, n, a[N], b[N], d1[N], d2[N];
void solve() {
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i) b[i]=read();
	int j=n;
	for(int i=n;i;--i) {
		int k=lower_bound(b+1,b+n+1,a[i])-b;
		d1[i]=b[k]-a[i];
		d2[i]=b[j]-a[i];
		if(k==i) j=i-1;
	}
	for(int i=1;i<=n;++i) printf("%lld%c",d1[i]," \n"[i==n]);
	for(int i=1;i<=n;++i) printf("%lld%c",d2[i]," \n"[i==n]);
}
signed main() {
	t=read();
	while(t--) solve();
}

D. Maximum AND

按位贪心。

答案的某一位是 \(1\)，说明每个 \(c_i\) 的这一位都是 \(1\)，因此对于这一位，\(a\) 和 \(b\) 中必须存在两两对应的 \(n\) 对 \(0\) 和 \(1\) 才行。

直接处理复杂度过高。

假设当前处理到了第 \(k\) 位，如果答案第 \(k\) 位为 \(1\)，那么在满足存在两两对应的 \(n\) 对 \(0\) 和 \(1\) 之外，还要满足之前的位仍然不变，否则一定不优。

设答案为 \(d\)，先让 \(d+2^k\)，尝试将配对。\(a_i \& d\) 表示 \(a_i\) 在此时 \(d\) 中的有效位，\(b_i \& d \oplus d\) 表示 \(b_i\) 的有效位关于 \(d\) 的补集，如果它和某个 \(a_j \& d\) 相等，说明二者异或起来为 \(d\)，进而 \(a_j \oplus b_i\) 一定满足第 \(k\) 位位为 \(1\) 和之前的所有条件。

使用std::map统计是否能够两两配对即可。

时间复杂度 \(O(n \log^2_2 n)\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int t, n, d, a[N], b[N];
map<int,int> p;
void solve() {
	n=read();
	d=0;
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i) b[i]=read();
	for(int k=29;~k;--k) {
		d|=1<<k;
		p.clear();
		for(int i=1;i<=n;++i) {
			++p[a[i]&d];
			--p[(b[i]&d)^d];
		}
		bool fg=1;
		for(int i=1;i<=n;++i) if(p[a[i]&d]!=0) {
			 d^=1<<k;
			 break;
		}
	}
	printf("%lld\n",d);
}
signed main() {
	t=read();
	while(t--) solve();
}