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;  l=mid;
	}
	
	l=x1,r=x2;
	 (l<=r){
		 mid=((r-l)>>)+l,now=(mid,y1,x2,y2);
		 (now==) bot=mid,l=mid;  r=mid;
	}
	
	l=y1,r=y2;
	 (l<=r){
		 mid=((r-l)>>)+l,now=(x1,mid,x2,y2);
		 (now==) left=mid,l=mid;  r=mid;
	}
	
	l=y1,r=y2;
	 (l<=r){
		 mid=((r-l)>>)+l,now=(x1,y1,x2,mid);
		 (now==) right=mid,r=mid;  l=mid;
	}

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

}

{
	(,&n);

	 l=,r=n;
	 (l<=r){
		 mid=((r-l)>>)+l;
		 x=(,,mid,n),y=(mid,,n,n);
		 (x== && y==){ divn=mid;divx=;; } 
		 (x== && y==){ divx=; ; } 
		 (x>y) r=mid;  l=mid;
	}
	 (!divx){
		l=,r=n;
		 (l<=r){
			 mid=((r-l)>>)+l;
			 x=(,,n,mid),y=(,mid,n,n);
			 (x== && y==){ divn=mid; ; } 
			
			 (x>y) r=mid;  l=mid;
		}
		(,,n,divn);
		(,divn,n,n);
	}  {
		(,,divn,n);
		(divn,,n,n);
	}
	();  ( i=;i<;i++) (,vec[i]);
	();
	(stdout);
	 ;
}

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|$ 最小。

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;
 a[maxn];
 delta[maxn][maxn];
 mid[maxn][maxn];
 f[maxn],last[maxn];

{
	n=();
	 ( i=;i<=n;i++) a[i]=();
	
	 ( i=;i<=n;i++){
		 (!heap()) heap();
		 (!heap()) heap();
		sum1=sum2=;
		 ( j=i;j<=n;j++){
			 now=a[j]-(j-i);
			 (heap()) heap(now),sum1+=now; 
			 (heap()==heap()){
				 (now<heap())
					heap(heap()),sum1+=heap(),
					sum2-=heap(),heap(),
					heap(now),sum2+=now;
				 heap(now),sum1+=now;
			}  {
				 (now>heap())
					heap(heap()),sum2+=heap(),
					sum1-=heap(),heap(),
					heap(now),sum1+=now;
				 heap(now),sum2+=now;
			}
			mid[i][j]=heap();
			delta[i][j]=(sum1-mid[i][j]*heap()) + (mid[i][j]*heap() - sum2);
			
		}
	}

	(f,,(f));
	last[]=-INF; f[]=;
	 ( i=;i<=n;i++){
		 ( j=i;j<=n;j++)  (mid[i][j] > last[i]){
			 (f[j] > f[i]+delta[i][j]) f[j]=f[i]+delta[i][j],last[j]=mid[i][j]+(j-i);
		}
	}
	(,f[n]);
	 ;
}