科學委員會講義新binarycodes-video

1、2022/8/10Binary codes1主要內(nèi)容問題：Binary codes2022/8/10Binary codes2問題描述給定一個N位的二進制串b1 b2 bN-1 bN將該串做旋轉(zhuǎn)，即將b1移到bN后面，得到一個新的二進制串：b2 bN-1 bN b1 2022/8/10Binary codes3問題描述對新的二進制串再做旋轉(zhuǎn)，得二進制串b3 b4 bN-1 bN b1 b2重復旋轉(zhuǎn)操作操作，可得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第一行有一個整數(shù) N 表示二進制串的長度第二行有N個整數(shù)，表示矩陣最后一列從上到下的數(shù)值。2022/8/10Binary codes8問題描述輸出文件名：bin

3、code.out第一行包括N個整數(shù)，表示矩陣第一行從左到右的數(shù)值。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解法三 迭代法證明該算法的本質(zhì)是逐一構(gòu)造矩陣的前 I 列對于I=1,重新排序后顯然成立對于IN，如果前I列就是矩陣的前I列，那么把最后一列加到前面，從序列的順序來說，是

4、正確的，重新對這I+1列排序保證了行順序的正確性。2022/8/10Binary codes20解法三 迭代法分析一個值得注意的現(xiàn)象是：每次排序總是把開頭是0的行按原來的先后次序移到前面，而把開頭是1的行按原來的先后次序移到后面。 2022/8/10Binary codes21解法四 線性算法算法描述：1.計算輸入列中0和1的個數(shù)，并用它們形成第一列.2022/8/10Binary codes22解法四 線性算法2. 生成一個Next數(shù)組，使得數(shù)組中的i個0指向最后一列第i個0的行數(shù)，數(shù)組中的第j個1指向最后一列第j個1的行數(shù).2022/8/10Binary codes23解法四 線性算法3.

5、 從第1行開始，按照Next指引的順序 從k到Nextk, 每次把該行最后一列的數(shù)字取出生成第一行的相應數(shù)字。2022/8/10Binary codes24解法四 線性算法例如 輸入 10010有3個0，2個1，所以第1列一定是000112022/8/10Binary codes25解法四 線性算法例如 輸入 100102.生成Next數(shù)組Next101220033005411151042022/8/10Binary codes26解法四 線性算法例如 輸入 10010 Next 235143.沿著Next，根據(jù) 輸入列，生成第一行0 0 0 1 12022/8/10Binary codes2

6、7解法四 線性算法證明對于序列（1） b1 b2 bN-1 bN，左旋一位變成（2） b2 bN-1 bN b1 ，我們只要知道（1）左旋后得到的（2）在矩陣中是哪一行，就可以根據(jù)該行第一列的值得到 b2，依次類推得到b3 ， b4 ， 2022/8/10Binary codes28解法四 線性算法證明假設矩陣中兩行都以0開始，則它們左旋后，前后次序不變，所以在矩陣中以0開始的第1行，它的左旋后的序列在最后一列的第一個0的行。對1開始的行有同樣的性質(zhì)。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解法四 線性算法證明該算法就是利用了這一性質(zhì)，根據(jù)第1列和最后1列，直接算出第1行。2022/8/10Binary codes31測試數(shù)據(jù)20 組100 位 全1100位 全0100位 01011000位 0011,5位，10位，15位的小數(shù)據(jù)長度為300-1000的隨機序列 13個2022/8/10Binary codes32北大ACM代表隊2002參賽介紹校內(nèi)比賽報名集訓參賽組隊成績?？?022/8/10Binary co

8、des33北大ACM代表隊2002參賽介紹校內(nèi)比賽79人參加比賽比賽時間為4小時5道比賽試題手工測試第1名 數(shù)學學院 魯劍峰 滿分2022/8/10Binary codes34北大ACM代表隊2002參賽介紹組隊堅持下來的12人組成4隊，以小組方式訓練，整套題目，配合2022/8/10Binary codes35北大ACM代表隊2002參賽介紹?？己笃谟柧氈饕阅？挤绞竭M行小組之間互賽交流討論（包括比賽經(jīng)驗）2022/8/10Binary codes36北大ACM代表隊2002參賽介紹報名經(jīng)過?？寂琶?，2，3 隊 參加清華賽區(qū)比賽1 隊參加日本賽區(qū)比賽2，3，4 隊參加西安賽區(qū)比賽2022/8/10Binary codes37北大ACM代表隊2002參賽介紹參賽清華 清華2日本1 日本2