集訓隊作業(yè)冬令營解題報告_第1頁
集訓隊作業(yè)冬令營解題報告_第2頁
免費預覽已結(jié)束，剩余1頁可下載查看

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領

文檔簡介

2004湖南省長沙市長郡中學偉一、孿生項m01串，它滿足：1、m≤n21<i≤m1i-1位移到最后一位后面，所得的n，去掉最后“0后的“1”全部刪除，并將最后的“0”改為“1B。R的第一個字符必定為“0性質(zhì)2：對于1<i≤m，取任意的l（1≤l≤m-i+1，必有從第i位開始的長l1l21°B1、由第二步和第三步，不難想到，Bm’≤nB12、為了說明B滿足條件2，把B分節(jié)，每m個字符為一節(jié)，最后剩下的不足m個字符的也看成一節(jié)，由性質(zhì)1，第三步加1時的進位不可能改變到前面的A所示。AAAA2iB，前面的用A表示最后一節(jié)用X表示，X>A，所以對于長度相等的兩個串AA……AAX是小于A……AXA……A的。這時滿足條件2。AAAAi正好是最后一節(jié)的第一位（圖C，同樣可用A、X表示每一節(jié)AAXXA……A2AAAAi指向除最后兩節(jié)的某一節(jié)的中間(D)，考慮第i位至第i+m-1位組成的它相當于原串的一和旋轉(zhuǎn)因為A是滿足條件2所以由第i位至第i+m-1位組成的串必定在由第1位至第m位的串的后面此時可以想到B是滿足條件2 AAi()所以最后一節(jié)的前面幾位(或整個最后一節(jié))不會小于其他串中從第一位開始的ii+-1A。AAAAAAAAAAAAAA所以，B2°BB’是由B去掉最后的若干個字符變成的(G)m為一節(jié)將B’分節(jié)，由構(gòu)造B的步驟不難想到，B’串最后一節(jié)(設長度為len)與第一節(jié)的前l(fā)enlen+1len+mm位的AAAAAAA AAAAAAA存在i(1≤i≤B的長度)B’的前i-1位與B的前i-1位相等且B’的第i位小于B的第ii所在的節(jié)必比Ai所在節(jié)的節(jié)首開始的旋轉(zhuǎn)也比AAAAAAAAACAACB是最小的滿足要求的串了。1ii。從不合法的串入手?？梢园巡缓戏ǖ拇譃閗1個旋轉(zhuǎn)都是不合法的合法串轉(zhuǎn)來，卻能轉(zhuǎn)成合法串。因為合法串數(shù)+第一類不合法串數(shù)+第二類不合法串數(shù)=k的二進制串數(shù)=22k就是(2-2k。1≤r≤kr22=∑i(i|kk=pa1p22p33pqaq，1 m?bius反演均可得到：

2pi

2pipji,j1

Fk

2k2k

2pipji,j1二、搬家公20次，本題只要用一個不太差的方法就可以對了。一1000121000012.02logn此題可以怎么優(yōu)化，怎樣使次數(shù)盡量趨近理論的最少次數(shù)卻是

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論