Editorial for Chuỗi hạt
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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],
Comments