警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「HNOI 2013」总题解 (5/6)

RT.

旅行

题意

给一个只有 \(\pm1\) 的序列,求一个字典序最小的分割方案,把序列分成 \(m\) 段,使得每一段和的绝对值的最大值最小。

解法

不会做,咕咕咕

消毒

详见这篇

比赛

题意

\(n\) 支球队,两两只比一场。平局各得一分,赢的三分,输的零分。给出最后总得分,问有多少种可能的比赛过程。

\(3\le n\le10\),保证有解。

解法

爆搜 + 剪枝:

  • 每个人的得分不超过总分;
  • 赢了所有的比赛也达不到总分;
  • 把整场比赛的总分算出来,解出平局和分出胜负的比赛数量;
  • 然后加个记忆化,用 hash 就好了。

代码

数列

题意

\(n,k,m,p\),求长度为 \(k\) 的,两数之间差 \(\le m\) 的,最后一个数 \(\le n\) 的,递增序列的数量模 \(p\)

\(n\le 10^{18},m,k,p\le10^9\)

解法

Orz lk

考虑差分。令差分数组的第 \(i\) 项为 \(s_i\quad(0\le i<n)\)

那么答案为 \(\displaystyle\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_k=1}^m\left(n-\sum_{i=1}^{k-1}a_i\right)\)

然后推柿子:

\[ \begin{aligned} &\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_k=1}^m\left(n-\sum_{i=1}^{k-1}a_i\right)\\ =&nm^{k-1}-\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_k=1}^m\sum_{i=1}^{k-1}a_i\\ =&nm^{k-1}-\sum_{i=1}^{k-1}\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_k=1}^ma_i\\ =&nm^{k-1}-\sum_{i=1}^{k-1}\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots\sum_{a_k=1}^ma_i\\ =&nm^{k-1}-(k-1)m^{k-2}\sum_{a=1}^ma\\ =&nm^{k-1}-(k-1)m^{k-2}\frac{m(m+1)}2 \end{aligned} \]

代码

超讨厌结论题的说 >_<

游走

题意

给一张无向连通图,一个人从 \(1\) 号点开始随机游走,每次等概率地选一条边,走到相邻的点,并获得这条边的编号的分数,到 \(n\) 号时游走结束。你可以给点重新编号,求最小化的期望得分。

\(2\le n\le500\)

解法

注意到如果统计边期望经过的次数复杂度会爆炸,所以统计点的。

\(d_i\) 为点 \(i\) 的度数,\(f_i\) 为点 \(i\) 期望经过的次数。

\[ f_i=\begin{cases} \sum_{(i,j)\in E,j\ne n}\frac{f_i}{d_i}+1,&i=1\\ \sum_{(i,j)\in E,j\ne n}\frac{f_i}{d_i},&i\ne n \end{cases} \]

那对于一条边 \((x,y)\),它的期望经过次数就是 \(\displaystyle\frac{f_x}{d_x}+\frac{f_y}{d_y}\)。然后排个序就好了。

代码

切糕

详见这篇