2014西安全国邀请赛简易题解

题目链接

A. Wow! Such Doge!

统计输入文本里面有多少只Doge,直接暴力统计即可。

B. Wow! Such Conquering!

搜索,变种的TSP问题,先对原图进行一次Floyd。

有两个比较重要的剪枝:

  • 如果当前存在一个没有走过的点,直接走过去也会超过Deadline,剪。
  • 如果当前搜到的时间和已经大于答案,剪。

有了这两个剪枝,这道题就可以通过了。

C. Wow! Such City!

很基础的最短路,直接Dijkstra即可。

D. Wow! Such String!

如果把三个连续的字符看成一个节点,原问题可以转化为求26^3个节点的欧拉路径问题。比如aaa后面加一个b,就相当于从aaa节点往aab节点连一条边。

注意n如果大于26^4+3是无解的。

E. Wow! Such Precision!

F. Wow! Such Tetris!

G. Trader Dogy

注意数据中的树是随机产生的,这就意味着树的深度不会很大,两个点之间的距离是$ O(logn) $级别的。

这样我们就可以把Dogy行动的整条路径给弄出来,在这条路径上dp。 我们设从出发到第i个点而且有车的最小费用为f[i],则f[i]可以从f[i - 1]开车过来,也可以之前把车放在上一次到i对应的节点,中间一段全部走路。

f[i]计算出来后,答案就是f[i]再加上从i出发走到终点的费用的最小值。

H. Round-table Conference

根据Hall定理,二分图存在完备匹配当且仅当任意X点集子集的基数,不大于对应Y点集的并集的基数。所以一个naive的想法是$ O(2^n) $枚举所有区间,看这些区间并集的大小,是否小于对应人数的总和。

不难发现,如果两个区间都是可行的,而它们又不相交,显然它们的并集也是可行的。所以我们只需验证所有连续的并集是否合法,这些并集就只有$ O(m^2) $种了。

不妨假设原问题是一条链,如果我们枚举一个区间$ [x,y] $ , 判断该区间是否可行,等价于判断: $ \sum_{x \leq L_i, R_i \leq y} A_i \leq y - x + 1 $是否成立,继续推导,等价于判断: $ \sum_{x \leq L_i, R_i \leq y} A_i + x \leq y + 1 $是否成立。如果固定一个$ y $,继续等价于 $ max(\sum_{x \leq L_i, R_i \leq y} A_i + x) \leq y + 1 $是否成立。

设$ magic[x] = \sum_{x \leq L_i, R_i \leq y} A_i + x $。 不难看出,如果当$ y $ += 1 时,需要插入所有$ R_i = y + 1 $的区间,按照$ magic $的定义,只需要把的$ magic[0] , magic[1] … magic[L_i] $ 都加上 $ A_i $。 剩下的就是用线段树来维护$ magic $ 了。

现在返回原问题。我们只需要把链倍长,枚举$ y $时限定一下$ x $的范围来判定即可。

I. Goddess

从原点往各个圆作切线,则切线把弧度划分成很多个区间。

而每一段区间内部,弦长与射线斜率的弧度的关系是单峰的,应该是一个凸函数。

这样就能在每一段区间里靠三分来求出极值。

J. Tunnels

求出全源最短路,就是一个简单的状压DP。