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

2025多校CSP模拟赛2

2025多校CSP模拟赛2

狂写大树套树通过 \(T3\) 的救赎感。

T1 查询

第一眼感觉不好做。

首先直接找绝对没前途,考虑二分 \(v\)

问题变成了统计 \(a_j+b_j\times c_i\le v\) 的数量,变换一下变成:

\[c_i\le \frac{v-a_j}{b_j} \]

发现可以更换为向下取整,那么对于每个 \(c_i\) 直接二分找到所有合法点对即可。

复杂度 \(O(n\log n\log V)\)

T2 参加

写了一个迷幻代码,挂了。

本来没觉得赛时代码能过样例,但是过了,就没管了。

发现区间加可以变为差分上两个点一个加一个减,那么答案就是加法和减法的 \(max\)

那么直接 \(dp\)(其实没必要)。

枚举作为中间点的是哪个,然后求出让左边差分全部变为正的代价,和右边全部变为负的代价,取个 \(max\) 就好了。

复杂度 \(O(n)\)

T3 决斗

比较神秘的题。

首先随意求出一个方案是显然的,那么如果我们以位置从小到大构造最优答案,其实就已经包含了一个性质就是得分点不可能在变为失分点。

所以可以对于每个位置向后找到每个使得交换两个位置的卡牌不影响得分的位置,那么在这些位置中找到最大的一个交换即可,可以证明是正确的。

这样就做出了一个 \(O(n^2)\) 的做法。

考虑怎么优化,先分讨当前点的得分情况。

\(a_i\) 表示柯南出的牌,\(pos_i\) 表示青蛙出的牌。

钦定 \(pos_j\ge pos_i\) 不然一定不优。

\(a_i < pos_i\) 得分

此时 \(a_i < pos_j\) 那么也会得一分。

那么如果 \(j\) 不得分,则可以任意选取。

如果 \(a_j < pos_j\) 此时要满足 \(a_j < pos_i\)

\(a_i \ge pos_i\) 不得分

如果 \(j\) 也不得分,那么可以随意选取。

否则分为两种情况:

  1. \(a_j\ge pos_i,pos_j>a_i\)
  2. \(a_j<pos_i,pos_j\le a_i\)

如果将 \((a_i,pos_i)\) 看做一个点,那么问题竟然变成了二维数点问题!

直接上树套树就做完了。

代码并不好写,应该没人想这么写......

T4 回文串问题

好题。

首先假设所有数不相等,将回文串拼在原序列后面,发现相等关系构成了 \(n\) 个等价类,那么只可能有 \(n-1\) 次合并。

如果此时我们只合并有意义的修改,那么复杂度就有保证了。

那么可以使用二分哈希找到所有不相等的地方,用一个数据结构维护一下就好。

然后等价类间的合并可以使用启发式合并,这样复杂度就是 \(O(n\log^2n)\)

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

相关文章:

  • 详细介绍:深入了解linux网络—— 基于UDP实现翻译和聊天功能
  • Rewind: Codeforces Round 1055 (Div.1+Div.2)
  • 10.4模拟赛总结
  • 01.linux基础
  • 英语完形填空
  • 2025整体橱柜厂家TOP企业品牌推荐排行榜,云南昆明整体橱柜全瓷砖,开放式厨房,经济型,一站式无烟柴火灶,嵌入式,智能,多功能,全屋无烟柴火灶整体橱柜公司推荐
  • Centos7安装mysql8
  • vite-vue3脚手架(参考帝莎编程-后台管理系统开发)
  • 上传文件的后端程序handleFileUpload()、getOriginalFilename()、UUID
  • 从模拟入侵到渗透测试:我摸清了黑客的套路,也懂了企业的软肋 - 详解
  • 同样的Python代码,在Windows上运行没有错误,在Linux Centos上运行出行错误。
  • FreeBSD 14发布后的技术问题解析
  • handleFileUpload()
  • 实用指南:Typescript高级类型详解
  • 集合幂级数,FMT 与 FWT 学习笔记
  • 2025多校CSP模拟赛1
  • 上传文件前端需要注意的三个点:
  • AT_arc189_b [ARC189B] Minimize Sum
  • Jenkins安装与配备
  • 2025-10-04 60S读世界
  • 适合新手的PPT模板网站,简单操作但效果好!
  • 2025多校冲刺CSP模拟赛2 总结
  • pip list 可以查到某个包,但是,import某个包,出现 ModuleNotFoundError: No module named
  • 详细介绍:conda使用指南
  • 探索 Docker/K8s 部署 MySQL 的创新实践与优化技巧 - 详解
  • 基于Registry搭建docker加速镜像服务
  • mssql 无锁读取
  • 2025年四川大学计算机学院专硕考研经验分享
  • 基础数学拾遗
  • 2025多校冲刺CSP模拟赛2(普通的颓唐)