2854. 统计特定字串模式的个数

10175102262 LarsPendragon

动态规划。
首先,i+1长度包含j个1子串的个数至少等于i长度包含j个1的子串的个数2(在数字串的后面添加0或1),再加上i+1长度数字串中结尾是j个1的子串个数,最后除去重复计算的i+1长度数字串前i-(j-1)个数字有j个1的子串个数。

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int m, n;
    long long num[32][32];
    for(int i=1;i<32;++i){num[i][i]=1;}
    for(int i=2;i<32;++i)
        for(int j=1;j<i;++j){
            num[i][j]=2*num[i-1][j]+int(pow(2.0,double(i-j-1)));
            if(i>2*j) num[i][j]-=num[i-j-1][j];}
    cin>>m>>n;
    while(m+1&&n+1){
        cout<<num[m][n]<<endl;
        cin>>m>>n;}
    return 0;
}
Deuchie

[EOJ 2854] 统计特定字串模式的个数

一开始看这题,像排列组合的问题。不过用动态规划思想直接做就行。

设 $dp(m, n)$:长度为 $n$ 的 BitString,其中「包含至少 $m$ 个连续 1」的子串的个数。

如果前 $n-1$ 个位已经有 $m$ 个连续 1 的子串,那么 $dp(m, n)$ 当然包含它们;而且由于新的一位可以是 0 也可以是 1,所以应该是 $2\times dp(m, n - 1)$。

如果前 $n-1$ 位里没有 $m$ 个连续 1 的子串,那么只有一种情况下加上一个 1 可以引入 连续 $m$ 个 1,那就是前面 $n-1$ 个位中,最后 $m-1$ 个都是 1 且倒数第 $m$ 个是 0(不然就有 $m$ 个连续 1 了)。这样,还剩下 $n-m-1$ 位没有确定。这一部分也不能有 $m$ 个连续的 1。很显然,总共有 $2^{n - m - 1}$ 种长为 $n-m-1$ 的串,其中有 $dp(m, n - m - 1)$ 个串是含有 $m$ 个连续 1 子串的。所以相反的有 $2^{n - m - 1} - dp(m, n - m - 1)$ 个串没有 $m$ 个连续的 1。

然后再考虑特殊情况即可。综上,可以得到以下式子。
$$
dp(m, n) = \begin{cases}0&n < m\ 1&n=m\ 2\times dp(m, n - 1) + 2^{n - m - 1} - dp(m, n - m - 1)&n>m\end{cases}
$$
楼上的大佬把我这里三种情况中的一些合并了一下,写成了 if 分支。我把它们分开写了。

代码

#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

int main() {
    u64 dp[32][32]; // array<array<u64, 32>, 32> dp;
    for (u64 i = 0; i < 32; ++i) {
        for (u64 j = 0; j < i; ++j) {
            dp[i][j] = 0;
        }
        dp[i][i] = 1;
        for (u64 j = i + 1; j < 32; ++j) {
            dp[i][j] = 2 * dp[i][j - 1] + (1 << (j - i - 1)) - dp[i][j - i - 1];
        }
    }
    for (i64 n, m; cin >> n >> m, n != -1;) {
        cout << dp[m][n] << '\n';
    }
}

OJ 的数学公式不能换行,所以只能那样了似乎。

你当前正在回复 博客/题目
存在问题!