国家集训队2009论文集浅谈信息学竞赛中的“

《国家集训队2009论文集浅谈信息学竞赛中的“》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅谈信息学竞赛中的“0”和“1”——二进制思想在信息学竞赛中的应用河北省石家庄二中武森前言在德国图灵根著名的郭塔王宫图书馆（SchlossbiliothkezuGotha）保存着一份弥足珍贵的手稿，其标题为：“1与0，一切数字的神奇渊源。这是造物的秘密美妙的典范，因为，一切无非都来自上帝。”众所周知，二进制是计算技术中广泛采用的一种数制,现代的电子计算机技术全部采用的是二进制，因为它只使用0、1两个数字符号，非常简单方便，易于用电子方式实现。计算机内部处理的信息，都是采用二进制数来表示的。二进制（Binary）数用0和1两个数字及其组合来

2、表示任何数。进位规则是“逢2进1”，数字1在不同的位上代表不同的值，按从右至左的次序，这个值以二倍递增。除了数值外，英文字母、符号、汉字、声音、图象等数据在计算机内部也采用二进制数的形式来编码。目前最常用的是使用国际标准代码ASCII码（美国标准信息交换码）。二进制思想在信息学竞赛中也有广泛的应用。本文通过几个例子，总结了二进制思想在信息学竞赛中的应用。关键字二进制十进制树状数组状态压缩01二叉树第1页共29页正文第一章：二进制思想在数据结构中的应用例题一：Matrix提供一个M*N的矩阵，其中每一个格子中的数不是1就是0，初始时每一个格

3、子的值为0，我们可以修改这个矩阵中的数字，每次给出矩阵的左上角坐标(x1,y1)，以及右下角的坐标(x2,y2)，并且将矩阵中的数字全部取反（原来是1现在变成0，原来是0现在变成1）,还可以每次查询第x行第y列的格子中的数字是什么。分析：根据这个题目中介绍的这个矩阵中的数的特点不是1就是0，这样我们只需记录每个格子改变过几次，即可判断这个格子的数字。�第一步我们不妨把这道题目简化一下，假定题目中给定的是长度为N的一列格子d。第2页共29页这样，这道题目就变得简单了。每次修改的时候，给定一个格子修改的范围(x,y)，这样我们不妨把这个范围变

4、成两个点,一个为更改的初始节点x，另一个为更改的终止节点y+1，然后往这列格子中的这两个节点中加1。x每次询问x的时候只需计算出Sumx=∑di这样就可以求出第x个i=1格子被修改过几次，输出的答案就是Summod2。x通过以上的方法，我们用一般的数据结构就可使得插入的复杂度第3页共29页为O(logN)，查询的复杂度为O(logN)。这样一维的问题我们就完美的解决了！�第二步我们已经解决了一维的问题，接下来我们就可以看看题目中的二维情况。我们能不能用上面的方法解决这一道题目呢？通过分析我们只改变两个格子的数字保证不了要求的性质(只改变矩

5、阵中的数字而不改变其他的数字)，由于一维的时候，我们加的两个点实际上给改变的区间定了一个范围，那么二维的情况，我们也给它设定一个范围，加上四个格子(x,y),(x+1,y),(x,y+1),(x+1,y+1)每次插入的时候往这四个格子中11211222加1。i=x,j=y查询(x,y)的时候输出Sumx,y=∑di,j即可。i=0,j=0第4页共29页这样做是否正确呢？证明：假设：插入(x1,y1),(x2+1,y1),(x1,y2+1),(x2+1,y2+1)四个值，查询(a,b)。不妨分类讨论：如上图所示。当(a,b)属于第1、2、3

6、、4或7这五个区域时，计算Sum不受插a,b入的影响；当(a,b)属于第5个区域时，Sum会受到(x,y)的影响，Suma,b11a,b相比以前会增加1，这个更改是正确的。当(a,b)属于第6个区域时，Sum会受到(x,y),(x+1,y)的影响，a,b1121第5页共29页Sum相比以前会增加2，答案是Summod2，结果不受影响，这个a,ba,b更改是正确的。当(a,b)属于第8个区域时，Sum会受到(x,y),(x,y+1)的影响，a,b1112Sum相比以前会增加2，答案是Summod2，结果不受影响，这个a,ba,b更改是正确的

7、。当(a,b)属于第9个区域时，Sum会受到a,b(x,y),(x+1,y),(x,y+1),(x+1,y+1)的影响，Sum相比以前会增加4，11211222a,b答案是Summod2，结果不受影响，这个更改是正确的。a,b证明完毕。通过证明我们发现以上的方法是正确的。�第三步那么二维的可以解决，三维的呢？N维的呢？根据上面的方法，我们不难想到，如果是三维的话，应该在长方体的周围加入8个点，N维的情况，应该在N维图形周围加入n个点2来处理这些情况。统计Sum即可。i1,i2...,in�第四步这道题的方法我们已经很明确了，要用到数据结构

8、来解决，但是用线段树等数据结构的话，如果推广到二维或者三维，可能写起来就相当复杂，并且出错的概率相当大，那么有没有一个写起来既简单快捷又易推广的数据结构呢？树状数组！！！第6页共29页树状数组