洛谷 P3048 [USACO12FEB]牛的IDCow IDs

题目描述

Being a secret computer geek, Farmer John labels all of his cows with binary numbers. However, he is a bit superstitious, and only labels cows with binary numbers that have exactly K "1" bits (1 <= K <= 10). The leading bit of each label is always a "1" bit, of course. FJ assigns labels in increasing numeric order, starting from the smallest possible valid label -- a K-bit number consisting of all "1" bits. Unfortunately, he loses track of his labeling and needs your help: please determine the Nth label he should assign (1 <= N <= 10^7).

FJ给他的奶牛用二进制进行编号，每个编号恰好包含K 个"1" (1 <= K <= 10)，且必须是1开头。FJ按升序编号，第一个编号是由K个"1"组成。

请问第N(1 <= N <= 10^7)个编号是什么。

输入输出格式

输入格式：

Line 1: Two space-separated integers, N and K.

输出格式：

输入输出样例

输入样例#1：

7 3

输出样例#1：

10110 

题解：
20暴力

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,pos,a[190];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=150;i<=149+k;i++)a[i]=1;
    pos=150;
    for(int i=2;i<=n;i++){
        int p;
        for(int j=149+k;j>=pos-1;j--)
         if(a[j]==0&&a[j+1]==1){
             p=j+1;break;
         }
         if(p==pos){
             pos--;memset(a,0,sizeof(a));
             a[pos]=1;
             for(int j=149+k;j>=151;j--)a[j]=1;
         }else {
             a[p]=0;a[p-1]=1;
         }
    }
    for(int i=pos;i<=149+k;i++)
     printf("%d",a[i]);
    return 0;
}

完全不懂这个AC代码

在洛谷上问了写这个代码的大佬..今天大佬给我讲了一下！

太神啦！这个题的题解网上都是一坨..(*゜ロ゜)ノ实在不愿意看..

（逃ヽ(ﾟ∀ﾟ*)ﾉ━━━ｩ♪

a[i]表示的是第i个1的位置，初始值为(按阳历来说)第一个1的位置是1，第二个

1的位置是2，第三个1的位置是3.二进制也就是1 1 1 。

我们开始找啦，样例是升序的第7个，我把1--7都列出来。

1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

1 0 0 1 1

1 0 1 0 1

1 0 1 1 0

发现的规律是，每次将二进制串的从右往左数的第1个前面为0的1往左移一位。

这个1右边的1全部靠后。因为二进制串的大小取决于1的位置，尽量别让高位有1。

然后我们从右往左找那个能移动的1吧。能移动的条件是，当前1的位置+1不等于

下一个1的位置，也就是前面是空的。然后就这样啊....

高质量的模拟确实应该学习一下...

代码：

#include<cstdio>
using namespace std;
int n,k,j;
int a[13];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)a[i]=i;
    for(int i=2;i<=n;i++){
        j=1;
        while(1){
            a[j]++;
            if(a[j]!=a[j+1])break;
            a[j]=j;
            j++;
        }
    }
    j=k;
    for(int i=a[k];i>=1;i--){
        if(a[j]==i)printf("1"),j--;
        else printf("0");
    }
    return 0;
}