您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 咨询培训 > 浅谈信息学竞赛中的“0”和“1”
WuSen“1与0,一切数字的神奇渊源。这是造物的秘密美妙的典范,因为,一切无非都来自上帝。”WuSen浅谈信息学竞赛中的“0”和“1”—二进制思想在信息学竞赛中的应用河北省石家庄二中武森WuSencontent二进制思想在数据结构中的应用•树状数组二进制思想在解题思想中的应用•状态压缩•模型转化•01二叉树WuSen例题一:Matrix•有一个M*N的矩阵,每一个格子中的数是1或0,初始时为0。有两种操作:–修改一个子矩阵,将子矩阵中的数字全部01取反。–查询第x行第y列的格子中的数字。WuSen如果给定的是一个长度为N的一排格子。退而求其次每次可以修改一个子列中的数字。WuSen这样,这道题目就变得简单了!根据这个题目中介绍的这个矩阵中的数的特点不是1就是0,这样我们只需记录每个格子改变过几次,即可判断这个格子的数字。WuSen每次修改的时候,不妨把格子修改的范围(x,y)变成两个点,一个为更改的初始节点x,另一个为更改的终止节点y+1,然后往这列格子中的这两个节点中加1。修改:WuSen每次修改的时候,不妨把格子修改的范围(x,y)变成两个点,一个为更改的初始节点x,另一个为更改的终止节点y+1,然后往这列格子中的这两个节点中加1。修改:WuSen每次询问的时候只需计算出Sumx就可以求出第x个格子被修改过几次。查询WuSen每次询问的时候只需计算出Sumx就可以求出第x个格子被修改过几次。查询WuSen寻根溯源用上面的方法看看能否解决原来的问题。WuSenWuSenWuSen推而广之如果是要处理三维的情况,甚至N维的情况呢?一般的数据结构能解决吗?不能!!怎么办呢???WuSen二进制思想二进制思想在数据结构中的应用:树状数组中的每一个元素的编号变成了二制编码,再通过这些二进制编码末尾的0的个数来决定存储什么信息,假设节点编号为x,那么这个节点存储数据的区间为2k(其中k为x二进制末尾0的个数)个元素。又由于每个十进制数转化成二进制位的话,1的个数最多只有O(logN)个,所以,复杂度只有O(logN)。WuSen具体操作:2k:Xand–X插入或删除:Whilex=maxdoBeginC[x]:=c[x]+delta;X:=x+(xand–x);End;查询:Whilex0doBeginSum:=sum+c[x];X:=x-(xand–x);End;WuSen树状数组优势代码长度短,不易出错。思想巧妙,算法复杂度低。维护简单,空间消耗低。易推广到二维甚至三维等等。WuSen例题二:CowXor农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1=N=100,000)个奶牛在他面前排成一行(按序号1..N的顺序),按照它们的社会等级排序。奶牛#1由最高的社会等级,奶牛#N最低。每个奶牛同时被赋予了一个唯一的数在0..221-1的范围内。帮助农民约翰找出应该从那一头奶牛开始喂,使得从它开始的某一个连续的子序列上的奶牛的数的异或值最大。如果有多个这样的子序列,选择结尾的奶牛社会等级最高的。如果还不唯一,选择最短的。WuSen•直接枚举起始点和终结点?时间复杂度是O(N*N)根据异或的性质,可以得出以下结论:Sumk=a1xora2xora3…ak-1xorakaixorai+1…aj-1xoraj=SumjxorSumi-1WuSen二进制思想•数的范围在0..221–1的整数•把这些数转化成二进制只有21位有用吗???WuSen01二叉树顾名思义,树的节点的值为0或1。WuSen插入•每次插入的时候,根据这个数的二进•制数进行建树,第i位是1则向左儿子•建一条边,反之向右儿子建边。WuSen插入•每次插入的时候,根据这个数的二进•制数进行建树,第i位是1则向左儿子•建一条边,反之向右儿子建边。WuSen查询•每次查询的时候,用贪心的思想根•据这个数的二进制数进行,第i位是•1如果有右儿子则向右儿子进行,反•之向左儿子进行。WuSen查询•每次查询的时候,用贪心的思想根•据这个数的二进制数进行,第i位是•1如果有右儿子则向右儿子进行,反•之向左儿子进行。WuSen这样,每次插入和查询的时间复杂度为O(logN)的,对与这道题目整体的时间复杂度为O(NlogN)。这道题目完美解决~WuSen总结二进制思想在信息学竞赛中的应用,巧妙的运用了十进制数与二进制数之间的关系,不仅在数据结构中有广泛应用。在解题中,将二进制思想引入,不仅可以用于状态压缩,还可以用与构建新的数学模型。从而达到转十为二,事半功倍的效果!WuSenThankYou!欢迎提问~
本文标题:浅谈信息学竞赛中的“0”和“1”
链接地址:https://www.777doc.com/doc-3667496 .html