CF1720.

A. Burenka Plays with Fractions

\[ \frac{a}{b} = \frac{c}{d} \]

\[ ad = cb \]

如果相等，答案为 \(0\)。

如果某一方是 \(0\)，答案为 \(1\)。

如果两者有倍数关系，答案为 \(1\)。

否则为 \(2\)。

#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;
void solve() {
	int a=read(), b=read(), c=read(), d=read();
	if(a*d==b*c) puts("0");
	else if(!a||!c) puts("1");
	else if(max(a*d,b*c)%min(a*d,b*c)==0) puts("1");
	else puts("2");
}
signed main() {
	t=read();
	while(t--) solve();
}

B. Interesting Sum

发现无论如何都能选择一个区间，满足区间内最大值是序列最大值或次大值，区间内最小值是序列最小值或次小值。

#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, a[N];
void solve() {
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	sort(a+1,a+n+1);
	int ans=a[n]-a[1]+a[n-1]-a[2];
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

C. Corners

发现第一次操作后，每次操作一定都能只消耗一个白点。

如果存在两个 \(0\) 能被同时操作，那么第 \(1\) 次操作就会消耗 \(1\) 个白点，否则，如果存在 \(0\)，就会消耗 \(2\) 个，否则就会消耗 \(3\) 个。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
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, a[505][505];
void solve() {
	n=read(), m=read();
	rep(i,1,n) rep(j,1,m) scanf("%1d",&a[i][j]);
	int cnt1=0, dlt=1;
	rep(i,1,n) rep(j,1,m) cnt1+=a[i][j];
	rep(i,1,n) rep(j,1,m) {
		if(!a[i][j]) {
			if(i>1&&!a[i-1][j]) dlt=0;
			else if(i<n&&!a[i+1][j]) dlt=0;
			else if(j>1&&!a[i][j-1]) dlt=0;
			else if(j<m&&!a[i][j+1]) dlt=0;
			else {
				if(i>1&&j>1&&!a[i-1][j-1]) dlt=0;
				else if(i>1&&j<m&&!a[i-1][j+1]) dlt=0;
				else if(i<n&&j>1&&!a[i+1][j-1]) dlt=0;
				else if(i<n&&j<m&&!a[i+1][j+1]) dlt=0;
			}
			if(!dlt) break;
		}
	}
	if(cnt1==n*m) dlt=2;
	printf("%lld\n",cnt1-dlt);
}
signed main() {
	t=read();
	while(t--) solve();
}

D1. Xor-Subsequence (easy version)

这题被 Hack 了，原因是使用memset()。

注意到 \(a_i \in [0,200]\)。

设 \(f(i)\) 为以 \(i\) 结尾的 beautiful subsequence 的最大长度，以下下标均从 \(0\) 开始。

初始值 \(f(i)=1\)。 \[ f(i) = \max_{j \in [0,i-1]} \{ f(j) + 1 \} \] 其中 \(a_j \oplus i < a_i \oplus j\)。

这样的复杂度是 \(O(n^2)\) 的。

由于 \(a_i\) 不超过 \(2^8\)，所以 \(j \in [\max(0,i-2^8),i-1]\)。

可过。

答案 \(\max_{i=0}^{n-1} f_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=3e5+5;
int t, n, a[N], f[N];
void solve() {
	n=read();
	for(int i=0;i<n;++i) f[i]=0;
	int ans=0;
	for(int i=0;i<n;++i) a[i]=read();
	for(int i=0;i<n;++i) {
		f[i]=1;
		for(int j=max(0ll,i-256);j<i;++j) {
			if((a[j]^i)<(a[i]^j)) f[i]=max(f[i],f[j]+1);
		}
		ans=max(ans,f[i]);
	}
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

D2. Xor-Subsequence (hard version)

\(a_i \in [0,10^9]\)，上面的做法失效了。考虑优化这个 DP。

如果 \(a_j \oplus i < a_i \oplus j\)，那么一定存在一个 \(k\)，满足前 \(k\) 位中，\(a_j \oplus i = a_i \oplus j\)，\(k+1\) 位上，前者为 \(0\)，后者为 \(1\)。

设 \(w(k,x)\) 为 \(x\) 二进制中第 \(k\) 位的值。

不知道为什么下面部分字体出现了问题，但是不影响观看。

如果 \(w(1 \sim k, a_j \oplus i) = w(1 \sim k,a_i \oplus j)\)，那么两边同时异或上 \(i \oplus j\)，即 \(w(1 \sim k,a_j \oplus j) = w(1 \sim k,a_i \oplus i)\)。这个转化，直接将 \(O(n^2)\) 级别的数对变成 \(O(n)\) 级别的了。

而 \(k+1\) 位上，有 \(a_j \oplus j < a_i \oplus i\)，这表明 \(w(k+1,a_i \oplus i) \oplus 1 = w(k+1,a_j \oplus j)\)，这是第一个要点。

由于 \(w(k+1,a_j \oplus i) < w(k+1,a_i \oplus j)\)，所以 \(w(k+1,a_i \oplus j) = 1\)，即 \(w(k+1,a_i) \neq w(k+1,j)\)，这是第二个要点。

建立一颗 0-1 Trie 来维护这个东西，插入 \(a_i \oplus i\)。对于每个 \(f(i)\)，通过上述方法找到满足条件的最大的 \(f(j)\)。

设 \(g(x,k=0/1)\) 为字典树上经过 \(x\) 节点，且这一位为 \(0/1\) 的最大的 \(f(j)\)。上文两个要点已经说明的求的满足条件的 \(j\) 的方法，即要过 \(w(k+1,a_i \oplus i) \oplus 1\) 这个节点，且第 \(k+1\) 位与 \(w(k+1,a_i)\) 不同。

复杂度 \(O(n \log_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=3e5+5;
int t, n, tot, a[N], f[N], trie[30*N][2], g[30*N][2];
void insert(int s,int id) {
	int x=0;
	for(int i=30;~i;--i) {
		int a=(s>>i)&1;
		if(!trie[x][a]) trie[x][a]=++tot;
		x=trie[x][a];
		g[x][(id>>i)&1]=max(g[x][(id>>i)&1],f[id]);
        // id为下标
	}
}
int query(int s,int k) {
	int ans=0, x=0;
	for(int i=30;~i;--i) {
		int a=(s>>i)&1, y=trie[x][a^1];
        // y=a[i]^i^1的这一位所在的节点
		ans=max(ans,g[y][(k>>i)&1^1]+1);
        // k为a[i],(k>>i)&1^1等于在这一位上，y与k不同
		if(!trie[x][a]) break;
        // 没有后续的节点了，结束
		x=trie[x][a];
	}
	return ans;
}
void solve() {
	n=read();
	for(int i=0;i<n;++i) a[i]=read(), f[i]=1;
	for(int i=0;i<=tot;++i) trie[i][0]=trie[i][1]=g[i][0]=g[i][1]=0;
	tot=0;
	for(int i=0;i<n;++i) {
		f[i]=query(a[i]^i,a[i]);
		insert(a[i]^i,i);
        // 注意插入和查询的参数不同
	}
	int ans=0;
	for(int i=0;i<n;++i) ans=max(ans,f[i]);
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}