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

CSP-S 考前集训

10.8-10.9:

whk

10.10

专题。

CF1798E Multitest Generator:直接做就行,发现答案至多为 \(2\)

CF2066C Bitwise Slides:我们维护那两个相同的数,再 dp。

CF431D Random Task:发现答案满足单调性,可以二分+数位 dp 简单求解。

假设 \(n_1=n,n_2=n+1\)

\([n_1+1,2n_1]=[n+1,2n]\)

\([n_2+1,2n_2]=[n+2,2n+2]=[n+2,2n]+[2n+1,2n+1]+[2n+2,2n+2]=[(n+1)<<1,(n+1)<<1]+[n+2,2n]+[2n+2,2n+2]=[n+1,2n]+[2n+2,2n+2]\)

证毕。

P4739 [CERC2017] Donut Drone

我们显然有一个 \(O(n^2 \log^2{n})\) 倍增的做法,在 \(8s\) 时限下可以通过。

考虑优化。

我们将 \(k\) 步拆为:\((sx,sy) \to (x1,1) \to (x2,1) \to (ex,ey)\)

显然 $(sx,sy) \to (x1,1) $ $ \to (x2,1) \to (ex,ey)$ 可以暴力跳

为维护 $(x1,1) \to (x2,1) $ ,我们对列建线段树,对于每个区间 \([l,r]\),记录 \(dp[p][x]\) 表示线段树第 \(p\) 个节点的 \((x,l)\) 这个点跳到 \(r+1\) 列,跳到那个点的横坐标。

在对于每个 \((x,1)\),使用倍增记录跳 \(2^k\) 圈之后跳到那个点的横坐标。

时间复杂度 \((n^2 \log n)\)

10.11

10.12

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

相关文章:

  • Arista EOS 4.35.0F 发布 - 适用于下一代数据中心和云网络的可扩展操作系统
  • 20251011 总结
  • 上课讲的部分 qoj 题记录
  • var与let
  • CSP-S 第二轮集训资料 **总结 + 专题细分精讲**_from_黄老师
  • AI元人文:迈向正负价值统一的文明架构
  • CSP-S 第二轮集训资料 **总结 + 专题细分精讲**。
  • 对抗训练提升产品搜索技术解析
  • Ubuntu Linux双网口主机实现在校园网环境下的网络共享
  • C# Avalonia 16- Animation- ExpandElement
  • DshanPI-A1 RK3576 armbian远程桌面
  • Docker安装MQTT
  • Ubuntu Linux双网卡实现在校园网环境下的网络共享
  • PVE8.x仅克隆虚拟机配置
  • 常用的sql语句
  • SQL常用语句分类及示例
  • 台式机主板上的电池要更换啦
  • 微信小程序 app.js中onLaunch中方法执行完毕后再执行index首页数据请求
  • 轻量服务器Lighthouse + 1Panel 部署.NET 8 Web应用
  • bash alias 多引号问题
  • 关于近期调研各类游戏开发引擎的一些感想
  • Electron38-Vue3OS客户端OS系统|vite7+electron38+arco桌面os后台管理
  • 终于在vim中用上了molokai的炫酷色彩配置了(゚∀゚)
  • 我是如何在Vim8.1中安装好的NERDTree插件的
  • Kafka监控工具 EFAK-AI 介绍
  • 视频拍摄技巧 - 希区柯克变焦/滑动变焦 All In One
  • 信息化说课-教学设计(6)
  • 记录:git
  • 实验1 现代C++编程初体验
  • 10.11总结