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

2025.10.5模拟赛

赛时

创飞了www

赛前还是给自己定了目标,事实证明,定目标对像昨天那种顺风局是有利的,然而对于今天纯逆风局是负面buff

赛时开T1,一眼区间dp,因为异或的和这种一看就不能贪心,然后也不具有局部最优性,所以赛时反复考虑的按位枚举也是错误的

发现当前区间的贡献是很好得出的

难点在于统计k个的分别贡献

事实上,应当想到多个散点可以用同一个状态来包含,然后状态更新时对于一个一个k个中的一个分别算出来所有情况

然后当区间大到可以合并为一个时,就更新答案

具体的,只考虑最左的第一个点可能包含区间的情况

然后就能包含所有情况

非常经典的区间dp套路

T2,想了1h,想到了一种图,然后倍增处理

但是发现会有环,更新的有问题

然后赛时就想了调了好久

发现还剩1h,直接炸了,也想不出别的解法

然后才看T3和T4,T3也想不出怎么暴力

想写T3的20pts,然后不会判环(事实上就用出度来更新就行)

转战T2,打了40pts,但是空间来不及算,炸了

T4赶紧打了10分,a_i<=1都来不及想了

策略绝对的失误

发现当我觉得很多都可想但是时间又紧,又没有很多分的时候,是没法静下心来想的

考虑到想一个暴力的时间很短,所以策略调整

开题,想正解没什么思路就先想暴力,然后想做法和实现(一定要想到觉得实现不复杂为止)

然后4题都又思路了,决定写题的优先级,然后开写

赛后

补了T1,思路如上

T2,想了半天,然后kh一句话点醒梦中人,就新更新的点新建一个点就行了(类似分层图最短路)

还可以线性做法,发现如果新建了点,就相当于又若干条链,然后按照l从小到大排序,双指针???(没搞明白!!!)

T3,正解

考虑到一个全都能到达环上的图的出度都大于0(这个trick之前在内向基环树的性质时想过,但没有想到

然后对于一张这样的图,我们更新答案即可

考虑到这样一张图,更新答案不好知道从哪开始更新

考虑最没有影响的边,即全图中r最大的边,因为它相当于是一个相当充分的条件,最大的限制,所以不会对答案的缩小造成影响

当点的出度为0时,相当于它的答案已经更新完毕了,可以更新别的点了

以上两种操作交替进行,就可以了

T4,还没完全会,但是前几步转化可以积累一下

看到有一个 a_i<=1 的部分分,往往具有提示意义

二分一下区间的第k大,于是就能把区间划分为0/1了

然后就分成两部分

1.判断0/1的个数是否合法

2.计算前k个0的和

具体还不太会,但是,简化了问题

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

相关文章:

  • C++/CLI
  • uboot 2020版本下gpio命令的使用
  • 盛世华诞 举国同庆|热烈庆祝 LEWISAK 英勇重创消火栓 1 周年!
  • 完整教程:<el-table>构建树形结构
  • 如何在markdown中插入折叠框
  • wqs二分
  • markdown语法详解
  • CF2115 VP 记录
  • 2-SAT模板
  • lab5
  • lab4
  • NumPy广播:12个技巧替代循环,让数组计算快40倍
  • 某中心2026年推出1111个技术实习岗位
  • 川土微变频器应用分享
  • POLIR-Society-Philosophy- Hegels 形而上学System Philosophy Dialectics 系统化哲学辩证法: 自由意志+封闭的绝对精神
  • 解决VLC 无法解码格式“h264” (H264 - MPEG-4 AVC (part 10))
  • CF2115 总结
  • luogu P8816 [CSP-J 2022] 上升点列 题解
  • CF558C Amr and Chemistry BFS解
  • Atbash密码和摩斯密码
  • Redis 中如何保证缓存与数据库的内容一致性?
  • Payload CMS:开发者优先的Next.js原生开源解决优秀的方案,重新定义无头内容管理
  • 第一次写博客
  • 07. 自定义组件
  • python语法记录
  • 2025 年储罐厂家推荐最新公司权威排行榜榜单发布,深度解析衬四氟储罐 / 硫酸储罐 / 盐酸储罐工厂选购指南
  • UnicodeEncodeError: locale codec cant encode character \u5e74 in position 2: encoding error
  • 2025 年生物除臭设备厂家最新推荐排行榜:覆盖污水处理厂 / 垃圾中转站等多场景,助力企业精准挑选优质设备
  • 2025 年球墨铸铁管公司:重庆南恩物资全品类管材供应与市政工程适配解决方案解析
  • 2025生物除臭设备厂家最新品牌企业推荐排行榜揭晓:印染厂污水,食品厂污水,污水处理厂,污水泵站,污水站,餐厨垃圾,屠宰场,厨余垃圾生物除臭设备公司推荐