首页 > 其他分享 >3.30 模拟赛 T3 记录

3.30 模拟赛 T3 记录

时间:2024-04-02 16:56:54浏览次数:22  
标签:head 端点 int T3 tail maxn dp 3.30 模拟

题面

首先先可以发现对于限制 \(\min_{i \in [l,r]} a_i \leq r-l+1\),的任意一个右端点,能贡献的 \(l\) 肯定是一个可以确定的前缀,这一部分可以用单调队列提前预处理出每个前缀记为 \(pre_i\)。同理对于任意一个左端点也对应可以转移到一个确定的后缀,也预处理出来记为 \(nxt_i\)。

到这里可以暴力 \(O(n^2)\text{dp}\),也可以做出特殊性质。

然后对于最大值的限制,考虑仿照 \(\text{cdq}\) 分治优化 \(dp\),找到分界点为当前区间最大值的位置,这样对于左边对右边的区间的最大值就确定了,然后发现有两种方案:

  • 枚举左端点 \(i \in [l,mid]\),发现他能贡献到的右端点肯定是连续的,可以用预处理出的值算出,然后树状数组计算,这样会多一个 \(\log\)。但是发现是先修改再查询,所以可以差分。
  • 枚举右端点 \(i \in [mid,r]\),发现可以贡献到他的左端点也是可以直接算出,维护左边的前缀和计算就行了。

由于最大值的分布位置不一定均匀,为了防止复杂度退化到 \(O(n^2)\),考虑两种方案那边区间小选对应方案计算。然后差分数组和前缀和数组可以用一个指针,时刻维护出已经计算完贡献的前缀的信息就可以做到复杂度 \(O(n\log n)\)。

#include <bits/stdc++.h>

using namespace std;

const int maxn=5e5+5;
const int lgn=25;
const int mod=1e9+7;
int a[maxn],pre[maxn],nxt[maxn],sum[maxn],sum2[maxn];
int que[maxn],head,tail,dp[maxn],now=1;
int st[maxn][lgn],lg[maxn];

inline void init(int n){
	lg[0]=-1;
	for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int j=1;j<=20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			if(a[st[i][j-1]]>=a[st[i+(1<<(j-1))][j-1]]) st[i][j]=st[i][j-1];
			else st[i][j]=st[i+(1<<(j-1))][j-1];
		}
	}
}
int query(int l,int r){
	int k=lg[r-l+1];
	if(a[st[l][k]]>=a[st[r-(1<<k)+1][k]]) return st[l][k];
	return st[r-(1<<k)+1][k];
}


void cdq(int l,int r){
	if(l>=r){
		if(now<=l){
			for(int i=now;i<l;i++){
				sum[i]=(sum[i-1]+sum[i])%mod;
				dp[i]=(dp[i]+sum[i])%mod;
				sum2[i]=(sum2[i-1]+dp[i])%mod;
			}
			now=l;
		}
		if(l==r&&a[l]==1) dp[l]=(dp[l]+dp[l-1])%mod;
		if(now<=r){
			for(int i=now;i<=r;i++){
				sum[i]=(sum[i-1]+sum[i])%mod;
				// printf("%d %d %d : %d\n",i,sum[i],sum2[i],dp[i]);
				dp[i]=(dp[i]+sum[i])%mod;
				sum2[i]=(sum2[i-1]+dp[i])%mod;
				// printf("%d %d %d : %d\n",i,sum[i],sum2[i],dp[i]);
			}
			now=r+1;
		}
		return;
	}
	int mid=query(l,r);
	cdq(l,mid-1);
	// for(int i=mid;i<=r;i++) sum[i]=sum2[i]=0;
	if(mid-l<r-mid+1){
		for(int i=l-1;i<mid;i++){
			int tmp=min(r,i+a[mid]);
			if(tmp<mid) continue;
			if(max(mid,nxt[i+1])<=tmp){
				// printf("kk%d : %d %d\n",i,max(mid,nxt[i+1]),tmp);
				sum[max(mid,nxt[i+1])]=(sum[max(mid,nxt[i+1])]+dp[i])%mod;
				sum[tmp+1]=(sum[tmp+1]-dp[i]+mod)%mod;
			}
		}
	}else{
		for(int i=mid;i<=r;i++){
			int tmp=max(l,i-a[mid]+1);
			if(tmp>mid) continue;
			if(min(pre[i],mid)>=tmp){
				dp[i]=(dp[i]+sum2[min(pre[i],mid)-1])%mod;
				if(tmp>=2) dp[i]=(dp[i]-sum2[tmp-2]+mod)%mod;
			}
		}
	}
	cdq(mid+1,r);
}

int main(){
	
	int n;
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		st[i][0]=i;
	}
	
	init(n);
	
	int mn=0;
	head=1;
	tail=0;
	
	for(int i=1;i<=n;i++){
		while(head<=tail&&a[que[tail]]>=a[i]) tail--;
		que[++tail]=i;
		while(head<=tail&&i-a[que[head]]+1>que[head]){
			mn=max(mn,que[head]);
			head++;
		}
		pre[i]=max(mn,i-a[que[head]]+1);
	}
	
	head=1;
	tail=0;
	mn=n+1;
	
	for(int i=n;i>=1;i--){
		while(head<=tail&&a[que[tail]]>=a[i]) tail--;
		que[++tail]=i;
		while(head<=tail&&i+a[que[head]]-1<que[head]){
			mn=min(mn,que[head]);
			head++;
		}
		nxt[i]=min(mn,i+a[que[head]]-1);
	}
	
	// for(int i=1;i<=n;i++) printf("%d : %d %d\n",i,pre[i],nxt[i]);
	
	// exit(0);
	
	sum2[0]=dp[0]=1;
	
	cdq(1,n);
	
	printf("%d\n",dp[n]);
	
	return 0;
}

标签:head,端点,int,T3,tail,maxn,dp,3.30,模拟
From: https://www.cnblogs.com/activeO/p/18110995

相关文章

  • 3.30毕设
    web系统通过axios传递参数首先安装axios,通过过下面这条命令npminstallaxios-g其中-g:表示全局安装,将会安装在你配置的项目目录下。执行GET请求  执行POST请求 ......
  • CS571 W6/HW5 -React3 笔记
    1.React返回多个组件functionComponent(){return(<p>一个p标签</p><h1>一个一级标题</h1>)}对于不同的组件,需要用小括号括起来,否则React只会返回最上面的那个。如果是整个组件返回,用div标签括起来另外,不要滥用空标签<>,例如使用<Carousel>和......
  • 下列关于静态,动态时序模拟的优缺点说法错误的是()
    A、静态时序分析是提取出整个电路存在的所有时序路径,计算信号在这些路径上的传播延时,检查信号的建立和保持时间是否满足时序要求B、静态时序分析可以对芯片设计进行全面的时序验证和功能验证,验证每一条路径,发现时序的重大问题,比如建立时间和保持时间冲突,slowpath以及过大的时钟......
  • 【数学建模】基于matlab模拟单摆运动
     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,代码获取、论文复现及科研仿真合作可私信。......
  • 【雷达】基于Matlab模拟固定雷达LFM信号的仿真与压缩,建立了对移动目标的回波模型
     ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,代码获取、论文复现及科研仿真合作可私信。......
  • 哈尔滨理工大学3-31校赛模拟赛第一场题解
    概览:ABF为签到题,CE模拟,D深搜,G最短路,H双指针A.提取数字:注意前导零的情况需要排除,由于组成的数不超过longlong范围,所以直接用res承接就好了#include<iostream>usingnamespacestd;longlongres;intmain(){charc;while(cin>>c)if(c>='0'&&c<='9......
  • CCF CSP模拟真题解答示例
    CCFCSP(CertifiedSoftwareProfessional)是中国计算机学会主办的软件能力认证考试,旨在评估参赛者在计算机科学和软件工程方面的基本知识和实践能力。请注意,以下解答仅作为示例,并非针对实际真题的准确答案。实际考试中的题目和答案可能会有所不同,因此建议参考官方发布的真题......
  • 模拟游戏《幸福工厂》好玩吗?《幸福工厂》怎么在mac电脑上打开?
    关于《幸福工厂》这款游戏是否好玩,普遍的玩家反馈和评价表明,《幸福工厂》(Satisfactory)因其深度的工厂建造模拟、自由度极高的探索以及精美的图形表现而受到许多玩家的喜爱。它允许玩家在一个开放的世界中规划并建立复杂的生产线,解决资源采集和物流问题,同时提供了一定的挑战性和......
  • TRICONEX 3604E(英维思/康吉森)数字量输出模块模拟量模块
    TRICONEX3604E是一款高性能、高可靠性的数字量输出模块模拟量模块,由英维思/康吉森公司推出。这款模块在工业自动化系统中有着广泛的应用,尤其在需要高度可靠性和冗余性的领域中表现出色,如石油、天然气、化工和核电站等。TRICONEX3604E模块支持多种通信接口,包括Modbus、DNP3和......
  • 模拟比赛-14届研究生组C++省赛
    A工作时长题意:若干条打卡记录字符串(年月日时分秒格式),保证打卡记录相邻。求该年工作时长。思路:对字符串处理,转换格式为秒数,排序后相邻相减求和。总结:2月有29天的情况要被4整除,如果能被100整除的话,一定要被400整除。structData{ intmonth;//5 intday;//8 inthour;//......