首页 > 其他分享 >CSP15

CSP15

时间:2024-08-07 21:29:27浏览次数:12  
标签:return int cin len CSP15 ull define

T1

image
唐了

点击查看代码
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N =1E6+6;const ull B=233;
int len;ull h[N],fh[N],p[N];
ull get(int l,int r)
{
	return h[r]-h[l-1]*p[r-l+1]; 
}
ull fget(int l,int r)
{
	int tl=len-r+1;int tr=len-l+1;
	return fh[tr]-fh[tl-1]*p[tr-tl+1];
}
bool check(int i)
{
	ull l=fget(1,max(1,i-1));
	if(2*i-1>len)
	{
		if(2*i-len>i-1||i+1>len)return 1;
		l=fget(2*i-len,i-1);
		ull r=get(i+1,len);
		// cout<<2*i-len<<" "<<i-1<<" "<<i+1<<" "<<len<<endl;
		
	//	cout<<l<<" "<<r<<endl;
		return l==r;
	}else
	{
		if(i==1)return 1;
		ull r=get(min(i+1,2*i-1),2*i-1);
		// cout<<1<<" "<<max(1,i-1)<<" "<<min(i+1,2*i-1)<<" "<<2*i-1<<endl;
		// cout<<l<<" "<<r<<endl;
		if(l==r)return check(2*i-1);
		else return 0;	
	}
}
int main()
{
	int T;
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>T;
	string s;p[0]=1;
	for(int i=1;i<=1e6;i++)p[i]=p[i-1]*B;
	while(T--)
	{
		cin>>s;
		len=s.size();
		for(int i=1;i<=len;i++)
		{
			h[i]=h[i-1]*B+s[i-1];
		}
		if(len==1)
		{
			cout<<1<<endl;
			continue;
		}
		for(int i=1;i<=len;i++)
		{
			fh[i]=fh[i-1]*B+s[len-i];
			// cout<<fh[i]<<endl;
		} 
		// cout<<fget(1,1)<<" "<<get(1,1)<<endl;
		for(int i=2;i<=len;i++)
		{
			if(check(i))
			{
				cout<<i<<" ";
			}
		}
		// cout<<len;
		cout<<endl;
	}
	return 0;
}

其实还能优化,这个复杂度类似倍增啊
可是到这循环可以做到\(O(N)\)

点击查看代码
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N =1E6+6;const ull B=233;
int len;ull h[N],fh[N],p[N],is[N];
ull get(int l,int r)
{
	return h[r]-h[l-1]*p[r-l+1]; 
}
ull fget(int l,int r)
{
	int tl=len-r+1;int tr=len-l+1;
	return fh[tr]-fh[tl-1]*p[tr-tl+1];
}
bool check(int i)
{
	ull l=fget(1,max(1,i-1));
	if(2*i-1>len)
	{
		if(2*i-len>i-1||i+1>len)return 1;
		l=fget(2*i-len,i-1);
		ull r=get(i+1,len);
		return l==r;
	}else
	{
		if(i==1)return 1;
		ull r=get(min(i+1,2*i-1),2*i-1);
		if(l==r&&is[2*i-1])return 1;
		else return 0;	
	}
}
int main()
{
	int T;
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>T;
	string s;p[0]=1;
	for(int i=1;i<=1e6;i++)p[i]=p[i-1]*B;
	while(T--)
	{
		cin>>s;
		
		len=s.size();
		for(int i=1;i<=len;i++)
		{
			is[i]=0;
			h[i]=h[i-1]*B+s[i-1];
			fh[i]=fh[i-1]*B+s[len-i];
		}
		if(len==1)
		{
			cout<<1<<endl;
			continue;
		}
		is[len]=1;
		for(int i=len-1;i>=1;i--)
		{
			if(check(i))is[i]=1;
		}
		for(int i=2;i<=len;i++)
		{
			if(is[i])cout<<i<<" ";
		}
		// cout<<len;
		cout<<endl;
	}
	return 0;
}

T2

image
考虑\(a[1]=1和a[n]=n\)与\(a[1]\ne 1或a[n]\ne n\)以及\(a[i]=i\)的情况
其中\(a[n]=1和a[1]=n\)情况特殊,必须操作\(3\)次

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
#define endl '\n'
#define pb push_back
using namespace std;
const int N = 2e5+5;
int n;
ll a[N];
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		bool ok=1;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			if(a[i]!=i)ok=0;
		}
		if(ok)cout<<0<<endl;
		else if(a[1]==1||a[n]==n)cout<<1<<endl;
		else 
		{
			if(a[n]!=1||a[1]!=n)
			{
				ll mx=0;bool ff=0;
				for(int i=1;i<=n;i++)
				{
					if(a[i]==i)
					{	
						if(mx<a[i])
						{	
							ff=1;break;
						}
					}
					mx=max(mx,a[i]);
				}
				if(ff)cout<<1<<endl;
				else cout<<2<<endl;

			}
			else
			{
				cout<<3<<endl;
			}
		}

	}
	return 0;
}
/*
4
5
2 1 3 5 4
3
1 2 3
7
3 2 1 7 5 6 4
6
1 2 3 4 5 6
*/

T3

回滚莫队,不过\(add\)函数复杂度为\(O(R-L+1)\)的,复杂度太高了

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
#define endl '\n'
#define pb push_back
using namespace std;
const int N = 1e5+5,mod=1e9+7;
int n,m,sq,s[N],st[320],ed[320],B,ans[N];
struct qu
{
	int l,r,id,bl;
}q[N];
struct ST
{
	int mi[20][N],mx[20][N];
	void init()
	{
		for(int i=1;i<=n;i++)
		{
			mi[0][i]=mx[0][i]=s[i];
		}
		mi[0][0]=mi[0][n+1]=1e9;
		mx[0][0]=mx[0][n+1]=-1e9;
		for(int j=1;j<=18;j++)
		{
			for(int i=1;i+(1<<j)-1<=n;i++)
			{
				mi[j][i]=min(mi[j-1][i],mi[j-1][i+(1<<j-1)]);
				mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<j-1)]);
			}
		}
	}
	ll qmx(int l,int r)
	{
		// int ans=0;
		// for(int i=l;i<=r;i++)ans=max(ans,s[i]);
		// return ans;
		if(l>r)swap(l,r);
		int k=__lg(r-l+1);
		return max(mx[k][l],mx[k][r-(1<<k)+1]);
	}
	ll qmi(int l,int r)
	{
		// int ans=1e9;
		// for(int i=l;i<=r;i++)ans=min(ans,s[i]);
		// return ans;
		if(l>r)swap(l,r);
		int k=__lg(r-l+1);
		return min(mi[k][l],mi[k][r-(1<<k)+1]);
	}
}rmq;
bool cmp(qu a,qu b)
{
	if(a.bl==b.bl)return a.r<b.r;
	return a.l<b.l;
}
ll force(int l,int r)
{
	ll ans=0;
	for(int i=l;i<=r;i++)
	{
		for(int j=i;j<=r;j++)
		{
			// cout<<"***"<<i<<" "<<j<<endl;
			// cout<<rmq.qmi(i,j)<<" "<<rmq.qmx(i,j)<<endl;
			ans=(ans+rmq.qmi(i,j)*rmq.qmx(i,j)%mod)%mod;
		}
	}
	return ans;
}
ll res;
int L=0,R=0;
void add(int x,bool lef)
{
	if(lef)
	{
		for(int i=L;i<=R;i++)
		{
			res=(res+rmq.qmi(L,i)*rmq.qmx(L,i)%mod)%mod;
		}
	}else 
	{
		for(int i=L;i<=R;i++)
		{
			res=(res+rmq.qmi(i,R)*rmq.qmx(i,R)%mod)%mod;
		}		
	}
}
void solve()
{
	
	for(int i=1,j=1;i<=B;i++)
	{
		R=ed[i];L=ed[i]+1;
		res=0;
		while(i==q[j].bl)
		{
			if(q[j].r-q[j].l<=sq)
			{
				ans[q[j].id]=force(q[j].l,q[j].r);
				j++;
				continue;
			}
			L=ed[i]+1;
			while(R<q[j].r)
			{
				R++;
				add(R,0);
			}
			ll tmp=res;
			while(L>q[j].l)add(--L,1);
			ans[q[j].id]=res;
			res=tmp;
			j++;
		}
	}	
}
signed main()
{
	speed();
	// freopen("sequence2.in","r",stdin);
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
	}
	rmq.init();
	sq=sqrt(n);B=n/sq;
	// sq=1e9;
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r;q[i].id=i;
		q[i].bl=(q[i].l-1)/sq+1;
		// cout<<solve(L,R)<<endl;
	}
	for(int i=1;i<=B;i++)
	{
		st[i]=ed[i-1]+1;ed[i]=st[i]+sq-1;
	}
	if(ed[B]<n)
	{
		B++;
		st[B]=ed[B-1]+1;ed[B]=n;
	}
	sort(q+1,q+1+m,cmp);
	solve();
	for(int i=1;i<=m;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}
/*
5 2
2 4 1 5 3
1 4
3 5
*/

T4 P5443 [APIO2019] 桥梁

image
暴力分,注意细节,MD本来能拿\(29\)结果爆零了

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
#define endl '\n'
#define pb push_back
using namespace std;
const int N = 5e4+5,M=1e5+5;
int n,m,fa[N];
vector <pii> edge[N];
struct node
{
	int u,v,w,id;

}br[M];
bool cmp(node a,node b)
{
	return a.w>b.w;
}
bool cmp2(node a,node b)
{
	return a.id<b.id;
}
bool cmp3(node a,node b)
{
	return a.u<b.u;
}
inline void add(int u,int v,int w)
{
	edge[u].pb({v,w});edge[v].pb({u,w});
}
inline int find(int x)
{
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
inline void kruskal()
{
	for(int i=1;i<=n;i++)fa[i]=i,edge[i].clear();
	int cnt=0;
	sort(br+1,br+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		if(cnt==n-1)break;
		int fu=find(br[i].u),fv=find(br[i].v);

		if(fu!=fv)
		{
			fa[fu]=fv;cnt++;
			// cout<<br[i].u<<" "<<br[i].v<<" "<<br[i].w<<endl;
			add(br[i].u,br[i].v,br[i].w);
		}
	}
	sort(br+1,br+1+m,cmp2);
}
bool vis[N];
ll ans=0;
inline void dfs(int u,int lim)
{
	vis[u]=1;
	// cout<<"**"<<u<<endl;
	for(auto [to,w]:edge[u])
	{
		// cout<<to<<" "<<w<<" "<<lim<<endl;
		if(!vis[to]&&w>=lim)
		{
			
			dfs(to,lim);
		}
	}
}
struct Tree
{
	int l,r,mi;
}st[N*4];
inline void pushup(int rt)
{
	st[rt].mi=min(st[lid].mi,st[rid].mi);
}
inline void bt(int rt,int l,int r)
{
	st[rt].l=l;st[rt].r=r;
	if(l==r)
	{
		st[rt].mi=br[l].w;
		return;
	}
	int mid=(l+r)>>1;
	bt(lid,l,mid);bt(rid,mid+1,r);
	pushup(rt);
}
inline void update(int rt,int l,int r,int val)
{
	if(l<=st[rt].l&&st[rt].r<=r)
	{
		st[rt].mi=val;
		return;
	}
	int mid=(st[rt].l+st[rt].r)>>1;
	if(l<=mid)update(lid,l,r,val);
	if(r>mid)update(rid,l,r,val);
	pushup(rt);
}
inline int query(int rt,int l,int r)
{
	if(l>r)return 0;
	if(l<=st[rt].l&&st[rt].r<=r)
	{
		return st[rt].mi;
	}
	int mid=(st[rt].l+st[rt].r)>>1;
	int ans=1e9;
	if(l<=mid)ans=min(ans,query(lid,l,r));
	if(r>mid)ans=min(ans,query(rid,l,r));
	return ans;
}
int main()
{
	speed();
	// freopen("bridge1.in","r",stdin);
	// freopen("in.in","r",stdin);
	// freopen("out1.out","w",stdout);
	cin>>n>>m;
	int u,v,w;
	bool lian=1;bool ercha=1;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		if(abs(u-v)!=1)lian=0;
		if(u!=(i+1)/2||v!=i+1)ercha=0;
		br[i]={u,v,w,i};
	}int q,op;
	// lian=0;
	// cout<<"****"<<ercha<<endl;
	if(m&&!lian&&!ercha)kruskal();
	else if(lian&&!ercha)
	{
		for(int i=1;i<=m;i++)add(br[i].u,br[i].v,br[i].w);
		sort(br+1,br+1+m,cmp3);
		bt(1,1,n-1);
	}else if(ercha)
	{
		// cout<<"*********"<<endl;
		for(int i=1;i<=m;i++)add(br[i].u,br[i].v,br[i].w);
	}
	cin>>q;bool has=0;
	while(q--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>u>>w;
			br[u].w=w;
			if(lian&&!ercha)update(1,u,u,w);
			has=1;
		}else
		{
			cin>>u>>w;
			// cout<<"&&&"<<u<<" "<<w<<endl;
			ans=0;
			if(!m)
			{
				cout<<1<<endl;
				continue;
			}
			if(lian==1&&!ercha)
			{
				// cout<<"***"<<endl;
				int l=1,r=max(u-1,1);
				int lans=max(u-1,1)+1,rans=min(u,n-1)-1;
				while(l<=r)
				{
					int mid=(l+r)>>1;

					if(query(1,mid,max(u-1,1))>=w)
					{	
						lans=mid;
						r=mid-1;
					}else l=mid+1;
				}
				l=min(u,n-1),r=n-1;
				while(l<=r)
				{
					int mid=(l+r)>>1;
					// cout<<min(u,n-1)<<" "<<mid<<" "<<query(1,min(u,n-1),mid)<<endl;
					if(query(1,min(u,n-1),mid)>=w)
					{	
						rans=mid;
						l=mid+1;
					}else r=mid-1;					
				}
				// cout<<lans<<" "<<rans<<endl;
				if(rans-lans+2)cout<<rans-lans+2<<endl;
				else cout<<1<<endl;
				continue;
			}
			if(has)
			{
				has=0;
				if(!ercha)kruskal();
				dfs(u,w);
			}else
			{
				dfs(u,w);
			}
			for(int i=1;i<=n;i++)
			{
				if(vis[i])ans++,vis[i]&=0;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

正解是可撤销并查集,也是与回滚莫队类似的思想,首先可撤销并查集合并和删除时的顺序必须是对应的类似栈(注意,别再路径压缩了),我们可以给\(q\)个询问分块,标记好时间,对于每一个块,分为\(1\)操作和\(2\)操作两部分,修改操作不超过块长\(B\),所以我们可以把边都按从大到小排序,然后先把未被修改且符合条件的边加入,然后因为修改操作比较少,直接暴力插入即可,类似回滚莫队,插入完计算出一个点以后再删除即可,如何暴力插入,就是遍历要修改的边然后判断符合条件的合并即可
\(ys\)为映射数组,因为修改的是原下表
复杂度分析,块长玄学

每个块处理的复杂度为\(O(m\log m+S^2\log n)\)。

根据实际情况取块大小即可。理论复杂度\(O(q\sqrt q\log m)\)。

可以把\(O(m\log m)\)的排序用归并优化掉\(\log\)。则理论复杂度可以做到\(O(q\sqrt{q\log m})\)

点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pii pair<int,int>
#define lid (rt<<1)
#define rid (rt<<1|1)
#define endl '\n'
#define pb push_back
using namespace std;
const int N = 1e5+5,B=1024;
int n,m,vis[N],ys[N],ans[N];
struct eg
{
	int u,v,w,id;
	bool operator < (const eg& A)const
	{
		return w>A.w;
	}
}edge[N];
struct qu
{
	int w,id,tim;
	bool operator < (const qu& A)const
	{
		return w>A.w;
	}
}q[N];
struct Disjoint_Set
{
	int fa[N],sz[N],top,st[N];
	void init()
	{
		top=0;
		for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
	} 
	int find(int x){if(fa[x]!=x)return find(fa[x]);return fa[x];}//别TM路径压缩
	void merge(int u,int v)
	{
		int fu=find(u),fv=find(v);
		if(fu!=fv)
		{
			if(sz[fu]>sz[fv])swap(fu,fv);
			sz[fv]+=sz[fu];fa[fu]=fv;
			st[++top]=fu;
		}
	}

	void del(int ls)
	{
		while(top>ls)
		{
			int u=st[top--];
			sz[fa[u]]-=sz[u];
			fa[u]=u;
		}
	}
}S;
vector <qu> M,Q;
void solve()
{
	sort(edge+1,edge+1+m);
	sort(Q.begin(),Q.end());
	vector <qu> MM;MM.clear();
	for(int i=1;i<=m;i++)ys[edge[i].id]=i;
	
	for(auto v:M)vis[v.id]=-1,MM.pb({edge[ys[v.id]].w,v.id,0});//时间为0必然
	for(auto v:M)MM.pb(v);
	S.init();
	int it=1;
	for(int i=0;i<Q.size();i++)
	{
		while(it<=m&&edge[it].w>=Q[i].w)
		{
			if(!vis[edge[it].id])S.merge(edge[it].u,edge[it].v);
			it++;
		}
		int ls=S.top;
		for(auto v:MM)
			if(v.tim<=Q[i].tim)vis[v.id]=v.w;//可能有多条相同但权值不同的边
		for(auto v:M)
			if(vis[v.id]>=Q[i].w)
				S.merge(edge[ys[v.id]].u,edge[ys[v.id]].v);
		ans[Q[i].tim]=S.sz[S.find(Q[i].id)];
		// cout<<S.sz[S.find(Q[i].id)]<<endl;
		S.del(ls);
	}
	for(auto v:M)edge[ys[v.id]].w=v.w,vis[v.id]=0;
	M.clear();Q.clear();
}
int main()
{
	speed();
	// freopen("bridge1.in","r",stdin);
	// freopen("in.in","r",stdin);
	// freopen("out1.out","w",stdout);
	cin>>n>>m;
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		edge[i]={u,v,w,i};
	}
	int q;cin>>q;int op;
	// cout<<q<<endl;
	for(int i=1;i<=q;i++)
	{
		cin>>op;qu x;
		x.tim=i;
		if(op==1){cin>>x.id>>x.w;M.pb(x);}
		else {cin>>x.id>>x.w;Q.pb(x);}
		if(i%B==0)solve();
	}
	if(q%B)solve();
	for(int i=1;i<=q;i++)
	{
		if(ans[i])
		cout<<ans[i]<<endl;
	}
	return 0;
}

标签:return,int,cin,len,CSP15,ull,define
From: https://www.cnblogs.com/wlesq/p/18347432

相关文章