科学委员会讲义新binarycodes-video

1、2022/8/10Binary codes1主要内容问题：Binary codes2022/8/10Binary codes2问题描述给定一个N位的二进制串b1 b2 bN-1 bN将该串做旋转，即将b1移到bN后面，得到一个新的二进制串：b2 bN-1 bN b1 2022/8/10Binary codes3问题描述对新的二进制串再做旋转，得二进制串b3 b4 bN-1 bN b1 b2重复旋转操作操作，可得N个二进制串，对这N个串排序，可得一个N*N的矩阵2022/8/10Binary codes4问题描述例如：1 0 0 0 1 0 0 0 1 11 1 0 0 00 0 1 1 00

2、1 1 0 02022/8/10Binary codes5问题描述对它们做排序，得矩阵0 0 0 1 10 0 1 1 0 0 1 1 0 01 0 0 0 1 1 1 0 0 02022/8/10Binary codes6问题描述问：给定这种矩阵的最后一列，求出矩阵的第一行。对于上面的例子，给出 1 0 0 1 0，要你的程序输出 0 0 0 1 1。2022/8/10Binary codes7问题描述输入文件名：bincode.in第一行有一个整数 N 表示二进制串的长度第二行有N个整数，表示矩阵最后一列从上到下的数值。2022/8/10Binary codes8问题描述输出文件名：bin

3、code.out第一行包括N个整数，表示矩阵第一行从左到右的数值。2022/8/10Binary codes9问题描述输入样例bincode.in51 0 0 1 02022/8/10Binary codes10问题描述输出样例bincode.out0 0 0 1 12022/8/10Binary codes11问题描述限制1 = N O(N3)N次迭代，每次要对一个N*N的矩阵排序2022/8/10Binary codes19解法三 迭代法证明该算法的本质是逐一构造矩阵的前 I 列对于I=1,重新排序后显然成立对于IN，如果前I列就是矩阵的前I列，那么把最后一列加到前面，从序列的顺序来说，是

4、正确的，重新对这I+1列排序保证了行顺序的正确性。2022/8/10Binary codes20解法三 迭代法分析一个值得注意的现象是：每次排序总是把开头是0的行按原来的先后次序移到前面，而把开头是1的行按原来的先后次序移到后面。 2022/8/10Binary codes21解法四 线性算法算法描述：1.计算输入列中0和1的个数，并用它们形成第一列.2022/8/10Binary codes22解法四 线性算法2. 生成一个Next数组，使得数组中的i个0指向最后一列第i个0的行数，数组中的第j个1指向最后一列第j个1的行数.2022/8/10Binary codes23解法四 线性算法3.

5、 从第1行开始，按照Next指引的顺序 从k到Nextk, 每次把该行最后一列的数字取出生成第一行的相应数字。2022/8/10Binary codes24解法四 线性算法例如 输入 10010有3个0，2个1，所以第1列一定是000112022/8/10Binary codes25解法四 线性算法例如 输入 100102.生成Next数组Next101220033005411151042022/8/10Binary codes26解法四 线性算法例如 输入 10010 Next 235143.沿着Next，根据 输入列，生成第一行0 0 0 1 12022/8/10Binary codes2

6、7解法四 线性算法证明对于序列（1） b1 b2 bN-1 bN，左旋一位变成（2） b2 bN-1 bN b1 ，我们只要知道（1）左旋后得到的（2）在矩阵中是哪一行，就可以根据该行第一列的值得到 b2，依次类推得到b3 ， b4 ， 2022/8/10Binary codes28解法四 线性算法证明假设矩阵中两行都以0开始，则它们左旋后，前后次序不变，所以在矩阵中以0开始的第1行，它的左旋后的序列在最后一列的第一个0的行。对1开始的行有同样的性质。2022/8/10Binary codes29解法四 线性算法证明例如 1 0 0 0 1 1 第1，2，3行以0 20 0 1 1 0 开始，

7、左旋后0 30 1 1 0 0 到最后1列，但 41 0 0 0 1 前后顺序不变， 51 1 0 0 0 所以是2，3，52022/8/10Binary codes30解法四 线性算法证明该算法就是利用了这一性质，根据第1列和最后1列，直接算出第1行。2022/8/10Binary codes31测试数据20 组100 位 全1100位 全0100位 01011000位 0011,5位，10位，15位的小数据长度为300-1000的随机序列 13个2022/8/10Binary codes32北大ACM代表队2002参赛介绍校内比赛报名集训参赛组队成绩模考2022/8/10Binary co

8、des33北大ACM代表队2002参赛介绍校内比赛79人参加比赛比赛时间为4小时5道比赛试题手工测试第1名 数学学院 鲁剑峰 满分2022/8/10Binary codes34北大ACM代表队2002参赛介绍组队坚持下来的12人组成4队，以小组方式训练，整套题目，配合2022/8/10Binary codes35北大ACM代表队2002参赛介绍模考后期训练主要以模考方式进行小组之间互赛交流讨论（包括比赛经验）2022/8/10Binary codes36北大ACM代表队2002参赛介绍报名经过模考排名1，2，3 队 参加清华赛区比赛1 队参加日本赛区比赛2，3，4 队参加西安赛区比赛2022/8/10Binary codes37北大ACM代表队2002参赛介绍参赛清华 清华2日本1 日本2