Hướng dẫn giải của Cô gái chăn bò
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; r:array[1..13] of longint=(0,1,2,4,5,8,9,10,16,17,18,20,21); var num,i,m,n,re:longint; a:array[0..1,0..31] of longint; p:array[0..5] of longint; d:array[0..31,0..31] of byte; procedure init; var i,j,k,max:longint; k1,k2:boolean; begin p[0]:=1; for i:=1 to m do p[i]:=p[i-1]*2; max:=p[m]-1; fillchar(d,sizeof(d),0); for i:=0 to max do for j:=0 to max do begin k1:=false; k2:=false; for k:=1 to 13 do begin if i and j=r[k] then k1:=true; if i or j=max-r[k] then k2:=true; end; if k1 and k2 then begin d[i,j]:=1; d[j,i]:=1; end; end; end; procedure pr; var i,j,max,k,t:longint; begin if m>n then begin i:=m; m:=n; n:=i; end; init; max:=p[m]-1; dec(m); t:=1; fillchar(a,sizeof(a),0); for i:=0 to max do a[1,i]:=1; for i:=2 to n do begin t:=i mod 2; for j:=0 to max do a[t,j]:=0; for j:=0 to max do for k:=0 to max do if d[j,k]=1 then a[t,j]:=a[t,j]+a[1-t,k]; end; re:=0; for i:=0 to max do re:=re+a[t,i]; end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); readln(num); for i:=1 to num do begin readln(m,n); pr; writeln(re); end; close(input); close(Output); end.
Code mẫu của happyboy99x
#include<cstdio> #include<algorithm> using namespace std; int f[40][160], m, n; bool ok( int mask, int mask2 ) { for(int i=1; i<n; ++i) { int a = (mask & (1<<i))!=0, b = (mask & (1<<(i-1)))!=0; int c = (mask2 & (1<<i))!=0, d = (mask2 & (1<<(i-1)))!=0; if(a==b&&b==c&&c==d) return 0; } return 1; } int main() { int tc; scanf("%d",&tc); while(tc--) { scanf("%d%d",&m,&n); if(m<n) swap(m,n); for(int mask = (1<<n)-1; mask >= 0; --mask) f[1][mask] = 1; for(int i = 2; i <= m; ++i) for(int mask = (1<<n)-1; mask >= 0; --mask) { f[i][mask] = 0; for(int mask2 = (1<<n)-1; mask2 >= 0; --mask2) { if(ok(mask,mask2)) f[i][mask] += f[i-1][mask2]; //printf("%d %d %d\n", mask, mask2, ok(mask,mask2)); } } unsigned long long res = 0; for(int state = (1<<n)-1; state >= 0; --state) res += f[m][state]; printf("%llu\n", res); } return 0; }
Code mẫu của ladpro98
program cowgirl; uses math; var m,n,x:longint; f:array[0..30,0..32] of longint; check:array[0..32,0..32] of boolean; inp:text; Function GetBit(a,k:longint):longint; begin exit((a shr (k)) and 1); end; procedure init; var i,j,k:longint; begin x:=1; for i:=1 to n do x:=x*2; for i:=0 to 32 do for j:=0 to 32 do check[i,j]:=true; for i:=0 to x-1 do for j:=0 to x-1 do for k:=0 to n-2 do begin if (getbit(i,k) = getbit(j,k)) and (getbit(i,k+1) = getbit(j,k+1)) and (getbit(i,k)=getbit(i,k+1)) then begin check[i,j]:=false; end; end; end; function process:longint; var row,i,j,k,x2:longint; sum:int64; begin sum:=0; x2:=1; for i:=1 to m do x2:=x2*2; if n=1 then exit(x2); fillchar(f,sizeof(f),0); for i:=0 to x do f[1,i]:=1; for row:=2 to m do for i:=0 to x-1 do for j:=0 to x-1 do begin if check[i,j] then inc(f[row,j],f[row-1,i]); end; for i:=0 to x do inc(sum,f[m,i]); exit(sum); end; procedure input; var t,sotest,i:longint; begin readln(sotest); for i:=1 to sotest do begin read(m,n); if m<n then begin t:=m; m:=n; n:=t; end; init; writeln(process); end; end; begin input; end.
Code mẫu của RR
{$R+,Q+} PROGRAM COWGIRL; CONST maxn=30; fi=''; fo=''; lt2:array[0..5] of integer=(1,2,4,8,16,32); VAR d:array[1..maxn,0..31] of longint; ok:array[0..31,0..31] of integer; m,n:integer; f1,f2:text; Procedure OpenFiles; Begin Assign(f1,fi); Reset(f1); Assign(f2,fo); Rewrite(f2); End; Procedure CloseFiles; Begin Close(f1); Close(f2); End; Procedure WriteOutput; Var i:integer; sl:longint; Begin sl:=0; For i:=0 to lt2[m]-1 do sl:=sl+d[n,i]; Writeln(f2,sl); End; Procedure Swap(var a,b:integer); Var temp:integer; Begin temp:=a; a:=b; b:=temp; End; Procedure Prepare; Var i,j,k,u,v:integer; b:boolean; Begin For i:=0 to lt2[m]-1 do For j:=0 to lt2[m]-1 do begin b:=true; For k:=0 to m-2 do begin u:=(i shr k) and 3; v:=(j shr k) and 3; If (u or v=0) or (u and v=3) then begin b:=false; break; end; end; If b then ok[i,j]:=1 else ok[i,j]:=0; end; End; Procedure Calculate; Var i,j,k:integer; Begin For j:=0 to lt2[m]-1 do d[1,j]:=1; For i:=2 to n do For j:=0 to lt2[m]-1 do begin d[i,j]:=0; For k:=0 to lt2[m]-1 do If ok[j,k]=1 then d[i,j]:=d[i,j]+d[i-1,k]; end; End; Procedure Solve; Var t,i:integer; Begin Readln(f1,t); For i:=1 to t do begin Readln(f1,m,n); If m>n then Swap(m,n); Prepare; Calculate; WriteOutput; end; End; BEGIN OpenFiles; Solve; CloseFiles; END.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> #include <math.h> int F(int m,int a,int b) { int A[6],B[6],i,t=1; for(int i=1;i<=m;i++) { A[i]=a%2; a=a/2; B[i]=b%2; b=b/2; } for(int i=1;i<m;i++) { if((A[i]==0&&B[i]==0&&A[i+1]==0&&B[i+1]==0)||(A[i]==1&&B[i]==1&&A[i+1]==1&&B[i+1]==1)) t=0; } return t; } main() { long T,n,m,KQ; scanf("%ld",&T); for(long i=0;i<T;i++) { KQ=0; long f[33][33],thay,t; scanf("%ld %ld",&n,&m); if(n<m) { thay=n; n=m; m=thay; } t=pow(2,m); for(long i=0;i<t;i++) f[1][i]=1; for(long i=2;i<=n;i++) for(long j=0;j<t;j++) { f[i][j]=0; for(long k=0;k<t;k++) if(F(m,j,k)==1) f[i][j]+=f[i-1][k]; } for(long i=0;i<t;i++) KQ+=f[n][i]; printf("%ld\n",KQ); } //getch(); }
Code mẫu của ll931110
Program COWGIRL; Const input = ''; output = ''; maxn = 30; maxd = 40; Var F: array[0..maxd,1..maxn] of longint; m,n: longint; t,i: longint; fi,fo: text; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure optimize; Var i,j,k,res: longint; a,b,c,d: longint; x,y,tmp: longint; ok: boolean; Begin Fillchar(F, sizeof(F), 0); Readln(fi, m, n); If m > n then Begin tmp:= m; m:= n; n:= tmp; End; For i:= 0 to 1 shl m - 1 do F[i,1]:= 1; For i:= 2 to n do For x:= 0 to 1 shl m - 1 do For y:= 0 to 1 shl m - 1 do Begin ok:= true; For k:= 0 to m - 2 do Begin If (x and (1 shl k)) = (1 shl k) then a:= 1 else a:= 0; If (x and (1 shl (k + 1))) = (1 shl (k + 1)) then b:= 1 else b:= 0; If (y and (1 shl k)) = (1 shl k) then c:= 1 else c:= 0; If (y and (1 shl (k + 1))) = (1 shl (k + 1)) then d:= 1 else d:= 0; tmp:= a + b + c + d; If (tmp = 0) or (tmp = 4) then Begin ok:= false; break; End; End; If ok then F[x,i]:= F[x,i] + F[y,i - 1]; End; res:= 0; For i:= 0 to 1 shl m - 1 do res:= res + F[i,n]; Writeln(fo, res); End; Procedure closefile; Begin Close(fo); Close(fi); End; Begin openfile; Readln(fi, t); For i:= 1 to t do optimize; closefile; End.
Code mẫu của skyvn97
#include<stdio.h> typedef unsigned long long ull; ull res1[]={ 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, }; ull res2[]={ 14, 50, 178, 634, 2258, 8042, 28642, 102010, 363314, 1293962, 4608514, 16413466, 58457426, 208199210, }; ull res3[]={ 322, 2066, 13262, 85126, 546410, 3507314, 22512862, 144506294, }; ull res4[]={ 23858, 275690, 3185462, 36806846, }; ull res5[]={ 5735478, 119310334, }; int t,ct; ull m,n,s; int main(void) { scanf("%d",&t); for (ct=1;ct<=t;ct=ct+1) { scanf("%llu",&m); scanf("%llu",&n); if (m>n) { s=m;m=n;n=s; } if (m==1) printf("%llu\n",res1[n-1]); if (m==2) printf("%llu\n",res2[n-2]); if (m==3) printf("%llu\n",res3[n-3]); if (m==4) printf("%llu\n",res4[n-4]); if (m==5) printf("%llu\n",res5[n-5]); } }
Code mẫu của khuc_tuan
def ok(a,b,c): for i in range(c-1): if (a&(1<<i))!=0 and (a&(1<<(i+1)))!=0 and (b&(1<<i))!=0 and (b&(1<<(i+1)))!=0:return False if (a&(1<<i))==0 and (a&(1<<(i+1)))==0 and (b&(1<<i))==0 and (b&(1<<(i+1)))==0:return False return True f = [[[0 for xx in range(100)] for yy in range(10)] for zz in range(40)] sum = [[0 for yy in range(10)] for zz in range(40)] for i in range(1,31): for j in range(1,6): for bit in range(1<<j): if i==1:f[i][j][bit]=1 else: for b2 in range(1<<j): if ok(bit,b2,j): f[i][j][bit] += f[i-1][j][b2] for i in range(1,31): for j in range(1,6): for bit in range(1<<j): sum[i][j] += f[i][j][bit] st=input() for i in range(st): m,n=[int(xx) for xx in raw_input().split()] if m>n: t=m m=n n=t print sum[n][m]
Bình luận