集訓(xùn)隊(duì)作業(yè)-ural1458war games解題報(bào)告

1、Ural 1458 War Games 解題北江中學(xué)【正文】一、問(wèn)題描述給出一個(gè)由B和W組成的 n*n 矩陣 C。一個(gè)操作(i,j)指將第 i 行和第j 列的所有元素（一共 2n-1 個(gè))的狀態(tài)都改變(B變成W,W變成B)， 2 = n = 1000, 且n 為偶數(shù)?，F(xiàn)在給出初始狀態(tài)，要求用最少的操作將矩陣變成一種顏色（只有W或B）。并將具體方案輸出。二、問(wèn)題分析算法是余方程組。不難發(fā)現(xiàn)，如果某個(gè)操作(i,j)出現(xiàn)多于一次，那么肯定不優(yōu)的，因?yàn)榭梢詫⑺?mod 2,使得結(jié)果不變，而總操作數(shù)減少。另外，操作執(zhí)行的順序，對(duì)結(jié)果也是不影響的。如果用 0 表示W(wǎng),用 1 表示B，Ai, j表示操作(i

2、, j)出現(xiàn)的次數(shù)，那么最后矩陣中 C(i, j)變?yōu)?C(i, j) + (Ai, 1 + . + Ai, n) + (A1, j + . + An, j)- Ai，j) mod 2.可以預(yù)先假定最后所有元素都變?yōu)?0，或 1(分別搜索)，用 k 表示。一共有 n2 個(gè)未知數(shù)，而對(duì)于每個(gè)元素,都可以列一個(gè)方程。所以只需要解出這個(gè)方程即可。現(xiàn)在是，如果運(yùn)用消,時(shí)間復(fù)雜度將會(huì)達(dá)到 O(n6)。事實(shí)上，任何復(fù)雜度高于 n2 的算法已經(jīng)不可能出解了。 通過(guò)觀察可以發(fā)現(xiàn)，這個(gè)方程組有自身的特殊性的。 n 是偶數(shù)將使很多表達(dá)式關(guān)于 2 同余了。對(duì)于某個(gè)元素 C(i, j),有 (C(i, j) + (A

3、i, 1 + . + Ai, n) + (A1, j + . + An,j) - Ai，j) mod 2 = k將所有 n2 個(gè)方程都相加，并化簡(jiǎn)，可以得知 sum = (n * 2 - 3)* 2(A1， 1 + . + An, n) mod 2 = (A1, 1 + . + An, n) mod的確切值，由于n 為偶數(shù)，所以 sum 等于矩陣中 1 的個(gè)數(shù) mod2。如果用 ai 表示 (Ci, 1 + Ci, 2 + . Ci, n) mod 2,用 bj 表示 (C1, j + C2,用 yi表示 (Ai, 1 + . +用 xj表示 (A1, j + . +將第i 行所有元素所有的方

4、程相j + Ai,An,.n)j)+ Cn, j) mod 2, mod 2mod 2們可以得出，yi = (ai * (n 2;們得出，xj = (bj * (n - 1)+-1) + sum) mod 2 = (ai + sum)mod同理，將第j 列所有的方程相sum) mod 2 = (bj + sum) mod 2;這時(shí)，將 yi,xj代入每個(gè)元素的方程中，有(yi + xj + Ci， j - Ai, j) mod 2 = k即 Ai, j = (yi + xj + Ci, j - k) mod 2 = (yi + xj +Ci, j + k) mod 2由于 y, x, c, k

5、 都已知，所以所有的 Ai, j都可以解出來(lái)。三、程序說(shuō)明由于n 可能達(dá)到 1000，所以我沒(méi)有將解出來(lái)的 Ai, j存下來(lái)(因?yàn)榇髷?shù)組的頻繁計(jì)算地址會(huì)耗費(fèi)很多時(shí)間)，而是采取臨時(shí)計(jì)算的方式。另外，將 mod 2 轉(zhuǎn)化為位運(yùn)算 and 1, 也可以大大加快程序的運(yùn)行速度?！靖健縞onstfin = ;/input.in;maxn = 1000;varc: array1 . maxn, 1 . maxnof short;a, b, x, y: array1 . maxnof long;count: array0n, sum: long. 1of long;procedure init; vari

6、, j, k: long ch: char;beginassign(input, readln(n);fin); reset(input);for i:= 1 to n do begin for j:= 1 to n do beginread(ch);if ch = W then k:= 0 else k:= ci, j:= k;inc(sum, k); inc(ai, k);inc(bj, k); end;readln; end;close(input);1;sum:= sum and 1;for i:= 1 to n do beginai:= ai andbi:= bi and end;1

7、;1;end;procedure find(k: long vari, j, ans: longbegin);for i:= 1 to n do begin xi:= (bi + sum) and 1;yi:= (ai + sum) and 1;end;for i:= 1 to n do for j:= 1 to n dobeginans:= (yi + xj + k + ci, j)and1;if ans = 1 thenend;inc(countk);end;procedure prvar(k: long);i, j, ans: long;beginfor i:= 1 to n do begin xi:= (bi + sum) and 1;yi:= (ai + sum) and 1;end;wrin(countk); for i:= 1 to n dofor j:= 1 to n do beginans:= (yi + xj + k +