We Learn   We Create   We Share

初学者指南
笔记
竞赛
关于我们
页面搜索

目录

AtCoder D 206

AtCoder

Leon | 27 Jun 2021

题目描述

题目给一个数字N，并且给一个长N长度的字符串，求最小的操作步骤将其变成回文。你可以做以下的操作:

选取一组数字（X，Y）并将字符串种所有的X替换成Y。这个算是为一次操作

例子

8

1 5 3 2 5 2 3 1

然后我将所有的3换成2

再将所有的2换成5

就会有1 5 5 5 5 5 5 1

思路

可以用UFDS将每一组的数union起来

比如说

a b c d e f g

a-g

b-f

c-e

总共将这一棵树的节点总数-1就是这一棵树的最优解

原因是如果是在这一棵树里面的所有数都必须要与树里面的任意一个数相等，所以是变换N-1次。

然后将每一棵树的最优解相加就是答案

复杂度

step1 遍历数组， O(N)；

step2 建立ufds时的union与findroot的复杂度为O(N)；（给代码做了优化（path compression) 之后可以将平均复杂度降为O(1))

step3 最后遍历ufds的复杂度O(N);

所以总体复杂度为O(N);

代码实现

import java.util.*;
import java.io.*;
public class kaibun{
    public static void main (String [] args){
        Scanner in  = new Scanner(System.in);
        int length = in.nextInt();
        int [] arr = new int [length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.nextInt();
        }
        length/=2;
        //take left and right into the two arrays
        int [] left = new int [length];
        int [] right = new int [length];
        for (int i = 0; i < length; i++) {
            left[i] = arr[i];
        }
        int index = 0;
        for( int i = arr.length-1;i>arr.length-length-1;i--){
            right[index] = arr[i];
            index++;
        }
        //System.out.println(Arrays.toString(left));
        //System.out.println(Arrays.toString(right));


        UFDS find = new UFDS(200005);
        for (int i = 0; i < right.length; i++) {
            find.union(right[i], left[i]);
        }
        
        HashMap< Integer, Long> count = new HashMap<Integer,Long>();

        for ( int i = 0;i<find.ufds.length;i++){
            int root = find.ufds[i];
            if(i!=root){
                if(count.get(root)!=null){
                    count.put(root, (long)count.get(root)+1L);
                }else{
                    count.put(root, 1L);
                }
            }
        }
        long result = 0;
        for ( long value : count.values()){
            result+=value;
        }

        System.out.println(result);
        
    }
}

class UFDS{
    int [] ufds;
    //union by rank
    int [] rank;

    public UFDS(int n){
        this.ufds = new int [n];
        this.rank = new int [n];
        for ( int i = 0;i<ufds.length;i++) {
            this.ufds[i] = i;
            this.rank[i] = 0;
        }
    }
    public void union(int u , int v){
        int rootU = this.findTheRoot(u);
        int rootV = this.findTheRoot(v);
        if(this.rank[u]<=this.rank[v]){
            if (rootU!=rootV) this.ufds[rootU] = rootV;
            this.rank[rootV]++;
        }else{
            if(rootU!=rootV) this.ufds[rootV] = rootU;
            this.rank[rootU]++;
        }
  
    }
    public int findTheRoot( int n){
        int ini = n;
        while(n!=this.ufds[n]) n = this.ufds[n];
        this.ufds[ini] = n;
        return n;
    }
    public boolean find(int u,int v){
        return findTheRoot(u)==findTheRoot(v);
    }
    public String toString(){
        return Arrays.toString(this.ufds);
    }
}

评论区