首页 > 其他分享 >2024牛客暑期多校训练营9 B.Break Sequence

2024牛客暑期多校训练营9 B.Break Sequence

时间:2024-10-24 16:59:28浏览次数:8  
标签:cnt Sequence int 多校 合法 Break add pos 区间

设 \(f_i\) 表示最后一个区间以 \(a_i\) 结尾的方案总数,也即前 \(i\) 个数的方案总数。最后的答案是 \(f_n\)。

很容易得到转移方程:

\[f_i = \sum_{j=1}^{i-1}f_j \]

其中,需要保证 \(a_i \sim a_j\) 是一个合法区间才能累加,这个检查的过程可以通过 \(j\) 倒序并计算不合法的数的个数,为 \(0\) 时代表是合法区间。

时间复杂度 \(O(N^2)\),附一份代码:

#include<cstdio>
using namespace std;

const int N=2e5+5,M=15,P=998244353;
int n,a[N],m,s[M];
bool no[N];
long long f[N];
int cnt[N];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&s[i]);
		no[s[i]]=true;
	}
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
			cnt[j]=0;
		int ins=0;
		for(int j=i;j>=1;j--) //range[j,i]
		{
			if(no[cnt[a[j]]]) ins--;
			cnt[a[j]]++;
			if(no[cnt[a[j]]]) ins++;
			if(!ins) f[i]=(f[i]+f[j-1])%P;
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}
#include<cstdio>
#include<vector>
using namespace std;

const int N=2e5+5,M=15,P=998244353;
int n,a[N],m,s[M];
long long f[N]; //f[i]表示前i个数分段的方案数 

namespace SegmentTree{

struct SegmentTree{
	int l,r;
	int dat;
	int add,mintag;
	/*
	 * mintag记录区间最小标记 
	 * dat记录带有区间最小标记的f值之和
	 * add作为延迟标记更新mintag 
	 */
}tree[N<<2];

void update(int p)
{
	tree[p].add=0;
	tree[p].mintag=min(tree[p<<1].mintag,tree[p<<1|1].mintag);
	//区间的最小标记为两子区间最小标记的最小值 
	if(tree[p<<1].mintag==tree[p<<1|1].mintag)
		tree[p].dat=(tree[p<<1].dat+tree[p<<1|1].dat)%P;
	//如果两子区间的最小标记相同,就可以合并两个区间的最小标记元素之和 
	else
	{
		if(tree[p<<1].mintag<tree[p<<1|1].mintag) tree[p].dat=tree[p<<1].dat;
		else tree[p].dat=tree[p<<1|1].dat;
		/*
		 * 不同的话去最小标记更小的子区间的最小标记元素之和
		 * 因为上面总区间的最小标记就是由这个最小标记更小的子区间更新而来
		 * 所以这里的最小标记元素和也需要跟随这个子区间 
		 */
	}
	return;
}
void spread(int p) //下传延迟标记 
{
	if(tree[p].add)
	{
		tree[p<<1].add+=tree[p].add;
		tree[p<<1|1].add+=tree[p].add;
		tree[p<<1].mintag+=tree[p].add;
		tree[p<<1|1].mintag+=tree[p].add;
		tree[p].add=0;
	}
	return;
}

void Build(int l,int r,int p=1)
{
	tree[p].l=l,tree[p].r=r;
	if(l==r) return;
	int mid=l+r>>1;
	Build(l,mid,p<<1),Build(mid+1,r,p<<1|1);
	return;
}
void add_range(int l,int r,int k,int p=1) //区间修改,为所有区间增加一个标记 
{
	if(l<=tree[p].l&&tree[p].r<=r)
	{
		tree[p].add+=k;
		tree[p].mintag+=k; //区间最小标记一定会被同时增加 
		return;
	}
	spread(p);
	int mid=tree[p].l+tree[p].r>>1;
	if(l<=mid) add_range(l,r,k,p<<1);
	if(r>mid) add_range(l,r,k,p<<1|1);
	update(p);
	return;
}
void add_point(int x,int k,int p=1) //单点修改,这里用作将一个f值打入线段树中(f[x]=k) 
{
	if(tree[p].l==tree[p].r)
	{
		tree[p].dat=k; //修改此处对应的f值 
		return;
	}
	spread(p);
	int mid=tree[p].l+tree[p].r>>1;
	if(x<=mid) add_point(x,k,p<<1);
	else add_point(x,k,p<<1|1);
	update(p);
	return;
}

} //namespace SegmentTree
using namespace SegmentTree;

vector<int> pos[N]; //pos[i][j]表示i第j次出现的位置  
int cnt[N]; //cnt[i]表示i已经出现的次数 

int main()
{
	scanf("%d%d",&n,&m);
	Build(0,n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&s[i]);
	f[0]=1,add_point(0,1);
	for(int i=1;i<=n;i++)
		pos[i].push_back(0);
	for(int i=1;i<=n;i++)
	{
		pos[a[i]].push_back(i);
		cnt[a[i]]++;
		for(int j=1;j<=m;j++) //对于第j个不合法次数来说 
		{ 
			if(cnt[a[i]]>=s[j]) //不合法标记
			{
				/* 
				 * 以i结尾关于x和s[j]不合法的区间左端点 
				 * 是从“x第(cnt[x]-s[j])次出现的位置”
				 * 到“x第(cnt[x]-s[j]+1)次出现的位置” 
				 */ 
				int l=pos[a[i]][cnt[a[i]]-s[j]]; //进入不合法区间的位置 
				int r=pos[a[i]][cnt[a[i]]-s[j]+1]; //退出不合法区间的位置 
				add_range(l,r-1,1); //为区间打上不合法标记 
			}
			if(cnt[a[i]]>s[j]) //撤销先前的标记 
			{
				int l=pos[a[i]][cnt[a[i]]-s[j]-1];
				int r=pos[a[i]][cnt[a[i]]-s[j]];
				/* 
				 * cnt相比上一次都多减了一个1
				 * 相当于获得上一次出现时的l和r
				 */
				add_range(l,r-1,-1); //-1抵消以抵消上次标记 
			}
		}
		if(tree[1].mintag==0)
		{
			f[i]=tree[1].dat;
			/*
			 * 此时标记为0的,即对于所有s[j]都合法的元素
			 * 就可以累加到f[i]当中,与f[i]组合成合法的区间
			 * 
			 * 所以在此处添加一个if语句判断mintag是否为0
			 * 其实更合理一些,同样可过 
			 * 至于不加为什么能过……世界未解之谜 
			 */
			add_point(i,f[i]); //将新的f值打入到线段树中 
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}

标签:cnt,Sequence,int,多校,合法,Break,add,pos,区间
From: https://www.cnblogs.com/jerrycyx/p/18499948

相关文章

  • 『模拟赛』多校A层冲刺NOIP2024模拟赛12
    Rank挂了不少,还行A.Alice和璀璨花签。一眼最长上升子序列,昨天在AT专题里刚见过,不过赛时没想到离散化之后树状数组,所以打的动态开点,结果细节挂了30pts。和最长上升子序列思路基本一致,直接区间查询\([1,a_i-1]\)的最大值,然后在\(a_i\timesb_{f_i}\)插入\(f_i\)......
  • 最新开发项目多校园跑腿小程序源码系统 带完整的安装代码包以及搭建部署教程
    系统概述随着移动互联网技术的快速发展,校园跑腿服务因其便捷性和高效性受到了越来越多学生的青睐。然而,目前市场上的跑腿小程序大多存在功能单一、操作复杂、用户体验差等问题。为了填补这一市场空白,我们开发了这款多校园跑腿小程序源码系统,旨在为学生提供更便捷、高效、可靠......
  • 【python学习记录篇】08.for、while、break、continue,在python里的使用比在英语阅读理
    小白学习纪实,跨专业学python的第八天~睡了一觉起来觉得自己又行了~   8.1循环    很多情况下,我们会比较讨厌重复着做着相同的事情,因为这样枯燥乏味。很直接的,在我们睡不着失眠的时候,我们会选择重复数绵羊加速我们睡眠。对于程序员来讲同样不喜欢重复地做......
  • 题解:P10977 Cut the Sequence
    题目传送门分析看到这种题就可以想到动态规划,先设状态:$f_i$表示考虑前$i$个数,所需要的最小代价。发现$f_i$可以从所有$i$以前的状态加后一段区间转移过来,于是可以列出状态转移方程:$$f_i=\min_{j=i-1}^{s_i-s_j\leqm}(f_j+\max_{k=j+1}^i)$$其中$j$......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛11
    前言T1不知道啥是冒泡排序,理解了一会儿题面代码发现是啥意思了于是就签了。后面的题都不是很可做,T2、T4计数,T3高级玩意看不懂。但是T2有点可做,但我的DP不知道哪儿假了,暴力还打挂了,不然加个bitset就操过去了。T1冒泡排序\(i\)只能和\(i+k,i+2k,……\)换,对于每一......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛11
    Rank考前不挂就是赢A.冒泡排序签,简单的有点格格不入。发现错误代码实质上是将原序列划分成了若干个连通块,并对每个连通块做一遍排序。并查集维护,\(\mathcal{O(n)}\)扫一遍合并连通块,然后按顺序输出即可。复杂度最坏\(\mathcal{O(n\logn)}\)。点击查看代码#include<b......
  • 多校A层冲刺NOIP2024模拟赛11
    多校A层冲刺NOIP2024模拟赛11\(T1\)A.冒泡排序\(100pts/100pts/100pts\)将循环\(j\)提到外面,本质上是对\(a_{j},a_{j+k},a_{j+2k},\dots,a_{j+xk}\)进行排序迭代的过程。按下标模\(k\)的余数分别排序即可。点击查看代码inta[1000010];vector<int>b[1000......
  • 2024牛客暑期多校训练营9 - VP记录
    A.ImageScaling签到题,找出举行宽高以后直接除以它们的\(\gcd\)使它们互质即可。(这道题居然会有人又WA又RE,我不说是谁)点击查看代码#include<cstdio>#include<cstring>usingnamespacestd;constintN=505;intn,m,x1,y1,x2,y2;charg[N][N];intgcd(intx,int......
  • 多校A层冲刺NOIP2024模拟赛11
    又双叒叕垫底了。rank11,T190,T212,T35,T435。accdoer上rank44,T1100,T20,T35,T435。难度难评,T1签,剩下的不可做?死磕T3了,猜一个结论假一个,打完暴力遗憾离场。好像两个题库都挂了几分,不管了,赛前挂分RP就++。慢报:5k_sync_closer成功地取得了NFLS模拟赛第一名的好成绩。冒泡......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛10
    前言不想说啥了最简单的一题是紫,去死吧只改了T1、T2,T2原题翻译和赛时题面描述都很唐,赛后断断续续加了好多hack。T1岛屿设\(f_{a,b}\)表示\(a\)条两端同色链,\(b\)条两端异色链时连通块数量的期望。红红蓝蓝相连得到红蓝\(\tof_{a-1,b+1}\)。红红红蓝相连得到红红......