(以“分类:位运算 ==摘要== {{信息题|Matrix|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}249|1|100|time=2015-2-16 16:22:43}} (AC 1014) ==题意...”为内容创建页面)
 
代码: 代码不匹配
 
第66行: 第66行:
 
int main()
 
int main()
 
{
 
{
     int n;
+
     int m,n;
     cin>>n;
+
     scanf("%d%d",&m,&n);
    cout<<2*n+1;
+
    for(int x=0;x<(1<<m);++x)
 +
    {
 +
        int u=(x^(x>>1))<<n;
 +
        for(int y=0;y<(1<<n);++y)
 +
            printf("%d ",u|(y^(y>>1)));
 +
        printf("\n");
 +
    }
 
     return 0;
 
     return 0;
 
}
 
}
 +
 
</pre>
 
</pre>
 
|sgu249}}
 
|sgu249}}

2015年2月17日 (二) 10:16的最后版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
Matrix ★☆☆☆☆ 答案正确 100 2015-2-16 16:22:43

(AC 1014)

题意

生成一个2^m*2^n的矩阵,使得矩阵中相邻的两个数之间二进制差不超过一位。

题解

没什么思路。百度下知道,这是一道二维Gray码题,Copy一段Matrix67大大的博文,写得蛮简单易懂的,我也就不再写题解了[1]

假如我有4个潜在的GF,我需要决定最终到底和谁在一起。一个简单的办法就是,依次和每个MM交往一段时间,最后选择给我带来的“满意度”最大的MM。但看了dd牛的理论后,事情开始变得复杂了:我可以选择和多个MM在一起。这样,需要考核的状态变成了2^4=16种(当然包括0000这一状态,因为我有可能是玻璃)。现在的问题就是,我应该用什么顺序来遍历这16种状态呢?    
传统的做法是,用二进制数的顺序来遍历所有可能的组合。也就是说,我需要以0000->0001->0010->0011->0100->…->1111这样的顺序对每种状态进行测试。这个顺序很不科学,很多时候状态的转移都很耗时。比如从0111到1000时我需要暂时甩掉当前所有的3个MM,然后去把第4个MM。同时改变所有MM与我的关系是一件何等巨大的工程啊。因此,我希望知道,是否有一种方法可以使得,从没有MM这一状态出发,每次只改变我和一个MM的关系(追或者甩),15次操作后恰好遍历完所有可能的组合(最终状态不一定是1111)。大家自己先试一试看行不行。    
解决这个问题的方法很巧妙。我们来说明,假如我们已经知道了n=2时的合法遍历顺序,我们如何得到n=3的遍历顺序。显然,n=2的遍历顺序如下:
    00
    01
    11
    10    
你可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态,其中前面4个把n=2的遍历顺序照搬下来,然后把它们对称翻折下去并在最前面加上1作为后面4个状态:
    000
    001
    011
    010  ↑
——–
    110  ↓
    111
    101
    100
用这种方法得到的遍历顺序显然符合要求。首先,上面8个状态恰好是n=3时的所有8种组合,因为它们是在n=2的全部四种组合的基础上考虑选不选第3个元素所得到的。然后我们看到,后面一半的状态应该和前面一半一样满足“相邻状态间仅一位不同”的限制,而“镜面”处则是最前面那一位数不同。再次翻折三阶遍历顺序,我们就得到了刚才的问题的答案:
    0000
    0001
    0011
    0010
    0110
    0111
    0101
    0100
    1100
    1101
    1111
    1110
    1010
    1011
    1001
    1000    
这种遍历顺序作为一种编码方式存在,叫做Gray码(写个中文让蜘蛛来抓:格雷码)。它的应用范围很广。比如,n阶的Gray码相当于在n维立方体上的Hamilton回路(哈密顿回路),因为沿着立方体上的边走一步,n维坐标中只会有一个值改变。再比如,Gray码和Hanoi塔(汉诺塔)问题等价。Gray码改变的是第几个数,Hanoi塔就该移动哪个盘子。比如,3阶的Gray码每次改变的元素所在位置依次为1-2-1-3-1-2-1,这正好是3阶Hanoi塔每次移动盘子编号。
如果我们可以快速求出Gray码的第n个数是多少,我们就可以输出任意步数后Hanoi塔的移动步骤。现在我告诉你,Gray码的第n个数(从0算起)是n xor (n shr 1),你能想出来这是为什么吗?先自己想想吧。    
下面我们把二进制数和Gray码都写在下面,可以看到左边的数异或自身右移的结果就等于右边的数。
    二进制数   Gray码
       000       000
       001       001
       010       011
       011       010
       100       110
       101       111
       110       101
       111       100    
从二进制数的角度看,“镜像”位置上的数即是对原数进行not运算后的结果。比如,第3个数010和倒数第3个数101的每一位都正好相反。假设这两个数分别为x和y,那么x xor (x shr 1)和y xor (y shr 1)的结果只有一点不同:后者的首位是1,前者的首位是0。而这正好是Gray码的生成方法。这就说明了,Gray码的第n个数确实是n xor (n shr 1)。
今年四月份mashuo给我看了这道题,是二维意义上的Gray码。题目大意是说,把0到2^(n+m)-1的数写成2^n * 2^m的矩阵,使得位置相邻两数的二进制表示只有一位之差。答案其实很简单,所有数都是由m位的Gray码和n位Gray码拼接而成,需要用左移操作和or运算完成。

代码

249.cpp代码已折叠
展开折叠内容
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int x=0;x<(1<<m);++x)
    {
        int u=(x^(x>>1))<<n;
        for(int y=0;y<(1<<n);++y)
            printf("%d ",u|(y^(y>>1)));
        printf("\n");
    }
    return 0;
}


参考资料和拓展阅读

  1. http://www.matrix67.com/blog/archives/266

著作权声明[编辑]

关于[编辑]