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

ROIR 2025

ROIR 2025

https://www.luogu.com.cn/problem/list?type=luogu&page=1&tag=479|62

二维蚱蜢

先贪心地往右上跳,跳到某维坐标与终点相同,再横着或竖着跳。

不完全质数

意义不明。

显然满足条件的数的形态是,恰有一位上的数字是质数,其余为 \(1\)

直接数位 dp。

酸雨

对于每个位置,其积水量为 \(\min(p_i,s_i)-h_i\)\(p_i\)\(s_i\) 分别表示其所在段内的前缀、后缀最大值,转化一下得到 \(p_i+s_i-\max(p_i,s_i)-h_i=p_i+s_i-h_i-H\)\(H\) 表示所在段的最大值。

分别维护这四个东西,\(h_i\)\(H\) 是非常简单的,而 \(p_i\) 在合并的过程中,右边的那段的前缀最大值数组,会有一段前缀变为左边那段的最大值,可以用线段树区间覆盖/求和维护,\(s_i\) 把序列反过来同理能做。

寻找宝藏

锻炼码力。

相邻两次结果作差分可以得到 一条斜线+一竖列 的数量情况。

\(i\) 扫描仪的情况可以由第 \(i-1\) 列的从内到外 \(k-1\) 条斜线的情况拼上第 \(i\) 列这一列单独的选择情况,可以 \(2^k\) 枚举,所以直接设计高维状压 dp 转移就行了。

平方差

\(x^2-y^2=d\),平方差公式得到 \((x+y)(x-y)=d\)\(O(\sqrt{d})\) 枚举 \(d\) 的因数(\(a,b\) 满足 \(ab=d\)),然后解方程。

不平衡划分

意义不明。

观察到选择的一定是一段区间作为最大值,一个长度为 \(1\) 的区间作为最小值。

这个东西随便维护,同时注意特判 \(k=2\) 后就可以过了。

个人 OI 比赛的原则

板子。

第一问,01 背包模板。

第二问,从最终状态往回 dfs,vector 记录方案,回溯时 pop_back 即可。

旅行路线

转化为从 \((1,1)\) 出发到 \((n,m)\) 的两条不相交路径。

肯定是一条为 \((1,2) \to (n-1,m)\) 的路径和一条为 \((2,1)\to (n,m-1)\) 的路径。

考虑单步容斥,用可能相交的方案数减去必相交的方案数。

既,用不限制相交,\((1,2) \to (n-1,m) \land (2,1)\to (n,m-1)\) 的方案数减去 \((1,2) \to (n,m-1) \land (2,1)\to (n-1,m)\) 的方案数(这个一定相交)。

求方案数,将点按 \(x+y\) 排序,二维 dp 转移。

dp 的设计和转移比较有价值。

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

相关文章:

  • trick 小记
  • python编写AI生常用匡架及使用指令集
  • 123123
  • 1005模拟赛总结
  • 2025.10.5 2024CCPC郑州
  • 20250531MATLAB三维绘图 - 教程
  • 概率期望dp 复习笔记
  • 2025.10
  • PCIe扫盲——物理层逻辑部分基础(一)
  • 仅需3%训练数据的文本归一化技术
  • 价值原语博弈协议:价值原语共识锚定原则
  • 实用指南:工作流引擎-16-开源审批流项目之 整合Flowable官方的Rest包
  • 25fall做题记录-October - Amy
  • 嗯嗯
  • PCIe扫盲——AckNak 机制详解(二)
  • ASP.NET Core SignalR 身份认证集成指南(Identity + JWT) - 详解
  • utorrent 2.2.1
  • 2025热缩管厂家 TOP 企业品牌推荐排行榜,氟橡胶,双壁,线缆标识,防滑花纹,DR 耐油橡胶,PVDF,标识,航插用,军用热缩管公司推荐!
  • 市场交易反心理特征之八:劣仓驱逐良仓
  • 做题笔记18
  • 2025桩基检测机构最新企业咨询服务推荐排行榜,海上桩基检测,水上桩基检测服务推荐这十家公司!
  • 算法坑点
  • [省选联考 2025] 图排列 题解
  • Windows下安装并采用kubectl查看K8S日志
  • 实用指南:UV 包管理工具:替代 pip 的现代化解决方案
  • C/C++与Java、Python、Go在各个阶段的区别
  • 古典密码之凯撒密码
  • vi/vim文本编辑器
  • AI一周资讯 250926-251005
  • B3869 [GESP202309 四级] 进制转换-题解