Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一个非DP的代码

Posted by C5Compound at 2019-08-23 00:34:45 on Problem 3252
#include <cstdio>
using namespace std;

// C(N, >= K)
int nk(int N, int K) {
    int re = 0;
    for (int i = N, s; i >= K; --i) {
        s = i == N ? 1 : s * (i + 1) / (N - i);
        re += s;
    }
    return re;
}

// round number [0 - 2 ^ N)
int func(int N) {
    int re = 1;
    for (int i = 1; i <= N; ++i) {
        re += nk(i - 1, (i >> 1) + (i & 1));
    }
    return re;
}

// round number [0, N)
int counts(int N) {
    int re = 0;
    // find highest bit
    for (int i = 30, s1 = 0, s0 = 0; i >= 0; --i) {
        if ((N >> i) & 1) {
            if (++s1 == 1) {
                re += func(i);
            } else {
                int t = s1 - s0 + i - 2;
                re += nk(i, (t >> 1) + (t & 1));
            }
        } else if (s1 > 0) {
            ++s0;
        }
    }
    return re;
}

int main(int argc, char **argv) {
    int S, F;
    scanf("%d%d", &S, &F);
    printf("%d\n", counts(F + 1) - counts(S));
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator