Java实现蓝桥杯算法训练 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



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);}

    }

}

}

巴特西

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

试题算法训练 Bit Compressor

最新文章

热门文章

巴特西

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

试题 算法训练 Bit Compressor

最新文章

热门文章

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

试题算法训练 Bit Compressor