NOIP2017 复盘

D1T1 小凯的疑惑

可惜了，我当时只会写\(1\leq a,b \leq 50\)的暴力。我还以为这道题就这样了。

首先，看到这道题目的输入输出这么少，就应该想到打表找规律！

暴力程序真的不要太好写，但是规律就难看出来了。

结论是\(a \times b - a - b\)。

合理利用diff或者fc就很好对拍了。

D1T2 时间复杂度

D1T3 逛公园

2019.03.16 把记忆化搜索的做法抄了下来

30pts做法

\((K=0)\)就是经典的最短路计数。在最短路算法的基础上算一下就行了。

70pts做法

很显然能发现这道题是与\(K\)有关的dp。

我们设一下dp状态：\(dp[u][l]\)代表从\(1\)点走到\(u\)点，满足\(dist \leq dist_u + l\)的方案数。最终答案就是\(\sum_{l=0}^K dp[n][l]\)。

要算某个状态对应的\(dist\)范围，显然我们需要从\(1\)点跑个最短路作为预处理。

如何求这个dp？我们可以用记忆化搜索。

在记忆化搜索中，我们翻回前面的边，看看能从前面的哪个状态转移得来。

如何翻回前面的边？建个反图即可。

那前面的状态中，\(l\)是什么？是\(l - (dist_v - dist_u + w)\)。（画个图很好理解，括号里面的是会走多的冤枉路）

按照这种思路去记忆化搜索就应该能拿70pts了吧。。。

100pts做法

知道为什么上面只有70pts吗？因为我们忘记考虑无解情况。

怎么样才能出现无穷多条路径？当走了0环的时候。

做法只需要在前面的基础上修改一点点：

• 给每个状态记录一个\(instack\)，如果碰到了就说明有0环。
• 只要在自己枚举的所有\(l\)出现了一个0环，那么就无解。
• 利用记忆化搜索的返回值很容易实现。

因为从\(1\)走到\(n\)跟从\(n\)走到\(1\)是等价的，所以你可以把上面的两个图颠倒顺序，答案是不变的。

看起来好像不是太难啊但是永远是独立写不出来的

D2T1 奶酪

00 最简单的做法：直接连边跑bfs就可以了。

其实并查集可以做，常数特别小。

D2T2 宝藏

这里是两种方法：第一种是随机算法，第二种是状压dp。

D2T3 列队

这道题可以用平衡树来做。

把每一行除了最后一个元素拿起来建一颗平衡树，再把最后一列独立建一颗平衡树。

其实思路很简单，但是代码就不是那么好写了。。。