CSP-S 模拟赛 35

rnk14，\(45+45+15+18=123\)。

T1 送花

愚蠢题。看到区间想到线段树，预处理出每个位置的颜色上一次出现的位置，记为 \(\mathit{las}_i\)。从左到右扫右端点，给 \([\max(1,\mathit{las}_{\mathit{las}_i}),\mathit{las}_i]\) 减去 \(d(c_i)\)，给 \((\mathit{las}_i,i]\) 加上 \(d(c_i)\)。最后用全局最大值更新答案。搓一个区间加、维护全局最大值的线段树就可解决。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define lp p<<1
#define rp p<<1|1
#define mid ((s+t)>>1)
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=1e6+5;
int n,m,c[MAXN],d[8005];
ll ans=LONG_LONG_MIN;
vector<int>v[8005];
int las[MAXN];
struct SegTree{
	ll c,lazy;
}st[MAXN<<2];
void pushdown(int p){
	if(!st[p].lazy)return;
	st[lp].c+=st[p].lazy;
	st[lp].lazy+=st[p].lazy;
	st[rp].c+=st[p].lazy;
	st[rp].lazy+=st[p].lazy;
	st[p].lazy=0;
}
void mdf(int l,int r,ll k,int s=1,int t=n,int p=1){
	if(l<=s&&t<=r)return st[p].c+=k,st[p].lazy+=k,void();
	pushdown(p);
	if(l<=mid)mdf(l,r,k,s,mid,lp);
	if(mid<r)mdf(l,r,k,mid+1,t,rp);
	st[p].c=max(st[lp].c,st[rp].c);
}

int main(){
	freopen("flower.in","r",stdin);
	freopen("flower.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;++i)c[i]=read();
	for(int i=1;i<=m;++i)d[i]=read();
	for(int i=1;i<=n;++i)v[c[i]].emplace_back(i);
	for(int i=1;i<=m;++i)
		for(int j=1;j<(int)v[i].size();++j)
			las[v[i][j]]=v[i][j-1];
	for(int i=1;i<=n;++i){
		if(las[i])mdf(max(1,las[las[i]]),las[i],-d[c[i]]);
		mdf(las[i]+1,i,d[c[i]]);
		ans=max(ans,st[1].c);
	}
	return write(ans),fw,0;
}

T2 星空

新鲜的计算几何题。（？

题目给定的这个 “直接距离” 特别的 bug，发现这样一来，所有位于直线 \((\forall b)~y=\pm x+b\) 的点的直接距离都是一样的。考虑将坐标轴逆时针旋转 45 度，这样原来的坐标 \((x,y)\) 会变成 \((x-y,x+y)\)，且所有横/纵坐标相等的点的直接距离都相等。

处理出距离为零的那些点用并查集合并，然后将点分别按照 \(x,y\) 排序并找到最近点对，这就是第一问的答案。对于第二问，将所有的最近点加到一个数组中去重，最后就是其中任两者的并查集连通块大小乘积。

#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;

char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))ch=='-'&&(f=-1),ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
template<typename T>
void write(T x,char sf='\n'){
	if(x<0)putchar('-'),x=~x+1;
	int top=0;
	do str[top++]=x%10,x/=10;while(x);
	while(top)putchar(str[--top]+48);
	if(sf^'#')putchar(sf);
}
constexpr int MAXN=1e5+5;
int n;
struct Star{
	int x,y,id;
}a[MAXN];
int f[MAXN],siz[MAXN];
int find(int x){
	if(f[x]^x)f[x]=find(f[x]);
	return f[x];
}
void combine(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy)return;
	if(siz[fx]<siz[fy])swap(fx,fy);
	f[fy]=fx;
	siz[fx]+=siz[fy];
}
vector<pair<int,int>>edge;

int main(){
	freopen("sky.in","r",stdin);
	freopen("sky.out","w",stdout);
	n=read();
	for(int i=1,xx,yy;i<=n;++i){
		xx=read(),yy=read();
		a[i]={xx-yy,xx+yy,i};
		f[i]=i,siz[i]=1;
	}
	sort(a+1,a+n+1,[&](Star x,Star y){
		return x.x^y.x?x.x<y.x:x.y<y.y;
	});
	int ans=INT_MAX,ans2=0;
	for(int i=1,j;i<=n;++i){
		j=i+1;
		while(j<=n&&(a[i].x==a[j].x||a[i].y==a[j].y)){
			combine(a[i].id,a[j].id);
			++j;
		}
		if(j<=n)ans=min(ans,a[j].x-a[i].x);
	}
	sort(a+1,a+n+1,[&](Star x,Star y){
		return x.y^y.y?x.y<y.y:x.x<y.x;
	});
	for(int i=1,j;i<=n;++i){
		j=i+1;
		while(j<=n&&(a[i].x==a[j].x||a[i].y==a[j].y)){
			combine(a[i].id,a[j].id);
			++j;
		}
		if(j<=n)ans=min(ans,a[j].y-a[i].y);
	}
	for(int i=1,j;i<=n;++i){
		j=i+1;
		while(j<=n&&(a[i].x==a[j].x||a[i].y==a[j].y))++j;
		if(j<=n&&a[j].y-a[i].y==ans){
			int fx=find(a[i].id),fy=find(a[j].id);
			if(fx>fy)swap(fx,fy);
			edge.emplace_back(fx,fy);
		}
	}
	sort(a+1,a+n+1,[&](Star x,Star y){
		return x.x^y.x?x.x<y.x:x.y<y.y;
	});
	for(int i=1,j;i<=n;++i){
		j=i+1;
		while(j<=n&&(a[i].x==a[j].x||a[i].y==a[j].y))++j;
		if(j<=n&&a[j].x-a[i].x==ans){
			int fx=find(a[i].id),fy=find(a[j].id);
			if(fx>fy)swap(fx,fy);
			edge.emplace_back(fx,fy);
		}
	}
	sort(edge.begin(),edge.end());
	edge.erase(unique(edge.begin(),edge.end()),edge.end());
	for(auto v:edge)ans2+=siz[v.first]*siz[v.second];
	write(ans),write(ans2);
	return fw,0;
}

T3 零一串

双端队列维护 \(0\) 和 \(1\) 的位置。

对于每一个 \(1\) 处理一个长度为 \(T\) 的零一串，每一个 \(1\) 代表这个时刻能不能左移。

考虑如果第 \(i\) 个 \(1\) 可以在 \(j\) 的时刻左移，如果第 \(i+1\) 个位置是紧邻的，那么它只能在 \(j+1\) 的时刻左移。反之如果不紧邻，则后面有几个 \(0\) 可以移几次。神秘差分维护。

#include<bits/stdc++.h>
#define int long long
using namespace std;

constexpr int MAXN=5e6+5,MOD=998244353;
int T,n,pw[MAXN]={1};
string s;
int pos[MAXN],tot;
int cf[MAXN],dis[MAXN],sum[MAXN],ans[MAXN],ans2;
void add(int&x,int y){
	x=x+y>=MOD?x+y-MOD:x+y;
}

signed main(){
	freopen("chuan.in","r",stdin);
	freopen("chuan.out","w",stdout);
	cin>>T>>s;
	for(int i=1;i<=T;++i)pw[i]=pw[i-1]*233%MOD;
	n=s.size();
	s=' '+s;
	for(int i=1;i<=n;++i)if(s[i]=='1')pos[++tot]=i;
	deque<int>q(T);
	iota(q.begin(),q.end(),1);
	for(int i=1,all=0;i<=tot;++i){
		++all;
		if(!q.empty()&&q.back()+all>T)q.pop_back();
		q.emplace_front(1-all);
		for(int j=1;!q.empty()&&j<=pos[i]-pos[i-1]-1;++j){
			++cf[q.front()+all];
			--cf[min(tot-i+q.front()+all+1,T+1)];
			q.pop_front();
		}
		dis[i]=T-q.size();
		ans[pos[i]-dis[i]]=1;
	}
	int nxd=0,num=0;
	for(int i=1;i<=n;++i)
		if(s[i]=='1')++num;
		else add(nxd,num);
	ans2=nxd;
	for(int i=1;i<=T;++i){
		sum[i]=(sum[i-1]+cf[i])%MOD;
		add(nxd,sum[i]);
		ans2^=pw[i]*nxd%MOD;
	}
	for(int i=1;i<=n;++i)cout<<ans[i];
	cout<<'\n'<<ans2<<'\n';
	return 0;
}

T4 Revive

唐。