蓝桥杯 决赛 异或变换 100分

问题描述

时间限制: 3.0s 内存限制: 512.0MB 本题总分：20 分

问题描述

  小蓝有一个 01 串 s = s1s2s3 ⋅ ⋅ ⋅ sn。
  以后每个时刻，小蓝要对这个 01 串进行一次变换。每次变换的规则相同。
  对于 01 串 s = s1s2s3 ⋅ ⋅ ⋅ sn，变换后的 01 串s' = s'1s'2s'3 ⋅ ⋅ ⋅ s'n为：
  s'1=s1;    
  s'i=si-1⊕si。
  其中 a ⊕ b 表示两个二进制的异或，当 a 和 b 相同时结果为 0 ，当 a 和 b
  不同时结果为 1。
  请问，经过 t 次变换后的 01 串是什么？

输入格式

  输入的第一行包含两个整数 n,t，分别表示 01 串的长度和变换的次数。
  第二行包含一个长度为 n 的 01 串。

输出格式

  输出一行包含一个 01 串，为变换后的串。

测试样例1
Input：
5 3
10110

Output：
11010

Explanation：
初始时为 10110，变换 1 次后变为 11101，变换 2 次后变为 10011，变换 3 次后变为 11010。

评测用例规模与约定

  对于 40% 的评测用例，1 ≤ n ≤ 100 , 1 ≤ t ≤ 1000。
  对于 80% 的评测用例，1 ≤ n ≤ 1000 , 1 ≤ t ≤ 10^9。
  对于所有评测用例，1 ≤ n ≤ 10000 , 1 ≤ t ≤ 10^18。
 

Java

import java.util.Scanner;

public class 异或变换 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int t = scanner.nextInt();
		int circle = 1;
		//最终的规律是当大于等于n的一个2的整数次幂情况下，必定存在循环。
		while(circle < n) {
			circle <<= 1;
		}
		t %= circle;
		char[] arr = scanner.next().toCharArray();
		for(int i = 0;i < t;i++) {
			for(int j = n - 1;j > 0;j--) {
				if(arr[j] == arr[j - 1]) {
					arr[j] = '0';
				}else {
					arr[j] = '1';
				}
			}
			
			//System.out.println(new String(arr));
		}
		System.out.println(new String(arr));
	}

}