程序员必知:国庆清北Day5T3holyshit

简介: 程序员必知:国庆清北Day5T3holyshit

一道神题 (holyshit)

Time Limit:1000ms Memory Limit:128MB

题目描述

LYK有n个数ai。

它想找两段互不相交的区间。

要求:不存在一个数在这两段区间中总共的出现次数超过1次。

LYK想使得取出的两段区间的长度的和尽可能大。

问这个值最大是多少。

输入格式(holyshit.in)

第一行一个数n。

接下来一行n个数ai。

输出格式(holyshit.out)

一个数表示可能的最大值是多少

输入样例

10

//代码效果参考: http://www.zidongmutanji.com/zsjx/176575.html

3 1 2 1 2 4 5 4 5 6

输出样例

6

样例解释

取区间【1,3】和【8,10】是最优的。

数据范围

对于20%的数据n<=10。

对于40%的数据n<=50。

对于60%的数据n<=200。

对于100%的数据2<=n<=2000,1<=ai<=n。

g【i】【j】 表示 【i,j】取一段子区间,没有元素重复,使得子区间长度最长 n^2

g【i】【j-1】 g【i+1】【j】 【i,j】没有元素重复

1 for (i=n; i>=1; i--){

2 for (j=1; j<=n; j++) v【j】=false; FLAG=true;

3 for (j=i; j<=n; j++){

4 if (v【a【j】】) FLAG=false;

5 v【a【j】】=true;

6 if (FLAG) g【i】【j】=j-i+1; else g【i】【j】=max(g【i+1】【j】,g【i】【j-1】);

7 }

8 }

先把所有符合条件的区间全部搞出来,由这些区间取扩展到g更大

【A,B】是合法的, 则 g【A】【B】=B-A+1 g【l】【r】 l=B 都有g【l】【r】>=B-A+1 n^2

先枚举第一段区间的右端点r,当l=1时,求出所有×的位置,并求出第二段区间能取的最大长度。

随着l往右走,部分×被解锁,更新第二段区间的最大长度(并查集实现),然后更新答案。

f【i】表示在并查集树上的父亲,i的祖先就表示从i出发向右最近×的位置。

x这个位置被解锁了,getf(x+1)表示新增的区间右端点在哪里, 更新f呢,f【x】=getf(x+1);

相关文章
|
2月前
|
人工智能 运维 安全
2025国内低代码开发平台大盘点
低代码平台正成为企业数字化转型的关键工具,凭借可视化开发、AI融合与高效协作等趋势,助力企业快速构建应用。然而,灵活性受限、平台依赖与安全风险仍是发展中的挑战。本文深入解析低代码发展趋势、常见问题及十大平台评测,为企业选型提供权威参考。
183 1
|
移动开发 监控 开发工具
mPaaS常见问题之pod里使用abstract_target后会报错如何解决
mPaaS(移动平台即服务,Mobile Platform as a Service)是阿里巴巴集团提供的一套移动开发解决方案,它包含了一系列移动开发、测试、监控和运营的工具和服务。以下是mPaaS常见问题的汇总,旨在帮助开发者和企业用户解决在使用mPaaS产品过程中遇到的各种挑战
233 0
|
前端开发 JavaScript
【JavaScript原型链prototype详解】
在JavaScript中,每个对象都有一个原型(prototype)属性,它指向另一个对象。这个被指向的对象也有自己的原型,以此类推,最终形成了一个原型链。原型链的顶端是Object.prototype,它是所有对象的根原型。 当我们访问一个对象的属性时,如果该对象自身没有这个属性,JavaScript会沿着原型链向上查找,直到找到匹配的属性或者到达原型链的末端。
339 0
【JavaScript原型链prototype详解】
|
7月前
|
人工智能 云计算
云工开物合作动态丨湖南大学与阿里云签署云工开物校企合作协议
2024年7月5日,湖南大学与阿里云签署合作协议,副校长李肯立与阿里云副总裁刘湘雯出席。双方将在课程共建、科研攻关、学生实践等方面展开合作。阿里云将为每位学生提供算力资源,并为教师每年提供40万元优惠权益。当天下午,阿里云-湖南大学人工智能学生实训营开营,200余名学生参与实操课程。此次合作旨在培养云计算与人工智能领域的高素质创新人才。
|
敏捷开发 测试技术 BI
禅道:从安装到使用,一篇文章带你全面了解
禅道:从安装到使用,一篇文章带你全面了解
2835 3
|
云安全 安全 API
2024 年 CSPM 产品该具备哪些能力?
云安全态势管理(CSPM)是一种持续管理IaaS和PaaS安全态势的解决方案,通过预防、检测和响应云基础设施风险来保障安全。CSPM应用通用框架、监管要求和企业政策,主动或被动地发现和评估云服务配置风险,并提供修复选项。例如,若阿里云OSS服务被错误地设置为公共读写权限,CSPM会检测出这种不当配置并提供修复建议。CSPM的核心功能包括实时配置检测、基于上下文的优先级排序、多云支持及自动修复选项,帮助企业及时发现并解决配置不当问题。
485 1
2024 年 CSPM 产品该具备哪些能力?
|
负载均衡 Java 网络架构
Spring Boot与Netflix Eureka的集成
Spring Boot与Netflix Eureka的集成
|
人工智能 安全 搜索推荐
低代码平台的坑有哪些?
低代码平台的坑有哪些?
308 0
|
前端开发 数据安全/隐私保护