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

古代史

P9034 「KDOI-04」Again Counting Set

第三条限制非常强,如果 \(\min \neq 0\),那么其它所有数都必须为 \(1\),也就是集合中的数全是 \(1\),这样,\(\min+\max+\operatorname{mex}=2\),因此集合大小必须为 \(2\)

否则,\(\min=0\),那么在第四个限制的式子中 \(\min\) 不贡献。考虑 \(\max\) 和集合中的 \(\max\) 会消掉一个,但是 \(\max\) 可能有多个,不好考虑,因此可以钦定 \(\operatorname{mex}<\max\)\(\operatorname{mex}>\max\) 算,先看小于的,\(\operatorname{mex}=i\) 说明 \(0 \sim i-1\) 都出现过,和至少为 \(\frac{i(i-1)}{2}\),因此 \(\frac{i(i-1)}{2} \le i\),解得 \(i \le 3\),那么就只需要分类讨论即可,必须有一个大于 \(i\)\(\max\),其他的就应该是 \(0\)。大于的也类似,\(\operatorname{mex}=i\) 可以直接推出 \(\max=i-1\),那么也是分讨一下即可。

P9992 [Ynoi Easy Round 2024] TEST_130

对于一个合法的点 \(x\),她的贡献大致是 \(dep_w+d-dep_x+1\),这个可以扫描线轻松求出。

写一下,有 \(dfn\) 限制,\(dep\) 限制,按照 \(dfn\) 扫描线方便,那么 \(dep\) 就是前缀限制,因为子树内不会有 \(dep\) 小于根的点,用 BIT。

有的时候会有问题,对于子树内最大深度 \(< dep_w+d\) 的会多算,会多算 \(dep_w+d-Mxdep_x\),然后如果 \(Mxdep_x<dep_w+d\) 那自然 \(dep_x \le dep_w+d\),所以继续扫描线即可。卡常/tuu

[ABC244F] Shortest Good Path

考虑走一条边只会改变终点节点的奇偶性,设 \(f_{S,j}\) 表示当前状态为 \(S\),走的终点是 \(j\) 的最短路,转移是枚举 \(j\) 的临边 \(y\),走到 \(f_{S \oplus 2^y,y}\)。转移可能是有环的,这是边权为 \(1\) 的最短路,使用 bfs 即可。

[ABC244G] Construct Good Path

考虑树怎么做,首先可以按照 dfs 序放点,然后这样一个点经过的次数不对可以向他父亲走一步再走下来。这样逐次向上调整,最后只会留下根,注意到我们可以随便定终点,如果根走的次数不对可以在前一步停止,因为路径的最后一步一定是根。

对于图的情况,随便取出一个生成树做即可,大约是 \(3n\) 的。

P9871 [NOIP2023] 天天爱打卡

\(f_i\) 表示第 \(i\) 天不跑步的最大收益,有

\[f_i=d(1-i)+\max_{i-k-1 \le j<i}f_j+dj+\sum_{l_k>j,r_k <i} v_k \]

记最后那个数是 \(w_j\),扫描加入 \(r_k=i\)\(k\),影响一段区间。

一个简单的事实:跑步是为了拿奖,也就是说不拿奖肯定不会跑步,因此每次转移的 \((j,i)\) 必然是包含了至少一个区间。

假设知道要包含哪些区间,那么 \((j,i)\) 是要尽量短的。因此可能的 \(j,i\) 会是 \(l_k-1\)\(r_k+1\) 之类的。

还有一种是,由于 \(k\) 的限制,无论如何都包含不了一个区间的,但是我要转移啊,\(f_i=\max f_j-(i-j-1)d\)

两个问题:1.为什么这样不会使得同时途两个颜色?

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

相关文章:

  • matlab运行时遇到的license问题
  • HarmonyOS 5.0+ 安全加密与数据存储最佳实践指南
  • EV论文修改工作
  • HarmonyOS之设备硬件能力调用:传感器、蓝牙与定位
  • 基于HarmonyOS SDK开放能力的微博社交体验构建实践
  • web三维
  • HarmonyOS 多线程编程:Worker 使用与性能优化指南
  • 质数(埃氏筛、欧拉筛)
  • HarmonyOS数据持久化:Preferences轻量级存储实战
  • HarmonyOS服务卡片开发:动态卡片与数据绑定实战指南
  • 有理数类的问题回答
  • HarmonyOS后台任务调度:JobScheduler与WorkManager实战指南
  • 总线传输的四个阶段
  • HarmonyOS事件订阅与通知:后台事件处理
  • HarmonyOS后台任务管理:短时与长时任务实战指南
  • Kali Linux 2025.3 发布 (Vagrant Nexmon) - 领先的渗透测试发行版
  • C语言多线程同步详解:从互斥锁到条件变量
  • Browser Use调用浏览器入门
  • 安防视频监控新时代:国标GB28181平台EasyGBS的可视化首页如何重塑运维与管理体验?
  • LazyForEach性能优化:解决长列表卡顿问题
  • java函数式编程的学习01
  • Manim实现镜面反射特效
  • 25Java基础之IO(二)
  • 【P2860】[USACO06JAN] Redundant Paths G - Harvey
  • GUI软件构造
  • 企业微信客服API模式接入第三方客服系统,对接大模型AI智能体
  • react使用ctx和reducer代替redux
  • KM 乱记
  • 深入解析:B树与B+树的原理区别应用
  • linux中的服务监控,停用自动重启