首页 > 试题广场 >

消息压缩

[编程题]消息压缩

热度指数：985 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

长度为n的线段有多少种切割方法，切割时两个为一组，一组中第一个数字必须为4，两个数字都必须为正整数，例如n=10有两种：

| 4 | 6 |

| 4 | 1 | 4 | 1 |

注意，在所有可能的结构中，消息的长度不可以为 0。也就是说，不能出现这样的消息：| 4 | 0 |。

当然，答案可能会很大，所以你需要给出答案模 998244353 之后的结果。

示例1

输入

输出

示例2

输入

输出

说明

| 4 | 7 |，| 4 | 1 | 4 | 2 |，| 4 | 2 | 4 | 1 |，共计三种不同的消息。

备注:

数据范围：
- 对于 30% 的数据，
- 对于 60% 的数据，
- 对于 100% 的数据，

算法知识视频讲解

牛客629672613号

* 高中数学有道题是这样的，一个N阶的楼梯，每次可以选择上一阶或者两阶，一共有多少种上法？
* 这个问题的关键在最后一步，是上一阶，还是上两阶？上一阶，那么前面 N-1 阶台接有多少种上法
* 上两阶，前面 N-2 阶台阶有多少种上法？如果 N-1 和 N-2的上法分别是 f(N-1) 和 f(N-2)，
* 那么N阶台阶的上法就是 f(N-1) + f(N-2)
* 这道题也类似，首先数据包接口都是4+N的格式（N>0)，再进一步简化，把一个数N拆成多个数相加，且每个加数都大于等于5
* N = a1 + a2 + ... + ai (ai >= 5)
* 结合上面爬楼梯的例子，就是最后可能是5阶，可能是6阶，可能是7阶，可能是x阶， x>=5
* 最后一步上5阶，那方案数就是f(N-5),最后一步上6阶就是f(N-6)，一直到f(5)
* 总共方案数就是f(N) = f(N-5) + f(N-6) + f(N-7) + ... + f(5),另外还有一种可能是一步上N阶，再+1
* 最终就是：f(N) = f(N-5) + f(N-6) + f(N-7) + ... + f(5) + 1
* f(N+1) = f(N-4) + f(N-5) + f(N-6) + f(N-7) + ... + f(5) + 1
* 所以f(N+1) = f(N-4) + f(N) ==> f(N) = f(N-5) + f(N-1)

* 上面讨论的都是N>5的情况，N<5时，f(N) = 0,f(5)=1

public int messageCount (int N) {
    int[] r = new int[N+1];
    for (int m=0; m<=N; m++) {
        r[m] = 0;
    }
    if (N < 5) {
        return r[N];
    } else {
        r[5] = 1;
        for(int i=6; i<=N; i++) {
            r[i] = (r[i-1] + r[i-5]) % 998244353;
        }
        return r[N];
    }
}

发表于 2020-07-25 10:36:45 回复(2)

Python

牛客81652600号

提交结果：答案正确运行时间：398ms 占用内存：6520KB 使用语言：Python 3 用例通过率：100.00%

class Solution:
    def messageCount(self , N ):
    # write code here
    if N < 11:
        return N // 5
    d = [(i + 6) // 5 for i in range(5)]
    for i in range(11, N+1):
        d[(i-1)%5] = (d[(i-1-1)%5] + d[(i-5-1)%5]) % 998244353
    return d[(N-1)%5]

提交结果：答案正确运行时间：272ms 占用内存：43960KB 使用语言：Python 3 用例通过率：100.00%

class Solution:
    def messageCount(self , N ):
    # write code here
    d = [i // 5 for i in range(11)]
    for i in range(11, N+1):
        d.append((d[i-1] + d[i-5]) % 998244353)
    return d[N]

提交结果：运行超时运行时间：2001ms 占用内存：6520KB 使用语言：Python 3 用例通过率：60.00%

class Solution:
    def messageCount(self , N ):
        # write code here
        d = {0: 0}
        def count(rest):
            try:
                return d[rest]
            except:
                pass
            if rest - 4 < 1:
                return 0
            result = 1
            for i in range(5, rest - 4):
                result += count(i)
            result = result % 998244353
            d[rest] = result
            return result
        return count(N)

编辑于 2020-07-30 14:09:01 回复(0)

heyJulian

class Solution {
public:
    /**
     * 返回可以被压缩为长度为 N 的不同消息的数量
     * @param N int整型 数据包的总字节数
     * @return int整型
     */
    int messageCount(int N) {
        // write code here
        if(N < 5)//小于5则只有一种可能
            return 0;
        deque<int> f = {0,0,0,0,1};//初始条件
        int i,temp;
        for(i = 6; i <= N; i++){
            //状态转移方程s[i]=s[i-1]+s[i-5]
            temp = (f.back() + f.front()) % 998244353;
            f.push_back(temp);
            f.pop_front();
        }
        return f.back();
    }
};

发表于 2020-07-24 11:03:26 回复(0)

大唐天空

用动态规划方法实现：

static long long dp[1000000];

int core(int N){
    long long n = 0;
    int i = 0;
    if(dp[N] != -1)
        return dp[N];
    if((N > 4) && (N <= 9))
        return (dp[N] = 1);
    else if(N <= 4)
        return (dp[N] = 0);
    else{
        for(i = 0; i <= 4; ++i)
            n += (dp[N - 4 - i] = core(N - 4 - i));
    }
    return n % 998244353;
}

int messageCount(int N ) {
    int i = 0;
    for(i = 0; i <= N; ++i)
        dp[i] = -1;
    return core(N) % 998244353;
}

编辑于 2020-08-11 13:05:44 回复(0)

牛客672037335号

class Solution {
public:
    /**
     * 返回可以被压缩为长度为 N 的不同消息的数量
     * @param N int整型 数据包的总字节数
     * @return int整型
     */
    int messageCount(int N) {
        // write code here
        
        int *dp = new int [N+1];
        
        for(int i=0;i<N+1;i++)
        {
            dp[i]=0;
        }
        if(N>=5)
        {dp[5]=1;}
        for(int i=6;i<N+1;i++)
        {
            dp[i]=(dp[i-1]+dp[i-5])% 998244353;  //第一次没有在这里加取模操作，用longlong 存储dp,只在return时加了取模操作。
        }
        return (int)dp[N]%998244353;

    }
};

发表于 2020-07-29 23:29:09 回复(0)

牛客784561436号

我的答案只能测试通过百分之三十，但是目前我一直没找到逻辑上哪里出现了漏洞，希望大神能指出，我的方法和大家的标准答案思路不大一样：

一个长度为N的数据，每一个数据包的开头都要有一个长度为4的长度信息，且不存在40结构，所以我可以认为，一个长度为N的数据，可以至少拆分成一个数据包，即4|N-4,至多可拆分成，可以至多拆分成N//5个数据包（整除）。所以设data_bag_max=N//5;

显而易见，一共的组成构成就是从1个数据包到data_bag_max，数据包个数不一样，当然构成也是各异的。接下来就是求从1~data_bag_max，每一个数据包个数下，分别有多少种构成方式。

for num=1：data_bag_max

整个数据中，如果有num个数据包，则代表有num个开头长度信息，他们所占的内存为4*num，也就是说，信息内容所占内存N-4*num，那么我们就是把这num个数据开头，插入到N-4*num个字节的信息当中，考虑到开头必须要占一个，则是将num-1个数据开头插入到N-4*num信息当中，N-4*num个信息一共存在N-4*num-1个空档，则当存在num个数据包时，一共有comb（N-4*num-1，num-1）种方式，comb即排列组合（从N-4*num-1个空档中，选num-1个空档插入开头信息）

将每次计算结果叠加即为最终结果，且不存在重复情况

希望大神能指出这个思路逻辑问题出现在哪里，因为我只能通过30%的测试。

目前我的判断是，排列组合数据过大后，我自己编写的函数和python scipy中的comb计算结果有一定出入，导致结果错误；而且我利用matlab计算，也和comb计算结果有一些差别

import math
n=input()
n=int(n)
max_message=n//5
struct_num=0
def combains(N,k):
    if k==0:
        num=1
    else:
        child=1
        for i in range(k):
            child*=N
            N-=1
        num=child/math.factorial(k)
    return int(num)
for i in range(1,max_message+1):
    struct_num+=combains(n-4*i-1,i-1)
print(int(struct_num)% 998244353)

发表于 2020-07-29 19:25:33 回复(6)

码农一号

public int messageCount (int N) {
        // write code here
    //先行判断N是否小于5
       if (N <= 4) {
            return 0;
        }
        int[] s = new int[N + 1];
        a[5] = 1;
        for (int i = 6; i <= N; i++) {
            a[i] = (a[i - 1] + a[i - 5]) % 998244353 ;//别忘了题目要求要%998244353。
        }
        return a[N];
        
    }

由”加一个 4 字节长度，消息的长度不可以为 0“可知当总字节数小于5时可能性皆为0，为5时有1种可能性|4|1|;又因为N==10时有两个可能性，N==11时有3个可能性，由此可得从0到11的可能性集合为【0，0，0，0，0，1，1，1，1，1，2，3】；由此可以联想到斐波那契数列。我本来是不懂里面的具体意义，他说明也不太清楚，所以当我有这个想法的时候我就试了一下，果不其然ac了，代码别怕试。结果都是试出来的。共勉之。

发表于 2020-07-24 11:19:38 回复(4)