191024省選試験問題解

T 1:n個の交差しない矩形の障害があって、原点からある目標点までの最短ルートを求めて、目標点はx軸の上で明らかに矩形の右端点は役に立たないので、私達は左を保留して明らかに左へ歩かないことができて、dpはすぐn 2 n^2 n 2のので、走査線で少し最適化します

#include
#define pb push_back
#define ll long long 
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=5e5+5,INF=1e9;
inline int D(int x1,int y1,int x2,int y2){return abs(x1-x2)+abs(y1-y2);}
int n,aim;
struct sqr{
	int lx,rx,ly,ry;
	inline bool operator < (const sqr &rhs)const{return lx<rhs.lx;}
}p[N];
struct info{
	int x,y,dis;
	info(){}
	info(int _x,int _y,int _dis):x(_x),y(_y),dis(_dis){}
	inline bool operator < (const info &rhs)const{return y<rhs.y;}
};
set<info>s;
int main(){
	n=read();aim=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;
	}
	s.insert(info(0,0,0));
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		set<info>::iterator l=s.lower_bound(info(0,p[i].ly,0));
		set<info>::iterator r=s.upper_bound(info(0,p[i].ry,0));
		int L=INF,R=INF;
		while(l!=r){
			L=min(L,l->dis+D(p[i].lx,p[i].ry,l->x,l->y));
			R=min(R,l->dis+D(p[i].lx,p[i].ly,l->x,l->y));
			s.erase(l++);
		}
		s.insert(info(p[i].lx,p[i].ry,L));
		s.insert(info(p[i].lx,p[i].ly,R));
	}
	int ans=INF;
	for(set<info>::iterator it=s.begin();it!=s.end();it++) ans=min(ans,it->dis+D(aim,0,it->x,it->y));
	cout<<ans;
	return 0;
}

T 2:LOJ火鍋の宴優先行列のメンテナンスが熟していないので、線分の木のメンテナンスが熟していて、シミュレーションが終わりました.

#include
#define pii pair
#define pb push_back
#define mp make_pair
#define ll long long
#define fi first
#define se second
#define db double
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
struct info{
	int x,id;
	info(){}
	info(int _x,int _id):x(_x),id(_id){}
	inline bool operator > (const info &rhs)const{return x>rhs.x;}
};
int n;
const int N=1e5+5;
namespace segtree{
	struct seg{int l,r,sum;}tr[N<<2];
	#define ls tr[k].l
	#define rs tr[k].r
	#define mid (ls+rs>>1)
	inline void build(int k,int l,int r){
		ls=l;rs=r;tr[k].sum=0;
		if(l==r) return;
		build(k<<1,l,mid);build(k<<1|1,mid+1,r);
	}
	inline void modify(int k,int pos){			//op 0 
		++tr[k].sum;
		if(ls==rs) return;
		if(pos<=mid) modify(k<<1,pos);
		else modify(k<<1|1,pos);
	}
	inline int query_min(int k){			 	//op 1 
		if(!tr[k].sum) return 0;
		--tr[k].sum;
		if(ls==rs) return ls;
		if(tr[k<<1].sum) return query_min(k<<1);
		else return query_min(k<<1|1);
	}
	inline int query_pos(int k,int pos){  		//op 2
		if(!tr[k].sum) return 0;
		if(ls==rs){--tr[k].sum;return 1;}
		int res=0;
		if(pos<=mid) res=query_pos(k<<1,pos);
		else res=query_pos(k<<1|1,pos);
		tr[k].sum-=res;return res;
	}
	inline int query_seq(int k,int ql,int qr){	//op 3
		if(ql>rs || qr<ls) return 0;
		if(ql<=ls && rs<=qr) return tr[k].sum;
		if(qr<=mid) return query_seq(k<<1,ql,qr);
		else if(ql>mid) return query_seq(k<<1|1,ql,qr);
		else return query_seq(k<<1,ql,mid)+query_seq(k<<1|1,mid+1,qr);
	} 
}
using namespace segtree;
int w[N];
priority_queue<info,vector<info>,greater<info> >q;
deque<int>son[N];
inline void file(){freopen("b.in","r",stdin);freopen("b.out","w",stdout);}
int main(){
	int t=read();
	while(t--){
		n=read();build(1,1,n);
		for(int i=1;i<=n;i++) w[i]=read(),son[i].clear();
		while(!q.empty()) q.pop();
		int Q=read();
		while(Q--){
			int t=read(),op=read();
			while(q.size() && q.top().x<=t){
				int y=q.top().id;modify(1,y);
				son[y].pop_front();q.pop();
			}
			if(op==0){
				int x=read();
				son[x].push_back(t+w[x]);
				q.push(info(t+w[x],x));
			}
			else if(op==1){
				if(!tr[1].sum) puts("Yazid is angry.");
				else cout<<query_min(1)<<"
";
			}
			else if(op==2){
	            int x=read();
				if(query_pos(1,x)) puts("Succeeded!");
                else if(son[x].size()) cout<<son[x].front()-t<<"
";
                else puts("YJQQQAQ is angry.");
            }
            else{
				int l=read(),r=read();
				cout<<query_seq(1,l,r)<<"
";
			}
		}
	}
	return 0;
}

T 3:多角形の三角断面を与えて、多角形の頂点からなる三角形を求めてそれができるだけ多い三角形と交差するようにして、最大交差数を求めて1つの対偶図(最も外のあの平面を含まない)を構築して、きっと1本の木で、それから木の上で1本の2つの葉を接続する経路は1種の2つの頂点の交差する三角形の方案に対応して、数が経路長であれば三角形を探して3つの経路で、木の形dpでいいです.
Code:

#include
#define pii pair
#define mp make_pair
#define pb push_back
#define ll long long 
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=1e5+5;
int vis[N<<1],head[N<<1],nxt[N<<1],tot=0;
inline void add(int x,int y){vis[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
map<pii,int>m;
int n,cnt=0,ans=0;
int h[N];
void dfs1(int v,int fa){
	for(int i=head[v];i;i=nxt[i]){
		int y=vis[i];
		if(y==fa) continue;
		dfs1(y,v);
		h[v]=max(h[v],h[y]);
	}
	++h[v];
}
void dfs2(int v,int fa,int val){
	int dp[2];dp[0]=dp[1]=0;
	for(int i=head[v];i;i=nxt[i]){
		int y=vis[i];
		if(y==fa) continue;
		if(h[y]>dp[0]) dp[1]=dp[0],dp[0]=h[y];
		else if(h[y]>dp[1]) dp[1]=h[y];
	}
	ans=max(ans,val+1);
	ans=max(ans,dp[0]+val+1);
	ans=max(ans,dp[0]+dp[1]+val+1);
	for(int i=head[v];i;i=nxt[i]){
		int y=vis[i];
		if(y==fa) continue;
		if(h[y]!=dp[0]) dfs2(y,v,max(val,dp[0])+1);
		else dfs2(y,v,max(val,dp[1])+1);
	}
}
int main(){
	n=read();
	for(int i=0;i<n-2;i++){
		static int seq[3];
		for(int j=0;j<3;j++) seq[j]=read();
		sort(seq,seq+3);
		for(int j=0;j<2;j++)
			for(int k=j+1;k<3;k++) if(m.count(mp(seq[j],seq[k]))){
				add(cnt,m[mp(seq[j],seq[k])]);
				add(m[mp(seq[j],seq[k])],cnt);
			}
		for(int j=0;j<2;j++)
			for(int k=j+1;k<3;k++)
				m[mp(seq[j],seq[k])]=cnt;
		++cnt;
	}
	dfs1(0,-1);dfs2(0,-1,0);
	cout<<ans;
	return 0;
}