?？投嘈Ｈ?B Black and white

在n*m的棋盤上，每個格子有一個數，初始可以選一定的格子標記為黑色，在任意四個形如(i1, j1)(i1, j2)(i2, j1)(i2, j2)的格子當中，如果有三個格子已經是黑色的了，那么剩下的一個可以自動染黑。問選哪些格子初始標記為黑色，可以使最終整個棋盤變為黑色的同時，選擇的格子數字之和最小。
數據范圍n, m <= 5000, a, b, c, d, p用于格子中的數字生成。

也是一個思維題，轉化成一個最小生成樹。

在拿到題時候可以發現，至少要選擇一行和一列，可以讓整個棋盤都變為黑色。不過不一定是要一整行或者一整列，有時候對角線也是可以的，但是可以確定最少選擇n + m - 1個數可以將整個棋盤染黑。

看到這個數字可以想到，如果有n + m個點，那么生成樹就是n + m - 1條邊。所以抽象出一個二分圖，一邊為A節點，有n個；另一邊為B節點，有m個。當(i, j)格子被染黑，這就代表著Ai和Bj在一個連通塊中。

而對于2 * 2格子當中的黑色塊的傳遞，可以這樣理解：假如（1,1）（1,2）（2,1）都已經染黑的，這就代表著，A1與B1有一條連邊，A1與B2有一條連邊，A2與B1有一條連邊，那么A2與B2就已經在一個連通塊當中了，所以就染黑了。

當所有的塊都染黑，表示都在一個連通塊里，同時要求初始染黑之和最小，這就是最小生成樹。注意數據范圍，用prim求。

const long long inf = 1e18 + 10; const int N = 5010; long long dis[N][N], mn[N << 1]; bool vis[N << 1];int main() {//freopen("in.txt", "r", stdin);int T = 1;//T = read();while (T --){int n, m, a, b, c, d, p;n = read(); m = read();a = read(); b = read(); c = read(); d = read();p = read();long long pre = a;for (int i = 1; i <= n + m; i ++)mn[i] = inf;for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++){dis[i][j] = (pre * pre * b + pre * c + d) % p;pre = dis[i][j];}int now = 1;long long ans = 0;for (int i = 1; i < n + m; i ++){vis[now] = 1;if (now <= n){for (int j = n + 1; j <= n + m; j ++)if (mn[j] > dis[now][j - n])mn[j] = dis[now][j - n];}else{for (int j = 1; j <= n; j ++)if (mn[j] > dis[j][now - n])mn[j] = dis[j][now - n];}long long mnn = inf, p = -1;for (int j = 1; j <= n + m; j ++)if (!vis[j] && mn[j] < mnn){mnn = mn[j];p = j;}ans += mnn;now = p;}cout << ans;}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的牛客多校三 B Black and white的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。