【CSP-S 2019模拟】题解

T1：

$md,L$自己机子出问题把我$65$分代码$T$成$0pts$，然后我就被$L$喷了一顿，重测了一次就过了。。委屈至极

虽然$65$也是正解打挂

我的做法：

可以发现实际上可以一直往右走
主要是每次走完一个障碍后原来被障碍覆盖的点的距离要重新更新
由于每个位置只会被上面或者下面的更新
于是可以二分出哪一段该被上/下更新
用线段树维护即可
然后挂成$65$

$Update:$
我最开始把所有值离散化了
发现自己有个地方计算应该用原来的下标，但是直接用离散化后的值计算了

就这样还尼玛有分

大草

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define poly vector<int>
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=1400005;
char xxx;
int n,des,sx,sy,dx,dy,px[N],py[N],tot1,tot2;
struct mat{
	int lx,ly,rx,ry;
}p[N];
namespace Seg{
	int ctag[N<<2],tag[N<<2],cov[N<<2],val[N<<2];
	#define lc (u<<1)
	#define rc ((u<<1)|1)
	#define mid ((l+r)>>1)
	inline void pushnow(int u,int k){
		val[u]+=k,tag[u]+=k;
	}
	inline void pushcov(int u,int k){
		val[u]=k,ctag[u]=tag[u]=0,cov[u]=k;
	}
	inline void pushnowc(int u,int k){
		ctag[u]+=k;
	}
	inline void pushdown(int u){
		if(cov[u]){
			pushcov(lc,cov[u]);
			pushcov(rc,cov[u]);
			cov[u]=0;
		}
		if(ctag[u]){
			pushnowc(lc,ctag[u]);
			pushnowc(rc,ctag[u]);
			ctag[u]=0;
		}
		if(tag[u]){
			pushnow(lc,tag[u]);
			pushnow(rc,tag[u]);
			tag[u]=0;
		}
	}
	inline void cover(int u,int l,int r,int st,int des,int k){
		if(st>des)return;
		if(st<=l&&r<=des){pushcov(u,k);return;}
		pushdown(u);
		if(st<=mid)cover(lc,l,mid,st,des,k);
		if(mid<des)cover(rc,mid+1,r,st,des,k);
	}
	inline void update(int u,int l,int r,int st,int des,int k){
		if(st>des)return;
		if(st<=l&&r<=des){pushnow(u,k);return;}
		pushdown(u);
		if(st<=mid)update(lc,l,mid,st,des,k);
		if(mid<des)update(rc,mid+1,r,st,des,k);
	}
	inline void updac(int u,int l,int r,int st,int des,int k){
		if(st>des)return;
		if(st<=l&&r<=des){pushnowc(u,k);return;}
		pushdown(u);
		if(st<=mid)updac(lc,l,mid,st,des,k);
		if(mid<des)updac(rc,mid+1,r,st,des,k);
	}
	inline int find(int u,int l,int r,int p){
		if(l==r){return val[u]+ctag[u]*py[l];}
		pushdown(u);
		if(p<=mid)return find(lc,l,mid,p);
		return find(rc,mid+1,r,p);
	}
}
vector<pii> del[N];
char yyy;
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	n=read();
	des=read();
	for(int i=1;i<=n;i++){
		int lx=read(),ly=read(),rx=read(),ry=read();
		if(lx>rx)swap(lx,rx);
		if(ly>ry)swap(ly,ry);
		p[i].lx=lx,p[i].rx=rx,p[i].ly=ly,p[i].ry=ry;
		px[++tot1]=lx,px[++tot1]=rx,py[++tot2]=ly,py[++tot2]=ry;
	}
	py[++tot2]=0,px[++tot1]=des,px[++tot1]=0;
	sort(px+1,px+tot1+1);
	tot1=unique(px+1,px+tot1+1)-px-1;
	sort(py+1,py+tot2+1);
	tot2=unique(py+1,py+tot2+1)-py-1;
	sx=lower_bound(px+1,px+tot1+1,0)-px,dx=lower_bound(px+1,px+tot1+1,des)-px;
	sy=dy=lower_bound(py+1,py+tot2+1,0)-py;
	for(int i=1;i<=n;i++){
		p[i].lx=lower_bound(px+1,px+tot1+1,p[i].lx)-px;
		p[i].rx=lower_bound(px+1,px+tot1+1,p[i].rx)-px;
		p[i].ly=lower_bound(py+1,py+tot2+1,p[i].ly)-py;
		p[i].ry=lower_bound(py+1,py+tot2+1,p[i].ry)-py;
	}
	for(int i=1;i<=n;i++){
		if(p[i].lx>=sx&&p[i].lx<=dx)
		del[p[i].rx].pb(pii(p[i].ly,p[i].ry));
	}
	Seg::update(1,1,tot2,sy+1,tot2,-py[sy]),Seg::updac(1,1,tot2,sy+1,tot2,1);
	Seg::update(1,1,tot2,1,sy-1,py[sy]),Seg::updac(1,1,tot2,1,sy-1,-1);
	for(int i=sx+1;i<=dx;i++){
		Seg::update(1,1,tot2,1,tot2,px[i]-px[i-1]);
		for(pii &x:del[i]){
			int l=x.fi,vl=Seg::find(1,1,tot2,l),r=x.se,vr=Seg::find(1,1,tot2,r),del=py[r]-py[l]-1;
			if(vr+del+1<=vl){Seg::cover(1,1,tot2,l+1,r-1,vr),Seg::update(1,1,tot2,l+1,r-1,py[r]),Seg::updac(1,1,tot2,l+1,r-1,-1);}
			else if(vl+del+1<=vr){Seg::cover(1,1,tot2,l+1,r-1,vl),Seg::update(1,1,tot2,l+1,r-1,-py[l]),Seg::updac(1,1,tot2,l+1,r-1,1);}
			else{
				int k=(vr+py[r]-vl+py[l])/2;k=lower_bound(py+1,py+tot2+1,k)-py;
				Seg::cover(1,1,tot2,k,r-1,vr),Seg::update(1,1,tot2,k,r-1,py[r]),Seg::updac(1,1,tot2,k,r-1,-1);
				Seg::cover(1,1,tot2,l+1,k-1,vl),Seg::update(1,1,tot2,l+1,k-1,-py[l]),Seg::updac(1,1,tot2,l+1,k-1,1);
			}
		}
	}
	cout<<Seg::find(1,1,tot2,dy)<<'
';
}

---

$std:$

实际上可以看做是一个障碍使得被覆盖的位置去更新上下两个点
而且实际上所有有用的只有障碍的端点和起终点
用$set$维护即可

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define fi first
#define bg begin
#define se second
#define poly vector<int>
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=500005;
char xxx;
int dist(int x1,int y1,int x2,int y2){
	return abs(x1-x2)+abs(y1-y2);
}
int n,des;
struct mat{
	int lx,rx,ly,ry;
	friend inline bool operator <(cs mat &a,cs mat &b){
		return a.lx<b.lx;
	}
}p[N];
struct node{
	int x,y,dis;
	node(int a=0,int b=0,int c=0):x(a),y(b),dis(c){}
	friend inline bool operator <(cs node &a,cs node &b){
		return a.y<b.y;
	}
};
set<node> st;
set<node>::iterator itl,itr;
char yyy;
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	n=read(),des=read();
	for(int i=1;i<=n;i++){
		int lx=read(),ly=read(),rx=read(),ry=read();
		if(lx>rx)swap(lx,rx);if(ly>ry)swap(ly,ry);
		p[i].lx=lx,p[i].rx=rx,p[i].ly=ly,p[i].ry=ry;
	}
	st.insert(node(0,0,0));
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		itl=st.lower_bound(node(0,p[i].ly,0));
		itr=st.upper_bound(node(0,p[i].ry,0));
		int up=1e9,dn=1e9;
		while(itl!=itr){
			chemn(up,itl->dis+dist(p[i].lx,p[i].ry,itl->x,itl->y));
			chemn(dn,itl->dis+dist(p[i].lx,p[i].ly,itl->x,itl->y));
			st.erase(itl++);
		}
		st.insert(node(p[i].lx,p[i].ry,up));
		st.insert(node(p[i].lx,p[i].ly,dn));
	}
	int res=1e9;
	for(itl=st.bg();itl!=st.end();++itl)
	chemn(res,itl->dis+dist(des,0,itl->x,itl->y));
	cout<<res;
}

T2：

送分模拟题
结果把其中一个$priority$_$queue$换成$queue$还更慢了

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define poly vector<int>
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
char xxx;
cs int N=100005;
priority_queue<pii,vector<pii>,greater<pii> > all;
priority_queue<int,vector<int>,greater<int> >ret[N];
int n,q,s[N];
namespace Seg{
	int s[N<<2];
	#define lc (u<<1)
	#define rc ((u<<1)|1)
	#define mid ((l+r)>>1)
	void build(int u,int l,int r){
		s[u]=0;
		if(l==r)return;
		build(lc,l,mid),build(rc,mid+1,r);
	}
	inline void pushup(int u){
		s[u]=s[lc]+s[rc];
	}
	inline void update(int u,int l,int r,int p,int k){
		if(l==r){s[u]+=k;return;}
		if(p<=mid)update(lc,l,mid,p,k);
		else update(rc,mid+1,r,p,k);
		pushup(u);
	}
	inline int query(int u,int l,int r,int st,int des){
		if(st<=l&&r<=des)return s[u];
		int res=0;
		if(st<=mid)res+=query(lc,l,mid,st,des);
		if(mid<des)res+=query(rc,mid+1,r,st,des);
		return res;
	}
	inline int find(int u,int l,int r){
		if(l==r)return l;
		if(s[lc])return find(lc,l,mid);
		return find(rc,mid+1,r);
	}
	#undef lc
	#undef rc
	#undef mid
}
char yyy;
inline void solve(){
	n=read();
	for(int i=1;i<=n;i++)s[i]=read();
	Seg::build(1,1,n),q=read();
	while(q--){
		int t=read(),op=read();
		while(all.size()&&all.top().fi<=t){
			int pos=all.top().se;all.pop();
			Seg::update(1,1,n,pos,1),ret[pos].pop();
		}
		if(op==0){
			int id=read();
			ret[id].push(t+s[id]),all.push(pii(t+s[id],id));
		}
		if(op==1){
			if(!Seg::s[1]){cout<<"Yazid is angry."<<'
';}
			else{
				int pos=Seg::find(1,1,n);
				cout<<pos<<'
';
				Seg::update(1,1,n,pos,-1);
			}
		}
		if(op==2){
			int id=read();
			if(Seg::query(1,1,n,id,id)){cout<<"Succeeded!"<<'
',Seg::update(1,1,n,id,-1);}
			else if(ret[id].size()){cout<<ret[id].top()-t<<'
';}
			else cout<<"YJQQQAQ is angry."<<'
';
		}
		if(op==3){
			int l=read(),r=read();
			cout<<Seg::query(1,1,n,l,r)<<'
';
		}
	}
	for(int i=1;i<=n;i++)while(ret[i].size())ret[i].pop();
	while(all.size())all.pop();
}
int main(){
	int T=read();
	while(T--)solve();
	return 0;
}

T3：

只会$n^4/w$暴力
还因为$L$机子又出锅少了$10pts$

考虑把所有剖出来的三角形看做点
如果有相邻边则连一条边

最后可以形成一棵树

那么实际上一条线能碰到的所有三角形就是树上对应的链
所以实际上就是在树上找一个$Y$这样的最长的东西

树形$dp$即可

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define bg begin
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define poly vector<int>
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
#define gc getchar
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=1005;
int n,ee[4];
int ans;
map<pii,vector<int> >line;
map<pii,vector<int> >::iterator it;
vector<int> e[N];
inline void addedge(int u,int v){
	e[u].pb(v),e[v].pb(u);
}
int mxdep[N];
void dfs1(int u,int fa){
	for(int &v:e[u]){
		if(v==fa)continue;
		dfs1(v,u),chemx(mxdep[u],mxdep[v]);
	}
	mxdep[u]++;
}
void dfs2(int u,int fa,int from){
	int mx=0,se=0;
	for(int &v:e[u]){
		if(v==fa)continue;
		if(mxdep[v]>mx)se=mx,mx=mxdep[v];
		else if(mxdep[v]>se)se=mxdep[v];
	}
	chemx(ans,mx+se+from+1);
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(v==fa)continue;
		int res=from;
		if(mxdep[v]==mx)chemx(res,se);
		else chemx(res,mx);
		dfs2(v,u,res+1);
	}
}
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	n=read();
	for(int i=1;i<=n-2;i++){
		ee[1]=read()+1,ee[2]=read()+1,ee[3]=read()+1;
		sort(ee+1,ee+4);
		line[pii(ee[1],ee[2])].pb(i),line[pii(ee[2],ee[3])].pb(i),line[pii(ee[1],ee[3])].pb(i);
	}
	for(it=line.bg();it!=line.end();it++){
		poly now=it->se;
		if(now.size()>1)addedge(now[0],now[1]);
	}
	dfs1(1,0);
	dfs2(1,0,0);
	cout<<ans;
}