【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),则有(0sim5)分不等。

(Subtak2sim 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
原文地址:https://www.cnblogs.com/chenxiaoran666/p/HHHOJ_ZJOI2019_14.html