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

云斗 YDR Special# 004 S 模拟赛

拜谢大水赛。玩爽了。


[YDR Special# 004] YDSP 2025 · 云斗 CSP-S 二轮(复赛)全真模拟

链接:link
题解:暂无

时间:4h (2025.10.22 07:40~11:40)
题目数:4
难度:

A B C D
\(\color{#F39C11} 橙\) \(\color{#52C41A} 绿\) \(\color{#52C41A} 绿\)
*1000 *1600 *1900

估分:100 + 100 + 100 + 40 = 340
得分:
Rank:


场祭

读题。A 这么签,看来真的是 S 模拟赛了 /qiang

直接去开 B 了,思考 20min 无果,于是先把 A 写掉了。然后继续回来看 B,发现似乎能用 LIS 的那个 dp 来做,但是这样就无法保证回文了,于是想到可以把必须相等的地方放到一块去 dp,想到这里就容易了,LIS 的那个 dp 改改就是了,无非就是需要考虑一下必须相同的两个元素是改一个还是改两个。

关于严格递增,直接 \(a_i \gets a_i-i\) 变成单调不减就可以了。

然后开 C,发现题意可以转化成把一棵树分成几个独立集,让它们大小的前缀和数组总和最小,考虑一个在 \(t\) 时刻被选择的数 \(a_i\) 会产生 \(t \times a_i\) 的贡献,于是就可以按照时刻来 dp 了。容易注意到有一个显然的方案就是黑白染色,不过不一定是最优的,但是继续手玩发现好像并不能构造出最优的时候 \(t\) 很大的情况,根据人类直觉这也是很对的,所以直接令 \(f_{u,i,j}\) 为子树 \(u\),当前是时刻 \(i\),且 \(u\) 在时刻 \(j\) 被删掉的最小代价,然后 \(i,j \in [1,5]\)……

……写写写发现怎么大样例都过了??

看来还是要相信人类直觉的。

不过保险起见,还是把 \(i,j\) 开到了 \(8\),这样稳一点。

啊?我怎么 2h 过掉了 3 个题?这还是 S 模拟赛吗??

开 D,去想正解,似乎是一个 tarjan 状物,但是不会写,打暴力吧,好像给了不少特殊性质的呢。一开始想的 \(O(S^2)\) 暴力是枚举每个 x,跑一遍 tarjan 跑出来所有 x 到 e 的割点,但是发现异常难写,还有不少特殊情况。

然后发现根本不用啊(,直接 \(O(S)\) 枚举每个 o 并当作 x,然后从所有 e 出发 \(O(S)\) 跑个多源 bfs 不就行了!写写写,过样例了。

然后去打 \(n=1\) 的特殊性质,对着 \(O(S^2)\) 的做法拍出来一坨 corner case 之后应该是能过掉了。

不过 \(n=2\) 的 corner case 更多,最后没打出来。


补题


天依宝宝可爱!

http://www.hskmm.com/?act=detail&tid=36522

相关文章:

  • Berry.Live:开箱即用的.NET直播流媒体服务器
  • 2025年10月上海ICL医生推荐榜:王晓瑛领衔五强对比
  • doris集成vertica 数据源catalog
  • JUnit 6.0.0发布:Java 17基线、取消API与Kotlin协程支持
  • 详细介绍:老题新解|合法C标识符
  • 2025年10月消泡剂厂家推荐:权威榜单一网打尽
  • 国产化Excel开发组件Spire.XLS教程:使用Python将TXT文件转换为CSV
  • VMware Holodeck 9.0.1.0 发布 - 自动化部署 VCF 实验环境
  • [题解]meal
  • CADSoftTools发布两款重要更新:CAD VCL Multiplatform 16.2 与 CAD .NET 16全新发布
  • linux常用命令 - 实践
  • 2025年10月河道防撞护栏厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • 在 Linux 系统上安装 Miniconda、安装 Xinference,并设置 Xinference 开机自启动
  • 作业三(结对编程)-小学四则运算题目生成与判卷(Python + 可视化)
  • 无穷小比较、等价无穷小替换
  • 【项目复现上新】Karpathy大神开源GitHub高分项目NanoChat!仅用100美元+8000行代码手搓ChatGPT
  • CF2159E
  • 2025年10月景区钢丝绳护栏厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • 技术 | 在单台电脑上管理多个 GitHub 账户并解决推送问题(测试中)
  • Stable Diffusion启动提示端口错误处理
  • 阿里云API网关日志问题
  • 2025年10月半封闭滑轨丝杆模组厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • ipad协议对个人微信机器人进行二次开发
  • 西安交通大学国家级医学公关交叉平台实验室建设实拍图
  • 小程序-定义头部导航
  • 2025年10月简易丝杆模组定制厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • 2025年10月智能门窗代理厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • Android插件化框架
  • 2025 年烧结砖厂家最新推荐榜单权威发布:四川蜀陶领衔企业,全方位解决采购难题,为建筑项目保驾护航铺地砖/劈开砖/陶土窗花/古建筑砖瓦厂家推荐
  • Java使用Graphics2D绘图在图片插入中文字符放到Linux上面运行时图片中的中文会变成方框或乱码的问题