Codeforces Round #371 Div1 ABC 题解

我回来啦！！希望尽早康复 QwQ

好像是第一次打 div1？

Link

A. Sonya and Queries

二叉树记录。

B. Searching Rectangles

Description

这是一道交互题。

给出 $n*n$ 的网格，其中有两个标记的长方形区域，保证无重叠。每次可以查询一个长方形区域内包含了几个标记的长方形（完全包含才算包含），返回的答案是 0、1 或者 2。询问次数不超过 200 次。

输出两个长方形区域的位置。

$n\le 2^{16}$。

Thoughs

题目的这个 $n\le 2^{16}$ 强暗示要二分。

一开始的想法是通过二分可以分别定位两个矩形的各个边界（即延长两个矩形的各条边形成「大矩形」的边界），然后直接验证，如果不正确则交换两个矩形的左边界、右边界。

但是 Test#4 的这组数据把这个想法 hack 了：

10
1 1 10 1
5 5 5 10

现在看来，这种明显没有想清楚也没有证明的做法我是怎么有胆交 6 发的……

Analysis

其实考虑如果只有一个长方形，问题就非常简单，直接用二分法可做。

现在有两个长方形，但是给出了一个保证：一定没有重叠。那么一定可以找到一条平行于 $x$ 轴或者 $y$ 轴的分界线，使得这条分界线把 $n*n$ 的网格分为两部分，每个部分各自独立包含一个完整的长方形。（这个是非常重要但是没有想到的性质 TAT）

首先可以二分枚举这个分界线，然后对于分出的两块，每块里只有一个矩形，二分可做。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>

using namespace std;

int n;

int queryy(int x1,int y1,int x2,int y2){
	printf("? %d %d %d %d\n",x1,y1,x2,y2);
	fflush(stdout);
	int x; scanf("%d",&x);
	return x;
}

int divn=-1; // where it broke
bool divx=false; // -------

vector<int> vec;

void make_answer(int x1,int y1,int x2,int y2){
	int top=-1,left=-1,bot=-1,right=-1;

	// Find top
	int l=x1,r=x2;
	while (l<=r){
		int mid=((r-l)>>1)+l,now=queryy(x1,y1,mid,y2);
		if (now==1) top=mid,r=mid-1; else l=mid+1;
	}
	// Find bot
	l=x1,r=x2;
	while (l<=r){
		int mid=((r-l)>>1)+l,now=queryy(mid,y1,x2,y2);
		if (now==1) bot=mid,l=mid+1; else r=mid-1;
	}
	// Find left
	l=y1,r=y2;
	while (l<=r){
		int mid=((r-l)>>1)+l,now=queryy(x1,mid,x2,y2);
		if (now==1) left=mid,l=mid+1; else r=mid-1;
	}
	// Find right
	l=y1,r=y2;
	while (l<=r){
		int mid=((r-l)>>1)+l,now=queryy(x1,y1,x2,mid);
		if (now==1) right=mid,r=mid-1; else l=mid+1;
	}

	vec.push_back(bot);
	vec.push_back(left);
	vec.push_back(top);
	vec.push_back(right);

}

signed main(){
	scanf("%d",&n);

	int l=1,r=n-1;
	while (l<=r){
		int mid=((r-l)>>1)+l;
		int x=queryy(1,1,mid,n),y=queryy(mid+1,1,n,n);
		if (x==1 && y==1){ divn=mid;divx=true;break; } else
		if (x==0 && y==0){ divx=false; break; } else
		if (x>y) r=mid-1; else l=mid+1;
	}
	if (!divx){
		l=1,r=n-1;
		while (l<=r){
			int mid=((r-l)>>1)+l;
			int x=queryy(1,1,n,mid),y=queryy(1,mid+1,n,n);
			if (x==1 && y==1){ divn=mid; break; } else
			// if (x==0 && y==0){ printf("ERROR!!!\n"); } else
			if (x>y) r=mid-1; else l=mid+1;
		}
		make_answer(1,1,n,divn);
		make_answer(1,divn+1,n,n);
	} else {
		make_answer(1,1,divn,n);
		make_answer(divn+1,1,n,n);
	}
	printf("! "); for (int i=0;i<8;i++) printf("%d ",vec[i]);
	printf("\n");
	fflush(stdout);
	return 0;
}

C. Sonya and Problem Wihtout a Legend

Description

给出一个数列，每次操作你可以对其中任意一个元素 +1 或者 -1。要求最终将其变为严格单调递增数列。求最少需要的操作数。

$1\le n\le 3000$，$1\le a_i\le 10^9$。

Analysis

• 先考虑这个问题的简化版：给出数列 $a_i$，如何用最少操作使得每个元素相等？其实就是如何确定一个 $x$ 使得 $\Sigma |a_i-x|$ 最小。

  答案是，使每个元素等于数列的中位数，即取 $x$ 为中位数。初中奥数「收费站」问题。

  • 如何动态维护一个前缀的这个答案？

    答案是，用两个堆维护中位数，一个大根堆，一个小根堆。使两个堆元素数量相等，则可以得到中位数。分别维护两个堆的和，可以得到操作数答案。

• 考虑简化问题的加强版：给出数列 $a_i$，如何用最少操作使得数列满足相差 $1$ 递增（即 $a_{i+1}=a_i+1$）？

  答案是，直接对一开始的 $a_i$ 操作，对 $a_i$ 减去 $i$，再按照第一个问题做。可以看成调整所有数字相等之后再把 $i$ 加回 $a_i'$。

• 回到这个问题。可以发现对于一对 $a_i > a_j$，我们的最优调整方式肯定是调整为一个由 $a_i$ 开始差 $1$ 递增的序列。所以可以预见，最后的最优调整方案（之一）可以是若干段差 $1$ 递增序列组成的。既然我们在上面可以预处理出任意区间修正为差 $1$ 序列的代价，则可以考虑线性 DP。

  • $F(i)$ 表示前 $i$ 个元素的答案，同时需要记录前 $i$ 个元素修改之后最后一个元素的最小值 $last_i$（因为最后一个值最小肯定保证之后最优，所以是唯一的，不需要纳入状态考虑）。

  • 对于 $F(i)$，枚举 $j$，考虑用 $F(i)$ 修正 $F(j)$，具体是假设 $[i+1,j]$ 这一段都相差 $1$ 递增（根据上面的思路预处理出 $delta(i,j)$）。

  • 能修正的条件是，调整之后 $a_{i+1}' > last_i$。事实上我们可以得到 $a_{i+1}'$，因为上面调整相差 $1$ 递增时，调整完毕后最小的数字（也就是排在第一个的 $a_{i+1}$）肯定是中位数+1（此处中位数指的是 $a_i-i$ 之后算的中位数）。构造 $delta(i,j)$ 时我们也可以存储中位数 $mid(i,j)$，满足 $mid(i+1,j)+1 > last_i$ 时则可以修正。

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>

using namespace std;

#define int long long

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

priority_queue<int,vector<int>,greater<int> > heap1; // min root
priority_queue<int> heap2; // max root
int sum1=0,sum2=0;

const int maxn=3005;
// const int INF=1LL<<60;
const int INF=0x3f3f3f3f3f3f3f3f;

int n;
int a[maxn];
int delta[maxn][maxn];
int mid[maxn][maxn];
int f[maxn],last[maxn];

signed main(){
	n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	
	for (int i=1;i<=n;i++){
		while (!heap1.empty()) heap1.pop();
		while (!heap2.empty()) heap2.pop();
		sum1=sum2=0;
		for (int j=i;j<=n;j++){
			int now=a[j]-(j-i+1);
			if (heap1.empty()) heap1.push(now),sum1+=now; else
			if (heap1.size()==heap2.size()){
				if (now<heap2.top())
					heap1.push(heap2.top()),sum1+=heap2.top(),
					sum2-=heap2.top(),heap2.pop(),
					heap2.push(now),sum2+=now;
				else heap1.push(now),sum1+=now;
			} else {
				if (now>heap1.top())
					heap2.push(heap1.top()),sum2+=heap1.top(),
					sum1-=heap1.top(),heap1.pop(),
					heap1.push(now),sum1+=now;
				else heap2.push(now),sum2+=now;
			}
			mid[i][j]=heap1.top();
			delta[i][j]=(sum1-mid[i][j]*heap1.size()) + (mid[i][j]*heap2.size() - sum2);
			// printf("mid,delta[%lld,%lld] = %lld %lld\n",i,j,mid[i][j],delta[i][j]);
		}
	}

	memset(f,0x3f,sizeof(f));
	last[0]=-INF; f[0]=0;
	for (int i=0;i<=n;i++){
		for (int j=i+1;j<=n;j++) if (mid[i+1][j]+1 > last[i]){
			if (f[j] > f[i]+delta[i+1][j]) f[j]=f[i]+delta[i+1][j],last[j]=mid[i+1][j]+(j-i+1);
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}