信息學(xué)集訓(xùn)隊作業(yè)0028-multiple_第1頁
信息學(xué)集訓(xùn)隊作業(yè)0028-multiple_第2頁
全文預(yù)覽已結(jié)束

下載本文檔

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

文檔簡介

題目0028Multiple(倍數(shù)一、英文原Writeaprogramthat,givenanaturalnumberNbetween0and4999(inclusively),andMdistinctdecimaldigitsX1,X2..XM(atleastone),findsthesmalleststrictlypositivemultipleofthathasnootherdigitsbesidesX1,X2..XM(ifsuchamultipleTheinputfilehasseveraldatasetsseparatedbyanemptyline,eachdatasethavingthefollowingformat:Onthefirstline-thenumberOnthesecondline-thenumberOnthefollowingMlines-thedigitsX1,X2..XMForeachdataset,theprogramshouldwritetostandardoutputonasinglelinethemultiple,ifsuchamultipleexists,and0otherwise.Anexampleofinputand37012110二、中文翻第一行:數(shù)n。m接下來m行:數(shù)字X1…XM輸3701211輸0三、初步討論情伍modn的余數(shù)是否以出現(xiàn)過,若出現(xiàn)過,則當(dāng)前擴展出的節(jié)點必定不是最優(yōu),不必再擴展。從左往右(從高位到低位)Mmodn的余數(shù)為狀態(tài)陸可1~9100以內(nèi)的…這樣可能可以有一定的周這題應(yīng)該很容易吧,就是很簡單的按余數(shù)為狀態(tài)的DPmodNDijkstra,100等n,這樣可以很快找到解高正2的方冪,最高幾位已經(jīng)給出。那道題是用連分?jǐn)?shù)做的,此題不知道能不能借鑒?modN的余數(shù)將所有數(shù)分類,求每一類能夠拼出的最小的數(shù),廣O(MN)的復(fù)雜度。張云寬度優(yōu)先搜索,按標(biāo)準(zhǔn)寬搜方法,opena,b=(a*10+X)modn;(X為輸入的M個數(shù)),若b為出現(xiàn)過這入寬搜隊列,并記錄下此時的n,及G[close]=open,直到找出B=0這時,按G[]的值一步步回退便可找到所求數(shù),可驗證起正確性,最小性,且最多n種狀劉才T(使10p10pTmodN成立的最小正數(shù)000a[I]modN=I的最小數(shù)的最高位的值,a[I]=0表示沒a[I]=0T個階段不再此題可以通過簡單廣搜來實現(xiàn),直接可以算出來。廣搜的隊列最大為n,狀態(tài)為modnO(NM),空間復(fù)雜度為O(N)。王知如果出現(xiàn)兩個數(shù)modn的余數(shù)相等,我們只需要保留教小的數(shù)就可以了,因此狀態(tài)量為N,O(N×M)項榮modnnx1modn,x2modn,xmmodn,0a到bb=(a*10+xi)modn,擴展每xi,就可以保證得到的是最小解了。O(n*m)。何O(10000n的p枚舉p的個位數(shù)字x10..9x1*n的個位不在給定集合,則這樣的xi就不滿足題目要求否則令more:=x1*ndiv10,more實際上是豎式乘法中剩下的前面一截只有moremoremoremoredpdxd。xd0..9依次循環(huán),xd*nmore’xd*ndiv10,more’和已經(jīng)擴展出來的某個節(jié)點重復(fù)則丟棄,否則放入隊列。林希BFS1、如果整數(shù)k的每位數(shù)字都∈{X1,X2…Xm}kV[k]true表示存在合法整數(shù)x滿足xk(modN)2、初始時V[XimodN]=trueV函數(shù)=false

如果存在整數(shù)

10trueV[k]3、復(fù)雜度==O(NM)劉一f[k]=min{f[m]*10+xi}(m*10+xi≡k(modn))f[k]n余kmultiplef[0]。multiple將所有的xi從小到大排序從隊列中取出隊首y,分別生成y*10+x1y*10+x2,…y*10+xm,入隊,如果其中有一個數(shù)恰好是n的倍數(shù),則輸出,結(jié)束。如果此時隊列為空,則無解;否則

溫馨提示

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

評論

0/150

提交評論