总结

今天真的是模拟赛吗，呜啊。今天是腊八节，学校似乎并没有给我们腊八粥，好伤心。（伤心个头啊，学校有那么多钱吃这么多东西吗），但是学校晚饭还是在饭里放了腊肉、豌豆之类的，还是感谢学校！今天说是 div1 的人继续专题，然后 div2 的人做一个模拟赛。不是很难。由于我们是逊逊的无所事事的 div2 的小菜菜啊，所以去做模拟赛了。

题解

简单讲一下，前两道题都比较简单。

[JXOI2018] 游戏

原题，发现区间形成了一个 dag 一样的东西，找到入度为的数量，然后用组合数算一下就行。

B. 最短路

一个无向简单连通图，每条边有边权，每过，每个边权都会加。现在要你求第个到第个时刻的之和对取模的值。

。

可以先求到每个点经过多少条边的最短路。容易发现只需要保留随着路径边数增加最短路径变小的即可。于是就可以简单 bfs 就可以了。然后这堆东西再求一个凸包搞一下就完了。

C. 移动箱子

就是一个无限长的一个横排有一些位置，然后有个位置（不超过个）分别在上面堆了个货物，，然后让你求对于，要求每个位置上面的货物都不超过个，每次只能把一个货物从一堆的顶端拿到右边下一个那个位置的上面。容易发现答案是最后形状所有货物位置和减去最开始的位置和。考虑限制从大到小有一些堆会合并，因此用并查集和大根堆维护一下就可以，动态合并。然后会发现每一个堆在一段区间的限制内生效，而且是独立的。容易发现就是一个区间加上一个等差数列，那么两次差分维护一下就行。

这道题让我又意识到了几个容易错误的地方：

• 如果输入数据要排序，不要在排序前记载一些和输入数据有关的数据存在数组里！
• 不仅要检查是否需要 long long，写代码时还要提防有些时候乘法爆 long long！特别是取一个的模数的时候，要注意，因为有些数可能并没有取模！

做一道 junjun 说的题目，就是一道怎么说呢，有意义的题。（现在不敢说有趣了啊瓦啊啊）。

P3713 [BJOI2017] 机动训练

这道题有一个思路非常巧妙。可以这么说，就是权值是某个等价类大小的平方。可以考虑其组合意义，就是两个东西相等的相组合的数量，然后这个样子就能很容易 dp 或者记忆化搜索了。

后记

今天还行，很好啊。