2021第十二届蓝桥杯国赛-G异或变换

2021-07-03 · 141次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #字符串

题面

官网链接
 Dotcpp

【问题描述】

小蓝有一个 01 串 $s = s_1s_2s_3\cdots s_n$ 。

以后每个时刻，小蓝要对这个 01 串进行一次变换。每次变换的规则相同。对于 01 串 $s = s_1s_2s_3\cdots s_n$ ，变换后的 01 串 $s'= s_1's_2's_3'\cdots s_n'$ 为：

$s'= s_1$ ;

$s_i'=s_{i-1}\oplus s_i$ 。

其中 $a ⊕ b$ 表示两个二进制的异或，当 $a$ 和 $b$ 相同时结果为 0，当 $a$ 和 $b$ 不同时结果为 1。

请问，经过 $t$ 次变换后的 01 串是什么？

【输入格式】

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

第二行包含一个长度为 $n$ 的 01 串。

【输出格式】

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

【样例输入】

5 3
10110

【样例输出】

【样例说明】

初始时为 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}$ 。

思路

模拟

枚举每次异或变换，找到其变换回原样的需要的次数（即为周期），将总的变换次数模掉周期，就可以减少很多次运算。

实际上，可以发现其变换规律，其变化的周期为 2 * (n - 1)，则时间复杂度为 $O(n^2)$ ，最坏情况下计算 $10^8$ 次，能在规定时间内AC。

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 1e4 + 10;
typedef long long LL;
char s[N], t[N];
int n;
LL m;

int main() {
    cin >> n >> m;
    scanf("%s", s);
    int k = 0;	//最小正周期长度
    memcpy(t, s, sizeof s);  //备份
    bool st = false;	//存在周期的标记，存在周期为 true, 不存在为 false
    for (int i = 0; i < m; i++) {
        k++;
        for (int j = n - 1; j; j--) {
            s[j] = (s[j - 1] ^ s[j]) + '0';
        }
        if (strcmp(s, t) == 0) { //首次出现和原序列相同的序列，存在周期，退出循环
            st = true;
            break;
        }
    }
    if (!st) printf("%s\n", s);	//走完了m 次变换，则不存在周期，输出最后一次变换的序列
    else {	//存在周期
        m %= k;		//模掉周期即为实际需要变换的次数
        memcpy(s, t, sizeof t);
        for (int i = 0; i < m; i++) {
            k++;
            for (int j = n - 1; j; j--) {
                s[j] = (s[j - 1] ^ s[j]) + '0';
            }
        }
        printf("%s\n", s);
    }

    return 0;
}

标题：	2021第十二届蓝桥杯国赛-G异或变换
链接：	https://www.fightingok.cn/detail/102
更新：	2022-09-18 22:38:57
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可