九连环问题和格雷码

以前一直都不用可视化编辑器…写出来的blog没有分段全部挤在一起难看死…从现在起用可视化编辑器来写。

连环锁

题目大意:

九连环的操作规则是对于一行上的每个环, 如果这个环没有被取下来并且这个环右边的所有环都被取下来了, 那么这个环左边相邻的环可以任意摘取。

用01串表示N连环的状态(0表示取下, 1表示未取下), 给两个01串, 问这两个01串相互转换最小需要操作多少次。

解题报告

首先%%% 大佬的Blog

很玄妙的题目。

普及格雷码:

1. 构造:对于二进制数A, A[i]表示A的第i位(最低位为0), 那么格雷码B[i]=A[i]^A[i+1]。
2. 反向转换:对于格雷码B, 可以这么构造A: A[i] = A[i+1]^B[i](A是B的后缀异或和)。
3. 性质:如果有数字a, a+1, 那么a的格雷码和a+1的格雷码异或值为[latex]2^k[/latex]。

考察九连环的01串变换:

九连环的串 ....010000 可变换成 ....110000
假设’….’部分的异或和为0, 如果我们把这两个串看成格雷码, 那么它们对应的二进制数变换就是 ....011111 - ....100000 , 刚好是+1进位! 反之则是-1, 若’….’部分异或和为1情况类似。 由于九连环变化要求’1’的右侧必须全部是0, 这就和二进制进位/退位完全吻合。

那么一次操作就转化单个数字的+1/-1操作, 反向转化格雷码后做差输出即可!

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
void translate (int *A, char *str, int len) {
    memset(str, 0, len+1);
    int cur = 0;
    for(int i = 1; i<=len; i++)
        str[i] = (cur^=A[i]);
}
inline int strcmpWithLength (char *s1, char *s2, int len) {
    for(int i = 1; i<=len; i++)
        if(s1[i] > s2[i]) return 1;
        else if(s1[i] < s2[i]) return -1;
    return 0;
}
int A[130], B[130];
char mem[2][130], *s1 = mem[0], *s2 = mem[1];
int main () {
    int C;
    scanf("%d", &C);
    while(C --) {
        int N;
        scanf("%d", &N);
        for(int i = 1; i<=N; i++)
            scanf("%d", &A[i]);
        translate(A, s1, N);
        for(int i = 1; i<=N; i++)
            scanf("%d", &B[i]);
        translate(B, s2, N);
        int val = strcmpWithLength(s1, s2, N);
        if(val == 0) puts("0");
        else {
            if(val < 0) swap(s1, s2);
            for(int i = 1; i<=N; i++) s1[i] -= s2[i];
            for(int i = N; i>=1; i--)
                while(s1[i]<0) s1[i] += 2, s1[i-1] --;
            int cur = 0;
            ULL num[4];
            num[0] = num[1] = num[2] = num[3] = 0;
            for(int i = N; i>=1; i--) {
                if(!s1[i]) {cur++; continue ;}
                num[cur>>5] |= 1ull<<(cur&31);
                cur ++;
            }
            ULL lvl = 1ull<<32;
            char out[45], *pointr = out;
            memset(out, 0, sizeof out);
            while(num[0] || num[1] || num[2] || num[3]) {
                int x;
                x = num[3]%10, num[3] /= 10;
                num[2] += lvl*x;
                x = num[2]%10, num[2] /= 10;
                num[1] += lvl*x;
                x = num[1]%10, num[1] /= 10;
                num[0] += lvl*x;
                x = num[0]%10, num[0] /= 10;
                *(pointr++) = '0'+x;
            }
            reverse(out, pointr);
            puts(out);
        }
    }
}
/*
100
70
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0
*/