国家集训队论文:浅谈信息学竞赛中的“0”和“1”.ppt
《国家集训队论文:浅谈信息学竞赛中的“0”和“1”.ppt》由会员分享,可在线阅读,更多相关《国家集训队论文:浅谈信息学竞赛中的“0”和“1”.ppt(28页珍藏版)》请在三一文库上搜索。
1、“1与0, 一切数字的神奇渊源。 这是造物的秘密美妙的典范, 因为, 一切无非都来自上帝。”,浅谈信息学竞赛中的“0”和“1” 二进制思想在信息学竞赛中的应用,河北省石家庄二中 武森,content,二进制思想在数据结构中的应用 树状数组 二进制思想在解题思想中的应用 状态压缩 模型转化 01二叉树,例题一:Matrix,有一个M*N的矩阵,每一个格子中的数是1或0,初始时为0。有两种操作: 修改一个子矩阵,将子矩阵中的数字全部01取反。 查询第x行第y列的格子中的数字。,如果给定的是一个长度为N的一排格子。,退而求其次,每次可以修改一个子列中的数字。,这样,这道题目就变得简单了!,根据这个题
2、目中介绍的这个矩阵中的 数的特点不是1就是0,这样我们只需记录 每个格子改变过几次,即可判断这个格子 的数字。,每次修改的时候,不妨把格子修改的范 围(x,y)变成两个点,一个为更改的初始节点 x,另一个为更改的终止节点y+1,然后往 这列格子中的这两个节点中加 1。,修改:,每次修改的时候,不妨把格子修改的范 围(x,y)变成两个点,一个为更改的初始节点 x,另一个为更改的终止节点y+1,然后往 这列格子中的这两个节点中加 1。,修改:,每次询问的时候只需计算出Sumx就可以 求出第x个格子被修改过几次。,查询,每次询问的时候只需计算出Sumx就可以 求出第x个格子被修改过几次。,查询,寻根
3、溯源,用上面的方法看看能否解决原来的问题。,推而广之,如果是要处理三维的情况,甚至N维的 情况呢?,一般的数据结构能解决吗?,不能!,怎么办呢?,二进制思想,二进制思想在数据结构中的应用: 树状数组中的每一个元素的编号变成了二制 编码,再通过这些二进制编码末尾的0的个数来 决定存储什么信息,假设节点编号为x,那么这 个节点存储数据的区间为2k(其中k为x二进制 末尾0 的个数)个元素。 又由于每个十进制数转化成二进制位的话,1的个数最多只有O(logN)个,所以,复杂度只有O(logN)。,具体操作:,2k:X and X,插入或删除: While x=max do Begin Cx:=cx+
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 国家 集训队 论文 浅谈 信息学 竞赛 中的
链接地址:https://www.31doc.com/p-2094175.html