我现在的日子是越来越囧了。。。比如今天做 SGU 307，我知道了题目中的结论，然后我想把它证明出来。在草稿纸上面写了一点点就觉得写不下去了。于是只能打开打开Dev-Cpp去写它。
这道题目题意为，原来的 N * M 矩阵 A 是一个 0 1 矩阵。现在给出一个 (N-1) * (M-1) 的矩阵 B ，其中
B[I][J] = A[I][J] + A[I+1][J] + A[I][J+1] + A[I+1][J+1]
要求去还原这个矩阵。有解的话，输出任意一组可行解；无解则给出无解信息。
这道题目 XYS 大牛给出的思路是，枚举最右下的一个点是 0 or 1 。然后对于 A[I][J] 可以表示为
A[I][J] = K + (-1)^p * A[I][M] + (-1)^q * A[N][J]
其中 K 是一个常数。
又因为每个点的取值只能是 0 1，这样就可以列出方程，变成一个 2-sat 问题然后轻松解决。
题目的难点不在 2-sat 与构造可行解，在于转化。下面是我的证明 ：
（点击可以看原图）
这样，问题就成功的转化为了 2-sat ！！
首先枚举右下角填 0 还是 填 1 。
输出的矩阵还依赖于最后一排和最后一列的数。。。
对于所有的 <i,j> ，其中 (i < n , j < m)。
因为有公式 ：
a[i][j] = c[i][j] + (-1)^(n-i) * a[n][j] + (-1)^(m-j) * a[i][m] + (-1)^(n-i+m-j+1) * a[n][m]
其中 除了 a[n][j] 和 a[i][m] 外都是常量。
而 - - a[n][j] 与 a[i][m] 的取值都是 0 或 1
那么对于这 4 种组合，查看 a[i][j] 的值是否在 {0 , 1} 中，如果不合法，则可以添加限制。2-sat 正好可以解决这个问题 ！
解决这个 2-sat，我所用的方法是构建一个有向图。。。具体的 2-sat 就不细说了，有兴趣的同学可以看看湖北华中师范大学第一附属中学的 赵爽 同学写的论文。
好像还有更佳的方法，不过我不会了。。
………………………………………………………………………………………………………………………………………………
PS 如果用强连通分量来写的话，输出方案的函数会暴恶心。。。
program Cipher ;
const maxn = 600 + 10 ;
type atype = record d , next : longint ; end ;
link = ^node ;
node = record d : longint ; next : link ; end ;
var a , b , c
: array[0..maxn,0..maxn] of longint ;
vr , vis , low , co
: array[-maxn..maxn] of longint ;
g : array[0..maxn * 2,0..maxn * 2] of boolean ;
on_stack: array[-maxn..maxn] of boolean ;
stack , id
: array[0..maxn * 2] of longint ;
scc : array[0..maxn * 2] of link ;
chosen : array[0..maxn * 2] of boolean ;
arc : array[0..maxn * maxn * 4] of atype ;
n , m , tot , clock , top , num , z
: longint ;
q : link ;
procedure addarc (u , v : longint) ;
begin
//writeln (u,' - > ',v) ;
inc (tot) ; arc[tot].d := v ;
arc[tot].next := vr[u] ; vr[u] := tot ;
end ;
function ok (k : longint) : boolean ;
begin
if (k = 0) or (k = 1) then
ok := true
else
ok := false ;
end ;
function tran (k : longint) : longint ;
begin
if (k and 1 = 0) then
tran := 1
else
tran := -1 ;
end ;
procedure dfs (u : longint) ;
var p : longint ;
begin
inc (clock) ; vis[u] := clock ; low[u] := clock ;
inc (top) ; stack[top] := u ; on_stack[u] := true ;
p := vr[u] ;
while (p <> -1) do begin
if (vis[arc[p].d] = 0) then begin
dfs (arc[p].d) ;
if (low[arc[p].d] < low[u]) then
low[u] := low[arc[p].d] ;
end
else
if (on_stack[arc[p].d]) and (vis[arc[p].d] < low[u]) then
low[u] := vis[arc[p].d] ;
p := arc[p].next ;
end ;
if (low[u] = vis[u]) then begin
inc (num) ;
while (true) do begin
p := stack[top] ; on_stack[p] := false ; dec (top) ;
co[p] := num ;
new (q) ; q^.d := p ; q^.next := scc[num] ; scc[num] := q ;
if (p = u) then
break ;
end ;
end ;
end ;
function process (anm : longint) : boolean ;
var i , j , u , v , p , x , t
: longint ;
begin
fillchar (vr , sizeof (vr) , $ff) ;
fillchar (on_stack , sizeof (on_stack) , 0) ;
fillchar (vis , sizeof (vis) , 0) ;
fillchar (scc , sizeof (scc) , 0) ;
clock := 0 ; top := 0 ; tot := -1 ; num := 0 ;
// n - 1 - > m - 1 - > z
// vr[+] - > a[x][y] = 1 ; vr[-] - > a[x][y] = 0
t := n - 1 ; z := n + m - 2 ;
for i := 1 to n - 1 do
for j := 1 to m - 1 do begin
x := c[i][j] + tran (n-i+m-j+1) * anm ;
u := tran (n-i) ; v := tran (m-j) ;
if (not ok (x + u + v)) then begin
addarc (t + j , -i) ;
addarc (i , -(t + j)) ;
end ;
if (not ok (x + u)) then begin
addarc (t + j , i) ;
addarc (-i , -(t + j)) ;
end ;
if (not ok (x + v)) then begin
addarc (i , t + j) ;
addarc (-(t + j) , -i) ;
end ;
if (not ok (x)) then begin
addarc (-(t + j) , i) ;
addarc (-i , (t + j)) ;
end ;
end ;
for i := -z to z do
if (i <> 0) and (vis[i] = 0) then
dfs (i) ;
for i := 1 to z do
if (co[i] = co[-i]) then begin
process := false ;
exit ;
end ;
process := true ;
end ;
procedure dye (u : longint) ;
var v : longint ;
begin
chosen[u] := false ;
for v := 1 to num do
if (g[u][v]) and (chosen[v]) then
dye (v) ;
end ;
procedure print (anm : longint) ;
var u , v , p , i , j
: longint ;
begin
fillchar (g , sizeof (g) , 0) ;
fillchar (id , sizeof (id) , 0) ;
fillchar (a , sizeof (a) , 0) ;
fillchar (chosen , sizeof (chosen) , 1) ;
for u := -z to z do
if (u <> 0) then begin
p := vr[u] ;
while (p <> -1) do begin
if (co[u] <> co[arc[p].d]) then
g[co[arc[p].d]][co[u]] := true ;
p := arc[p].next ;
end ;
end ;
top := 0 ;
for u := 1 to num do
for v := 1 to num do
if (g[u][v]) then
inc (id[v]) ;
for u := 1 to num do
if (id[u] = 0) then begin
inc (top) ; stack[top] := u ;
end ;
while (top > 0) do begin
u := stack[top] ; dec (top) ;
if (chosen[u]) then begin
q := scc[u] ;
while (q <> nil) do begin
if (chosen[co[-q^.d]]) then
dye (co[-q^.d]) ;
q := q^.next ;
end ;
end ;
for v := 1 to num do
if (g[u][v]) then begin
dec (id[v]) ;
if (id[v] = 0) then begin
inc (top) ; stack[top] := v ;
end ;
end ;
end ;
for i := 1 to z do
if (chosen[co[i]]) then
if (i < n) then
a[i][m] := 1
else
a[n][i-n+1] := 1 ;
a[n][m] := anm ;
for i := n - 1 downto 1 do
for j := m - 1 downto 1 do
a[i][j] := b[i][j] - a[i+1][j] - a[i][j+1] - a[i+1][j+1] ;
for i := 1 to n do begin
for j := 1 to m - 1 do
write (a[i][j]) ;
writeln (a[i][m]) ;
end ;
end ;
procedure solve ;
var i , j : longint ;
ch : char ;
begin
readln (n , m) ;
for i := 1 to n - 1 do begin
for j := 1 to m - 1 do begin
read (ch) ;
b[i][j] := ord (ch) - 48 ;
end ;
readln ;
end ;
for i := n - 1 downto 1 do
for j := m - 1 downto 1 do
c[i][j] := b[i][j] - c[i+1][j] - c[i][j+1] - c[i+1][j+1] ;
{
for i := 1 to n - 1 do begin
for j := 1 to m - 1 do
write (b[i][j],' ') ;
writeln ;
end ;
writeln ;
for i := 1 to n - 1 do begin
for j := 1 to m - 1 do
write (c[i][j],' ') ;
writeln ;
end ;
writeln ;
}
if (process (0)) then begin
print (0) ;
exit ;
end ;
if (process (1)) then begin
print (1) ;
exit ;
end ;
writeln ('CORRUPT') ;
end ;
begin
assign (input , 's307.in') ; reset (input) ;
assign (output , 's307.out') ; rewrite (output) ;
solve ;
close (input) ; close (output) ;
end .
