洛谷7295 [USACO21JAN] Paint by Letters P
Luogu 分析 如果我们在相邻的两个相同字符间连一条边，可以发现得到的图为平面图。 对于平面图，我们有欧拉公式 其中 $F$ 为区域数（无界域也算一个区域）、$V$ 为点数、$E$ 为边数、$C$ 为连通块数。 于是我们可以想办法求出 $F, V, E$。 $V$ 是好求的，即为 $(x_2 - x_1 + 1)(y_2 - y_1 + 1)$；$E$ 也是好求的，只需要维护二维前缀和即...
Luogu 分析 如果我们在相邻的两个相同字符间连一条边，可以发现得到的图为平面图。 对于平面图，我们有欧拉公式 其中 $F$ 为区域数（无界域也算一个区域）、$V$ 为点数、$E$ 为边数、$C$ 为连通块数。 于是我们可以想办法求出 $F, V, E$。 $V$ 是好求的，即为 $(x_2 - x_1 + 1)(y_2 - y_1 + 1)$；$E$ 也是好求的，只需要维护二维前缀和即...