链接：https://ac.nowcoder.com/acm/contest/897/J

来源：牛客网

Binary Number

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

As a programmer, you are probably familiar with the binary representation of integers. That is, write an integer x as

∑

a

i

2

i

∑ai2i, where each

a

i

ai is either 0 or 1. Particularly, n-digit binary number can be written as

∑

n

−

1

i

0

a

i

2

i

∑i=0n−1ai2i, in which

a

n

−

1

an−1 must equal to 1.

This time, to test your mastery of binary numbers, Leg Han raises a problem to you.

Among all n-digit binary numbers whose amount of 1 is m, please print the k-th smallest one.

It is guaranteed that k is legal.

输入描述:

The first line contains an integer number T, the number of test cases.

i

t

h

ith of each next T lines contains three integers n, m, k(

1

≤

m

≤

n

≤

31

,

1

≤

k

≤

2

×

10

8

1≤m≤n≤31,1≤k≤2×108).

输出描述:

For each test case print the \(k\)-th smallest one.

示例1

输入

复制

2

5 2 2

5 3 3

输出

复制

10010

10110

题意：

思路：

我是反着来求的，要求第k小，我把所有情况sum算出来,令id=sum-k+1.然后求第id大的

从高位到低位，每一位我们考虑如果填了1，剩下还有种组合情况x，是否还够达到第id大，如果够就填1，不够就填0，并且id-=x。这样操作即可。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define rt return

#define dll(x) scanf("%I64d",&x)

#define xll(x) printf("%I64d\n",x)

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;}

inline void getInt(int *p);

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll getpc(ll m, ll n) //m 中 选 n 个

{

    long long ans = 1;

    for (long long k = 1; k <= n; k++) {

        ans = (ans * (m - n + k)) / k;

    }

    return ans;

}

ll n, m, k;

int main()

{

    //freopen("D:\\code\\text\\input.txt","r",stdin);

    //freopen("D:\\code\\text\\output.txt","w",stdout);

    int t;

    gbtb;

    cin >> t;

    while (t--) {

        cin >> n >> m >> k;

        ll sum = getpc(n - 1, m - 1);

        ll id = sum - k + 1ll;// 反过来求第id大的数。

        ll temp = 0ll;

        ll rm = m;// 剩余1的数量

        for (ll i = n; i > 0; --i) {

            ll x = getpc(i - 1, rm - 1);

            if (x >= id && rm) {

                cout << 1;

                rm--;

            } else {

                id -= x;

                cout << 0;

            }

            cout << flush;

        }

        cout << endl;

    }

    return 0;

}

inline void getInt(int *p)

{

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    } else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西

2019长安大学ACM校赛网络同步赛 J Binary Number（组合数学+贪心）

最新文章

热门文章