Bit Compressor [蓝桥杯题目训练]_综合

Bit Compressor

问题描述

数据压缩的目的是为了减少存储和交换数据时出现的冗余。这增加了有效数据的比重并提高了传输速率。有一种压缩二进制串的方法是这样的：
　　将连续的n个1替换为n的二进制表示（注：替换发生当且仅当这种替换减少了二进制串的总长度）
　　（译者注：连续的n个1的左右必须是0或者是串的开头、结尾）
　　比如：11111111001001111111111111110011会被压缩成10000010011110011。原串长为32,被压缩后串长为17.
　　这种方法的弊端在于，有时候解压缩算法会得到不止一个可能的原串，使得我们无法确定原串究竟是什么。请你写一个程序来判定我们能否利用压缩后的信息来确定原串。给出原串长L，原串中1的个数N，以及压缩后的串。
　　L<=16 Kbytes，压缩后的串长度<=40 bits。

输入格式

第一行两个整数L,N，含义同问题描述
　　第二行一个二进制串，表示压缩后的串

输出格式

输出"YES"或"NO"或"NOT UNIQUE"（不包含引号）
　　分别表示：
　　YES：原串唯一
　　NO：原串不存在
　　NOT UNIQUE：原串存在但不唯一

样例输入

样例1：
32 26
10000010011110011
样例2：
9 7
1010101
样例3：
14 14
111111

样例输出

样例1：YES
样例2：NOT UNIQUE
样例3：NO

解题思路

对于这一个问题我们当然得用我们熟悉的dfs来搜索他的可能性啦
首先对于题目分析得出的结果是我们可以依次走压缩后的字符串每一个位置的可能性并且对于每一个为1的位置我们可以去截取从当前 k 到k+i-1 位置的字符串
并且求出他的长度和所包含的1 其实就是长度
然后进行下一轮dfs(k+1,l+ll,v+vv)
如果当前位置是0或者不满足一串1的前后都为0这俩个条件就进行k+1个字符串
对于l和v都满足条件并且k打印s长度遍历完成时我们就可以ans++

#include<iostream>
using namespace std;
const int N = 111;
int n,m,ans,f;
string s;
int d[N];
inline int getlow(string sss){
    int tans(0);for(int i=0;i<sss.size();i++){
    tans=tans*2+sss[i]-'0';}return tans;
}
void dfs(int k,int l,int v){
    if(ans>1) return;if(v>m) return;if(l>n) return;if(k==s.size()){
    
// cout<<l<<" "<<v<<endl;if(v==m&&l==n) ans++;return; }int i(1);while(1){
    i++;if(k+i>s.size()) break;if(s[k]!='1') break;if(k&&s[k-1]!='0') break;string stt = s.substr(k,i);if(stt=="10") continue;if(k+i!=s.size()&&s[k+i]!='0') continue;int ll = getlow(stt);dfs(k+i,l+ll,v+ll);}if(s[k]=='1') v++;dfs(k+1,l+1,v);
}
int main(){
    cin>>n>>m;cin>>s;dfs(0,0,0);if(ans>1){
    cout<<"NOT UNIQUE"<<endl;}else if(ans==1){
    cout<<"YES"<<endl;}else{
    cout<<"NO"<<endl;}return 0;
}

还好这道题没有特别需要注意 的边缘 一遍过

ac情况