Codeforces Round #815 (Div. 2) 题解

CF1720A. Burenka Plays with Fractions

给出两个分数 $ dfrac{a}{b}$ 和 (dfrac{c}{d}) ，你每次操作能够选择其中一个分数的分子或分母，将其乘上任意一个整数（当然不能对分母乘 (0)）。要求求出能够使两个分数相等的最小操作次数。

分类讨论题。

考虑证明最多操作次数不超过两次：

最多在分子分母分别乘上 (bc,ad) 两次。

什么时候不用乘 (2) 次：

• 若 (ad=bc) 则为 (0) 次；
• 若 (ad=0) 或 (bc=0) 或 (adbmod bc=0) 或 (bcbmod ad=0) 则为 (1) 次；
• 剩下皆为 (2) 次。

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
 
int t,a,b,c,d,x,y;
 
signed main(){
	t=read();
	while(t--){
		a=read(),b=read(),c=read(),d=read();
		x=a*d,y=b*c;
		if(x==y)puts("0");
		else if(!x||!y)puts("1");
		else if(x%y==0||y%x==0)puts("1");
		else puts("2");
	}
	return 0;
}

CF1720B. Interesting Sum

给定一个长度为 (n) 的序列 (a)，令 (s=max(a_1,a_2,dots,a_{l-1},a_{r+1},dots,a_{n-1},a_n)-min(a_1,a_2,dots,a_{l-1},a_{r+1},dots,a_{n-1},a_n)+max(a_l,a_{l+1},dots,a_{r-1},a_r)-min(a_l,a_{l+1},dots,a_{r-1},a_r))
要求选定一个区间 ([l,r])，使得 (s) 最大，输出 (s)。

结论题。

• 即为选一个区间使区间内极差加上区间外极差最大。
• 将 (a) 排序，取区间 ([2,n-1])，答案即为 (a[n]+a[n-1]-a[2]-a[1])。

#include<bits/stdc++.h>
using namespace std;
 
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
 
const int N=1e5+5;
int t,n,a[N]; 
 
int main(){
	t=read();
	while(t--){
		n=read();
		for(int i=1;i<=n;++i)a[i]=read();
		sort(a+1,a+n+1);
		print(a[n]+a[n-1]-a[1]-a[2]),puts("");
	}
	return 0;
}

CF1720C. Corners

有一个由 0 和 1 组成的矩阵。

每次操作可以选择一个 (2times 2) 的子矩阵，在这个子矩阵中选择一个 L 形，将这个 L 形里的 3 个数变成 (0)，注意，这个 L 形至少含有一个 1，你想最大化操作个数，问最多操作多少次。

我们最想一次操作选的 (L) 形中有且只有一个 (1)，此时答案即为 (sum a_i)，我们考虑什么时候不能达到。

对一个 (2times 2) 的子矩阵进行研究，发现当子矩阵中有一个 (1) 时，最多操作 (1) 次，没有浪费。

有两个 (1) 时，不论是斜对角还是同行同列，都可以进行两次操作，没有浪费。

有三个 (1) 时，只能进行两次操作，浪费了 (1) 次。

有四个 (1) 时，也只能进行两次操作，浪费了 (2) 次。

而当我们清空出一个 (2times 2) 的子矩形时，其他所有 (1) 都能被 (1) 次操作消去，不会浪费。

统计每个子矩形中最小的浪费个数即可。

#include<bits/stdc++.h>
using namespace std;
 
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
 
const int N=505;
int t,n,m,a[N][N],ans,minn,tmp;
char c;
 
int main(){
	t=read();
	while(t--){
		n=read(),m=read(),ans=0,minn=1e9;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				cin>>c;
				if(c=='1')a[i][j]=1,ans++;
				else a[i][j]=0;
			}
		}
		for(int i=1;i<n;++i){
			for(int j=1;j<m;++j){
				tmp=a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1];
				if(tmp==1||tmp==2)minn=min(minn,0);
				else if(tmp==3)minn=min(minn,1);
				else minn=min(minn,2);
			}
		}
		if(!ans)puts("0");
		else print(ans-minn),puts("");
	}
	return 0;
}

CF1720D1. Xor-Subsequence (easy version)

给你一个长为 (n) 的整数数组 (a_0,a_1,dots,a_{n-1})。求一个最长的序列 (b_0,b_1,dots,b_m) 满足：(0leq b_0<b_1<dots<b_{m-1}<n) 且 (forall pin[0,m)captextbf{N},a_{b_p}oplus b_{p+1}<a_{b_{p+1}}oplus b_p)。输出最大的 (m)。

(1leq Tleq 10^5,2leq nleq 3times 10^5,0leq a_ileq 200,sum nleq 3times 10^5)

有意思的题。

首先你要读懂题，读透题。

然后我们考虑 (dp)，记 (f[i]) 为以 (i) 为结尾的最长的 (b) 序列长度。

可以枚举 (j) 转移 (f[i]=max_{j<i}(f[i],f[j]+1))，总时间复杂度 (O(Tn^2))，显然不行。

考虑不枚举 (j)。

发现这题的特别点：(0leq a_ileq 200)，由于异或，考虑二进制。

显然 (a_i) 在二进制下最多有 (8) 位。

分析这个式子：(a_joplus i<a_ioplus j)，其中 (j<i) 为枚举的转移点。

由于 (i>j) 但是 (i) 在式子的左边，并且 (a_i,a_j) 又特别小，所以要想满足此式，(i,j) 在二进制下位数大于 (8) 时必须有最高位到第 (8) 位相等，再比较第 (0sim 7) 位。

我们考虑通过此优化转移过程：

• (i<256) 时，暴力转移；
• (ige 256) 时，我们可以限定 (j) 的范围 (256timeslfloorfrac{i}{256}rfloorleq j<i)，暴力转移。

这样时间复杂度就优化到了 (O(256Tn))，足以通过。

#include<bits/stdc++.h>
using namespace std;
 
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
 
const int N=3e5+5;
int t,n,a[N],f[N],ans;
 
int main(){
	t=read();
	while(t--){
		n=read(),ans=0;
		for(int i=0;i<n;++i)a[i]=read(),f[i]=1;
		for(int i=0;i<n;++i){
			if(i<256){
				for(int j=0;j<i;++j){
					if((a[j]^i)<(a[i]^j))f[i]=max(f[i],f[j]+1);
				}
			}else{
				int tmp=((i>>8)<<8); 
				for(int j=tmp;j<i;++j){
					if((a[j]^i)<(a[i]^j))f[i]=max(f[i],f[j]+1);
				}
			}
			ans=max(ans,f[i]);
		}
		print(ans),puts("");
	}
	return 0;
}

CF1720D2. Xor-Subsequence (hard version)

题意同上，(0leq a_ileq 10^9)。

我们无法再分块 (dp) 了。

考虑解决异或问题最常见的三种方法：按位讨论，字典树，线性基。这里考虑字典树，按位讨论。

观察这个式子 (a_joplus i<a_ioplus j)，我们发现两者从最高位向下一直相等直到第 (k) 位才不同，而这个不同，一定是：(a_joplus i) 的第 (k) 位为 (0)，(a_ioplus j) 的第 (k) 位为 (1)。

相等？异或虽然不能在不等式里移项，但可以在等式中移项。

所以有：从最高位到第 (k) 位，(a_joplus i=a_ioplus j)，等价于 (a_joplus j=a_ioplus i)。

列出满足(a_joplus i) 第 (k) 位为 (0)，(a_ioplus j) 第 (k) 位为 (1) 的四种有关于 (a_j,i,a_i,j) 在第 (k) 位的情况：

可以发现，(a_ioplus i) 正好与 (a_joplus j) 相反，而此时正好满足 (a_joplus i<a_ioplus j)。

结合上面两种发现，我们考虑在字典树中插入 (a_ioplus i)。

我们记 (nxt[p][0/1]) 为节点 (p) 的 (0/1) 儿子的编号。既然想用字典树优化 (dp) 的转移，就要统计节点所在子树内的 (f[j]) 最大值，所以我们插入的时候加上一个参数 (i) 以便计算子树内 (f) 最大值。

而想要满足不等式，除了让两者相反，还必须让 (a_i,j) 相反，要不然第 (k) 位 (a_j=1,i=0,a_i=0,j=0) 虽然相反，却无法保证小于。

所以我们在记录节点子树内最大值时还要记录经过该点的数在这一位上的 (0/1) 值。

记 (g[p][0/1]) 为插入的 (a_ioplus i) 经过 (p) 点后，以 (p) 为根，(i) 在此位上为 (0/1) 时的子树内最大 (f) 值。

寻找时我们将 (a_ioplus i) 的第 (k) 位取反并且满足 (i) 与此点表示的 (a_j) 相反此位相反的 (g) 值取最大即可，可以看看代码。

每一次先通过字典树寻找最优的 (j)，再插入 (a_ioplus i) 即可。

#include<bits/stdc++.h>
using namespace std;
 
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
 
const int N=3e5+5;
int t,n,a[N],f[N],ans;
int nxt[N*31][2],g[N*31][2],cnt;
 
void insert(int x,int k){
	int p=0;
	for(int i=29;i>=0;--i){
		if(!nxt[p][x>>i&1])nxt[p][x>>i&1]=++cnt;
		p=nxt[p][x>>i&1];
		g[p][k>>i&1]=max(g[p][k>>i&1],f[k]);
	}
}
 
int find(int x,int k){
	int p=0,ans=0;
	for(int i=29;i>=0;--i){
		ans=max(ans,g[nxt[p][!(x>>i&1)]][!(k>>i&1)]);
		p=nxt[p][x>>i&1];
		if(!p)break;
	}
	return ans; 
} 
 
int main(){
	t=read();
	while(t--){
		n=read(),ans=cnt=0;
		for(int i=0;i<=n*30;++i)nxt[i][0]=nxt[i][1]=g[i][0]=g[i][1]=0;
		for(int i=0;i<n;++i)a[i]=read();
		for(int i=0;i<n;++i){
			f[i]=find(a[i]^i,a[i])+1;
			insert(a[i]^i,i);
			ans=max(ans,f[i]);
		}
		print(ans),puts("");
	}
	return 0;
}

CF1720E. Misha and Paintings

给你一个 (ntimes n) 的矩阵 (a)，你可以对 (a) 进行任意次操作，操作的具体步骤如下：

• 选择矩阵 (a) 的一个正方形子矩阵；
• 选择一个正整数数 (x)，其中 (1leq xleq n^2)；
• 将子矩阵内的所有元素修改为 (x)。

你需要求出使矩阵 (a) 恰好包含 (k) 个不同元素所需的最小操作次数，最小操作次数可以为 (0)。

(1leq nleq 500,1leq a_{i,j},kleq n^2)

记原始矩阵中不同值的个数为 (m)。

• (mleq k)

每次只要选中一个 (1times 1) 的小矩阵改变值即可，最小操作次数为 (k-m)。

• (m>k)

样例以及手玩似乎答案不超过 (2)？考虑证明。

我们构造出一种两次一定能解决的方案。

不妨让第一次选中的正方形左上角为原矩阵左上角，假设我们能增加长度 (L) 就增加，并且此矩形的颜色我们不统计上，即颜色为剩下 (k) 个之一，不增加颜色。

也就是说，我们选择了最大的 (L) 使得 (m'ge m)，(L) 再增加 (1) 就会使 (m'<m)。

我们考虑第二个矩形，将它的右下角置于 ((L+1,L+1))，向左上扩展，颜色与第一个矩形相同，都不对整体做贡献。

可以发现，每当第二个矩形边长多 (1) 就会多两个格子消失，最多消失两种颜色，所以可以通过此将颜色变到 (k) 或 (k-1)。

当 (m'=k) 时，已满足要求；当 (m'=k-1) 时，我们可以将第二个矩形的颜色换成一种新的颜色，将 (m') 增加 (1)，使其等于 (k)。

这样我们就证明了最多两次。

我们考虑什么时候答案为 (1)，其余时候都为 (2)。

先计算出每个颜色的上界 ((x1,y1))，下界 ((x2,y2))。即 ((x_1,y_1),(x2,y2)) 是满足能覆盖此种颜色的最小子矩阵。

枚举一个正方形的边长 (len)，然后枚举左上角 ((i,j))，记 (c[i][j]) 为当边长为 (len) 左上角为 ((i,j)) 时，能覆盖的颜色个数。

考虑如何计算 (c[i][j])，直接算复杂度太高，考虑每个颜色的贡献。

对于一种颜色 ，通过它的上下界可以计算出在哪一个区域内的点以 (len) 为边长得到正方形可以覆盖这种颜色。

我们通过二维差分加二维前缀和解决 (c) 的计算。

最后我们只需要判断每一个点 ((i,j)) 在长为 (len) 的前提下计算出的 (m-c[i][j]) 是否等于 (k) 或 (k-1) 即可。

(k-1) 是选中的矩阵颜色可以改变导致的。注意计算细节。

#include<bits/stdc++.h>
using namespace std;
 
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
 
const int N=505;
int n,k,a[N][N],c[N][N],m;
struct node{
	int x1,y1,x2,y2;
}b[N*N];
 
int main(){
	n=read(),k=read();
	for(int i=1;i<=n*n;++i)b[i].x1=b[i].y1=1e9;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			a[i][j]=read();
			b[a[i][j]].x1=min(b[a[i][j]].x1,i);
			b[a[i][j]].y1=min(b[a[i][j]].y1,j);
			b[a[i][j]].x2=max(b[a[i][j]].x2,i);
			b[a[i][j]].y2=max(b[a[i][j]].y2,j);
		}
	}
	for(int i=1;i<=n*n;++i)if(b[i].x1!=1e9)m++;
	if(m<=k){print(k-m);return 0;}
	for(int len=1;len<=n;++len){
		memset(c,0,sizeof(c));
		for(int i=1;i<=n*n;++i){
			if(b[i].x1==1e9)continue;
			int X1=max(1,b[i].x2-len+1);
			int Y1=max(1,b[i].y2-len+1);
			int X2=min(n-len+1,b[i].x1);
			int Y2=min(n-len+1,b[i].y1);
			if(X1<=X2&&Y1<=Y2){
				c[X1][Y1]++;
				c[X2+1][Y1]--;
				c[X1][Y2+1]--;
				c[X2+1][Y2+1]++;
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
				if(m-c[i][j]==k||m-c[i][j]==k-1){
					puts("1");return 0;
				}
			}
		}
	}
	puts("2");
    return 0;
}

• 总结：冷静读题，观察特殊点。

完结撒花！