昨天情人節~wissqu題解
Wisconsin Squares 威斯康星州的牧场
描述
威斯康星州的春天来了，是该把小奶牛们赶到小牧场上并把大奶牛们赶到北纬 40 度的大牧场上的时候了。
农夫约翰的牧场上有五种奶牛（括号内的是缩写）：格恩西奶牛（A），泽西奶牛（B），赫里福奶牛（C），黑安格斯奶牛（D），朗赫恩奶牛（E）。这些奶牛群放养在一片 16 英亩的牧场上，每英亩上都有一小群奶牛，像下面这样排列成 4 x 4 的格子（用行和列标号）：
1 2 3 4
+-------
1|A B A C
2|D C D E
3|B E B C
4|C A D E
最初，牧场上的奶牛群总共有 3 群 A，3 群 B，4 群 C，3 群 D，3 群 E。今年的 D 种小奶牛比去年多一群 ，C 种少一群，共有 3 群 A，3 群 B，3 群 C，4 群 D，3 群 E。
农夫约翰对于他牧场上的奶牛群的布局非常小心。这是因为如果同一种类型的奶牛群靠得太近，她们就乱来：她们聚集在栅栏边上抽烟，喝牛奶。如果她们在相同的格子上或者在临近的 8 个格子上，就是靠得太近了。
农夫约翰得用他的棕色旧福特皮卡把他的大奶牛群运出牧场，并把他的小奶牛群运进牧场，皮卡一次只能运一群奶牛。他装上一群小奶牛，开车到小牧场的一个方格中，卸下这群小奶牛，再装上这个格子上的那群大奶牛，开到北纬 40 度的大牧场卸下来。他重复这样的操作 16 次，然后开车去杰克商店办理低脂酸奶的交易和家居装修。
帮助农夫约翰。他必须选择正确的顺序来替换他的奶牛群，使得他从不把一群小奶牛放入当前被同样类型奶牛占有的方格或者当前被同样类型奶牛占据的方格的临近方格。当然，一旦大奶牛走了，小奶牛就被安置好（in place），他必须小心以后的情况，要根据新的排列把奶牛群分开。
非常重要的提示：农夫约翰从过去的经验知道，他必须先移动 D 种奶牛群。
找出农夫约翰将他的小奶牛搬迁到她们的新牧场上的办法。输出 16 个连续的 奶牛群类型/行/列 的信息，使得这样的安排能够符合安全经验。
计算 4 x 4 牧场的最终排列总数和产生那些排列的方式的总数。
格式
PROGRAM NAME: wissqu
INPUT FORMAT
四行，每行四个字母，表示奶牛群。
OUTPUT FORMAT
16 行，每行分别由奶牛群类型/行/列组成。如果有多解（一定有），那么你应该输出奶牛群类型按照字典序排列在最前面的那个解。如果不只一个解满足条件，那么你应该输出行信息按照字典需排列在最前面的那个解。如果仍然不只一个解满足条件，那么你应该输出列信息按照字典序排列在最前面的那个解。
最后多输出一行，包含能够由这个排列方式产生的排列的总数。
SAMPLE INPUT (file wissqu.in)
ABAC
DCDE
BEBC
CADE
SAMPLE OUTPUT (file wissqu.out)
D 4 1
C 4 2
A 3 1
A 3 3
B 2 4
B 3 2
B 4 4
E 2 1
E 2 3
D 1 4
D 2 2
C 1 1
C 1 3
A 1 2
E 4 3
D 3 4
14925
只有一組數據。就是樣例~
很容易cheat，但是~我的號不是ChaoShi的ch1~(cheat_one).
就是暴搜~只是個常數優化的問題：
大概就是盲目搜索的樣子，限時是5s。一般來說，自己電腦上跑多久USACO評測 就大概多久，因為雖然處理器弱但是Unix比較強~但是這道題貌似是很欠揍的，不知道是故意掐時間還是什麽，自己機子上5s絕對超時，要優化到你的機子大 概2s的樣子，然後就可以A它的5s。（2s是啊lyk推薦的值，然後我最後測來真的是~~~~）
總計提交了9次，從第2次開始答案就全部是正確的~（第一次WA+TLE是因為看 錯題）然後不停的優化，總共寫了10個多的版本，試過修改循環順序~等等等等，反正是常數優化的樣子。從它5.400s終了你的程序，改到5.289s， 到5.281s，到5.127s，再到5.029s，最後4.666sAC……
痛苦啊~
| 原來的程序~ |
常數優化後的程序： |
{$IFDEF NORMAL}
{$I-,OBJECTCHECKS-,Q-,R-,S-}
{$ENDIF NORMAL}
{$IFDEF DEBUG}
{$I+,OBJECTCHECKS-,Q+,R+,S-}
{$ENDIF DEBUG}
{$IFDEF RELEASE}
{$I-,OBJECTCHECKS-,Q-,R-,S-}
{$ENDIF RELEASE}
//wissqu原版本
{
TASK: wissqu
LANG: PASCAL
ID: awesome5
}
//for tripley
//by phoeagon
//search_stupid
//keep it simple, stupid
//2009-2-13
//tomorrow is valentines'
type
Toprt=^oprt;
oprt=record
cow,x,y:longint;
pre:toprt;
end;
map=array[1..4,1..4]of char;
tot=array[1..4,1..4]of boolean;
ct=array[-1..4]of longint;
const
tt:Array[0..7,1..2]of longint=((0,-1),(0,1),(1,0),(-1,0),
(1,1),(-1,-1),(-1,1),(1,-1));
var
outt:boolean;
root,neww:toprt;
yy:map;
rec:tot;
count:longint;
cs:ct=(16,3,3,3,4,3);
{procedure prn(const a:tot);inline;
var
i,j:longint;
begin
for i:=1 to 4 do begin
for j:=1 to 4 do
write(a[i,j]);
writeln;
end;
end;}
function okay(const a,b:longint):boolean;inline;
begin
if a>0 then
if a<5 then
if b>0 then
if b<5 then
exit(true);
exit(false);
end;
procedure init;inline;
var
i,j:longint;
begin
for i:=1 to 4 do
begin
for j:=1 to 4 do
read(yy[i,j]);
readln;
end;
new(root);
fillchar(root^,sizeof(root^),0);
new(newW);
fillchar(neww^,sizeof(neww^),0);
neww^.pre:=root;
end;
procedure trace(const n:toprt);inline;
begin
if n<>root then
begin
trace(n^.pre);
writeln( chr(n^.cow+ord('A')) ,' ',n^.x,' ',n^.y);
end;
end;
procedure dfs(var rt:map;var rec:tot;var cos:ct;const node:toprt);inline;
var
tmp:char;
a,i,j,c:longint;
can:boolean;
nod:toprt;
begin
if cos[-1]=0 then
begin
inc(count);
if not outt then begin
trace(node^.pre);
outt:=true; end;//writeln(count);
end
else
for a:=0 to 4 do //determine the current cow
if cos[a]>0 then
begin
dec(cos[a]);dec(cos[-1]);
node^.cow:=a;
//check availability
for i:=1 to 4 do
for j:=1 to 4 do //try to put it on (i,j)
begin
if rec[i,j]then continue;
tmp:=rt[i,j];
if chr(a+ord('A'))=tmp then
continue;
can:=true;
for c:=0 to 7 do
if okay(i+tt[c,1],j+tt[c,2])then
if ord(rt[i+tt[c,1],j+tt[c,2]])-
ord('A')=a then
begin
can:=false;
break;
end;
if not can then continue;
rec[i,j]:=true;
node^.x:=i;node^.y:=j;
new(nod);
fillchar(nod^,sizeof(nod^),0);
nod^.pre:=node;
rt[i,j]:=chr(a+ord('A'));
//prn(rec);
dfs(rt,rec,cos,nod);
rt[i,j]:=tmp;
dispose(nod);
rec[i,j]:=false;
end;
//check availablility
inc(cos[a]);inc(cos[-1]);
end;
end;
procedure dfs_first(var rt:map;var rec:tot;var cos:ct;const node:toprt);inline;
var
tmp:char;
a,i,j,c:longint;
can:boolean;
nod:toprt;
begin
//determine the current cow
a:=3;
if cos[a]>0 then
begin
dec(cos[a]);dec(cos[-1]);
node^.cow:=a;
//check availability
for i:=1 to 4 do
for j:=1 to 4 do //try to put it on (i,j)
begin
tmp:=rt[i,j];
if rec[i,j]then continue;
if chr(a+ord('A'))=tmp then
continue;
can:=true;
for c:=0 to 7 do
if okay(i+tt[c,1],j+tt[c,2])then
if ord(rt[i+tt[c,1],j+tt[c,2]])-
ord('A')=a then
begin
can:=false;
break;
end;
if not can then continue;
rec[i,j]:=true;
node^.x:=i;node^.y:=j;
new(nod);
fillchar(nod^,sizeof(nod^),0);
nod^.pre:=node;
rt[i,j]:=chr(a+ord('A'));
//prn(rec);
dfs(rt,rec,cos,nod);
rt[i,j]:=tmp;
dispose(nod);
rec[i,j]:=false;
end;
//check availablility
inc(cos[a]);inc(cos[-1]);
end;
end;
begin
assign(input,'wissqu.in');reset(input);
assign(output,'wissqu.out');rewrite(output);
init;
dfs_first(yy,rec,cs,neww);
writeln(count);
close(input);close(output);
end. |
{$ A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$ M 65520,0,655360}
{
TASK: wissqu
LANG: PASCAL
ID: awesome5
}
//AC版本
//ac——Optimization改变：
//if continue改到循环外、静态数组记录路径、longint取代其他类型、第一层循环优化
//inline优化、编译开关优化、固定内存空间的编译优化、不关闭读入文件的优化：
//优化结果：USACO： 4.666s
//for tripley
//by phoeagon
//search_stupid
//keep it simple, stupid
//2009-2-15
//yesterday was valentines'
type
{Toprt=^oprt;
oprt=record
cow,x,y:longint;
pre:toprt;
end;}
toprt=array[0..17,1..3]of longint;
map=array[0..5,0..5]of longint;
tot=array[0..5,0..5]of boolean;
ct=array[-1..4]of longint;
const
tt:Array[0..8,1..2]of longint=((0,-1),(0,1),(1,0),(-1,0),
(1,1),(-1,-1),(-1,1),(1,-1),(0,0));
var
outt:boolean;
root{,neww}:toprt;
yy:map;
rec:tot;
count:longint;
cs:ct=(16,3,3,3,4,3);
tmp:array[0..5,0..5]of boolean;
{procedure prn(const a:tot);inline;
var
i,j:longint;
begin
for i:=1 to 4 do begin
for j:=1 to 4 do
write(a[i,j]);
writeln;
end;
end;}
{function okay(const a,b:longint):boolean;inline;
begin
if a>0 then
if a<5 then
if b>0 then
if b<5 then
exit(true);
exit(false);
end; }
procedure init;inline;
var
i,j,c:longint;x:char;
begin
fillchar(yy,sizeof(yy),10);
for i:=1 to 4 do
begin
for j:=1 to 4 do begin
read(x);
if x='D'then
for c:=0 to 8 do
tmp[i+tt[c,1],j+tt[c,2]]:=true;
yy[i,j]:=ord(x)-ord('A');
end;
readln;
end;
//new(root);
//fillchar(root,sizeof(root),0);
//new(newW);
//fillchar(neww^,sizeof(neww^),0);
//neww^.pre:=root;
end;
procedure trace(const n:toprt);inline;
var i:longint;
begin
for i:=1 to 16 do
writeln( chr(n[i][1]+ord('A')),' ',n[i][2],' ',n[i][3]);
end;
procedure dfs(var rt:map;var rec:tot;var cos:ct;var node:toprt);inline;
var
{***}tmp:longint;{***}
a,i,j,c:longint;
can:boolean;
//nod:toprt;
begin
if cos[-1]=0 then
begin
inc(count);//writeln(count);
if not outt then begin
trace(node);
outt:=true; end;//writeln(count);
end
else
begin
inc(node[0][1]);
for a:=0 to 4 do //determine the current cow
if cos[a]>0 then
begin
dec(cos[a]);dec(cos[-1]);
node[node[0][1]][1]:=a;
//check availability
for i:=1 to 4 do
for j:=1 to 4 do
if not rec[i,j]then//try to put it on (i,j)
begin
//if rec[i,j]then continue;
if a=rt[i,j] then
continue;
can:=true;
for c:=0 to 7 do
//if okay(i+tt[c,1],j+tt[c,2])then
if rt[i+tt[c,1],j+tt[c,2]]=a then
begin
can:=false;
break;
end;
if not can then continue;
tmp:=rt[i,j];
rec[i,j]:=true;
//node^.x:=i;node^.y:=j;
{new(nod);
fillchar(nod^,sizeof(nod^),0);
nod^.pre:=node;
rt[i,j]:=chr(a+ord('A'));
//prn(rec);}
node[node[0][1]][2]:=i;node[node[0][1]][3]:=j;
rt[i,j]:=a;
dfs(rt,rec,cos,node);
rt[i,j]:=tmp;
{dispose(nod);}
rec[i,j]:=false;
end;
//check availablility
inc(cos[a]);inc(cos[-1]);
end;
dec(node[0][1]);
end;
end;
procedure dfs_first(var rt:map;var rec:tot;var cos:ct;var node:toprt);inline;
var
//tmp:char;
a,i,j,c:longint;
{***}can:longint;{***}
//nod:toprt;
begin
{a:=3;inc(node[0,1]);dec(cos[-1]);
rec[4,1]:=true;rt[4,1]:='D';dec(cos[3]);
node[node[0,1]][1]:=3;
node[node[0,1]][2]:=4;node[node[0,1]][3]:=1;
dfs(rt,rec,cos,node);
dec(node[0,1]);}
//a:=3;
inc(node[0,1]);dec(cos[-1]);dec(cos[3]);
node[node[0,1]][1]:=3;
for i:=1 to 4 do
for j:=1 to 4 do
if not tmp[i,j]then begin
can:=rt[i,j];
rec[i,j]:=true;rt[i,j]:=3;
node[node[0,1]][2]:=i;
node[node[0,1]][3]:=j;
dfs(rt,rec,cos,node);
rt[i,j]:=can;
rec[i,j]:=false;
end;
//dec(node[0,1]);
end;
begin
assign(input,'wissqu.in');reset(input);
assign(output,'wissqu.out');rewrite(output);
init;
dfs_first(yy,rec,cs,root);
writeln(count);
//close(input);
close(output);
end.
|
| |
|
完毕。
实践证明，这道题不Cheat也可以过，只是会浪费许多脑力和体力而已~~~当民族的USACO时，脑力体力和创造民族就这样~灰飞烟灭
BS那些cheat过这道题的人。
phoeagon
昨天情人节。
|
