2023-08-26 17:00 南京外国语学校算法工程师发布于江苏

关注

C. Kevin的七彩旗 without dp

Kevin的七彩旗

https://ac.nowcoder.com/acm/contest/63804/C

看到官方解法是 DP 于是回来补个档，我没用 DP，看不懂 DP 的可以看看这个题解。

提示 1：分段一定是分成若干个 $\{i,i 1,i 2,i 3,\dots\}$ 的序列。

提示 2：我们发现拼接数列的时候，如果两个数列元素有重叠不影响可行性；如果不是完全包含也不影响最优性。

所以我们直接找出，对于每个元素，它能直接连到后面的最大元素。我们设为 $f(i)$ ，那么拿样例来举例子， $[2,1,4,5,6,7,3,4,1,2]\to[2][1][4,5,6,7][3,4][1,2]$ ， $f=\{2,2,4,7,7,7,7\}$ 。

注意到，虽然在 $[1]$ 这一段中 $1$ 只能到 $1$ ，但是它在 $[1,2]$ 中可以到 $2$ ，所以 $f(1)=2$ 。

我们考虑对 $x$ 初值为 $1$ ，不断进行 $x\gets f(x) 1$ 的迭代，迭代次数就是答案，如果迭代永远无法到达 $m$ 就是 $-1$ 。

Code

全部评论

推荐最新楼层

zhangas

山东科技大学 C++

很巧的方法，感谢分享

点赞回复分享

发布于 2023-08-26 18:44 山东

04-03 22:35

已编辑

广东工业大学 Java

美的JAVA 暑期实习线下二面

线下选了广州 面试地点在华工五山校区二面是HR面1、实习经历大概说说？2、遇到什么困难？3、对美的什么看法？4、为什么选择这个行业？5、加班和出差?6、在校经历？有学生会经历吗？7、在学生会遇到了什么问题？怎么解决的？如果从头再来会怎么解决？8、读硕的时候情况如何？小论文发了吗？反问：1、培养体系怎样？2、结果最早什么时候出？ 下周开始出结果很轻松 面试官很和蔼 没有压力 面试官说最快一周内OC 许愿Offer

查看8道真题和解析

点赞评论收藏

03-29 16:49

多益网络-游戏策划-面经

游戏经历部分一定要好好写！！！面试时候大部分题材都是从里面挑的写了精通的游戏最好都自己先整理一下思路（只准备了MMO的，结果问了别的，导致所有问题都是现场想的思路有点乱）一面专业面（40+分钟）3.261 自我介绍2 无畏契约精通到什么程度3 有玩过cs的话，精通到什么程度（游戏经历里写了）4 同属于FPS竞技类，两者有什么区别5 PUBG和APEX，两者有什么区别 （也是游戏经历里写了，还好是真玩了挺久的）6 APEX和无畏契约同属英雄射击类有什么差异7 这两个游戏的技能和枪械射击有什么联动8 技能和射击体验占比应该怎么调整9 对一个在开发中的游戏如何做数值平衡10 命运2里有什么设计的比较...

多益网络一面77人在聊

点赞评论收藏

03-11 16:30

武汉工商学院财务

有没有老板看看我啊

点赞评论收藏

03-25 19:00

东北大学 Java

这还能冲后端吗😅

后端卷飞了，到时候一个offer没有还不如去客户端了😅

程序员牛肉：太好了，是聊天记录。不得不信了。当个乐子看就好，不要散播焦虑

点赞评论收藏

03-30 19:03

联想_产品经理(准入职员工)

联想内推，联想内推码

联想超超全投递攻略来啦，手把手教你从网申到offer的全流程，全流程跟进，欢迎各位找我内推👇先上内推码：2025XZLMWWY内推码填写指南：其他＞从哪获取招聘信息＞选择联想员工推荐＞输入 2025XZLMWWY如果投递前有任何信息不能修改请及时与我联系一、招聘项目介绍1. 面向对象（春招&暑期实习）✅ 对象：2025届毕业生（毕业时间2024.9.1-2025.8.31）2026届暑期实习生（毕业时间2025.9.1-2026.8.31）25，26届都有岗位✅ 流程：网申→能力测评/技术测评→面试→offer敲重点：26届暑期实习没有笔试，只有测评，有及格线，不高，大家正常做没问题...

联想公司氛围 260人发布

点赞评论收藏

全站热榜

创作者周榜

正在热议

# 毕业季，你想好怎么跟生活对线了吗？ #