侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 662 篇文章
  • 累计创建 128 个标签
  • 累计收到 15 条评论

目 录CONTENT

文章目录

【打表, 找规律】异或变换

GabrielxD
2023-02-26 / 0 评论 / 0 点赞 / 71 阅读 / 1,205 字
温馨提示:
本文最后更新于 2023-02-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

异或变换 - 蓝桥云课


题目描述

小蓝有一个 0101s=s1s2s3sns = s_1 s_2 s_3 \cdots s_n

以后每个时刻,小蓝要对这个 0101 串进行一次变换。每次变换的规则相同。 对于 0101s=s1s2s3sns = s_1 s_2 s_3 \cdots s_n ,变换后的 0101s=s1s2s3sns′ = s′_1s′_2s′_3\cdots s′_n 为:

s1=s1s′_1 = s_1 ;

si=si1sis′*i = s*{i−1} \oplus s_i

其中 aba \oplus b 表示两个二进制的异或,当 aabb 相同时结果为 00 ,当 aabb 不同时结果为 11

请问,经过 tt 次变换后的 0101 串是什么?

输入描述

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

第二行包含一个长度为 nn0101 串。

输出描述

输出一行包含一个 0101 串,为变换后的串。

输入输出样例

示例

输入

5 3
10110
copy

输出

11010
copy

样例说明

初始时为 1011010110 ,变换 11 次后变为 1110111101 ,变换 22 次后变为 1001110011 ,变换 33 次后变为 1101011010

评测用例规模与约定

对于 4040 % 的评测用例, 1n100,1t10001 ≤ n ≤ 100, 1 ≤ t ≤ 1000

对于 8080 % 的评测用例, 1n1000,1t1091 ≤ n ≤ 1000, 1 ≤ t ≤ 10^9

对于所有评测用例, 1n10000,1t10181 ≤ n ≤ 10000, 1 ≤ t ≤ 10^{18}

运行限制

  • 最大运行时间:3s
  • 最大运行内存: 256M

解题

方法一:暴力 模拟

思路

没有思路的话可以直接暴力模拟拿40%的分。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = in.readLine().split(" ");
        int n = Integer.parseInt(tmp[0]);
        int t = Integer.parseInt(tmp[1]);
        char[] s = in.readLine().toCharArray();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = s[i] - '0';
        while (t-- > 0) {
            for (int i = n - 1; i >= 1; --i) a[i] ^= a[i - 1];
        }
        for (int x : a) System.out.print(x);
    }
}

方法二:打表找规律

思路

tt 最大的数据范围是 [1,1018][1, 10^{18}] ,显然不能靠模拟过全部测试用例。

遇到这种多次变换的题难免想到变换存在一个周期 pp 使得串 ss 变换 pp 次后与 ss 相同,那么变换 2p,3p,2p, 3p, \dots 次后也应该与 ss 相同,此时我们只需要模拟 tmodpt \mod p 次变换就可以得到变换后的串。

最简单的方法是打表找找周期有什么规律,通过打表发现周期 ppss 的长度 nn 有关:

import java.util.*;
import java.io.*;

public class Test {
    public static void main(String[] args) throws IOException {
        for (int i = 1; i <= 20; ++i) {
            int n = i;
            char[] s = Integer.toString(1 << (i - 1), 2).toCharArray();
            int[] a = new int[n];
            for (int j = 0; j < n; ++j) a[j] = s[j] - '0';
            int[] ori = a.clone();
            int cnt = 0;
            outer: while (true) {
                for (int j = n - 1; j > 0; --j) a[j] ^= a[j - 1];
                ++cnt;
                for (int j = 0; j < n; ++j) {
                    if (a[j] != ori[j]) continue outer;
                }
                break;
            }
            System.out.println("length: " + n + ", peroid: " + cnt);
        }
    }
}
n = 1, p = 1
n = 2, p = 2
n = 3, p = 4
n = 4, p = 4
n = 5, p = 8
n = 6, p = 8
n = 7, p = 8
n = 8, p = 8
n = 9, p = 16
n = 10, p = 16
n = 11, p = 16
n = 12, p = 16
n = 13, p = 16
n = 14, p = 16
n = 15, p = 16
n = 16, p = 16
n = 17, p = 32
n = 18, p = 32
n = 19, p = 32
n = 20, p = 32

显然, p=2(log2n+1)p = 2^{(\lfloor \log_2{n} \rfloor + 1)} ,用人话说就是:周期等于第一个大于等于 nn22 的幂。

有了周期接下来的就是模拟了,要注意:tt 的数据范围会爆int,要输入long。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long t = in.nextLong();
        in.nextLine();
        char[] s = in.nextLine().toCharArray();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = s[i] - '0';
        int p = 1;
        while (p < n) p <<= 1;
        t %= p;
        while (t-- > 0) {
            for (int i = n - 1; i > 0; --i) a[i] ^= a[i - 1];
        }
        for (int x : a) System.out.print(x);
    }
}
0

评论区