Steins;Gate模拟赛

Steins;Gate

T1.电话微波炉(暂定)

考试真的没想到这个做法

题解

先把原数组\(v\)差分一下, 我们改变原数组中的一个数$ v_i $相当于把差分数组中的第 \(i\) 个和第 \(i + 1\) 个换一下

那么我们要做的就是将差分数组重排使得最后原数组的和最大

那么 \(sort\) 一下就好了, 记得要把 \(v_{n+1}\) 也考虑进去

T2.世界线的波动

很有趣的一道计数题

题解

题目要我们求一张不存在任意一个三元组使得三元组中的两两之间距离相同的图, 图中边权均为一

转化一下问题这就是要我们求出有多少图满足任意点的度小于 \(3\) 且不包括 \(3n\) 元环的图的个数

那么这张图中就只有链和非 \(3n\) 元环了

我们考虑\(dp\), 设 \(f_i\) 表示考虑了 \(i\) 个点的总方案数, 有三种转移

  • 加入一个点并且它是孤立的
  • 加入一个点它与之前的点组成链
  • 加入一个点它与之前的点组成环

转移式子如下 \[ f_i += \begin{cases} f_{i-1} \\ f_{i - j} \cdot \binom{i - 1}{j - 1} \cdot \frac{j!}{2} \\ f_{i - j} \cdot \binom{i - 1}{j - 1} \cdot \frac{(j - 1)!}{2} \ \ \ if \ \ j \ne0\ \ (mod \ \ 3) \end{cases} \] 然后由于出题人太毒瘤了, 这个东西并不是在膜意义下的所以我们要写高精度

然后我就顺便学了一下压位高精太毒瘤辣

T3.Time Leaper

一道很水的题

题解

按照题目的意思连一下边, 然后\(Dijkstra​\)一下就好了