CSP 模拟 49

A 传送 (teleport)

暴力连边一定不行，寻找最优的连边。先说下我的连法，手玩一下发现，如果对横坐标排序，点 \(u\) 只连下一个横坐标中与它纵坐标最近的即可，这样对于下一个横坐标的点，\(u\) 的连法都是最优的，纵坐标同理。
题解连法也一样，考虑本质就是在一维上走，所以两维排序后都连一下就行。赛时一开始就推了横坐标，发现假了被硬控一小时。

B 排列 (permutation)

只跟 \(k\) 的倍数有关，设 \(f_{i,s,j}\) 表示到 \(i\) 已经有的 \(k\) 的倍数的集合为 \(s\)，当前是 \(j\)，转移直接观察 gcd 即可，时间复杂度 \(\mathcal{O}(10n2^{10})\)。
还能直接数学做，其他数无所谓，只考虑 \(k\) 的倍数的排列方式，枚举一下全排列，然后其他看着填即可。

C 战场模拟器

首先考虑没有护盾和保证不死亡怎么做，线段树维护最小值及数量即可。发现死亡和护盾只有 \(\mathcal{O}(n)\) 个，总的影响是 \(\mathcal{O}(n\log n)\) 的，所以每次暴力去找死亡和护盾更新即可。赛时就是没有想到这个性质，只有 32pts。

#include<bits/stdc++.h>
#define FA std::cout<<"take easy\n"
#define int long long
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10,mod=998244353,inf=1e18;
int n,Q,a[N];
inline void Min(int &x,int y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void W(int &x,int y){x=(x+y)%mod;}
inline pii operator+(pii a,pii b){
	if(a.fi<0||b.fi<0){
		if(a.fi<0&&b.fi<0){return {inf,0};}
		if(a.fi<0)return b;
		else return a;
	}
	if(a.fi==b.fi){return {a.fi,a.se+b.se};}
	return std::min(a,b);
}
struct TREE{pii ans;int dead,grd,tag;}t[N<<2];
inline void update(int p){t[p].ans=t[ls].ans+t[rs].ans;t[p].dead=t[ls].dead+t[rs].dead;t[p].grd=t[ls].grd+t[rs].grd;}
inline void pushdown(int p){int x=t[p].tag;t[ls].tag+=x;t[rs].tag+=x;t[ls].ans.fi+=x,t[rs].ans.fi+=x;return t[p].tag=0,void();}
inline void build(int p,int l,int r){
	if(l==r){t[p].ans={a[l],1};return;}
	int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);update(p);
}
inline void protect(int p,int l,int r,int pos){
	if(l==r){if(!t[p].dead)t[p].grd++;return;}
	int mid=l+r>>1;pushdown(p);
	if(pos<=mid)protect(ls,l,mid,pos);else protect(rs,mid+1,r,pos);update(p);
}
inline void change(int p,int l,int r,int L,int R,int x);
inline void ATC(int p,int l,int r,int x);
inline void ATC(int p,int l,int r,int x){
	if(l==r){
		if(t[p].grd){t[p].grd--;}
		else t[p].ans.fi+=x;
		if(t[p].ans.fi<0)t[p].ans={inf,0},t[p].dead=1;
		return;
	}
	int mid=l+r>>1;pushdown(p);
	if(t[ls].grd||t[ls].ans.fi+x<0)ATC(ls,l,mid,x);else change(ls,l,mid,l,mid,x);
	if(t[rs].grd||t[rs].ans.fi+x<0)ATC(rs,mid+1,r,x);else change(rs,mid+1,r,mid+1,r,x);
	update(p);
}
inline void change(int p,int l,int r,int L,int R,int x){
	if(l>=L&&r<=R){
		if(x>=0||(!t[p].grd&&t[p].ans.fi+x>=0)){
			t[p].tag+=x,t[p].ans.fi+=x;return;
		}
		ATC(p,l,r,x);return;
	}
	int mid=l+r>>1;pushdown(p);
	if(L<=mid)change(ls,l,mid,L,R,x);if(R>mid)change(rs,mid+1,r,L,R,x);
	update(p);
}
inline int querydead(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R){return t[p].dead;}
	int mid=l+r>>1,res=0;pushdown(p);
	if(L<=mid)res+=querydead(ls,l,mid,L,R);
	if(R>mid)res+=querydead(rs,mid+1,r,L,R);
	return res;
}
inline pii query(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R){return t[p].ans;}
	int mid=l+r>>1,vis=0;pii res;pushdown(p);
	if(L<=mid)vis=1,res=query(ls,l,mid,L,R);
	if(R>mid){
		auto it=query(rs,mid+1,r,L,R);
		if(vis)res=res+it;else res=it;
	}
	return res;
}
signed main(){
    freopen("simulator.in","r",stdin);freopen("simulator.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read();for(int i=1;i<=n;++i)a[i]=read();build(1,1,n);
    Q=read();for(int i=1;i<=Q;++i){
    	int op=read(),l=read(),r,x;
    	if(op==1)r=read(),x=read(),change(1,1,n,l,r,-x);
   		if(op==2)r=read(),x=read(),change(1,1,n,l,r,x);
   		if(op==3)protect(1,1,n,l);
   		if(op==4)std::cout<<querydead(1,1,n,l,read())<<'\n';
   		if(op==5){
   			auto it=query(1,1,n,l,read());
   			std::cout<<(!it.fi?it.se:0)<<'\n';
   		}
    }
}

点亮 (light)

不会