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

20251021 NOIP模拟赛

T2

题目大意;

有一棵大小为 \(n\) 的树和 \(m\) 个关键点,你要从这 \(m\) 个关键点中随机选择 \(k\) 个点,问这 \(k\) 个点两两之间最长距离的期望是多少。
\(n \le 2000, m \le 300\)

解题思路:

最暴力的做法肯定是直接 dp,但时间复杂度是 \(O((nm)^2)\) 起步的,所以我们考虑使用 “最长距离” 的性质。
我们单独把这 \(k\) 个点的生成树抠出来,那么最长距离显然等价于直径。

我们考虑枚举 \((u,v)\) 字典序的直径,只需要计算方案数,但我们有一个特殊的性质,那就是树的直径的两个端点对于每一个点都是最远的。

那么任意一对点,你只需要判他们到我们枚举的直径是否大于直径即可。
\(O(m^3)\)

这是本题的特殊性质,遇到 dp 复杂度太高的计数题,可以去观察 dp 的条件的特殊性来优化之间复杂度。

T3

题目大意:

有一个大小为 \(n\),边数为 \(m\) 的仙人掌,求他的邻接矩阵的行列式。
\(n \le 10^5\)

解题思路:

我们发现行列式枚举的 \(p\) 的置换环在仙人掌中必须也是环,包括二元环。
相当于从仙人掌里找到几个不交的环,算他们的贡献。
套路地,圆方树上做树形 dp。
现在唯一的难点变成了怎么算 \(2^{inv(p)}\),而且我们现在只知道每个环长,希望对他俩进行一个转化。
考虑在一个排列中,每次交换任意两个相邻的数会将逆序对变化 1,而且也会对置换环的个数变化 1。

由于 \(-1\) 的幂只和奇偶性有关系,所以我们发现 \((-1)^{inv(p)} = (-1)^{n - cyc(p)}\)
\(O(n)\)
这题最后一步还是很有意思的,就是如何将我们未知的转化成我们已知的。

T4:

题目大意:

你要将 \(n\) 个石子分到 \(k\) 堆里,然后两人流操作,每个人可以选择至少一堆,至多 \(m\) 堆并取任意数量的石子,求第一个人获胜的不同的分法。
\(n \le 10^4, k \le 10^3\)

解题思路:

还是太不敢猜了。
考虑 \(m = 1\) 时,就是经典 \(Nim\) 游戏,然后你设 \(dp_{i,j,0/1}\) 表示考虑了二进制前 \(i\) 位,和为 \(j\),异或值是否不为 0 的方案数。
然后我们希望将 \(nim\) 的结论推广出去,先考虑最经典的 \(nim\)

我们胜利的条件为:他们整体的二进制位下,并非每一位的 1 的出现次数为 2 的倍数的方案。

那么考虑将 \(2\) 替换成 \(m + 1\),这就是这个题。

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

相关文章:

  • 关于2025年暑假自主巡航小车脚本文件的学习笔记
  • 欧拉操作系统搭建docker
  • xcode程序创建文件存储位置
  • RocketMQ+Spring Boot的简单实现及其深入分析
  • RFSOC学习记录(五)带通采样定理
  • 3dmax下载安装教程及激活教程(附安装包)3dmax2025超详细下载安装步骤
  • LLM 场景下的强化学习技术扫盲
  • vmware虚拟机下载安装教程(付安装包)详细图文下载安装教程
  • deepin 25 虚拟机安装vgpu客户机驱动
  • NXP S32K118的FTM模块分析
  • 66页作业
  • 写电商详情页不用挠头了:一个还算实用的AI指令模板
  • CF2153D
  • 20232417 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • iPhone口袋状态检测技术揭秘
  • 搜维尔科技:IROS 2025现场,触觉力反馈、数据手套遥操作机器人灵巧手平台系统解决方案
  • 一些题解
  • Node.js JSON import attributes All In One
  • DeepSeek的“认知提纯”能力解析
  • 梦熊知更鸟赛水题题解合集 (两个人的演唱会 使一颗心免于哀伤 空气蛹)
  • CF2154D
  • Plya 定理学习笔记 | ABC428G 题解
  • 第十八天
  • 第十七天
  • vue3+elementPlus el-date-picker 自定义禁用状态hook 建立结束时间不能小于开始时间
  • [优先队列] P3611 [USACO17JAN] Cow Dance Show S 题解
  • 搜维尔科技将携手Xsens|Haption|Tesollo|Manus亮相IROS 2025国际智能机器人与系统会议
  • 【做题记录】贪心--提高组
  • 如何炫酷地使用集合划分容斥
  • 简单云计算算法--20251023