csp-s模拟47 Emotional Flutter，Endless Fantasy题解

概述题面：https://www.cnblogs.com/Juve/articles/11558523.html A：Emotional Flutter 如果起点确定，那么我们后面走的点都是固定的，及mod k余数相同 如果路径中有一个%k在黑块里，那么这个起点是不可行的 然后我们可以对于所有黑块，看它限制了哪些余数 最后我们要判断的就是有没有一个长度为s的连续区间，使得它没有被限制 #include

题面：https://www.cnblogs.com/Juve/articles/11558523.html

A：Emotional Flutter

如果起点确定，那么我们后面走的点都是固定的，及mod k余数相同

如果路径中有一个%k在黑块里，那么这个起点是不可行的

然后我们可以对于所有黑块，看它限制了哪些余数

最后我们要判断的就是有没有一个长度为s的连续区间，使得它没有被限制

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#define int long longusing namespace std;const int MAXN=5e5+5;inline int read(){	int x=0;char ch=getchar();	while(ch<‘0‘||ch>‘9‘) ch=getchar();	while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}	return x;}int t,s,k,n,a[MAXN],sum[MAXN];struct node{	int l,r;	frIEnd bool operator < (node x,node y){		return x.l==y.l?x.r<y.r:x.l<y.l;	}}lim[MAXN];int tot=0;signed main(){	//freopen("test.in","r",stdin);	//freopen("vio.out","w",stdout);	t=read();	while(t--){		s=read(),k=read(),n=read();		sum[0]=tot=0;		bool flag=0;		for(int i=1;i<=n;++i){			a[i]=read();			sum[i]=sum[i-1]+a[i];			if(i%2==0) continue;			if(a[i]>=k) flag=1;			int p=(sum[i-1]+1)%k;			int q=sum[i]%k;			if(a[i]-1==q-p){				lim[++tot]=(node){p,q};			}			else{				lim[++tot]=(node){p,k-1};				lim[++tot]=(node){0,q};			}		}		if(flag){			puts("NIE");			continue;		}		sort(lim+1,lim+tot+1);		int mn=0x7fffffffffffff,mx=0;		for(int i=1;i<=tot;++i){			//cout<<lim[i].l<<‘ ‘<<lim[i].r<<endl;			mn=min(mn,lim[i].l);			mx=max(mx,lim[i].r);		}		lim[++tot]=(node){k,k};		flag=0;		int i=1;		int l=0,r=0;		while(i<=tot){			while(i<=tot&&l<=lim[i].l&&lim[i].l<=r){				r=max(r,lim[i].r);				++i;			}			if(lim[i].l-r-1>=s){				flag=1;				break;			}else{				l=lim[i].l,r=lim[i].r;				++i;			}		}		if(mn+k-mx-1>=s) flag=1;		if(s>k) flag=0;		if(flag) puts("TAK");		else puts("NIE");	}	return 0;}

B：Endless Fantasy

线段树合并模板题

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;const int MAXN=4e5+5;inline int read(){	int x=0;char ch=getchar();	while(ch<‘0‘||ch>‘9‘) ch=getchar();	while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}	return x;}int n,m,b[MAXN],ans[MAXN],ID[MAXN];int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0;voID add(int u,int v){	++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;}int root[MAXN],tot=0;struct node{	int ls,rs,mx,ID;}tr[MAXN*40];int update(int k){	if(tr[tr[k].ls].mx>=tr[tr[k].rs].mx) tr[k].mx=tr[tr[k].ls].mx,tr[k].ID=tr[tr[k].ls].ID;	else tr[k].mx=tr[tr[k].rs].mx,tr[k].ID=tr[tr[k].rs].ID;}voID insert(int &k,int l,int r,int pos,int val){	if(!k) k=++tot;	if(l==r){		tr[k].mx=val;		tr[k].ID=pos;		return ;	}	int mID=(l+r)>>1;	if(pos<=mID) insert(tr[k].ls,l,mID,pos,val);	else insert(tr[k].rs,mID+1,r,val);	update(k);}int merge(int x,int y,int r){	if(!x||!y) return x+y;	if(l==r){		tr[x].mx+=tr[y].mx;		return x;	}	int mID=(l+r)>>1;	tr[x].ls=merge(tr[x].ls,tr[y].ls,mID);	tr[x].rs=merge(tr[x].rs,tr[y].rs,r);	update(x);	return x;}voID dfs(int x,int fa){	for(int i=pre[x];i;i=nxt[i]){		int y=to[i];		if(y==fa) continue;		dfs(y,x);		root[x]=merge(root[x],root[y],1,m);	}}int main(){	n=read(),m=read();	for(int i=1,u,v;i<n;++i){		u=read(),v=read();		add(u,v),add(v,u);	}	for(int i=1;i<=n;++i){		scanf("%d%d",&a[i],&b[i]);		insert(root[i],a[i],b[i]);	}	dfs(1,0);	for(int i=1;i<=n;++i){		printf("%d %d\n",tr[root[i]].ID,tr[root[i]].mx);	}	return 0;}

总结

以上是内存溢出为你收集整理的csp-s模拟47 Emotional Flutter，Endless Fantasy题解全部内容，希望文章能够帮你解决csp-s模拟47 Emotional Flutter，Endless Fantasy题解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。