Editorial for Help Conan 13!
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 RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=20000; oo=1000000000000000000; var f1,f2:text; sl,test,hsize:longint; n:int64; h,a,x:array[1..MAXN] of int64; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure swap(var a,b:int64); var temp:int64; begin temp:=a; a:=b; b:=temp; end; procedure downHeap(i:longint); var j:longint; begin j:=i<<1; while (j<=hsize) do begin if (j<hsize) and (h[j+1]<h[j]) then inc(j); if (h[j]<h[i]) then swap(h[i],h[j]); i:=j; j:=i<<1; end; end; procedure upHeap(i:longint); var j:longint; begin j:=i>>1; while (i>1) and (h[i]<h[j]) do begin swap(h[i],h[j]); i:=j; j:=i>>1; end; end; procedure push(u:int64); begin inc(hsize); h[hsize]:=u; upHeap(hsize); end; procedure pop(var u:int64); begin u:=h[1]; swap(h[1],h[hsize]); dec(hsize); downHeap(1); end; function get(u:int64):int64; var x1,x2:int64; begin if (u=0) then exit(0); if (u=1) then exit(1); if (u=2) then exit(1); while u mod 2=0 do u:=u>>1; u:=u>>1; x1:=1; x2:=1; while (u>=2) do begin if u mod 2=0 then x1:=x1+x2 else x2:=x2+x1; u:=u>>1; end; exit(x1+x2); end; procedure init; var u,v:int64; ln:int64; begin hsize:=1; h[1]:=1; ln:=-oo; sl:=0; while hsize>0 do begin pop(u); v:=get(u); while (hsize>0) and (h[1]=u) do pop(u); if v>ln then begin inc(sl); a[sl]:=u; x[sl]:=v; ln:=v; if u<<1-1<=oo then push(u<<1-1); if u<<1+1<=oo then push(u<<1+1); if u<<2-1<=oo then push(u<<2-1); if u<<2+1<=oo then push(u<<2+1); end; end; end; procedure solve; var l,r,mid,kq:longint; begin l:=1; r:=sl; repeat mid:=(l+r)>>1; if a[mid]<=n then begin kq:=mid; l:=mid+1; end else r:=mid-1; until l>r; writeln(f2,x[kq]); end; begin openF; init; read(f1,test); for test:=1 to test do begin read(f1,n); solve; end; closeF; end.
Code mẫu của hieult
#include <cstdio> //#include <conio.h> typedef unsigned long long ul; ul fibo[65],n,c1,c2,temp; ul f(ul x) { if(x == 0) return 0; while(x%2==0) x=x>>1; if(x== 1) return 1; ul x1 = 1,x2=1; x = x>>1; while (x>=2) { if (x%2 ==1) x2+=x1; else x1+=x2; x = x>>1; } return x1+x2; } int main() { fibo[0] = 0; fibo[1] = 1; for(int i = 2;i<=64;i++) fibo[i] = fibo[i-1]+fibo[i-2]; int test; scanf("%d",&test); for(int ii = 1;ii<=test;ii++) { scanf("%llu",&n); ul KQ = 0; for(int i = 0;n>0;i++,n/=2) { if(n%2==1) { c1 = f(n-1); c2 = f(n); if(c1<c2) {temp = c1; c1 = c2;c2 = temp;} if(KQ<c1*fibo[i+1]+c2*fibo[i]) KQ = c1*fibo[i+1]+c2*fibo[i]; } } printf("%llu\n",KQ); } //getch(); }
Code mẫu của ll931110
#include <iostream> #include <queue> #include <vector> #include <cmath> using namespace std; long long calc(long long x) { if (x < 2) return x; while (!(x & 1)) x >>= 1; if (x < 3) return 1; long long y = 1, z = 1; for (x >>= 1; x > 1; x >>= 1) (x & 1)?(z += y):(y += z); return y + z; }; int main() { int inf,sup,med,nTest; long long ret; // freopen("mr.in","r",stdin); // freopen("mr.o1","w",stdout); priority_queue<long long> q; vector< pair<long long, long long> > v; q.push(-1); v.push_back(make_pair(0,0)); while (!q.empty()) { long long u = -q.top(); q.pop(); if (u != v[v.size() - 1].first) { long long t = calc(u); if (t > v[v.size() - 1].second) { v.push_back(make_pair(u,t)); if (4 * u + 1 <= 1e18) q.push(-(4 * u + 1)); if (4 * u - 1 <= 1e18) q.push(-(4 * u - 1)); if (2 * u + 1 <= 1e18) q.push(-(2 * u + 1)); if (2 * u - 1 <= 1e18) q.push(-(2 * u - 1)); }; }; }; long long n; scanf("%d\n", &nTest); do { nTest--; scanf("%lld\n", &n); inf = 0; sup = v.size() - 1; ret = 0; while (inf <= sup) { med = (inf + sup)/2; if (v[med].first <= n) { ret = v[med].second; inf = med + 1; } else sup = med - 1; }; printf("%lld\n", ret); } while (nTest > 0); };
Comments