题目描述

Farmer John has taken to yodeling from the top of the barn in order to communicate with the cows out in the pastures. Being bovine and all, cows can hear binary messages (0's and 1's) but have trouble with perfect communications because FJ's yodeling echoes off the silo. In fact, in a sequence of bits, Bessie will always receive a sequence of N bits, with the same number of 0s and 1s, but each 0 or 1 might be delayed.
Precisely speaking, for a given number , the i-th bit might be heard as the j-th one as long as (in other words, no bit appears in a position farther than distance D from its original position). Consider the following message as an example: 0110. Four possible messages might be heard if D = 1: 0101, 0110, 1001, and 1010.
Given the message to be yodeled by FJ, along with two numbers D and , determine the number of different messages that might be heard by Bessie, modulo 100,000,000. Also determine the K-th smallest such message in lexicographical order (in binary representation, with 0 coming before 1). It is guaranteed that K will be no larger than the number of different possible messages.

输入描述:

* Line 1: Three space-separated integers: N, D, and K
* Line 2: FJ's binary message, containing exactly N bits

输出描述:

* Line 1: The number of different possible messages that can heard by Bessie, mod 100,000,000
* Line 2: The K-th smallest such message (in binary representation)
Note that if your program's first line of output is correct but the second line of output is either missing or wrong, you will receive 40% of the points for that test case.

示例1

输入
4 1 3 
0110 
输出
4
1001

解答

这题是个dp。

定义方程表示从，用了个的方案数。要倒着处理是为之后的第大做帮助。

第一问就直接dp，我们记录下分别表示从左往右第个的位置，第个的位置。转移的时候根据当前位放还是放，且是否满足距离小于等于，计算即可。

然后对于第二问，我们这么做：

  • 如果当前位置放的方案数，当前位就放。

  • 如果不能放，就放，并且减去放的方案数。

以上所有说的可以放或放都是建立在题目要求的前提下的，即距离不超过

然后我们有一个问题了：如果方案数超过的超过太多了怎么办？按照题意来说我们应该是要的，但是由于要求后面的第k大需要用到这个方案数，如果我们直接，就会导致结果不正确了。

对于这个问题我们再开一个也记录方案数，如果了就把它设成，然后之后算第大的时候就用当做方案数，这样就没事了。

下面放代码： 

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

const int N = 2010;
const int MOD = 1e8;
int n, d, k, cnt0 = 0, cnt1 = 0;
int p0[N], p1[N], f[N][N], g[N][N];
char s[N];

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    scanf("%s", s+1);
    for (int i = 1; i <= n; i ++)
        if (s[i] == '0') p0[++ cnt0] = i;
        else p1[++ cnt1] = i;
    f[n+1][0] = g[n+1][0] = 1;
    for (int i = n; i >= 1; i --)
        for (int j = 0; j <= min(n-i+1, cnt0); j ++){
            int k = n-i+1-j;
            if (j && abs(p0[cnt0-j+1]-i) <= d){
                f[i][j] += f[i+1][j-1];
                if (f[i][j] > MOD) f[i][j] -= MOD;
                g[i][j] = min(g[i][j]+g[i+1][j-1], MOD+1);
            }
            if (k && abs(p1[cnt1-k+1]-i) <= d){
                f[i][j] += f[i+1][j];
                if (f[i][j] > MOD) f[i][j] -= MOD;
                g[i][j] = min(g[i][j]+g[i+1][j], MOD+1);
            }
        }
    printf("%d\n", f[1][cnt0]);
    int s0 = cnt0, s1 = cnt1;
    for (int i = 2; i <= n; i ++){
        if (s0 && abs(p0[cnt0-s0+1]-i+1) <= d){
            if (g[i][s0-1] >= k) s0 --, putchar('0');
            else s1 --, k -= g[i][s0-1], putchar('1');
        } else s1 --, putchar('1');
    }
    if (s0) putchar('0'); else putchar('1');
    return 0;
}


来源：无晴