经典例题

cool007zqw

头昏。IOI竞赛与其说是计算机语言竞赛还不如说是智力竞赛。唉，本人的智商看来是太低了。

shst

好亲切的题目

Tuturo

好,有一个比较变态的题目:
农场场主养了N头牛,牛棚是类似单元格子的形式,A行B列，（A*B>N）
实行现代化养牛以后，农场在每行，每列，每个斜线都安装了红外线设备，可以知道这一条支线上到底有多少牛，但是不能知道具体的位置。
现在，请通过编写程序，读取数据（每行的牛的个数Ai，每列的牛的个数Bi,和每斜线牛的个数遵循先左倾斜后右倾斜的存储方式存储Ci），生成一张表格，表示牛的具体位置。
呵呵，慢慢做吧……

cc90042938

我的天啊!!!???[em06]

shst

以下是引用Tuturo在2005-1-7 18:49:09的发言：

好,有一个比较变态的题目:

农场场主养了N头牛,牛棚是类似单元格子的形式,A行B列，（A*B>N）

实行现代化养牛以后，农场在每行，每列，每个斜线都安装了红外线设备，可以知道这一条支线上到底有多少牛，但是不能知道具体的位置。

现在，请通过编写程序，读取数据（每行的牛的个数Ai，每列的牛的个数Bi,和每斜线牛的个数遵循先左倾斜后右倾斜的存储方式存储Ci），生成一张表格，表示牛的具体位置。

呵呵，慢慢做吧……

是不是usaco的?

Tuturo

这个都被你发现了？的确如此

csung

.................................
我无语。。。。。。
Pascal还这么牛*？

qyfcool

好BT.

gongyilun

还是USACO比较系统，循序渐进，题库做起来太散了。

神秘客

【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行
每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max;   {放皇后数组}
b:array[2..2*max] of boolean; {/对角线标志数组}
c:array[-(max-1)..max-1] of boolean; {\对角线标志数组}
col:array[1..max] of boolean; {列标志数组}
total:integer;   {统计总数}

procedure output; {输出}
var i:integer;
begin
     write('No.':4,'[',total+1:2,']');
     for i:=1 to max do write(a:3);write('     ');
     if (total+1) mod 2 =0 then  writeln;  inc(total);
end;

function  ok(i,dep:integer):boolean;  {判断第dep行第i列可放否}
begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and
  (col=true) then   ok:=true
end;

procedure try(dep:integer);
var i,j:integer;
begin
     for i:=1 to max do    {每一行均有max种放法}
       if  ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false;  {/对角线已放标志}
c[dep-i]:=false;  {\对角线已放标志}
col:=false;    {列已放标志}
if dep=max then output
  else try(dep+1); {递归下一层}
a[dep]:=0;    {取走皇后,回溯}
b[i+dep]:=true;   {恢复标志数组}
c[dep-i]:=true;
col:=true;
       end;
end;

begin
     for i:=1 to max do begin a:=0;col:=true;end;
     for i:=2 to 2*max do b:=true;
     for i:=-(max-1) to max-1 do c:=true;
     total:=0;
     try(1);
     writeln('total:',total);
end.

【测试数据】
n=8 八皇后问题
No.[ 1]  1  5 8  6  3  7  2  4      No.[ 2]  1  6  8 3  7  4  2  5
No.[ 3]  1  7 4  6  8  2  5  3      No.[ 4]  1  7  5 8  2  4  6  3
No.[ 5]  2  4 6  8  3  1  7  5      No.[ 6]  2  5  7 1  3  8  6  4
No.[ 7]  2  5 7  4  1  8  6  3      No.[ 8]  2  6  1 7  4  8  3  5
No.[ 9]  2  6 8  3  1  4  7  5      No.[10]  2  7  3 6  8  5  1  4
No.[11]  2  7 5  8  1  4  6  3      No.[12]  2  8  6 1  3  5  7  4
No.[13]  3  1 7  5  8  2  4  6      No.[14]  3  5  2 8  1  7  4  6
No.[15]  3  5 2  8  6  4  7  1      No.[16]  3  5  7 1  4  2  8  6
No.[17]  3  5 8  4  1  7  2  6      No.[18]  3  6  2 5  8  1  7  4
No.[19]  3  6 2  7  1  4  8  5      No.[20]  3  6  2 7  5  1  8  4
No.[21]  3  6 4  1  8  5  7  2      No.[22]  3  6  4 2  8  5  7  1
No.[23]  3  6 8  1  4  7  5  2      No.[24]  3  6  8 1  5  7  2  4
No.[25]  3  6 8  2  4  1  7  5      No.[26]  3  7  2 8  5  1  4  6
No.[27]  3  7 2  8  6  4  1  5      No.[28]  3  8  4 7  1  6  2  5
No.[29]  4  1 5  8  2  7  3  6      No.[30]  4  1  5 8  6  3  7  2
No.[31]  4  2 5  8  6  1  3  7      No.[32]  4  2  7 3  6  8  1  5
No.[33]  4  2 7  3  6  8  5  1      No.[34]  4  2  7 5  1  8  6  3
No.[35]  4  2 8  5  7  1  3  6      No.[36]  4  2  8 6  1  3  5  7
No.[37]  4  6 1  5  2  8  3  7      No.[38]  4  6  8 2  7  1  3  5
No.[39]  4  6 8  3  1  7  5  2      No.[40]  4  7  1 8  5  2  6  3
No.[41]  4  7 3  8  2  5  1  6      No.[42]  4  7  5 2  6  1  3  8
No.[43]  4  7 5  3  1  6  8  2      No.[44]  4  8  1 3  6  2  7  5
No.[45]  4  8 1  5  7  2  6  3      No.[46]  4  8  5 3  1  7  2  6
No.[47]  5  1 4  6  8  2  7  3      No.[48]  5  1  8 4  2  7  3  6
No.[49]  5  1 8  6  3  7  2  4      No.[50]  5  2  4 6  8  3  1  7
No.[51]  5  2 4  7  3  8  6  1      No.[52]  5  2  6 1  7  4  8  3
No.[53]  5  2 8  1  4  7  3  6      No.[54]  5  3  1 6  8  2  4  7
No.[55]  5  3 1  7  2  8  6  4      No.[56]  5  3  8 4  7  1  6  2
No.[57]  5  7 1  3  8  6  4  2      No.[58]  5  7  1 4  2  8  6  3
No.[59]  5  7 2  4  8  1  3  6      No.[60]  5  7  2 6  3  1  4  8
No.[61]  5  7 2  6  3  1  8  4      No.[62]  5  7  4 1  3  8  6  2
No.[63]  5  8 4  1  3  6  2  7      No.[64]  5  8  4 1  7  2  6  3
No.[65]  6  1 5  2  8  3  7  4      No.[66]  6  2  7 1  3  5  8  4
No.[67]  6  2 7  1  4  8  5  3      No.[68]  6  3  1 7  5  8  2  4
No.[69]  6  3 1  8  4  2  7  5      No.[70]  6  3  1 8  5  2  4  7
No.[71]  6  3 5  7  1  4  2  8      No.[72]  6  3  5 8  1  4  2  7
No.[73]  6  3 7  2  4  8  1  5      No.[74]  6  3  7 2  8  5  1  4
No.[75]  6  3 7  4  1  8  2  5      No.[76]  6  4  1 5  8  2  7  3
No.[77]  6  4 2  8  5  7  1  3      No.[78]  6  4  7 1  3  5  2  8
No.[79]  6  4 7  1  8  2  5  3      No.[80]  6  8  2 4  1  7  5  3
No.[81]  7  1 3  8  6  4  2  5      No.[82]  7  2  4 1  8  5  3  6
No.[83]  7  2 6  3  1  4  8  5      No.[84]  7  3  1 6  8  5  2  4
No.[85]  7  3 8  2  5  1  6  4      No.[86]  7  4  2 5  8  1  3  6
No.[87]  7  4 2  8  6  1  3  5      No.[88]  7  5  3 1  6  8  2  4
No.[89]  8  2 4  1  7  5  3  6      No.[90]  8  2  5 3  1  7  4  6
No.[91]  8  3 1  6  2  5  7  4      No.[92]  8  4  1 3  6  2  7  5
total:92
对于N皇后:
┏━━━┯━━┯━━┯━━┯━━┯━━┯━━┯━━┓
┃皇后 N│ 4  │ 5  │ 6  │ 7 │ 8  │ 9  │ 10 ┃
┠───┼──┼──┼──┼──┼──┼──┼──┨
┃方案数│ 2  │ 10 │ 4  │ 40 │ 92 │352 │724 ┃
┗━━━┷━━┷━━┷━━┷━━┷━━┷━━┷━━┛

[此贴子已经被作者于2004-9-12 10:31:30编辑过]