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 版权协议，转载请附上原文出处链接和本声明。