板刷计划:ARC061

  • Post author:
  • Post category:其他


https://atcoder.jp/contests/arc061/tasks

C.dfs水题.

题目大意:给你一个长度不超过10的只含1~9的字符串。让你从里面插入任意个’+’。问你所有合法方案的算数和.

例如: S = 12

12

1 + 2

答案为12 + (1 + 2) = 15.

拓展:当 n >= 1e5(要求取模) 时如何求?
方法:动态规划

待补:

D.STL模拟水题

题目大意:略

根据题意,不难发现改变一个点,就只改变以它为中心的 5 * 5 的方格里的每个 3 * 3格的状态.所以用STL存点,暴力模拟即可.

E.重构图,拉虚点跑最短路.
题目大意:给你一张图。每条边属于一个公司C_i管辖。当你上一步所经过的C_i 不等于现在经过的C_j. 那么将产生 1 的花费,问你1 ~ n 的最短路.
题目思路:

不难发现,如果只关注某一个公司所占用的边,他们所构成的连通块内游走是无花费的。并且同一个公司的两个不同的连通块无关联,可视作不同公司。

那么我们显然可以使用

拉超级虚点

的方法: 对于一个公司的一个连通块,我们拉出一个虚点,连接着连通块的每个点与这个虚点建立双向边。去时花费1,回来时花费0.原理也很好理解:进入超级虚点可以想象成买门票。买完之后,你就可以到达连通块内的任意点了。所以回来的时候不产生花费。

之后就是简单跑个Dijstra或者01BFS都行。

F.组合数学。1100.太难了



版权声明:本文为qq_35577488原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。