B.小红的排列构造

https://ac.nowcoder.com/acm/contest/80742/B

定义两个数组和的汉明距离为：有多少个下标满足。例如，和的汉明距离是。 现在小红拿到了一个长度为的排列，她希望你构造一个长度为的排列，满足和的汉明距离恰好等于。

排列指长度为的数组，其中到每个元素恰好出现了一次

若 或者，显然无解。

因为每个元素都只出现一次，交换两个无汉明距离的元素必定产生增加汉明距离， 交换一个有汉明距离的元素和一个无汉明距离的元素必定增加一个汉明距离。

遍历序列，设第个数为，不断让和交换，交换次即可。

——第一次交换产生 2 个距离，后面每一次产生 1 个距离。

import java.util.*;
public class Main {
    static Scanner s = new Scanner(System.in);
    static int n, k, a[];
    public static void main(String[] args){
    	n = s.nextInt();
    	k = s.nextInt();
    	a = new int[n];
    	if(k > n || k == 1) {
    		System.out.print(-1);
    		return;
    	}
    	for(int i = 0; i<n; i++) a[i] = s.nextInt();
    	for(int i = 0; i<=k - 2; i++) {
    		int t = a[i];
    		a[i] = a[i + 1];
    		a[i + 1] = t;
    	}
    	for(int i = 0; i<n; i++) System.out.print(a[i] + " ");
    }
}

C. 小红的循环移位

小红拿到了一个数字串，她每次操作可以使得其向左循环移动一位。 将串 ​ 向左循环移动一位，将得到串 小红想知道，使得该数字串变成4的倍数，需要最少操作多少次？（可以包含前导零）

枚举一下 4 的倍数：4 8 12 16 20 24 28 32 36 40 44 ......

发现规律：若数字位数大于1位，若个位数字为 2/6且高一位为奇数，则为4的倍数；若个位数字为4/8/0且高一位为偶数，则为4的倍数。

有了该规律就可以遍历一遍的情况下找出最小操作次数。

1. 特判一下一位数
2. 先判断 0 次操作是否可行。
3. 再判断次操作，设为从左往右第位数字，若与满足规律，则需要操作次
4. 若都不行则输出

时间复杂度：

import java.util.*;
public class Main {
    static Scanner s = new Scanner(System.in);
    public static void main(String[] args){
    	String num = s.next();
    	int n = num.length();   	
    	//特判 一位数
    	if(n == 1) {
    		int x = num.charAt(0) - '0';
    		if(x == 4 || x == 8) {
    			System.out.print(0);return;
    		}else {
    			System.out.print(-1);return;
    		}
    	}
    	// 0 次操作
    	int a = num.charAt(n - 2) - '0';
		int b = num.charAt(n - 1) - '0';
		if(isVlid(a, b)) {System.out.print(0);return;}
		// 1 ~ n - 1次操作
    	for(int i = 0; i<=n - 2; ++ i) {
     		a = num.charAt(i - 1 < 0 ? n - 1 : 0) - '0';//
    		b = num.charAt(i) - '0';
    		if(isVlid(a, b)) {
    			System.out.print(i + 1);return;
    		}
    	}
    	System.out.print(-1);
    }
    public static boolean isVlid(int a, int b) {
    	if(a % 2 == 0) {
			if(b == 4 || b == 8 || b == 0) {
				return true;
			}
		}else {
			if(b == 2 || b == 6) {
				return true;
			}
		}
    	return false;
    }
}