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.

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

Please read the guidelines before commenting.


There are no comments at the moment.