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

2025.10.2 测试

烤柿题,简单
zelensky 和 haochangjian 的

1.

AT_abc237_g [ABC237G] Range Sort Query

经典 trick ,考虑我们不关心其他数的位置

所以把 > x 的赋成 1,否则为 0

这样之后排序就变成区间覆盖

以及需要维护 0 的个数

线段树简单做,不要想根号

2.

AT_agc038_f [AGC038F] Two Permutations

题意转化很简单

每个置换环要么不动,要么一起动

将其缩点后,贡献变成类似两个环同时选可以获得 ... 贡献

显然网络流

然后这个很像文理分科,但不一样,为了处理不同环的贡献,不要想拆点

然后这个其实是可以直接连的

我懒得写了

我们发现情况分为 5 种:

  • \(P_i=Q_i​=i\),此时必然 \(A_i​=B_i\)​。
  • \(P_i​=i,Q_i!=i\),当且仅当 \(q_i\)​ 被拆分时 \(A_i​=B_i\)​。
  • \(P_i​!=i,Q_i​=i\),当且仅当 \(p_i\)​ 被拆分时 \(A_i=B_i\)​。
  • \(P_i​!=Q_i​,P_i​!=i,Q_i​!=i\),当且仅当 \(p_i​\)\(q_i​\) 都被拆分时 \(A_i​=B_i\)​。
  • \(P_i​=Q_i​!=i\),当且仅当 \(p_i\)​ 和 \(q_i\)​ 都被拆分或都不被拆分时 \(A_i​=B_i​\)

我们设 \(p_i\)​ 被拆分时在 \(S\) 集合中,\(q_i\)​ 被拆分时在 \(T\) 集合中,建出最小割模型。

  • \(P_i​=Q_i​=i\),必定耗费 \(1\) 代价。
  • \(P_i​=i,Q_i​!=i,q_i\)​ 在 \(T\) 集合中耗费 \(1\) 代价,\(S\)\(q_i\)​ 连边权为 \(1\) 的边。
  • \(P_i​!=i,Q_i​=i,p_i\)​ 在 \(S\) 集合中耗费 \(1\) 代价,\(p_i​\)\(T\) 连边权为 \(1\) 的边。
  • \(P_i​!=Q_i​,P_i​!=i,Q_i​!=i,p_i\)​ 在 \(S\)\(q_i​\)\(T\) 耗费 \(1\) 代价,\(p_i\)​ 向 \(q_i\)​ 连边权为 \(1\) 的边。
  • \(P_i​=Q_i​!=i,p_i\)​ 和 \(q_i\)​ 在不同集合耗费 \(1\) 代价,\(p_i\)​ 和 \(q_i​\) 互连边权为 \(1\) 的边。

然后跑最小割即可。

由于是二分图单位边权,时间复杂度 \(O(n \sqrt{n}​)\)

3.

AT_abc305_g [ABC305G] Banned Substrings

一眼板纸

字符串长度很小,暴搜或 AC 自动机都行

然后写出 dp 矩阵优化即可

4.

AT_abc282_h [ABC282Ex] Min + Sum

柿子中有 min

考虑序列分治

然后板纸没了

刚开始觉得一个 log ,是双指针套双指针,但写着写着发现不单调

没事,用个 lower_bound 就行了

两个log , 但第二个 log 跟现在处理的长度有关,超级小

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

相关文章:

  • 数学章节总结
  • 软件工程_作业一
  • CF VP 记录
  • LabVIEW与PLC 汽车驻车制动自动调整 - 实践
  • 04. 布局管理
  • 关于安装博客园皮肤中有关于配置音乐播放器的补充(awescnb)
  • AGC VP 记录 2
  • 2025 --【J+S 二十连测】-- 第四套 总结
  • Websocket+cpolar:如何轻松实现服务远程访问? - 教程
  • 如何用C语言实现5种基本的排序算法
  • 函数-装饰器基础知识+推导式
  • VUE - 实战 2
  • QBXT2025S刷题 Day1
  • 2025多校冲刺CSP模拟赛1(螳臂复活祭)
  • mobvista三月之旅(In Peking)
  • 大学生HTML期末大作业——HTML+CSS+JavaScript购物商城(草莓) - 指南
  • P6782 [Ynoi2008] rplexq
  • AT_agc040_b [AGC040B] Two Contests
  • AT_arc084_b [ABC077D] Small Multiple 题目分析
  • 287. 寻找重复数
  • 福州市 2025 国庆集训 Day2 前三题题解
  • 2025 年马赛克厂家 TOP 企业品牌推荐排行榜,陶瓷,游泳池,喷墨,冰裂,拼花,防滑,复古,家装马赛克推荐这十家公司!
  • oppoR9m刷Linux系统: 手动备份系统与基带IMEI/NVRAM/QCN
  • 原来你是这样的claude code aciton:没想象中好
  • 实用指南:【Python】正则表达式
  • FlareOn1 -- 5get_it
  • 2025 年阀门厂家 TOP 企业品牌推荐排行榜,管道阀门,气动,调节,电动执行器,生产,电磁,不锈钢,进口,耐高温阀门推荐这十家公司
  • 深入解析:Ceph 分布式存储学习笔记(二):池管理、认证和授权管理与集群配置(下)
  • tcp与udp 协议 - 摘星
  • 赛前训练4 extra 字典树