2023.8.8 练习
ARC061E
首先有个套路的想法：以边作点，然后前后缀优化建图，但是这样是麻烦的。
我们重新考虑：
我们发现，如果把同一个公司的联通块处理一下，最短路径其实就是其经过联通块个数。
我们把在同一个联通块的点互相建边，权值为 \(1\)。
但是这样是不优的，边数会被卡成 \(n^2\)。
我们考虑对每个联通块建立虚点，对一个联通块中的点，向对应的虚点建 \(0.5\) 权值的边即可。
ARC061F
发现所有的牌的方案刚好对应一种出牌顺序。
于是我们只需处理出牌的序列即可。
A 获胜的条件是序列中含有 \(n_1\) 个 \(a\)，且最后一位是 \(a\).
而且不能含有 \(n_2+1,n_3+1\) 个 \(b,c\).
我们枚举 \(k\)，表示出牌序列有 \(k\) 个 \(b,c\).