「联赛模拟测试30 」题解

T1.maze

沙雕题，不会建议重学最短路

提示：由于是稠密数据加强会卡掉afps

T2.bird

考试时受到贪婪大陆（查询一段区间内不同区间的个数）的影响，使劲用起点终点去推，用线段树维护，最后也没能搞出来

考虑暴力，先运用初中物理知识把鸟动化成人在坐标轴上走

定义状态 (f_i) 表示当前位置在 (i) ，且在 (i) 开枪的最大收获

转移： (f_i=max(f_j+b_i-c_{i,j})) (b_i) 表示 (i) 上空的鸟的个数， (c_{i,j}) 表示 (i,j) 共有的线段个数

炡解是线段树，动态维护最大值和共有鸟数，区间修改，区间查最大， (O(nlogn))

/* cinput
4 5
-1 1
2 4
5 9
6 8
*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=8e5+5,maxe=1e6+5,INF=0x3f3f3f3f;
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int n,m,maxr,ans,f[maxn],b[maxn];
struct Node{
	int l,r;
}a[maxn];
bool cmp1(Node A,Node B){return A.l==B.l?A.r<B.r:A.l<B.l;}
struct Segment_Tree{
	int l,r,w,lazy;
}tree[maxn*4];
vector<int> g1[maxn],g2[maxn];
#define mid ((l+r)>>1)
void pushup(int rt){tree[rt].w=max(tree[rt*2].w,tree[rt*2+1].w);}
void Build(int rt,int l,int r){
	tree[rt].l=l,tree[rt].r=r;
	if(l==r)return;
	Build(rt*2,l,mid);Build(rt*2+1,mid+1,r);
}
void update(int rt,int w){
	tree[rt].w+=w,tree[rt].lazy+=w;
}
void pushdown(int rt){
	if(!tree[rt].lazy)return;
	update(rt*2,tree[rt].lazy);update(rt*2+1,tree[rt].lazy);
	tree[rt].lazy=0;
}
void modify(int rt,int s,int t,int w){
	int l=tree[rt].l,r=tree[rt].r;
	if(s<=l&&r<=t)return update(rt,w),void();
	pushdown(rt);
	if(s<=mid)modify(rt*2,s,t,w);
	if(mid<t)modify(rt*2+1,s,t,w);
	pushup(rt);
}
int query(int rt,int s,int t){
	int l=tree[rt].l,r=tree[rt].r,sum=0;
	//if(t>s)return 0;
	if(s<=l&&r<=t)return tree[rt].w;
	pushdown(rt);
	if(s<=mid)sum=query(rt*2,s,t);
	if(mid<t)sum=max(sum,query(rt*2+1,s,t));
	return sum;
}
int main(){
	freopen("bird.in","r",stdin);
	freopen("bird.out","w",stdout);
	n=read(),m=read();
	for(register int i=1;i<=n;i++){
		a[i].l=max(read()+1,1),a[i].r=read()+1;
		if(a[i].r<1)continue;
		b[a[i].l]++;b[a[i].r+1]--;
		g1[a[i].l].push_back(a[i].r);
		g2[a[i].r].push_back(a[i].l);
		maxr=max(maxr,a[i].r);
	}
	for(register int i=1;i<=maxr;i++)b[i]+=b[i-1];
	Build(1,1,maxr);
	for(register int i=1;i<=maxr;i++){
		for(register int j=0;j<g1[i].size();j++)modify(1,i,g1[i][j],-1);
		int x=b[i];
		if(i-m>=1)x+=query(1,1,i-m);
		//cout<<i<<" "<<x<<" "<<i-m<<" "<<b[i]<<" "<<query(1,1,i-m)<<" "<<g1[i].size()<<" "<<g2[i].size()<<endl;
		ans=max(ans,x);
		modify(1,i,i,x);
		for(register int j=0;j<g2[i].size();j++)modify(1,g2[i][j],i,1);
	}
	printf("%d
",ans);
	return 0;
}

T3.stone

貌似是神仙DP，没改

T4.椎

线段树维护单调栈，咕了

RUA~