首页 > 其他分享 >CSP16

CSP16

时间：2024-08-08 20:27:42浏览次数：15  
标签：int ll long CSP16 ans tie define

image

这题，唯一坑点，子序列是不连续的
注意,子序列可以不连续,子串必须连续。
有一个很显然的暴力

点击查看代码 
int dp[N][N],n,p[N],q[N];
int main()
{
	speed();
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i];
	for(int i=1;i<=n;i++)cin>>q[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			if(q[j]%p[i]==0)
			{
				dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);
			}
		}
	}
	cout<<dp[n][n]<<endl;
	return 0;
}

优化就是拿树状数组优化，顺便滚掉一位，注意啊倒序遍历，否则会更新错误，预处理处每个\(p_i\)对应的倍数
复杂度\(O(n\ln n\log n)\)

点击查看代码 
#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 dp[N],n;
int p[N],q[N];
int posq[N],posp[N];
vector <int> pos[N];
int c[N];
int lowbit(int x){return x&-x;}
int query(int x)
{
	int ans=0;
	if(x<=0)return 0;
	while(x)
	{
		ans=max(ans,c[x]);
		x-=lowbit(x);
	}return ans;
}
void upd(int x,int val)
{
	if(x<=0)return ;
	while(x<=n)
	{
		c[x]=max(c[x],val);
		x+=lowbit(x);
	}
	return;
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i],posp[p[i]]=i;
	for(int i=1;i<=n;i++)cin>>q[i],posq[q[i]]=i;
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j+=i)
			if(posq[j])pos[i].pb(posq[j]);
		sort(pos[i].begin(),pos[i].end());
		reverse(pos[i].begin(),pos[i].end());
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int ls=0;
		for(auto v:pos[p[i]])
		{
			int j=v;
			// cout<<v<<endl;
			dp[j]=query(j);
			dp[j]=max(query(j-1)+1,dp[j]);
			ans=max(ans,dp[j]);
			// cout<<dp[i][j]<<endl;
			upd(j,dp[j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}

image

两种写法，
回滚莫队（常熟略大）

点击查看代码 
#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,mod=1e9+7;
int x[N],n,m;
int sq,B,st[500],ed[500],b[N],cnt[N],ans[N],cc[N];
struct qu
{
	int l,r,id,bl;
	bool operator < (const qu& A)const
	{
		if(bl==A.bl)return r<A.r;
		return l<A.l;
	}
}q[N];
void init()
{
	sq=sqrt(n);B=n/sq;
	for(int i=1;i<=B;i++)
	{
		st[i]=ed[i-1]+1;ed[i]=st[i]+sq-1;
		// cout<<st[i]<<" "<<ed[i]<<endl;
	}
	if(ed[B]<n)
	{
		B++;st[B]=ed[B-1]+1;ed[B]=n;
	}
}
int RES;
void add(int d)
{
	
	cnt[x[d]]++;
	// cout<<cnt[x[d]]<<endl;
	RES=max(RES,cnt[x[d]]);
	// cout<<res<<endl;
}
void del(int d)
{
	cnt[x[d]]--;
}
int force(int l,int r)
{
	memset(cc,0,sizeof cc);
	int ans=0;
	for(int i=l;i<=r;i++)cc[x[i]]++,ans=max(ans,cc[x[i]]);
	return ans;
}
int main()
{
	speed();
	// freopen("T2.in","r",stdin);
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];b[i]=x[i];
	}
	sort(b+1,b+1+n);
	int res=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)
	{
		x[i]=lower_bound(b+1,b+1+res,x[i])-b;
		// cout<<x[i]<<endl;
	}
	init();
	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;
	}
	sort(q+1,q+1+m);int j=1;int L,R;
	// sq=1e9;
	for(int i=1;i<=B&&j<=m;i++)
	{
		L=ed[i]+1;R=ed[i];RES=0;
		memset(cnt,0,sizeof cnt);
		while(q[j].bl==i)
		{
			if(q[j].r-q[j].l<=sq)
			{
				ans[q[j].id]=force(q[j].l,q[j].r);
				j++;
				continue;
			}
			// cout<<L<<" "<<R<<" "<<q[j].l<<endl;
			L=ed[i]+1;
			while(R<q[j].r)
			{
				++R;
				add(R);
			}
			// cout<<res<<endl;
			ll tmp=RES;
			while(L>q[j].l)
			{
				L--;
				// cout<<L<<endl;
				add(L);
			}
			ans[q[j].id]=RES;
			// cout<<res<<endl;
			RES=tmp;
			while(L<=ed[i])del(L++);
			j++;
		}
	}
	for(int i=1;i<=m;i++)cout<<-ans[i]<<endl;
	return 0;
}

莫队

点击查看代码 
#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,m,st[500],ed[500],sq,B,x[N],b[N],t[N],cnt[N],aa[N];
struct qu
{
	int l,r,id,bl;
	bool operator < (const qu& A)const
	{
		if(bl!=A.bl)return l<A.l;
		if(bl&1)return r<A.r;
		return r>A.r;
	}
}q[N];
void init()
{
	sq=sqrt(n);B=n/sq;
	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;
	}
}
int ans;
inline void del(int x)
{
	if(ans==cnt[b[x]])ans--;
	t[cnt[b[x]]]--;
	if(t[cnt[b[x]]])ans=max(ans,cnt[b[x]]);
	cnt[b[x]]--;
	t[cnt[b[x]]]++;
	ans=max(ans,cnt[b[x]]);
}
inline void add(int x)
{
	t[cnt[b[x]]]--;
	cnt[b[x]]++;
	t[cnt[b[x]]]++;
	ans=max(ans,cnt[b[x]]);
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];b[i]=x[i];
	}
	sort(x+1,x+1+n);
	int res=unique(x+1,x+1+n)-x-1;
	for(int i=1;i<=n;i++)
	{
		b[i]=lower_bound(x+1,x+1+res,b[i])-x;
		// cout<<x[i]<<endl;
	}init();
	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;
	}
	sort(q+1,q+1+m);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l>q[i].l){add(--l);}
		while(l<q[i].l){del(l++);}
		while(r>q[i].r){del(r--);}
		while(r<q[i].r){add(++r);}
	
		aa[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++)cout<<-aa[i]<<endl;
	return 0;
}

T3Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

image

简单路径有两个义项，可以指图G(V，E)中路径上的顶点都不相同的路径，还可以指Rn中的弧，亦称简单弧，是曲线弧概念的推广。
所以说，一个子树中的简单路径，是不包含自身，不重复走且是可以横跨两个儿子的路径
暴力的话，我们可以得到性质:一条路可以回文，必须每个字母出现次数为偶数，最多有一个奇数，这时候可以二进制压缩一下，当一个状态为全是\(0\)或只有一个\(1\)时才合法,期望得分\(50pts\)

点击查看代码 
#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
#define pii pair<int,int>
using namespace std;
const int N = 5e5+5;
int n,ans[N],fa[N];char val[N];
vector <int> edge[N];
map <int,int> len[N];
inline int get(int x)
{
	return 1<<(val[x]-'a');
}
inline void dfs(int u)
{
	len[u][0]=0;
	for(auto to:edge[u])
	{
		dfs(to);
		ans[u]=max(ans[to],ans[u]);
		for(auto v:len[to])
		{
			int zt=get(to)^v.first;
			if(len[u].find(zt)!=len[u].end())ans[u]=max(ans[u],len[u][zt]+v.second+1);
			if((zt^(zt&-zt))==0)ans[u]=max(ans[u],v.second+1);
			for(int j=0;j<22;j=-~j)
			{
				if(len[u].find(zt^(1<<j))!=len[u].end())
					ans[u]=max(ans[u],len[u][zt^(1<<j)]+v.second+1);
			}
		}
		for(auto v:len[to])
			len[u][get(to)^v.first]=max(len[u][get(to)^v.first],v.second+1);
	}
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>fa[i]>>val[i];
		edge[fa[i]].pb(i);
	}
	dfs(1);
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	return 0;
}

正解用到了启发式合并，我们先想最原始的暴力,我们可以计算\(x\)到\(1\)路径上的异或状态，想求\(u,v\)之间，直接异或即可\(lca\)以上部分可以抵消掉,只有一条路径合法当且仅当二进制表示下只有一个\(1\)或全是\(0\)的时候,如果\(u,v\)合法(要么\(dis_u=dis_v和dis_udis_v只有1个1\))，那么产生的贡献为\(dep_u+dep_v-2dep_{lca}\),我们可以用一个数组\(book\)存储每个状态对应的深度，遍历其所有子树，然后对于一个状态\(dsu\)与其\(⊕\)得到结果合法的状态是固定的\(23\)种，于是我们只要检查\(book\)内有没有合法的即可,\(book\)首先存的是重链里面的状态，然后再与其他儿子中的状态合并,这也是启发式合并的意义所在，这也就从\(O(23n^2)\)优化到了\(O(23n\log n)\)

点击查看代码 
#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 = 1e6+5;
int fa[N],L[N],R[N],rk[N],dfstot,sz[N],son[N],dis[N],dep[N],n;char val[N];
int ans[N],book[1<<22];//book表示当前路径状态对应的深度
vector <int> edge[N];
inline void dfs1(int u)
{
	dep[u]=dep[fa[u]]+1;sz[u]=1;
	L[u]=++dfstot;rk[dfstot]=u;//欧拉序,作用是方便遍历所有儿子
	for(auto to:edge[u])
	{
		dis[to]=dis[u]^(1<<(val[to]-'a'));//计算路径状态
		dfs1(to);
		sz[u]+=sz[to];
		if(sz[to]>sz[son[u]])son[u]=to;
	}
	R[u]=dfstot;
}
inline void dfs2(int u,bool heavy)
{
	for(auto to:edge[u])
	{
		if(to==son[u])continue;
		dfs2(to,0);
		ans[u]=max(ans[u],ans[to]);
	}
	if(son[u])dfs2(son[u],1),ans[u]=max(ans[u],ans[son[u]]);
	if(book[dis[u]])ans[u]=max(ans[u],book[dis[u]]-dep[u]);//更新答案
	for(int j=0;j<22;j++)
		if(book[dis[u]^(1<<j)])ans[u]=max(ans[u],book[dis[u]^(1<<j)]-dep[u]);//异或判断状态合法
	book[dis[u]]=max(book[dis[u]],dep[u]);//更新()别忘了
	for(auto to:edge[u])
	{
		if(to==son[u])continue;
		for(int j=L[to];j<=R[to];j++)
		{
			int id=rk[j];
			if(book[dis[id]])ans[u]=max(ans[u],book[dis[id]]+dep[id]-2*dep[u]);
			for(int k=0;k<22;k++)
				if(book[dis[id]^(1<<k)])ans[u]=max(ans[u],book[dis[id]^(1<<k)]+dep[id]-2*dep[u]);
		}
		for(int j=L[to];j<=R[to];j++)book[dis[rk[j]]]=max(dep[rk[j]],book[dis[rk[j]]]);//计算完当前儿子分支，就可更新为下一个儿子做准备
	}
	if(!heavy)for(int j=L[u];j<=R[u];j++)book[dis[rk[j]]]=0;
}
int main()
{
	speed();
	// freopen("T3.in","r",stdin);
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>fa[i]>>val[i];
		edge[fa[i]].pb(i);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=n;i++)	
		cout<<ans[i]<<" ";
	return 0;
}

T4[AGC049D] Convex Sequence

image

暴力

点击查看代码 
#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;
ll ans=0;int n,m;
unordered_map <int,unordered_map<int,unordered_map<int,unordered_map<int,int>>>> f;
inline ll dfs(int now,ll cha,int sum,int ai)
{
	if(sum>m)return 0;
	if(now==n+1)
	{
		// for(int i=1;i<=n;i++)cout<<p[i]<<" ";
		// cout<<endl;
		return (m==sum);
	}
	if(f[now][cha][sum][ai])return f[now][cha][sum][ai];
	ll ans=0;
	for(int i=0;i<=m-sum;i++)
	{
		if(i-ai>=cha)
		{
			ans=(ans+dfs(now+1,i-ai,sum+i,i))%mod;
		}	
	}
	return f[now][cha][sum][ai]=ans;
}
int main()
{
	speed();
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	cin>>n>>m;
	ll ans=0;
	for(int i=0;i<=m;i++)
	{
		ans=(ans+dfs(2,-1e9,i,i))%mod;
	}
	cout<<ans;
	return 0;
}

怎么说呢挂分变少了，有进步

标签：int,ll,long,CSP16,ans,tie,define
From： https://www.cnblogs.com/wlesq/p/18348908

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99