当前位置: 首页 > news >正文

【Codeforces】 CF1870E Another MEX Problem

题目链接

CF方向
Luogu方向

题目解法

解法1
考虑优化 d p dp dp 转移次数,即只转移有用的区间
不难发现, m e x ( l , r ) = m e x ( l + 1 , r ) mex(l,r)=mex(l+1,r) mex(l,r)=mex(l+1,r) m e x ( l , r ) = m e x ( l , r − 1 ) mex(l,r)=mex(l,r-1) mex(l,r)=mex(l,r1),那么区间 [ l , r ] [l,r] [l,r] 就没用
考虑证明剩下有用的区间个数是 O ( n ) O(n) O(n)
[ l , r ] [l,r] [l,r] 是有用的,我们不妨令 a l > a r a_l>a_r al>ar
如果有 R > r R>r R>r 且满足 [ l , R ] [l,R] [l,R] 是有用的,且 a l > a R a_l>a_R al>aR
根据上面的定义, m e x ( l , r ) > a l mex(l,r)>a_l mex(l,r)>al,不然可以踢掉 l l l,所以 a R < m e x ( l , r ) a_R<mex(l,r) aR<mex(l,r),那么 r r r 就没有加的必要
所以对于 a l > a r a_l>a_r al>ar,有用的 r r r 只有一个
对于 a l < a r a_l<a_r al<ar 同理, a l = a r a_l=a_r al=ar 随便删去 l , r l,r l,r 都比 [ l , r ] [l,r] [l,r]
所以剩余的区间个数是 2 n 2n 2n
直接 d p dp dp 即可

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=5100;
int mex[N][N],cnt[N],a[N];
bool ok[N][N<<1];
vector<int> trans[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void work(){int n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++){int curmex=0;for(int j=i;j<=n;j++){cnt[a[j]]++;while(cnt[curmex]) curmex++;mex[i][j]=curmex;}for(int j=0;j<=n;j++) cnt[j]=0;}for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) if(mex[i][j]!=mex[i+1][j]&&mex[i][j]!=mex[i][j-1]) trans[j].pb(i);ok[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=n<<1;j++) ok[i][j]=ok[i-1][j];for(int j:trans[i]) for(int k=0;k<=n<<1;k++) if(ok[j-1][k]) ok[i][k^mex[j][i]]=1;}for(int i=n<<1;;i--) if(ok[n][i]){ printf("%d\n",i);break;}for(int i=1;i<=n;i++) trans[i].clear();
}
int main(){int T=read();while(T--) work();fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

解法2
我们发现 m e x mex mex 的上界是 2 n 2n 2n
所以我们考虑 g i g_i gi 表示异或 m e x mex mex 和为 i i i 最少需要的前缀长度
显然 g i g_i gi 可用类似最短路的方式实现
但这样会多一个 l o g log log,因为值域较小,开 n n n v e c t o r vector vector 存最优位置对应的异或 m e x mex mex 值即可

相关文章:

【Codeforces】 CF1870E Another MEX Problem

题目链接 CF方向 Luogu方向 题目解法 解法1 考虑优化 d p dp dp 转移次数&#xff0c;即只转移有用的区间 不难发现&#xff0c; m e x ( l , r ) m e x ( l 1 , r ) mex(l,r)mex(l1,r) mex(l,r)mex(l1,r) 或 m e x ( l , r ) m e x ( l , r − 1 ) mex(l,r)mex(l,r-1…...

【Objective-C】Objective-C汇总

方法定义 参考&#xff1a;https://www.yiibai.com/objective_c/objective_c_functions.html Objective-C编程语言中方法定义的一般形式如下 - (return_type) method_name:( argumentType1 )argumentName1 joiningArgument2:( argumentType2 )argumentName2 ... joiningArgu…...

怎么查找性别为女性的不同学历层次不同学位以及所有人不同职务职称的人数

怎么查找性别为女性的不同学历层次不同学位以及所有人不同职务职称的人数 需求分析&#xff1a; 1.统计性别为女性的所获学位下不同学历层次的人数 2.统计不同职务职称的不同学位和学历层次的人数代码 def cal_xuewei_number(self):# 读取表格文件table pd.read_excel("…...

浅谈Elasticsearch查询和搜索

Elasticsearch查询和搜索 Elasticsearch是一个分布式、实时的搜索和分析引擎&#xff0c;广泛应用于全文搜索、日志分析、实时数据分析等场景。Elasticsearch提供了丰富的查询和搜索功能&#xff0c;如查询DSL、过滤、排序、分页、高亮和聚合等。本文将详细介绍如何在Elastics…...

SLAM从入门到精通(被忽视的基础图像处理)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 工业上用激光slam的多&#xff0c;用视觉slam的少&#xff0c;这是大家都知道的常识。毕竟对于工业来说&#xff0c;健壮和稳定是我们必须要考虑的…...

【C++】继承详解

本篇要分享的内容是关于继承的内容哼哼哼啊啊啊啊啊啊啊啊啊啊啊啊啊啊 以下为本篇目录 目录 1.简单了解继承 2.继承的简单定义 3.继承简单使用 4.继承方式 4.1基类的privat 4.2基类的protected 4.3不可见与private的区别 5.父子类对象赋值转换 6.继承的作用域 7.子…...

react:swr接口缓存

useSWR 是一个 React Hooks&#xff0c;是 HTTP 缓存库 SWR 的核心方法之一。SWR 是一个轻量级的 React Hooks 库&#xff0c;通过自动缓存数据来实现 React 的数据获取。 第一个参数是被缓存的数据的 key&#xff0c; 第二个参数是一个函数&#xff0c;该函数返回数据或者一个…...

2023-11 | 短视频批量下载/爬取某个用户的所有视频 | Python

这里以鞠婧祎的个人主页为demo https://www.douyin.com/user/MS4wLjABAAAACV5Em110SiusElwKlIpUd-MRSi8rBYyg0NfpPrqZmykHY8wLPQ8O4pv3wPL6A-oz 【2023-11-4 23:02:52 星期六】可能后面随着XX的调整, 方法不再适用, 请注意 找到接口 找到https://www.douyin.com/aweme/v1/web/…...

【JAVA学习笔记】66 - 本章作业(IO流)

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter19/src/com/yinhai/homework 1.使用File类和FileWriter类 (1)在判断e盘下是否有文件夹mytemp&#xff0c;如果没有就创建mytemp public class Homework01 {public static void main(String…...

vscode中 vue3+ts 项目的提示失效,volar插件失效问题解决方案

文章目录 前情提要bug回顾解决方案最后 前情提要 说起来很耻辱&#xff0c;从mac环境换到window环境&#xff0c;vscode的配置都是云端更新过来的&#xff0c;应该是一切正常才对&#xff0c;奇怪的是我的项目环境出现问题了&#xff0c;关于组件的ts和追踪都没有效果&#xff…...

Elasticsearch:在 ES|QL 中使用 DISSECT 和 GROK 进行数据处理

目录 DISSECT 还是 GROK&#xff1f; 或者两者兼而有之&#xff1f; 使用 DISSECT 处理数据 Dissect pattern 术语 例子 DISSECT 关键修饰符 右填充修饰符 (->) 附加修饰符 () 添加顺序修饰符&#xff08; 和 /n&#xff09; 命名的跳过键&#xff08;&#xff1f…...

基于自适应自回归模型的高级人工智能概念及其实现

基于自适应自回归模型的高级人工智能概念及其实现 摘要:一、引言:二、方法:三、讨论:四、结论:草稿实现计算摘要: 在人工智能研究领域中,预测未来的信息往往会遇到信息不明确的问题,尤其是在自回归模型中,这一问题尤为突出。本研究提出一个新颖的假设,将能自主解决信…...

windows的mysql启动错误,查看windows日志

1、点击左下角开始按钮&#xff0c;计算机上右键&#xff0c;点击【管理】。 2、在计算机管理界面依次找到【系统工具】&#xff0c;选择【时间查看器】&#xff0c;打开【windows日志】&#xff0c;点击【应用程序】 3、在右侧找到&#xff0c;最新的mysql错误信息。双击查看。…...

centos7部署Canal与Canal集成使用

1、简介 canal [kə’nl]&#xff0c;译意为水道/管道/沟渠&#xff0c;主要用途是基于 MySQL 数据库增量日志解析&#xff0c;提供增量数据订阅和消费 早期阿里巴巴因为杭州和美国双机房部署&#xff0c;存在跨机房同步的业务需求&#xff0c;实现方式主要是基于业务 trigge…...

C语言--分段函数--switch语句

如何用switch语句写分段函数呢&#xff1f;⭐️ 首先介绍一下switch语句的语法规则⭐️ switch(整形表达式) {case 常量表达式1&#xff1b; //标签必须唯一语句块1;break;case 常量表达式2&#xff1b; //if(a0),而case中时系统自动加语句块2&#xff1b;break&#xff1b;c…...

动态规划31(Leetcode188买卖股票的最佳时机4)

代码&#xff1a; 我的状态方程&#xff1a; buy[i][j]max{buy[i−1][j],sell[i−1][j-1]−price[i]} 题解里的&#xff1a; buy[i][j]max{buy[i−1][j],sell[i−1][j]−price[i]} ..没理解题解的 但我的通过了 class Solution {public int maxProfit(int k, int[] pric…...

npm包管理相关命令

前置条件&#xff0c;准备npm账号&#xff0c;并登录&#xff0c;npm login 或者 npm adduser &#xff08;这一行同样需要输入账号密码登录&#xff0c;之后就不用登录了&#xff09; 验证是否登录&#xff1a;npm whoami 还可以查看用户简介&#xff1a;npm profile get …...

2023年Q3乳品行业数据分析(乳品市场未来发展趋势)

随着人们生活水平的不断提高以及对健康生活的追求不断增强&#xff0c;牛奶作为优质蛋白和钙的补充品&#xff0c;市场需求逐年增加。 今年Q3&#xff0c;牛奶乳品市场仍呈增长趋势。根据鲸参谋电商数据分析平台的相关数据显示&#xff0c;2023年7月-9月&#xff0c;牛奶乳品市…...

软考 系统架构设计师系列知识点之边缘计算(2)

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之边缘计算&#xff08;1&#xff09; 所属章节&#xff1a; 第11章. 未来信息综合技术 第4节. 边缘计算概述 3. 边缘计算的特点 边缘计算是在靠近物或数据源头的网络边缘侧&#xff0c;融合网络、计算、存储、应用核心…...

Maven中的继承与聚合

一&#xff0c;继承 前面我们将项目拆分成各个小模块&#xff0c;但是每个小模块中有很多相同的依赖于是我们创建一个父工程将模块中相同的依赖定义在父工程中&#xff0c;然后子工程继承父工程Maven作用&#xff1a;简化依赖配置&#xff0c;统一依赖管理,可以实现多重继承像J…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录

#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...