【HHHOJ】ZJOI2019模拟赛（十四）03.12 解题报告

点此进入比赛

得分： \(50+5+24=79\)

排名： \(Rank\ 2\)

\(Rating\)：\(+79\)

\(T1\)：【HHHOJ197】古明地（点此看题面）

基本上全部时间都用来想这题正解，最后只能写了个\(50\)分暴力。

\(50\)分做法如下：

考虑一个贪心，对于每次询问，我们先把\(k_i\)排个序，并预处理时把每个宠物的区间按左端点排个序。

然后从小到大枚举\(k_i\)，同时维护一个\(p\)，每次把左端点小于\(k_i\)的宠物的右端点扔入一个小根堆里。

接下来，我们把堆中小于\(k_i\)的元素，即右端点小于\(k_i\)的宠物全部弹掉，因为\(k_i\)是递增的，所以现在小于\(k_i\)，以后也一定小于\(k_i\)。

然后贪心，把堆中前\(k_i\)个元素弹掉（因为弹掉右端点越小的宠物肯定越优，显然），如果元素不足\(k_i\)

个，输出\(0\)。

否则，在枚举完\(k_i\)后，输出\(1\)。

具体实现过程中不要忘记剪枝，详见代码：

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 500000

#define M 200000

#define Gmin(x,y) (x>(y)&&(x=(y)))

#define Gmax(x,y) (x<(y)&&(x=(y)))

#define INF 1e9

using namespace std;

int n,m,a[M+5],suf[M+5];

struct Pet {int l,r;I bool operator < (Con Pet& t) Con {return l<t.l;}}s[N+5];

priority_queue<int,vector<int>,greater<int> > q;

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		char c,*A,*B,FI[FS];

	public:

		I FastIO() {A=B=FI;}

		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}

		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

}F;

int main()

{

	RI Qtot,i,p,t,tot,flag,Min=INF,Max=-INF;

	for(F.read(n),i=1;i<=n;++i) F.read(s[i].l,s[i].r),Gmin(Min,s[i].l),Gmax(Max,s[i].r);//求出最小的左端点和最大的右端点，用于剪枝

	sort(s+1,s+n+1),F.read(Qtot);W(Qtot--)//预处理时将每个宠物按左端点排序

	{

		for(F.read(m),i=1;i<=m;++i) F.read(a[i]);for(sort(a+1,a+m+1),suf[m+1]=0,i=m;i;--i) suf[i]=a[i]+suf[i+1];//将询问排序，求后缀和用于剪枝

		for(flag=(Min<=a[1]&&Max>=a[m]&&suf[1]<=n),p=1,tot=n,i=1;i<=m&&flag;++i)//先判断是否肯定不合法，然后枚举询问

		{

			W(p<=n&&s[p].l<=a[i]) q.push(s[p++].r);W(!q.empty()&&q.top()<a[i]) --tot,q.pop();//将左端点小于当前询问的宠物的右端点加入小根堆，将堆中小于当前询问的宠物弹出

			W(!q.empty()&&a[i]) --a[i],--tot,q.pop();flag=(!a[i]&&tot>=suf[i+1]);//弹出堆中元素，若元素个数不足，则可直接判断无解

		}puts(flag?"1":"0");W(!q.empty()) q.pop();//输出答案，然后记得清空堆

	}return 0;

}

\(T2\)：【HHHOJ198】觉（点此看题面）

一如既往地看不懂 \(T2\)题目。。。（突然发现最近每次比赛\(T2\)都会挂）

但是\(R_i=P_i=S_i\)这送的\(5\)分还是拿到了，输出\(\frac43n\)即可，代码略。

\(T3\)：【HHHOJ199】少女觉的第三只眼（点此看题面）

一道拿来手玩+玄学调参的交互题。

\(Subtask233\)

我的做法是一直向左移动，移到角落里。

然而据说不动就可以了？

\(Subtask0\)

不难发现右上角始终没有子弹，移过去即可。

\(Subtask1\)

如果全返回\(1\)，则有\(0\sim5\)分不等。

\(Subtak2\sim Subtask3\)

爆\(0\)。

代码如下：

#include"Eye.h"

int operate_Test(int N,double x[],double y[],double r[],double X,double Y,int T,int D_ti) {return 1;}//移动到角落里，然而似乎原地不动即可

int operate_Cirno(int N,double x[],double y[],double r[],double X,double Y,int T,int D_ti) {return T<36?2:3;}//移到右上角

int operate_Shinmyoumaru(int N,double x[],double y[],double r[],double X,double Y,int T,int D_ti) {return 1;}//直接返回1，有0~5分不等

int operate_Suwako(int N,double x[],double y[],double r[],double X,double Y,int T,int D_ti) {}//爆0

int operate_Sagume(int N,double x0[],double y0[],double x[],double y[],double r[],double X,double Y,int T,int D_ti) {}//爆0

巴特西