下⾯分享的是我⾃⼰写的三个代码，⾥⾯有些题⽬也是我⾃⼰出的。这些代码都是在我的Pascal时代写的，恕不提供C语⾔了。代码写得并不好，我只是想告诉⼤家位运算在实战中的应⽤，包括了搜索和状态压缩DP⽅⾯的题⽬。其实⼤家可以在⽹上到更多⽤位运算优化的题⽬，这⾥整理出⼀些⾃⼰写的代码，只是为了原创系列⽂章的完整性。这⼀系列⽂章到这⾥就结束了，希望⼤家能有所收获。 Matrix67原创，转贴请注明出处。
Problem : 费解的开关
06年NOIp模拟赛（⼀） by Matrix67 第四题
问题描述
你玩过“拉灯”游戏吗？25盏灯排成⼀个5×5的⽅形。每⼀个灯都有⼀个开关，游戏者可以改变它的状态。每⼀步，游戏者可以改变某⼀个灯的状态。游戏者改变⼀个灯的状态会产⽣连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们⽤数字“1”表⽰⼀盏开着的灯，⽤数字“0”表⽰关着的灯。下⾯这种状态
10111
01101
10111
10000
11011
在改变了最左上⾓的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定⼀些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输⼊格式
第⼀⾏有⼀个正整数n，代表数据中共有n个待解决的游戏初始状态。
以下若⼲⾏数据分为n组，每组数据有5⾏，每⾏5个字符。每组数据描述了⼀个游戏的初始状态。各组数据间⽤⼀个空⾏分
隔。
对于30%的数据，n<=5；
对于100%的数据，n<=500。
输出格式
输出数据⼀共有n⾏，每⾏有⼀个⼩于等于6的整数，它表⽰对于输⼊数据中对应的游戏状态最少需要⼏步才能使所有灯变亮。
对于某⼀个游戏初始状态，若6步以内⽆法使所有灯变亮，请输出“-1”。
样例输⼊
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
样例输出
3
2
-1
程序代码
const
BigPrime=3214567;
MaxStep=6;
type
pointer=^rec;
rec=record
v:longint;
step:integer;
next:pointer;
end;
var
total:longint;
hash:array[0..BigPrime-1]of pointer;
q:array[1..400000]of rec;
function update(a:longint;p:integer):longint;
begin
a:=a xor (1 shl p);
if p mod 5<>0 then a:=a xor (1 shl (p-1));
if (p+1) mod 5<>0 then a:=a xor (1 shl (p+1));
if p<20 then a:=a xor (1 shl (p+5));
if p>4 then a:=a xor (1 shl (p-5));
exit(a);
end;
function find(a:longint;step:integer):boolean;
var
now:pointer;
begin
now:=hash[a mod BigPrime];
while now<>nil do
begin
if now^.v=a then exit(true);
now:=now^.next;
end;
new(now);
now^.v:=a;
now^.step:=step;
now^.next:=hash[a mod BigPrime];
hash[a mod BigPrime]:=now;
total:=total+1;
exit(false);
end;
procedure solve;
var
p:integer;
close:longint=0;
open:longint=1;
begin
find(1 shl 25-1,0);
q[1].v:=1 shl 25-1;
q[1].step:=0;
repeat
inc(close);
for p:=0 to 24 do
if not find(update(q[close].v,p),q[close].step+1) and (q[close].step+1<MaxStep) then begin
open:=open+1;
q[open].v:=update(q[close].v,p);
q[open].step:=q[close].step+1;
end;
until close>=open;
end;
procedure print(a:longint);
var
now:pointer;
begin
now:=hash[a mod BigPrime];
while now<>nil do
begin
if now^.v=a then
begin
writeln(now^.step);
exit;
end;
now:=now^.next;
end;
writeln(-1);
end;
procedure main;
var
ch:char;
i,j,n:integer;
t:longint;
begin
readln(n);
for i:=1 to n do
begin
t:=0;
for j:=1 to 25 do
begin
read(ch);
t:=t*2+ord(ch)-48;
if j mod 5=0 then readln;
end;
print(t);
if i<n then readln;
end;
end;
begin
solve;
main;
end.
======================= 性感的分割线 =======================
Problem : garden / 和MM逛花园
题⽬来源
第四题
问题描述
花园设计强调，简单就是美。Matrix67常去的花园有着⾮常简单的布局：花园的所有景点的位置都是“对齐”了的，这些景点可以看作是平⾯坐标上的格点。相邻的景点之间有⼩路相连，这些⼩路全部平⾏于坐标轴。景点和⼩路组成了⼀个“不完整的⽹格”。 ⼀个典型的花园布局如左图所⽰。花园布局在6⾏4列的⽹格上，花园的16个景点的位置⽤红⾊标注在了图中。⿊⾊线条表⽰景点间的⼩路，其余灰⾊部分实际并不存在。
Matrix67 的⽣⽇那天，他要带着他的MM在花园⾥游玩。Matrix67不会带MM两次经过同⼀个景点，因此每个景点最多被游览⼀次。他和他MM边⾛边聊，他们是如此的投⼊以致于他们从不会“主动地拐弯”。也就是说，除⾮前⽅已没有景点或是前⽅的景点已经访问过，否则他们会⼀直往前⾛下去。当前⽅景点不存在或已游览过时，Matrix67会带MM另选⼀个⽅向继续前进。由于景点个数有限，访问过的景点将越来越多，迟早会出现不能再⾛的情况（即四个⽅向上的相邻景点都访问过了），此时他们将结束花园的游览。Matrix67希望知道以这种⽅式游览花园是否有可能遍历所有的景点。Matrix67可以选择从任意⼀个景点开始游览，以任意⼀个景点结束。 在上图所⽰的花园布局中，⼀种可能的游览⽅式如右图所⽰。这种浏览⽅式从(1,2)出发，以(2,4)结束，经过每个景点恰好⼀次。
输⼊格式
第⼀⾏输⼊两个⽤空格隔开的正整数m和n，表⽰花园被布局在m⾏n列的⽹格上。
以下m⾏每⾏n个字符，字符“0”表⽰该位置没有景点，字符“1”表⽰对应位置有景点。这些数字之间没有空格。
输出格式
你的程序需要寻满⾜“不主动拐弯”性质且遍历所有景点的游览路线。
如果没有这样的游览路线，请输出⼀⾏“Impossible”（不带引号，注意⼤⼩写）。
如果存在游览路线，请依次输出你的⽅案中访问的景点的坐标，每⾏输出⼀个。坐标的表⽰格式为“(x,y)”，代表第x⾏第y 列。
如果有多种⽅案，你只需要输出其中⼀种即可。评测系统可以判断你的⽅案的正确性。
样例输⼊
6 4
1100
1001
1111
1100
1110
1110
样例输出
(1,2)
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(6,1)
(6,2)
(6,3)
(5,3)
(5,2)
(4,2)
(3,2)
(3,3)
(3,4)
(2,4)
数据规模
对于30%的数据，n,m<=5；
对于100%的数据，n,m<=10。
</BLOCKQUOTE>
程序代码：
<CODE>program garden;
const
dir:array[1..4,1..2]of integer=
((1,0),(0,1),(-1,0),(0,-1));
type
arr=array[1..10]of integer;
rec=record x,y:integer;end;
var
map:array[0..11,0..11]of boolean;
ans:array[1..100]of rec;
n,m,max:integer;
step:integer=1;
state:arr;
procedure readp;
var
i,j:integer;
ch:char;
begin
readln(m,n);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ch);
map[i,j]:=(ch='1');
inc(max,ord( map[i,j] ))
end;
readln;
end;
end;
procedure writep;
var
i:integer;
begin
for i:=1 to step do
writeln( '(' , ans.x , ',' , ans.y , ')' );
end;
procedure solve(x,y:integer);
var
tx,ty,d:integer;
step_cache:integer;
state_cache:arr;
begin
step_cache:=step;
state_cache:=state;
if step=max then
begin
writep;
exit;
end;
for d:=1 to 4 do
begin
tx:=x+dir[d,1];
ty:=y+dir[d,2];
while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
begin
inc(step);
ans[step].x:=tx;
ans[step].y:=ty;
state[tx]:=state[tx] or ( 1 shl (ty-1) );
tx:=tx+dir[d,1];
ty:=ty+dir[d,2];
end;
maxstep
tx:=tx-dir[d,1];
ty:=ty-dir[d,2];
if (tx<>x) or (ty<>y) then solve(tx,ty);
state:=state_cache;
step:=step_cache;
end;
end;
{====main====}
var
i,j:integer;
begin
assign(input,'garden.in');
reset(input);
assign(output,'garden.out');
rewrite(output);
readp;
for i:=1 to n do
for j:=1 to m do
if map[i,j] then
begin
ans[1].x:=i;
ans[1].y:=j;
state:=1 shl (j-1);
solve(i,j);
state:=0;
end;
close(input);
close(output);
end.</CODE>
对C语⾔中位运算的⼀点补充：（位数不同的运算数之间的运算规则）-
C语⾔中，位运算的对象可以是整型（int）和字符型（char）数据。（整形数据可以直接转化成⼆进
制数，字符型数据在内存中以它的ASCII码值存放，也可以站化成⼆进制数）当两个运算数类型不同时，位数亦会不同。遇到这种情况，系统将⾃动进⾏如下处理：
1将两个运算数右端对齐。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议