Hướng dẫn giải của Số không (I)


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.

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

var n,num,k:longint;
    d:array[0..65] of byte;
    c:array[0..32,0..32] of longint;
    sl:array[0..32] of int64;
    re:int64;

procedure init;
var i:longint;
begin
     fillchar(d,sizeof(d),0);
     i:=0;
     while n>0 do
     begin
          d[i]:=n mod 2;
          n:=n div 2;
          inc(i);
     end;
     num:=i;
end;

procedure ini;
var i,j:longint;
begin
     fillchar(c,sizeof(c),0);
     c[0,0]:=1;
     for i:=1 to 32 do
     begin
          c[i,0]:=1;
          c[i,i]:=1;
          for j:=1 to i-1 do
              c[i,j]:=c[i-1,j]+c[i-1,j-1];
     end;
end;

procedure work(k:longint);
var i,num0,j:longint;
begin
     fillchar(sl,sizeof(sl),0);
     for i:=1 to num-1 do
         for j:=1 to i-1 do
             sl[j]:=sl[j]+c[i-1,j];
     num0:=0;
     for i:=num-2 downto 0 do
         if d[i]=1 then
         begin
              for j:=0 to i do
                  sl[j+num0+1]:=sl[j+num0+1]+c[i,j];
         end
         else inc(num0);
     num0:=0;
     for i:=0 to num-1 do
         if d[i]=0 then inc(num0);
     inc(sl[num0]);
     for i:=1 to 32 do
         for j:=(i-1)*k+1 to i*k do
        if j<=32 then
             re:=re+sl[j]*i;
end;

begin
     ini;
     while not eof do
     begin
          readln(n,k);
          if n=1 then
          begin
               writeln(0);
               continue;
          end;
          init;
          re:=0;
          work(k);
          writeln(re);
     end;
end.

Code mẫu của happyboy99x

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

long long f[32][32][2][2];
int g[32][2][2];
int n;
int k;

int G(int bit, int smaller, int started) {
    if (bit == -1) return started;
    int &res = g[bit][smaller][started];
    if (res != -1) return res;
    res = G(bit - 1, smaller | (n >> bit & 1), started);
    if (smaller == 1 || (n >> bit & 1) == 1) {
        res += G(bit - 1, smaller, 1);
    }
    return res;
}

long long F(int bit, int fromLastZero, int smaller, int started) {
    if (bit == -1) return 0;
    long long &res = f[bit][fromLastZero][smaller][started];
    if (res != -1) return res;
    res = F(bit - 1, started == 1 ? (fromLastZero + 1) % k : 0, smaller | (n >> bit & 1), started)
          + (started == 1 && fromLastZero == 0 ? G(bit - 1, smaller | (n >> bit & 1), started) : 0);
    if (smaller == 1 || (n >> bit & 1) == 1) {
        res += F(bit - 1, fromLastZero, smaller, 1);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while (cin >> n >> k) {
        memset(f, -1, sizeof f);
        memset(g, -1, sizeof g);
        printf("%lld\n", F(31, 0, 0, 0));
    }
    return 0;
}

Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Pham Quang Vu
program VN_ZR_I;
const
  inp='';
  out='';
type
  mang=array[1..50] of longint;
var
  fi,fo:text;
  n,k,nbit:longint;
  bit:mang;
  c:array[0..40,0..40] of int64;
procedure openfile;
begin
  assign(fi,inp);reset(fi);
  assign(fo,out);rewrite(fo);
end;
procedure getbit(x:longint;var c:mang;var top:longint);
begin
  top:=0;
  while x>0 do
    begin
      inc(top);
      c[top]:= x and 1;
      x:=x shr 1;
    end;
end;
procedure init;
var
  i,j:longint;
begin
  for i:=0 to 34 do c[0,i]:=1;
  for i:=1 to 34 do
    begin
      c[i,i]:=1;
      for j:=i+1 to 34 do c[i,j]:=c[i,j-1]+c[i-1,j-1];
    end;
end;
procedure solve;
var
  count,i,j:longint;
  result:int64;
begin
  getbit(n,bit,nbit);
  result:=0;
  for i:=nbit-1 downto 1 do
    for j:=1 to i-1 do
      result:=result+c[j,i-1]*((j-1) div k+1);
  count:=0;
  for i:=nbit-1 downto 1 do
    if bit[i]=1 then
      begin
        for j:=0 to i-1 do
          result:=result+c[j,i-1]*((j+count) div k+1);
      end
    else inc(count);
  if count>=1 then result:=result+(count-1) div k+1;
  writeln(fo,result);
end;
procedure enter;
begin
  init;
  while not eof(fi) do
    begin
      readln(fi,n,k);
      if (n=0) and (k=0) then exit;
      solve;
    end;
end;
procedure closefile;
begin
  close(fi);
  close(fo);
end;
begin
  openfile;
  enter;
  closefile;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 790972
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
#define maxn 505
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, -1, 0, +1};

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

typedef long long ll;

#define modun 2

int num, a[100];
ll dp[33][2][2][33];
long long n, m;

ll go(int pos, int less, int zero, int cnt) {
    if (pos < 0){
        if(!cnt) return 0;
        else return (cnt - 1)/ m + 1;
    }

    ll &ret = dp[pos][less][zero][cnt];
    if (ret != -1) return ret;

   // cout << pos << " " << less << " " << zero << " " << cnt << endl;

    ret = 0;

    int maxd = less ? 1 : a[pos];
    for (int d = 0; d <= maxd; ++d) {
        ret += go(pos - 1, less | (d < a[pos]), zero | d, cnt + (zero && (!d)));
    }

    return ret;
}

ll howmany(ll A) {
    if (A <= 0) return 0;

    num = 0;
    while (A > 0) {
    a[num++] = A & 1;
    A >>= 1;
    }

    memset(dp, -1, sizeof(dp));
    return go(num - 1, 0, 0, 0);
}

ll solve(ll A, ll B) {
    if (A == 0) {
    if (B == 0) return 1;
    return howmany(B) + 1;
    }
    return howmany(B) - howmany(A - 1);
}


int main(){
    //OPEN();
    while(scanf("%lld %lld", &n, &m) > 0){
        printf("%lld\n", howmany(n));
    }
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int n,k;
int c[34][34];
int digit,d[34];

void getC()
{
     memset(c,0,sizeof(c));
     for (int i = 0; i <= 32; i++) c[0][i] = 1;
     for (int j = 1; j <= 32; j++)
       for (int i = 1; i <= 32; i++) c[i][j] = c[i - 1][j - 1] + c[i][j - 1];     
};

ll rec(int pos,int p)
{
   if (p < 0) return 0;
   if (!pos) return (p == 0) ? 1 : 0;
   if (d[pos] == 0) return (rec(pos - 1,p - 1));
   else
   {
     ll tmp = rec(pos - 1,p);
     if (p) tmp += c[p - 1][pos - 1];
//     cout << "answer: " << pos << ' ' << p << ' ' << tmp << endl;
     return tmp;
   };
};

ll calc(int x)
{
   //x zeroes in the numbers
//   if (x != 2) return 0;
   ll ret = 0;
   for (int i = 2; i < digit; i++) ret += c[x][i - 1];
//   cout << ret << endl;
   ret += rec(digit - 1,x);
   return ret;
};

ll solve()
{
   ll ret = 0;
   digit = 0;  int tmp = n;
   while (tmp)
   {
         d[++digit] = tmp % 2;  tmp /= 2;
   };
   for (int i = 1; i < digit; i++)
   {
       tmp = calc(i); //if (i == 2) cout << "query: " << i << ' ' << tmp << endl;
       ret += 1LL * tmp * ((i + k - 1)/k);
   };
   return ret;
};

int main()
{
//    freopen("zr.in","r",stdin);
//    freopen("zr.ou","w",stdout);
    getC();
    while (cin >> n >> k) cout << solve() << endl;
};

Code mẫu của khuc_tuan

#include "stdio.h"
#include "string.h"

    int n, k;
    int a[40], b[40];
    long long result;
    long C[33][33];

    void tinh(int i,int sk) {
        for(int j=0;j<=i;++j) {
            if(j+sk>0) result += C[j][i] * ((j+sk-1)/k+1);
        }
    }

    void duyet(int i, int sk) {
        if(i<0) {
            if(sk>0) result += (sk-1)/k + 1;
            return;
        }
        bool nhohon = false, lonhon = false;
        for(int j=33;j>i;--j) {
            if(a[j]>b[j]) {
                nhohon = true;
                break;
            }
            if(a[j]<b[j]) {
                lonhon = true;
                break;
            }
        }
        if(nhohon) { tinh(i+1,sk); return; }
        if(lonhon) return;
        b[i] = 0;
        duyet(i-1,sk+1);
        if(a[i]==1) {
            b[i] = 1;
            duyet(i-1,sk);
        }
    }

    void run() {
        memset( a, 0, sizeof(a));
        memset( b, 0, sizeof(b));
        int last=-1;
        for(int i=0;i<31;++i) if((n&(1<<i))!=0) { a[i] = 1; last = i; }

        result = 0;
        for(int i=last;i>=0;--i) {
            memset( b, 0, sizeof(b));
            b[i] = 1;
            duyet(i-1,0);
        }

        printf("%lld\n",result);
    }

    void init() {
        C[0][0] = 1;
        for(int i=1;i<33;++i) {
            C[0][i] = C[i][i] = 1;
            for(int j=1;j<i;++j) C[j][i] = C[j-1][i-1] + C[j][i-1];
        }
    }

    int main() {
        init();
        while(true) {
            n = -11;
            scanf("%d%d",&n,&k);
            if(n==-11) break;
            run();
        }
    }

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.