Description

Input

第一行為兩個整數n, m。第二行有n個整數，為a1，a2, …, an。

Output

包含n行，每行m個1~n×m的正整數，各不相同，以空格分開。如果有多解，輸出任意一組解；如果無解，輸出一個整數0。

Sample Input &?Sample Output

HINT

30%的數據滿足n, m≤10

100%的數據滿足3≤n, m≤200

?

題解：

把ai認為是i的父親，使其連邊，那么題目給出的關系構成了一個基環樹森林。

對于在環外、指向環的邊（即“樹”的部分），使骰子的每一個面都比其父親大。

觀察1、4樣例可以發現一個構造方式：對于一個大小為n環，從第一個點開始，逆著父親邊放入1~n；再從第一個點在環上的兒子開始，逆著父親邊以此放入n+1~2*n，直到放滿n*m個數。

但是這個構造法在樣例3中失敗了。事實上，可以證明，只有在像樣例3這種環大小為3，骰子面數為4的情況下，該方法會失效。對于這種情況，進行特判。

注意環大小為2或是m<=2的情況，一定無法構造。

?

代碼：

1 const 2 bb:array[1..12]of longint=(1,2,4,3,7,5,10,8,6,11,9,12); 3 var 4 i,j,k,l,n,m,cnt:longint; 5 fa,a,b,c:array[0..1001]of longint; 6 d:array[0..1001,0..1001]of longint; 7 procedure ss2(x:longint); 8 var i:longint; 9 begin 10 if a[x]<2 then 11 begin 12 for i:=1 to m do 13 begin inc(cnt); d[x,i]:=cnt; end; 14 a[x]:=2; 15 end; 16 i:=c[x]; 17 while i>0 do 18 begin 19 if a[i]<2 then ss2(i); 20 i:=b[i]; 21 end; 22 end; 23 procedure ss(x:longint); 24 var i,j,k,l,xx:longint; 25 begin 26 a[x]:=1; x:=fa[x]; 27 while a[x]=0 do 28 begin 29 a[x]:=1; x:=fa[x]; 30 end; 31 k:=1; xx:=fa[x]; a[x]:=2; 32 while x<>xx do begin inc(k); a[xx]:=2; xx:=fa[xx]; end; 33 if k<=2 then begin writeln(0); halt; end; 34 if(k=3)and(m=4)then 35 begin 36 for i:=1 to 12 do 37 begin 38 d[x,1+((i-1)div 3)]:=bb[i]; 39 x:=fa[x]; 40 end; 41 end else 42 begin 43 for i:=1 to m do 44 begin 45 l:=cnt+k; 46 for j:=1 to k do 47 begin 48 d[x,i]:=l; dec(l); 49 if j<>k then x:=fa[x]; 50 end; 51 cnt:=cnt+k; 52 end; 53 end; 54 for i:=1 to k do 55 begin 56 ss2(x); x:=fa[x]; 57 end; 58 end; 59 begin 60 readln(n,m); 61 for i:=1 to n do 62 begin 63 read(fa[i]); 64 b[i]:=c[fa[i]]; c[fa[i]]:=i; 65 end; 66 for i:=1 to n do 67 if a[i]=0 then ss(i); 68 for i:=1 to n do 69 begin 70 for j:=1 to m do write(d[i,j],' '); 71 writeln; 72 end; 73 end. View Code

轉載于:https://www.cnblogs.com/GhostReach/p/6255679.html

總結

以上是生活随笔為你收集整理的BZOJ1298:[SCOI2009]骰子的学问的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。