专栏文章

关于我让deepseek给我出了一套noi试题这档子事

qqsn123
科技·工程参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq8r5an
此快照首次捕获于
2025/12/04 00:48
3 个月前
此快照最后确认于
2025/12/04 00:48
3 个月前
查看原文
下面是题目描述和时间，空间限制以及deepseek给出的大致解法，各位大神可以看看可不可做，合不合理。

D1T1:动态树统计

题目描述
给定一棵有根树(n≤1e5)(n \le 1e5)，每个节点有权值。要求支持两种操作：
  1. 将路径 u→vu→v 上所有节点权值增加k
  2. 查询子树uu内权值的中位数
输入输出要求
操作次数 m≤1e5m \le 1e5，强制在线，时间限制2s
解法思路
树链剖分+线段树+权值线段树二分。维护DFS序子树区间，路径修改用重链剖分，中位数查询通过权值线段树上二分实现。

D1T2:矩阵覆盖

题目描述
在 n×mn \times m 矩阵中放置L型骨牌（覆盖 33 格），要求严格覆盖所有格子且不允许重叠。求合法方案数模1e9+71e9+7。
n,m≤20n,m \le 20，时间限制3s3s
解法思路
轮廓线DP+状态压缩。设计 1313 进制状态表示当前行和前一行覆盖状态，状态转移时枚举L型块的 66 种放置方式。预处理合法转移，使用滚动数组优化空间。

D1T3:时空穿梭

题目描述
给定有向图(n≤5e4，m≤2e5)(n \le 5e4，m \le 2e5)，每条边有时间偏移量 wi(−1e9≤wi≤1e9)w_i(-1e9 \le w_i \le 1e9)。
定义一条路径的时空稳定性为路径总时间偏移量的相反数(即 −∑wi- \sum w_i)。
若路径的时空稳定性严格小于0 ，则判定为悖论状态。
求从起点 ss 到终点 tt 的所有路径中，满足以下条件的路径：
  1. 不处于悖论状态
  2. 在满足条件1的前提下，经过的边数最多
若存在无限条可行路径（即存在可无限重复的合法环），输出 INF，否则输出最大边数。
输入输出
保证图中无重边自环，时间限制3s
解法思路
将问题转化为带约束的最长路径问题,定义状态 dpu,kdp_{u,k} 表示到达节点 uu 时经过 kk 条边条边的最小总时间偏移量，动态维护每个节点的可能边数层级，预处理所有强连通分量，若某个SCC满足条件且该SCC能到达终点 tt，则答案为INFINF。使用合理剪枝来提高运行效率，使用双端队列优化SPFA。

D2T1:异或金字塔

题目描述
构造高度 nn 的金字塔，每层是长度为 kk 的 0/10/1 序列，满足：
  1. 第 ii 层恰有 aia_i 个 11。
  2. 相邻层对应位置异或和为 11。
求构造方案数模 998244353998244353。
(n≤1e5，k≤20)(n \le 1e5，k \le 20)
解法思路
矩阵快速幂优化递推。发现每层状态由上一层唯一确定，问题转化为首层状态数。预处理转移矩阵，通过矩阵快速幂计算可行初始状态数。

D2T2:量子纠缠

题目描述
nn 个粒子排成环，每个粒子有状态 0/10/1。每次操作选择相邻三个粒子，将中间粒子状态翻转。求至少多少次操作可使全环变为 00。(n \le 1e3)，时间限制 2s2s。
解法思路
环形线性方程组+高斯消元。将操作建模为异或方程组，发现方程秩为 n−1n-1，枚举自由变量计算最小操作次数。使用bitsetbitset优化消元过程。

D2T3:星间航路

题目描述
在三维空间中有 nn 个星门（坐标互异），建立航路需满足：
  1. 航路不相交
  2. 形成生成树
求建立航路的方案数模 1e9+71e9+7。
n≤200n \le 200，时间限制 5s5s。
解法思路 LGV引理+矩阵行列式计算。将三维投影到二维保证无交点，转化为求有向生成树计数。通过Kirchhoff矩阵求行列式，处理符号问题后取绝对值。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...