• 欢迎光临~

# Codeforces Round #815 (Div. 2) 题解

## CF1720A. Burenka Plays with Fractions

• 剩下皆为 (2) 次。
``````#include<bits/stdc++.h>
using namespace std;

#define int long long

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(){
while(t--){
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

• 即为选一个区间使区间内极差加上区间外极差最大。
• (a) 排序，取区间 ([2,n-1])，答案即为 (a[n]+a[n-1]-a[2]-a[1])
``````#include<bits/stdc++.h>
using namespace std;

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(){
while(t--){
sort(a+1,a+n+1);
print(a[n]+a[n-1]-a[1]-a[2]),puts("");
}
return 0;
}
``````

## CF1720C. Corners

``````#include<bits/stdc++.h>
using namespace std;

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(){
while(t--){
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)

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

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

``````#include<bits/stdc++.h>
using namespace std;

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(){
while(t--){
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)

(a_j) (i) (a_i) (j)
(0) (0) (0) (1)
(1) (1) (0) (1)
(0) (0) (1) (0)
(1) (1) (1) (0)

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

``````#include<bits/stdc++.h>
using namespace std;

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(){
while(t--){
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){
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

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

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

• (mleq k)

• (m>k)

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

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

``````#include<bits/stdc++.h>
using namespace std;

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(){
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){
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;
}
``````
• 总结：冷静读题，观察特殊点。