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

· · 科技·工程

下面是题目描述和时间，空间限制以及deepseek给出的大致解法，各位大神可以看看可不可做，合不合理。

D1T1:动态树统计

题目描述

给定一棵有根树(n \le 1e5)，每个节点有权值。要求支持两种操作：

  1. 将路径 u→v 上所有节点权值增加k

  2. 查询子树u内权值的中位数

输入输出要求

操作次数 m \le 1e5，强制在线，时间限制2s

解法思路

树链剖分+线段树+权值线段树二分。维护DFS序子树区间，路径修改用重链剖分，中位数查询通过权值线段树上二分实现。

D1T2:矩阵覆盖

题目描述

在 n \times m 矩阵中放置L型骨牌（覆盖 3 格），要求严格覆盖所有格子且不允许重叠。求合法方案数模1e9+7。

n,m \le 20$，时间限制$3s

解法思路

轮廓线DP+状态压缩。设计 13 进制状态表示当前行和前一行覆盖状态，状态转移时枚举L型块的 6 种放置方式。预处理合法转移，使用滚动数组优化空间。

D1T3:时空穿梭

题目描述

给定有向图(n \le 5e4，m \le 2e5)，每条边有时间偏移量 w_i(-1e9 \le w_i \le 1e9)。

定义一条路径的时空稳定性为路径总时间偏移量的相反数(即 - \sum w_i)。

若路径的时空稳定性严格小于0 ，则判定为悖论状态。

求从起点 s 到终点 t 的所有路径中，满足以下条件的路径：

  1. 不处于悖论状态
  2. 在满足条件1的前提下，经过的边数最多

若存在无限条可行路径（即存在可无限重复的合法环），输出 INF，否则输出最大边数。

输入输出

保证图中无重边自环，时间限制3s

解法思路

将问题转化为带约束的最长路径问题,定义状态 dp_{u,k} 表示到达节点 u 时经过 k 条边条边的最小总时间偏移量，动态维护每个节点的可能边数层级，预处理所有强连通分量，若某个SCC满足条件且该SCC能到达终点 t，则答案为INF。使用合理剪枝来提高运行效率，使用双端队列优化SPFA。

D2T1:异或金字塔

题目描述

构造高度 n 的金字塔，每层是长度为 k 的 0/1 序列，满足：

  1. 第 i 层恰有 a_i 个 1。

  2. 相邻层对应位置异或和为 1。

求构造方案数模 998244353。

(n \le 1e5，k \le 20)

解法思路

矩阵快速幂优化递推。发现每层状态由上一层唯一确定，问题转化为首层状态数。预处理转移矩阵，通过矩阵快速幂计算可行初始状态数。

D2T2:量子纠缠

题目描述

解法思路 环形线性方程组+高斯消元。将操作建模为异或方程组，发现方程秩为 $n-1$，枚举自由变量计算最小操作次数。使用$bitset$优化消元过程。 ### D2T3:星间航路 题目描述 在三维空间中有 $n$ 个星门（坐标互异），建立航路需满足： 1. 航路不相交 2. 形成生成树 求建立航路的方案数模 $1e9+7$。 $n \le 200$，时间限制 $5s$。 解法思路 LGV引理+矩阵行列式计算。将三维投影到二维保证无交点，转化为求有向生成树计数。通过Kirchhoff矩阵求行列式，处理符号问题后取绝对值。