题目：

http://acm.hdu.edu.cn/diy/diy_previewproblem.php?cid=30741&pid=1004

http://cogs.pro/cogs/problem/problem.php?pid=1407

A lot of frogs are living in a water tank, but none of them know exactly how much water are there.

The water tank has an infinite height, but with a narrow bottom. The length of the tank is N,
and the width is only 1.

Now N−1 boards
has divided the tank into N parts,
each with an 1×1 bottom.
Boards may have different heights. Water cannot flow through the boards, but can run freely if the water level is higher, following the basic physical rules.

The Frog King wants to know more details of the tank, so he sent someone to choose M positions
and find whether there’s water at that position.

For example, each time he’ll choose(x,y),
checking the xth part
of the tank(1≤x≤N),
counting from left to right, and find whether there’s water at height (y+0.5).

Now the King gets M results,
but he finds some of them might be wrong. The King wants to find out the maximum possible number of the correct results.

题解：

基础想法是很简单的：假设先考虑所有N个部分。我们找出其中最高的那个隔板，分两种情况讨论：①如果这个隔板没有被淹没，那就可以分别处理左右两个部分。②如果这个隔板被淹没，我们就取出那些比这个隔板高的观测点，顺序扫描一遍，找出最优解。综合①②就能得到答案了。

但是细节比较……麻烦。怎么“找出最高的隔板”呢？我写了个ST算法求RMQ。怎么“取出比它高的观测点”呢？我在分治时，对每个区间储存两个set（分别表示观测值为0和1的结果），递归上来时按秩合并，删掉那些比隔板低的观测点，并固定下来它们对答案的贡献。总之写的非常不优美。

更好的解法能在网上找到，似乎是类似建一棵树然后DP。

模拟训练的时候出了两个错误：第一个是打错了一个变量名，第二个是没有把删去点的贡献传给上一层。始终没debug出来。

代码：

#include
#include
#include
#include
#include
#include
using namespace std;
typedef multiset::iterator ITER;
const int SIZEN=100010;
const int INF=0x7fffffff/2;
void printset(multiset s){
	for(ITER key=s.begin();key!=s.end();key++){cout<<(*key)<<" ";}cout<>=1;}
	if(ans<0) ans=0;
	return ans;
}
int ST[20][SIZEN];
void build_st(int a[],int n){
	int m=log2(n);
	for(int i=0;ia[q]?p:q);
			}
		}
	}
}
int RMQ(int a[],int l,int r){
	int m=log2(r-l+1);
	int p=ST[m][l],q=ST[m][r-(1<a[q]?p:q;
}
int N;
int H[SIZEN];
multiset SL[SIZEN],SH[SIZEN];
int calc(multiset &sl,multiset &sh,int high){//l:0,h:1
	ITER key1=sl.begin(),key2=sh.begin();
	int now=sl.size(),ans=now;
	for(;key1!=sl.end()&&(*key1)<=high;key1++){
		while(key2!=sh.end()&&(*key1)>=(*key2)) now++,key2++;
		ans=max(ans,now);
		now--;
	}
	key1=sl.begin(),key2=sh.begin();
	now=sl.size();
	for(;key2!=sh.end()&&(*key2)<=high;key2++){
		now++;
		while(key1!=sl.end()&&(*key2)>(*key1)) now--,key1++;
		ans=max(ans,now);
	}
	return ans;
}
int merge(int a,int b,int lim,int &cnt){
	if(SL[a].size()+SH[a].size()>SL[b].size()+SH[b].size()) swap(a,b);
	for(ITER key=SL[a].begin();key!=SL[a].end();key++){
		if((*key)>lim) SL[b].insert(*key);
	}
	for(ITER key=SH[a].begin();key!=SH[a].end();key++){
		if((*key)>lim) SH[b].insert(*key);
		else cnt++;
	}
	for(ITER key=SL[b].begin();key!=SL[b].end();){
		ITER key1=key;key1++;
		if((*key)<=lim){
			SL[b].erase(key);
			key=key1;
		}
		else break;
	}
	for(ITER key=SH[b].begin();key!=SH[b].end();){
		if((*key)<=lim){
			ITER key1=key;key1++;
			SH[b].erase(key);
			key=key1;
			cnt++;
		}
		else break;
	}
	return b;
}
int DQ(int a,int b,int mx,int &s,int &cnt){
	if(a==b){
		cnt=0;
		s=a;
		return calc(SL[a],SH[a],mx);
	}
	int p=RMQ(H,a,b-1);
	int ans=0;
	int s1,s2,cnt1,cnt2;
	ans=DQ(a,p,H[p],s1,cnt1)+DQ(p+1,b,H[p],s2,cnt2);
	cnt=cnt1+cnt2;
	s=merge(s1,s2,H[p],cnt);
	ans=max(ans,calc(SL[s],SH[s],mx)+cnt);
	return ans;
}
void read(void){
	int Q;
	scanf("%d%d",&N,&Q);
	for(int i=1;i

[Shanghai2015]Discover Water Tank解题报告

题目：

题解：

代码：

发表回复取消回复

题目：

题解：

代码：

发表回复 取消回复

发表回复取消回复