总结

今天腊月十二，月亮或许渐渐圆起来了吧！今天又是模拟赛啊，最近头都要考昏了。今天发挥的不是很好，但是暴力拿了 178 分还行。改起来感觉也不难，感觉各个题都是差临门一脚的感觉。看来还是不够熟练，也或许是晚上没睡好，总之是要身体好，精神好。

题解

说一下题解，感觉有一点发挥失常了呢，也兴许是这类题我刚好没有做过不是很熟悉。今天学习的欲望不是很强烈啊。

还有今天机房的三个同学被宣判了死刑结束，万恶的电子科大不能让他们去省选了。祝他们有一个美好的假期。

A. Easy

真的 Easy 吗？

题面：

给定一个个点，条边的无向联通图。第天的末尾你在结点，并且战斗力为, 除了结点之外的个节点都有一个BOSS，第个节点BOSS的战斗力可以表示为。每天你可以挑战最多一个BOSS，到其所在结点打败他，前提是当前结点到BOSS结点的一条路径上没有其他BOSS存活。

当你的战斗力大于该BOSS时，BOSS会被消灭，否则不能挑战该BOSS。

当击败一名BOSS，奖励的经验值会使你的战斗力提高。而每天的一开始，BOSS的战斗力会提高。

你必须打败结点的BOSS来获得游戏的胜利。问是否存在这样的方案，如果存在，最少需要多少天？

就分 A，B 大小讨论一下，A 小直接暴力 bfs 就可以，反之用优先队列维护一下每个时刻能到达的点，或者用 dijkstra 也行。

B. 幂

很喜欢的题目。

已知，求有多少种不同取值。

容易发现，大于不会重。那就暴力枚举最小的底和它的幂，然后就发现问题转换成了一个和一个以内的正数两两相乘有多少种乘积的问题。这个直接用 set 维护有 60 分，因为有两个点很小哈哈。也可以用容斥，就从大到小枚举，然后不能和比它大的重。考场上写出来了，但是挂了，为什么呢？因为我本来想求的，结果记错了使用了函数 __lg，导致最小的求成最大的了。（低级错误啊，函数用法都搞混了）。但是这样发现是最大的。考虑优化。我们相当于容斥一个数乘上一个数是比它大的一个数倍数有多少个，因此这个数的倍数就可以不用考虑了。这样就最多只有个用来枚举了。

C. 星际穿越

原题。容易发现一个走最多在最开始的时候往右跳一下然后后面都往前跳。画一下能够发现，第一步之后如果往后跳都能转换成少一步的情况，因此倍增就可以了。查询就区间差分查询，然后每次第一步考虑一下，因为第一步不能向后跳。

D. 哈夫曼回路

简化一下题意。就是有一张一维的方格图，每条边有边权。每次询问一个区间的方格，可以覆盖一些边使得做后每个点都被覆盖偶数次或两个点奇数次。求最小权值和。

容易列出一个 dp 式子，容易发现是一个矩阵的东西，满足结合律，用线段树维护动态 dp 就可以了。听说分治也行？

后记

周四就要去重庆了，休息好，养足精神。争取获得好成绩。还是很伤心，三个人走了之后，机房一下子就冷清了。