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

CF Global Round 29(#2147) 总结

CF Global Round 29(#2147) 总结

A

void solve() {int x,y;cin>>x>>y;if(x<y) return cout<<"2\n",void();--x;if(y<x&&y>1) return cout<<"3\n",void();cout<<"-1\n";
}

B

可以考虑构造 \(i\) 的距离为 \(2i\),发现如下构造是合法的:

\[n,n-1,\dots,2,1,n,1,2,\dots n-1 \]

C

考虑 DP。分为四种:

  • 当前位为兔子,且兔子往左看。
  • 当前位为兔子,且兔子往右看。
  • 当前位为空,且之前有兔子往这个空位看。
  • 当前位为空,且之前没有兔子往这个空位看。

D

全是偶数的情况,先手选完,后手可以跟着选最优。因此贡献平分。

存在奇数的情况,一个奇数被选了就会转化成偶数的情况,在被变成偶数后贡献平分。

因此两人的策略就是依次选当前最优的奇数。于是按奇数个数排序即可。

E

最优答案一定是优先把一个二进制为前缀填满。考虑计算 \(f_i\) 表示把前 \(i\) 位填满的最小代价,查询时二分即可。

考虑贪心。可以从高位往低位填,每次填 \(2^j-(a_i\bmod 2^{j+1})\) 最小的位置,如果已经有 1 就可以不用填。

复杂度 \(O(n\log ^2V+q\log \log n)\)

H

看起来很奇怪的题。可以猜奇怪的结论:颜色数最多为 \(2\)

对颜色数为 \(1\) 的情况,可以建最小割树。

剩下的情况,我们让最小割为偶数。先把偶权边去掉,然后黑白染色,总有一种方案使得每个点只有偶数个同色邻点,此时有欧拉回路,则最小割为偶数。

可以高斯消元解异或方程组给每个点染色。

I1 & I2

考虑如果有一个等差数列(差为 \(1\)),那么可以从中间开始左右反复跳。

考虑拆成多个等差数列,我们需要一种方案使得任意一对等差数列都能来回跳。

考虑相邻等差数列间的距离呈指数增长,那么可以依次跳等差数列对 \((2,1),(3,2),(3,1),(4,3),(4,2),(4,1),(5,4)\dots\),即对于 \((a,b),(c,d)\) 先跳 \(a,c\) 为第一关键字、\(b,d\) 为第二关键字排序的对。

但还有一个问题,就是跳完 \((i,j)\) 后怎么切换到跳 \((i,j-1)\)。因为直接跳会使得 \(r_i\to r_{j-1}\to l_i\) 不合法。可以考虑此时从 \(r_i\) 先往右跳、再往左跳到 \(l_i-1\),这样就合法了。

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

相关文章:

  • 详细介绍:C语言中#pragma的用法
  • JAVA 中断处理
  • 第十五天
  • 软件工程学习日志2025.10.17
  • 天黑了,睡觉
  • 升鲜宝生鲜配送供应链管理系统---- 门店收银 POS 离线工作设计文档(支持线上线下一体化)---02
  • 2025.10.16NOIP模拟
  • Python 基于Python开发的数据库同步检测工具
  • 当AI学会进化:荣耀与用户的“共生式成长”新范式
  • VSCode的下载安装以及配置
  • 2025年终极公众号排版神器排行榜 最新案例研究权威测评
  • NAS安装远程协作神器twake
  • 把三门问题做成了"游戏"
  • 下一代CPU驱动高性能计算革新
  • [KaibaMath]1010 关于关于收敛数列有界性的证明
  • 卫星地图匹配定位 - MKT
  • 10.17 —— (VP) 2021icpc沈阳
  • 10.17每日总结
  • 今天宝宝进面了
  • 《大象Thinking in Projects》读书笔记1
  • 20251017
  • MT签名去除签名校验分析
  • uml
  • P3643 [APIO2016] 划艇 分析
  • day016
  • uml九图和数据流图总结
  • UpdateSourceTrigger和Mode的区别
  • NOIP2020 T2
  • Alex-VGG3
  • 第二章日志分析-redis应急响应