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

CF VP 记录

CF2129

B

因为是排列所以我们可以从小到大考虑每个数。对于一个数,如果不变那么贡献是前面比它大的数个数,如果改变那么贡献是后面比它大的数的个数,取最小值即可。

C

首先我们得找到一个确定的括号,这样我们才可以判断。因为题目保证至少有一个 ( 和一个 ) 所以字符串中至少有一个 () 或者一个 )(,考虑前者贡献为一,后者无贡献于是考虑二分找即可。这里需要用掉 \(1+\left\lceil\log_2n\right\rceil=11\) 次查询。

C1

考虑还有 500 多次查询所以我们每次确定 2 个位置即可。我们考虑一个形如下面的查询:

( ( i j ( j i

我们分讨一下 4 种取值对应的结果即可。

C2

我们尝试让每次询问确定更多的位置,考虑一组形如 (((iii 的查询,其取值要么是零要么是长度的一半,我们状压一下就可以每次查询 8 个位置,因为有 \(7+\sum_{i=0}^82^i=518\) 如果再大就超过限制了。这样一共需要查 \(11+\left\lceil n\over 8\right\rceil=136\) 次。

C3

上面我们考虑括号嵌套的查询,其实我们还可以让括号并排,这样能构造出形如下面的东西:

( i ( i ( i ( ( j ( j ( j ( ( k ( k ( k

每次一个位置所带来的贡献要么为零要么为 \(cnt\times(cnt+1) \over 2\),考虑构造出不同的 cnt 保证每种组合唯一。可以构造出如下的 cnt 序列:

1,2,3,5,7,10,15,21,30,43,61,87,123

最后我们一次查询能够确定 13 个位置,总询问次数为 :\(11+\left\lceil n\over 13\right\rceil=88\)

D

神秘计数题我们考虑先去寻找性质,然后通过性质入手。

我们先去考虑一个位置 \(i\) 被贡献的情况,不考虑其他位置,于是左右对称,我们考虑左边。首先染色的位置应该从远到近,否则就贡献不到当前考虑的位置。然后考虑我们贡献的上限能是多少。最近的位置肯定是 \(i-1\),下一个不能是 \(i-2\),因为这时我们 \(i-1\) 的贡献就会给 \(i-2\),于是下一个位置实际是 \(i-3\)。再下一个呢?经过实践我们发现是 \(i-7\)。发现了吗?每次能作贡献的最右端点形如 \(i-2^k+1\),所以每个位置的贡献上界是 \(\log\) 的。

然后我们考虑一个位置被填了后,左边的位置显然不能贡献到右边去了,所以一个问题就被简化成了子区间,于是我们肯定是往区间 dp 的方向思考。所以首先我们的状态有 \(f_{i,j}\) 表示区间 \([i,j]\) 的答案,但是显然这样没法进一步转移,所以我们需要增加限制。因为我们转移的时候肯定要去枚举那个划分的位置,考虑那个位置对外置位做的贡献以及那个位置得到贡献的情况。考虑新划分出来的两个子区间肯定对划分位置有贡献,于是我们重新定义 dp 状态。设 \(f_{i,j,x,y}\) 表示考虑到了区间 \([i,j]\) 并且区间内没有染色,但是 \(i-1\)\(j+1\) 已经被染色,区间对 \(i-1\) 的贡献为 \(x\),对 \(j+1\) 的贡献为 \(y\)

转移的时候我们枚举了划分位置 \(k\),考虑 \(k\) 对外置位的贡献。如果 \(k\) 在区间左半部分,那么会对 \(i-1\) 有 1 的贡献;否则对 \(j+1\) 有 1 的贡献。枚举的时候注意减掉。然后两个子区间对 \(k\) 的贡献就枚举一下即可。注意因为是统计排列数,考虑两个子区间独立,于是在排列中只要相对顺序正确即可,所以还要带一个组合数 \(j-i\choose k-i\)。最后转移就是 \(f_{i,j,x,y}\leftarrow f_{i,k-1,x't}\times f_{k+1,j,q,y'\times{j-i\choose k-i}}\)。时间复杂度 \(\mathcal O(n^3\log^3n)\)

E

发现单次的修改是简单的,但是跟边数有关。注意到 \(n,m\) 同阶于是考虑对 \(m\) 分块跑莫队。然后注意到正常用平衡树是 \(\mathcal O(q\sqrt m\log n)\) 的修改加上 \(\mathcal O(q\log n)\) 的查询,于是考虑值域分块平衡复杂度。注意如果直接按照度数分块可能出现很多点度数为零导致块长爆炸,于是我们按照度数加点数分块,于是就是 \(\mathcal O(q\sqrt{n+m})\) 的。

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

相关文章:

  • 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 字典树
  • CF1450E Capitalism
  • 二分图最大匹配 匈牙利算法
  • 2025 年脱硫剂厂家 TOP 企业品牌推荐排行榜,氧化铁,羟基氧化铁,常温氧化铁,沼气,天然气,煤气,煤层气,液化气,二氧化碳,氨气脱硫剂公司推荐