20xx南京市小學(xué)生信息學(xué)競賽初賽復(fù)習(xí)-知識要點(diǎn)-資料下載頁
2025-08-04 18:44本頁面
【正文】 () （已做）【問題描述】小明的數(shù)學(xué)老師布置了一堆數(shù)學(xué)題作為作業(yè)，這些數(shù)學(xué)題有一個(gè)共同的特點(diǎn)，就是都是要求計(jì)算出C(N,M)中不同質(zhì)因子的個(gè)數(shù)。Steven請你幫他寫一個(gè)程序，來幫助他盡快地完成這些作業(yè)。C(N,M)即求在N個(gè)數(shù)中選M個(gè)數(shù)的組合數(shù)。【輸入格式】()輸入文件中只有一行，其中有兩個(gè)整數(shù)，表示N和M(1=N, M=50000)?！据敵龈袷健?) 輸出一個(gè)整數(shù)，表示C(N,M)中質(zhì)因子的個(gè)數(shù)?！据斎霕永? 3【輸出樣例】 2（2）細(xì)胞分裂()【問題描述】Hanks 博士是BT (BioTech，生物技術(shù)) 領(lǐng)域的知名專家。現(xiàn)在，他正在為一個(gè)細(xì)胞實(shí)驗(yàn)做準(zhǔn)備工作：培養(yǎng)細(xì)胞樣本。Hanks 博士手里現(xiàn)在有N 種細(xì)胞，編號從1~N，一個(gè)第i 種細(xì)胞經(jīng)過1 秒鐘可以分裂為Si 個(gè)同種細(xì)胞（Si 為正整數(shù)）?，F(xiàn)在他需要選取某種細(xì)胞的一個(gè)放進(jìn)培養(yǎng)皿，讓其自由分裂，進(jìn)行培養(yǎng)。一段時(shí)間以后，再把培養(yǎng)皿中的所有細(xì)胞平均分入M 個(gè)試管，形成M 份樣本，用于實(shí)驗(yàn)。Hanks 博士的試管數(shù)M 很大，普通的計(jì)算機(jī)的基本數(shù)據(jù)類型無法存儲這樣大的M 值，但萬幸的是，M 總可以表示為m1 的m2 次方，即 ，其中mm2均為基本數(shù)據(jù)類型可以存儲的正整數(shù)。注意，整個(gè)實(shí)驗(yàn)過程中不允許分割單個(gè)細(xì)胞，比如某個(gè)時(shí)刻若培養(yǎng)皿中有4 個(gè)細(xì)胞，Hanks 博士可以把它們分入2 個(gè)試管，每試管內(nèi)2 個(gè)，然后開始實(shí)驗(yàn)。但如果培養(yǎng)皿中有5個(gè)細(xì)胞，博士就無法將它們均分入2 個(gè)試管。此時(shí)，博士就只能等待一段時(shí)間，讓細(xì)胞們繼續(xù)分裂，使得其個(gè)數(shù)可以均分，或是干脆改換另一種細(xì)胞培養(yǎng)。為了能讓實(shí)驗(yàn)盡早開始，Hanks 博士在選定一種細(xì)胞開始培養(yǎng)后，總是在得到的細(xì)胞“剛好可以平均分入M 個(gè)試管”時(shí)停止細(xì)胞培養(yǎng)并開始實(shí)驗(yàn)?，F(xiàn)在博士希望知道，選擇哪種細(xì)胞培養(yǎng)，可以使得實(shí)驗(yàn)的開始時(shí)間最早。【輸入】輸入文件名為 ，共有三行。第一行有一個(gè)正整數(shù) N，代表細(xì)胞種數(shù)。第二行有兩個(gè)正整數(shù)mm2，以一個(gè)空格隔開，即表示試管的總數(shù)M。第三行有 N 個(gè)正整數(shù)，第i 個(gè)數(shù)Si 表示第i 種細(xì)胞經(jīng)過1 秒鐘可以分裂成同種細(xì)胞的個(gè)數(shù)?！据敵觥枯敵鑫募? 共一行，為一個(gè)整數(shù)，表示從開始培養(yǎng)細(xì)胞到實(shí)驗(yàn)?zāi)軌蜷_始所經(jīng)過的最少時(shí)間（單位為秒）。如果無論 Hanks 博士選擇哪種細(xì)胞都不能滿足要求，則輸出整數(shù)1。【輸入輸出樣例 1】12 131【輸入輸出樣例1 說明】經(jīng)過 1 秒鐘，細(xì)胞分裂成3 個(gè)；經(jīng)過2 秒鐘，細(xì)胞分裂成9 個(gè)；……?？梢钥闯?，無論怎么分裂，細(xì)胞的個(gè)數(shù)都是奇數(shù)，因此永遠(yuǎn)不能分入2 個(gè)試管。【輸入輸出樣例 2】224 130 122【輸入輸出樣例2 說明】第 1 種細(xì)胞最早在3 秒后才能均分入24 個(gè)試管，而第2 種最早在2 秒后就可以均分（每試管144/(241)=6 個(gè)）。故實(shí)驗(yàn)最早可以在2 秒后開始。【數(shù)據(jù)范圍】對于 50%的數(shù)據(jù)，有。對于所有的數(shù)據(jù)，有1 ≤N≤ 10000，1 ≤m1 ≤ 30000，1 ≤m2 ≤ 10000，1 ≤ Si ≤ 2,000,000,000。13. 回溯（1）自然數(shù)的有序拆分。（2）數(shù)的分解（JS2010，T4，15分）【問題描述】一個(gè)正整數(shù)N（4=N=10000）可以分解為K個(gè)正整數(shù)的和（2=K=10，K=N）?！据斎搿縉, K?！据敵觥恳粋€(gè)整數(shù)，即N能夠分為K個(gè)正整數(shù)和的分法個(gè)數(shù)?！据斎霕永?,3【輸入樣例】3【樣例說明】6=1+1+4 =1+2+3 =2+2+2共有三種分法（1+1+4與1+4+1與4+1+1被認(rèn)為是相同的）。14. 貪心（1）奶牛曬衣服()【問題描述】在熊大媽的英明帶領(lǐng)下，時(shí)針和它的同伴生下了許多牛寶寶。熊大媽決定給每個(gè)寶寶都穿上可愛的嬰兒裝。于是，為牛寶寶洗曬衣服就成了很不爽的事情了。圣人王擔(dān)負(fù)起了這個(gè)重任。在洗完衣服后，你就要弄干衣服。衣服在自然條件下，用1的時(shí)間就可以曬干A點(diǎn)濕度。熊大媽買了一臺烘干機(jī)，它可以讓你用1的時(shí)間，使一件衣服除了自然曬干的A點(diǎn)濕度外，還可烘干B點(diǎn)濕度，但在1的時(shí)間內(nèi)，只能對一件衣服進(jìn)行烘干?，F(xiàn)有濕度不一樣的N件衣服?，F(xiàn)在，告訴你每件衣服的濕度，要求你求出弄干所有衣服所需的最少時(shí)間（濕度0為干）。【輸入格式】()第一行有三個(gè)整數(shù)，即N、A和B；接下來有N行，每行中有一個(gè)數(shù)，表示每件衣服的濕度(1=濕度, A, B=500 000, 1=N=500 000)?！据敵龈袷健?) 輸出所需的最少時(shí)間?！据斎霕永? 2 1123【輸出樣例】 1【樣例說明】 第1個(gè)時(shí)間內(nèi)，用機(jī)器處理第3件衣服。此外，所有衣服自然曬干2?；ㄙM(fèi)1時(shí)間全部弄干。15. 表達(dá)式計(jì)算16. 動(dòng)態(tài)規(guī)劃（1）取數(shù)（JS2010，T8，20分）【問題描述】設(shè)有N個(gè)正整數(shù)（1=N=50），其中每一個(gè)均是大于等于小于等于300的數(shù)。從這N個(gè)數(shù)中任取出若干個(gè)數(shù)（不能取相鄰的數(shù)），要求得到一種取法，使得到的和最大。 例如，當(dāng)N=5時(shí)，有5個(gè)數(shù)分別為：13，18，28，45，21此時(shí)，有許多種取法，如：13，28，21，和為62；13，45 和為58；18，45 和為63；……其中，和為63應(yīng)該是滿足要求的一種取法?！据斎搿勘绢}采用文件輸入。文件的第一行是一個(gè)整數(shù)N；第二行是N個(gè)符合條件的整數(shù)，數(shù)與數(shù)之間用一個(gè)逗號（BASIC語言）或一個(gè)空格（PASCAL）分開?！据敵觥枯敵龅狡聊唬阂粋€(gè)整數(shù)，即最大和。【樣例】 見問題中的舉例。17. 文件操作；18
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1