题解 | Transmission-牛客假日团队赛9B题

输入描述:

这题是个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;
}