2016年蓝桥杯javaB省赛——压缩变换

偏执的太偏执、 2022-07-28 06:30 225阅读 0赞

> 压缩变换  
> 小明最近在研究压缩算法。  
> 他知道，压缩的时候如果能够使得数值很小，就能通过熵编码得到较高的压缩比。  
> 然而，要使数值很小是一个挑战。  
> 最近，小明需要压缩一些正整数的序列，这些序列的特点是，后面出现的数字很大可能是刚出现过不久的数字。对于这种特殊的序列，小明准  
> 备对序列做一个变换来减小数字的值。  
> 变换的过程如下：  
> 从左到右枚举序列，每枚举到一个数字，如果这个数字没有出现过，将数字变换成它的相反数，如果数字出现过，则看它之前在原序列中最后的  
> 一次出现后面（且在当前数前面）出现了几种数字，用这个种类数替换原来的数字。  
> 比如，序列(a1, a2, a3, a4, a5)=(1, 2, 2, 1, 2)在变换过程为：  
> a1: 1未出现过，所以a1变为-1；  
> a2: 2未出现过，所以a2变为-2；  
> a3: 2出现过，最后一次为原序列的a2，在a2后、a3前有0种数字，所以a3变为0；  
> a4: 1出现过，最后一次为原序列的a1，在a1后、a4前有1种数字，所以a4变为1；  
> a5: 2出现过，最后一次为原序列的a3，在a3后、a5前有1种数字，所以a5变为1。  
> 现在，给出原序列，请问，按这种变换规则变换后的序列是什么。  
> 输入格式：  
> 输入第一行包含一个整数n，表示序列的长度。  
> 第二行包含n个正整数，表示输入序列。  
> 输出格式：  
> 输出一行，包含n个数，表示变换后的序列。  
> 例如，输入：  
> 5  
> 1 2 2 1 2  
> 程序应该输出：  
> \-1 -2 0 1 1  
> 再例如，输入：  
> 12  
> 1 1 2 3 2 3 1 2 2 2 3 1  
> 程序应该输出：  
> \-1 0 -2 -3 1 1 2 2 0 0 2 2  
> 数据规模与约定  
> 对于30%的数据，n<=1000；  
> 对于50%的数据，n<=30000；  
> 对于100%的数据，1 <=n<=100000，1<=ai<=10^9  
> 资源约定：  
> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗 < 3000ms

当时做的时候以为用某种规律，只是用了一个数组，赛后想到了用map，但是还是没有头绪，后来询问一大神，给出如下解答，顿时膜拜：

> 称原数列为a\[i\]。依次处理数列中的每一个数值，同时维护如下的两个数据结构：  
> 1. 一个HashMap M，把一个数值map到它最后一次出现的位置；  
> 2. 一个0/1/序列b，b\[i\] = 1表示a\[i\]这个数值最后一次就是出现在位置i上。  
> 处理a\[i\]的步骤如下：  
> 如果a\[i\]不在M中，说明a\[i\]没有出现过，输出-a\[i\]，令M\[a\[i\]\] = i，并置b\[i\] = 1。  
> 如果a\[i\]在M中，说明a\[i\]最后一次出现在位置M\[a\[i\]\]，则应当输出b\[M\[a\[i\]\]+1\]至b\[i-1\]共有多少个1，并令b\[M\[a\[i\]\]\] = 0, b\[i\] = 1, M\[a\[i\]\] = i。  
> 上面的一个关键步骤是“求b的一段子序列中有多少个1”，而b是动态变化的。可以用线段树使得每次查询和修改都是O(logn)的复杂度。这样，算法的时间复杂度为O(nlogn)，空间复杂度为O(n)。

由于线段树还不会用，所以只是用了一个区间遍历，时间复杂度为O（n^2)

import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    public class Main {
    
        public static int n;
        public static int[] flag,res;
        public static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
        public static int cnt(int l,int r){
            int sum = 0;
            for(int i=l;i<r;i++){
                if(flag[i]==1) sum++;
            }
            return sum;
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                n = in.nextInt();
                flag = new int[n+10];
                res = new int[n+10];
                Arrays.fill(flag, 0);
                map.clear();
                int t,last=-1;
                for(int i=0;i<n;i++){
                    //nums[i] = in.nextInt();
                    t = in.nextInt();
                    if(!map.containsKey(t)){
                        res[i] = -t;
                        map.put(t, i);
                        flag[i] = 1;
                    }
                    else{
                        last = map.get(t);
                        res[i] = cnt(last+1, i); 
                        flag[last] = 0;
                        //map.remove(t);
                        map.put(t, i);
                        flag[i] = 1;
                    }
                }
                for(int i=0;i<n;i++) System.out.print(res[i]+" ");
            }
        }
    
    }

note:  
1. Map如果对同一个键两次调用put方法，第二个值会取代第一个值  
2. 如果没有特殊需求，一般用HashMap，因为它对速度进行了优化；而LinkedHashMap的特性是“在遍历键值对时，以元素的插入顺序返回键值对”。  
3. 数据结构+算法=程序。之前只是着眼于算法，可是这道题就是对于数据结构的使用，而且设计一个好的数据结构，明显可以事半功倍。算法与数据接口是相辅相成的。

采用线段树进行求和：

import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    
    public class Main {
    
        public static int n,m;
        public static int[] res,segTree;
        public static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
        public static void init(int n_){
            m = 1;
            while(m<n_) m <<= 1;
            //for(int i=0;i<m*2-1;i++) segTree[i] = 0;
            Arrays.fill(segTree, 0);
        }
    
        public static void update(int k,int v){
            k += m-1;
            if(v==1) segTree[k]++;
            else segTree[k]--;
            while(k>0){
                k = (k-1)/2;
                if(v==1) segTree[k]++;
                else segTree[k]--;
            }
        }
    
        public static int query(int a,int b,int k,int l,int r){
            if(a<=l&&r<=b) return segTree[k];
            else if(l>=b||r<=a) return 0;
            else{
                int m = l + (r-l)/2;
                int left = query(a, b, k*2+1, l, m);
                int right = query(a, b, k*2+2, m, r);
                return left + right;
            }
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                n = in.nextInt();
                segTree = new int[4*n];
                res = new int[n+10];
                map.clear();
                init(n);
                int t,last=-1;
                for(int i=0;i<n;i++){
                    t = in.nextInt();
                    if(!map.containsKey(t)){
                        res[i] = -t;
                        map.put(t, i);
                        update(i, 1);
                    }
                    else{
                        last = map.get(t);
                        res[i] = query(last+1,i,0,0,m);
                        update(last, 0);
                        map.put(t, i);
                        update(i, 1);
                    }
                }
                for(int i=0;i<n;i++) System.out.print(res[i]+" ");
                System.out.println();
            }
        }
    
    }

这道题，不论是自行设计的Map、标记数组，还是线段树，都是数据结构的应用，而这道题的关键也在于Map及标记数组的运用。