Bit compressor [Blue Bridge Cup training]

Bit Compressor

Problem description

The purpose of data compression is to reduce redundancy when storing and exchanging data . This increases the proportion of valid data and increases the transmission rate . There is a way to compress binary strings like this ：
　　 Will be continuous n individual 1 Replace with n The binary representation of （ notes ： Substitution occurs if and only if it reduces the total length of the binary string ）
　　（ translator's note ： Successive n individual 1 It has to be 0 Or the beginning of a string 、 ending ）
　　 such as ：11111111001001111111111111110011 Will be compressed into 10000010011110011. The original string length is 32, The length of the compressed string is 17.
　　 The disadvantage of this method is that , Sometimes the decompression algorithm will get more than one possible original string , So we can't determine what the original string is . Please write a program to determine whether we can use the compressed information to determine the original string . Give the original string length L, In the original string 1 The number of N, And the compressed string .
　　L<=16 Kbytes, The length of the compressed string <=40 bits.

Input format

The first line has two integers L,N, The meaning is the same as the problem description
　　 The second line is a binary string , Represents the compressed string

Output format

Output "YES" or "NO" or "NOT UNIQUE"（ No quotation marks ）
　　 respectively ：
　　YES： The original string is unique
　　NO： The original string does not exist
　　NOT UNIQUE： The original string exists but is not unique

The sample input

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

Sample output

Examples 1：YES
Examples 2：NOT UNIQUE
Examples 3：NO

Their thinking

For this question Of course we have to use what we are familiar with dfs To search for his possibilities
First The result of the topic analysis is We can take the possibility of each position of the compressed string in turn also For each is 1 The location of We can intercept From the current k To k+i-1 String of positions
And find out its length and its content 1 It's actually length
And then the next round dfs(k+1,l+ll,v+vv)
If the current location is 0 Or not satisfied with a string of 1 Both before and after are 0 These two conditions it k+1 A string
about l and v Both meet the conditions and k Print s When length traversal is complete We can 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;
} 

 Fortunately, there is no special need to pay attention to this problem   The edge of   Over and over again