以前一直都不用可视化编辑器…写出来的blog没有分段全部挤在一起难看死…从现在起用可视化编辑器来写。
连环锁
题目大意:
九连环的操作规则是对于一行上的每个环, 如果这个环没有被取下来并且这个环右边的所有环都被取下来了, 那么这个环左边相邻的环可以任意摘取。
用01串表示N连环的状态(0表示取下, 1表示未取下), 给两个01串, 问这两个01串相互转换最小需要操作多少次。
解题报告
首先%%% 大佬的Blog
很玄妙的题目。
普及格雷码:
- 构造:对于二进制数A, A[i]表示A的第i位(最低位为0), 那么格雷码B[i]=A[i]^A[i+1]。
- 反向转换:对于格雷码B, 可以这么构造A: A[i] = A[i+1]^B[i](A是B的后缀异或和)。
- 性质:如果有数字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 */
Pingback: 神题专练(一) « Hineven!