Hướng dẫn giải của Chuỗi hạt
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 maxn=255; base=1000000000; dg=9; type bignum=array[0..20] of longint; var n,re,i,j,t:longint; f:array[1..maxn,1..maxn*2] of bignum; d:array[0..maxn] of longint; a:bignum; s,st:string; code:integer; procedure plus(var a,b,c:bignum); var i,mem,max:longint; begin mem:=0; if b[0]>c[0] then max:=b[0] else max:=c[0]; for i:=1 to max do if b[i]+c[i]+mem>=base then begin a[i]:=(b[i]+c[i]+mem) mod base; mem:=1; end else begin a[i]:=b[i]+c[i]+mem; mem:=0; end; if mem=1 then begin inc(max); a[max]:=1; end; a[0]:=max; end; procedure minus(var a,b,c:bignum;z:longint); var i,mem:longint; begin mem:=0; for i:=1 to b[0] do if b[i]-c[i]-mem>=0 then begin a[i]:=b[i]-c[i]-mem; mem:=0; end else begin a[i]:=b[i]+base-c[i]-mem; mem:=1; end; a[0]:=b[0]; while (a[a[0]]=0) and (a[0]>1) do dec(a[0]); if z=0 then exit; mem:=1; for i:=1 to a[0] do if a[i]+mem=base then begin a[i]:=0; mem:=1; end else begin inc(a[i]); mem:=0; break; end; if mem=1 then begin inc(a[0]); a[a[0]]:=1; end; end; procedure put(var a,b:bignum); var i:longint; begin for i:=0 to b[0] do a[i]:=b[i]; end; function small(var a,b:bignum):boolean; var i:longint; begin small:=true; if a[0]<b[0] then exit; if a[0]>b[0] then begin small:=false; exit; end; for i:=a[0] downto 1 do begin if a[i]<b[i] then exit; if a[i]>b[i] then begin small:=false; exit; end; end; end; begin readln(n); readln(s); a[0]:=(length(s)+dg-1) div dg; for i:=1 to a[0]-1 do begin st:=copy(s,length(s)-i*dg+1,dg); val(st,a[i],code); end; t:=length(s) mod dg; if t=0 then t:=dg; st:=copy(s,1,t); val(st,a[a[0]],code); f[n,n*2,0]:=1; f[n,n*2,1]:=1; for j:=n*2-1 downto n do begin f[n,j,0]:=1; f[n,j,1]:=2*n-j+1; end; for i:=n-1 downto 1 do begin put(f[i,i*2],f[i+1,i*2+1]); for j:=i*2-1 downto i do plus(f[i,j],f[i+1,j+1],f[i,j+1]); end; minus(a,f[1,1],a,1); for i:=1 to n do for j:=i*2 downto d[i-1]+1 do if small(a,f[i,j]) then begin d[i]:=j; minus(a,a,f[i,j+1],0); break; end; for i:=1 to n do write(d[i],' '); end.
Code mẫu của happyboy99x
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cassert> using namespace std; const int N = 250 + 5, BASE = 1000000000, MAX_DIGIT = 30, LOG_BASE = 9; struct BigInteger { int d[MAX_DIGIT], n; void operator = (const int &x) { memset(d, 0, sizeof d); n = 0; for(int t = x; t != 0; t /= BASE) d[n++] = t % BASE; } bool operator < (const BigInteger &a) const { if(n < a.n) return true; if(n > a.n) return false; for(int i = n-1; i >= 0; --i) if(d[i] < a.d[i]) return true; else if(d[i] > a.d[i]) return false; return false; } void operator += (const BigInteger &a) { int rem = 0; n = max(n, a.n); for(int i = 0; i < n; ++i) { int p = d[i] + a.d[i] + rem; if(p >= BASE) d[i] = p - BASE, rem = 1; else d[i] = p, rem = 0; } if(rem) d[n++] = rem; } void operator -= (const BigInteger &a) { int rem = 0; for(int i = 0; i < n; ++i) { int p = d[i] - a.d[i] - rem; if(p < 0) d[i] = p + BASE, rem = 1; else d[i] = p, rem = 0; } while(n > 0 && d[n-1] == 0) --n; } void scan() { string s; cin >> s; int l = s.size(); reverse(s.begin(), s.end()); memset(d, 0, sizeof d); for(n = 0; LOG_BASE * n < l; ++n) for(int j = min(LOG_BASE * (n+1), l) - 1; j >= LOG_BASE * n; --j) d[n] = d[n] * 10 + s[j] - '0'; } } f[N][2*N]; int main() { int n; BigInteger x; scanf("%d", &n); x.scan(); for(int v = 2*n; v >= n; --v) f[n][v] = 1; for(int p = n-1; p >= 1; --p) for(int v = 2*p; v >= p; --v) for(int nv = 2*(p+1); nv > v; --nv) f[p][v] += f[p+1][nv]; for(int p = 1, v = 1; p <= n; ++p, ++v) { while(f[p][v] < x) x -= f[p][v], ++v; if(p > 1) printf(" "); printf("%d", v); } printf("\n"); return 0; }
Code mẫu của RR
{$R+,Q+} program CHUOIHAT; uses math; const FINP=''; FOUT=''; MAXN=251; oo=100000000; type bigNum=array[0..100] of longint; var n:longint; c:array[1..MAXN,0..MAXN*2] of bigNum; k:bigNum; procedure inp; var f:text; s:string; code:integer; begin assign(f,FINP); reset(f); readln(f,n); readln(f,s); while length(s)>8 do begin inc(k[0]); val(copy(s,length(s)-7,8),k[k[0]],code); s:=copy(s,1,length(s)-8); end; inc(k[0]); val(s,k[k[0]],code); close(f); end; operator +(a,b:bigNum) c:bigNum; var nho,i:integer; begin fillchar(c,sizeof(c),0); c[0]:=max(a[0],b[0]); nho:=0; for i:=1 to c[0] do begin c[i]:=a[i]+b[i]+nho; nho:=c[i] div oo; c[i]:=c[i] mod oo; end; if nho>0 then begin inc(c[0]); c[c[0]]:=nho; end; end; procedure tru(var a:bigNum;b:bigNum); var nho,i:integer; begin nho:=0; for i:=1 to a[0] do begin a[i]:=a[i]-b[i]-nho; if a[i]<0 then begin nho:=1; a[i]:=a[i]+oo; end else nho:=0; end; for i:=a[0] downto 1 do if a[i]<>0 then break; a[0]:=i; end; operator >=(a,b:bigNum) c:boolean; var i:integer; begin if a[0]>b[0] then begin c:=true; exit; end; if b[0]>a[0] then begin c:=false; exit; end; for i:=a[0] downto 1 do begin if a[i]>b[i] then begin c:=true; exit; end; if b[i]>a[i] then begin c:=false; exit; end; end; c:=true; end; procedure solve; var i,j:integer; begin for j:=n to n*2 do begin c[n,j,0]:=1; c[n,j,1]:=1; end; for i:=n-1 downto 1 do begin c[i,i*2+1]:=c[i+1,i*2+2]; for j:=i*2 downto i do c[i,j]:=c[i+1,j+1]+c[i,j+1]; end; end; procedure ans; var f:text; i,j,jj:integer; begin assign(f,FOUT); rewrite(f); jj:=0; for i:=1 to n do begin for j:=jj+1 to 2*i do if c[i,j]>=k then break else tru(k,c[i,j]); write(f,j,' '); jj:=j; end; close(f); end; begin inp; solve; ans; end.
Code mẫu của khuc_tuan
n=input() X=input() F=[[0 for _x in range(2*n+1)] for _y in range(n+1)] a=[0 for _x in range(n+1)] for k in range(1,2*n+1): F[n][k]=1 for i in range(n-1,0,-1): F[i][2*i]=F[i+1][2*i+1]+F[i+1][2*i+2] for j in range(2*i-1,0,-1): F[i][j]=F[i][j+1]+F[i+1][j+1] def truyvet(i,j,X): if(i<=n): for k in range(j+1,2*n+1): if F[i][k]>=X: a[i]=k truyvet(i+1,k,X) return else: X-=F[i][k] truyvet(1,0,X) for i in range(1,n+1): print a[i],
Bình luận