Java实现蓝桥杯算法训练 Bit Compressor（暴力）

「爱情、让人受尽委屈。」 2023-07-25 06:28 10阅读 0赞

## 试题 算法训练 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

import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    
    public class Main {  
    // 转自: https://blog.csdn.net/a1439775520 
    static  int l; 
    static int n; 
        static int ans=0;
        static  int len; 
        static  char[] s;
        public static void main(String[] args) throws IOException { 
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter wr=new BufferedWriter(new OutputStreamWriter(System.out));
            String []nm=br.readLine().split(" ");
            l=Integer.parseInt(nm[0]);
            n=Integer.parseInt(nm[1]);
            s=br.readLine().toCharArray();
           // wr.write(Arrays.toString(s));
            len=s.length;
            dfs(0,0,0);
            //wr.write(ans+" ");
            //wr.write(" "+l+" "+n+" "+len);
            if(ans>=2){ 
                wr.write("NOT UNIQUE");
            }
            else if(ans==1)
            { 
                wr.write("YES");
            }
            else
            { 
                wr.write("NO");
            }
            wr.close();
        } 
    static void dfs(int i,int num,int curlen)
    { 
        if(ans>=2||num>n||curlen>l){ return;}
        if(i>=len)
        { 
            if(curlen==l&&num==n)
            { 
                ans++;
            }
            return;
        } 
        if(s[i]=='0')
        { 
            dfs(i+1,num,curlen+1);
            return;
        } 
        if(i!=0&&s[i-1]=='1')
        { 
            dfs(i+1,num+1,curlen+1);
            return;
        } 
        dfs(i+1,num+1,curlen+1); 
        int tem=0; 
        for (int j=i;j<len;j++)
        { 
            //
            tem*=2;
            tem+=s[j]-'0'; 
            if (tem+num>n||tem+curlen>l)
            { 
                break;
            } 
            if(tem>j-i+1&&(j+1==len||(j+1<len&&s[j+1]=='0')))
            { dfs(j+1,num+tem,tem+curlen);}
        }
    
    
    }
    }