Hướng dẫn giải của Đàn bò hỗn loạn
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=''; maxc=65535; maxn=15; var n,k:longint; re:int64; a:array[0..maxn] of longint; f:array[0..maxc,0..maxn] of int64; p:array[0..maxn] of longint; procedure rf; var i:longint; begin assign(input,fi); reset(input); read(n,k); dec(n); for i:=0 to n do read(a[i]); close(input); end; procedure init; var i:longint; begin p[0]:=1; for i:=1 to n+1 do p[i]:=p[i-1]*2; end; function out(j,i:longint):boolean; begin out:=((i shr j) and 1)=0; end; procedure pr; var i,j,max,q:longint; begin init; fillchar(f,sizeof(f),0); for i:=0 to 15 do f[p[i],i]:=1; max:=p[n+1]-1; for i:=1 to max do for j:=0 to n do if not out(j,i) then for q:=0 to n do if out(q,i) and (abs(a[q]-a[j])>k) then f[i or p[q],q]:=f[i or p[q],q]+f[i,j]; re:=0; for i:=0 to n do re:=re+f[max,i]; end; procedure wf; begin assign(output,fo); rewrite(output); write(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; #define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i) #define N 16 int a[N], n, k; long long f[1<<N][N]; vector<int> suit[N]; void enter() { scanf("%d%d",&n,&k); for(int i = 0; i < n; ++i) scanf("%d", a+i); } long long F(int state, int x) { long long & res = f[state][x]; if(res != -1) return res; if(state == 0) return res = 1; res = 0; TR(suit[x], it) { int t = *it; if(state & 1 << t) res += F(state & ~(1 << t), t); } return res; } void solve() { for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) if(abs(a[i] - a[j]) > k) suit[i].push_back(j); memset(f, -1, sizeof f); long long res = 0; for(int i = 0; i < n; ++i) res += F((1 << n) - 1 & ~(1 << i), i); printf("%lld\n", res); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
program mixup2; uses math; const maxN=16; maxS=1 shl maxN; fi=''; var f:array[0..maxS,0..maxN] of int64; a,power:array[0..maxN] of longint; n,m,k:longint; function getbit(a,i:longint):longint; begin exit(a shr (i-1) and 1); end; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,n,k); for i:=1 to n do readln(inp,a[i]); close(inp); end; procedure init; var i:longint; begin power[0]:=1; for i:=1 to n do power[i]:=power[i-1] shl 1; m:=power[n]-1; end; procedure dp; var i,j,t:longint; begin for i:=1 to n do f[0,i]:=1; for i:=1 to m do for t:=1 to n do if getbit(i,t)=0 then begin for j:=1 to n do if (getbit(i,j)=1) and (abs(a[n-t+1]-a[n-j+1])>k) then inc(f[i,t],f[i-power[j-1],j]); end; end; procedure output; var i:longint; res:int64; begin res:=0; for i:=0 to n-1 do inc(res,f[m-power[i],i+1]); write(res); end; begin input; init; dp; output; end.
Code mẫu của RR
{ PROG: mixup2 LANG: PASCAL ID: invinci3 } const FINP=''; FOUT=''; MAXN=16; var n,k:longint; kq:int64; s:array[0..MAXN] of longint; d:array[0..1 shl MAXN,1..MAXN] of int64; procedure inp; var f:text; i:longint; begin assign(f,FINP); reset(f); readln(f,n,k); for i:=1 to n do readln(f,s[i]); close(f); end; procedure ans; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,kq); close(f); end; procedure solve; var mask,last,next:longint; begin for last:=1 to n do d[1 shl (last-1),last]:=1; for mask:=0 to 1 shl n do for last:=1 to n do if mask and (1 shl (last-1))>0 then for next:=1 to n do if (mask and (1 shl (next-1))=0) and (abs(s[next]-s[last])>k) then inc(d[mask or (1 shl (next-1)),next],d[mask,last]); kq:=0; for last:=1 to n do inc(kq,d[1 shl n-1,last]); end; begin inp; solve; ans; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> long long f[70000][17], tong=0; int TTD(int x) { return x>0 ? x:-x;} int main() { //freopen("mixup.in","r",stdin); int n,M, a[17],b[17],chay=1; tong=0; scanf("%d %d",&n,&M); for(int i = 0;i<n;i++) scanf("%d",&a[i]); for(int i = 0;i<n;i++) f[0][i] = 1; b[0] = 1; for(int i = 1;i<n;i++) { b[i] = b[i-1]*2; chay = chay + b[i]; } for(int i = 1;i<=chay;i++) { int t[n],m= i; for(int j = 0;j<n;j++) { t[j] = m%2; m = m/2; } for(int j = 0;j<n;j++) { f[i][j]=0; if(b[j]==i) f[i][j]=1; else if(t[j]!=0) { for(int k = 0;k<n;k++) if(TTD(a[j]-a[k])>M) f[i][j]+=f[i-b[j]][k]; //if(i==8) printf("%d %d\n",j); } } //for(int j = 0;j<n;j++) //printf("%d ",f[i][j]); //printf("\n"); } for(int i = 0;i<n;i++) tong += f[chay][i]; printf("%lld",tong); //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program MIXUP2; Const input = ''; output = ''; Var a,d: array[0..16] of integer; F: array[0..65535,1..16] of int64; n,k: integer; Procedure init; Var fi: text; i: integer; Begin Assign(fi, input); Reset(fi); Readln(fi, n, k); For i:= 1 to n do read(fi, a[i]); Close(fi); End; Procedure power; Var i: integer; Begin d[0]:= 1; For i:= 1 to n do d[i]:= d[i - 1] shl 1; End; Procedure optimize; Var i,j,t,s,tmp: integer; Begin Fillchar(F, sizeof(F), 0); For i:= 1 to n do F[d[i - 1],i]:= 1; For i:= 0 to d[n] - 1 do For j:= 1 to n do if i and d[j - 1] = d[j - 1] then Begin t:= i - d[j - 1]; For s:= 1 to n do if t and d[s - 1] = d[s - 1] then Begin tmp:= abs(a[j] - a[s]); If tmp > k then F[i,j]:= F[i,j] + F[t,s]; End; End; End; Procedure printresult; Var fo: text; res: int64; i: integer; Begin Assign(fo, output); Rewrite(fo); res:= 0; For i:= 1 to n do res:= res + F[d[n] - 1,i]; Writeln(fo, res); Close(fo); End; Begin init; power; optimize; printresult; End.
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAX 17 typedef long long ll; ll f[MAX][1<<MAX]; int n,k; int a[MAX]; int lg2[1<<MAX]; int iabs(const int &x) { if (x<0) return (-x); else return (x); } void init(void) { scanf("%d",&n); scanf("%d",&k); int i; for (i=0;i<n;i=i+1) scanf("%d",&a[i]); for (i=0;i<MAX;i=i+1) lg2[1<<i]=i; } void optimize(void) { int i,j,s,t; for (i=0;i<n;i=i+1) f[i][(1<<n)-1-(1<<i)]=1; for (j=(1<<n)-1;j>=0;j=j-1) for (i=0;i<n;i=i+1) { if ((j|(1<<i))==j) continue; s=j; while (s>0) { t=lg2[s&(-s)]; if (abs(a[t]-a[i])>k) f[t][j-(1<<t)]+=f[i][j]; s=s-(1<<t); } } ll res=0; for (i=0;i<n;i=i+1) res+=f[i][0]; printf("%lld",res); } int main(void) { init(); optimize(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; int main() { int n, k; cin >> n >> k; int a[22]; for(int i=0;i<n;++i) cin >> a[i]; long long *f[n]; for(int i=0;i<n;++i) { f[i] = new long long[1<<n]; memset( f[i], 0, sizeof(long long) * (1<<n)); } for(int i=0;i<n;++i) f[i][1<<i] = 1; for(int bit=1;bit<(1<<n);++bit) for(int last=0;last<n;++last) if((bit&(1<<last))!=0) for(int l2=0;l2<n;++l2) if(l2!=last && (bit&(1<<l2))!=0 && abs(a[l2]-a[last])>k) f[last][bit] += f[l2][bit ^ (1<<last)]; long long r = 0; for(int i=0;i<n;++i) r += f[i][(1<<n)-1]; cout << r << endl; return 0; }
Bình luận