初賽、復(fù)賽試題csp-js2019第二輪認(rèn)證

2019CCFCSP-時(shí)間：2019111708:30～題目Emiya家今天劃樹的題目傳統(tǒng)可執(zhí)行文輸入文輸出文每個(gè)測(cè)試1.02.03.0內(nèi)存2561256子任務(wù)測(cè)試點(diǎn)是是是是提交源程對(duì)于 語對(duì)于 語Pascal編譯選對(duì)于 語-對(duì)于 語-Pascal文件名（程序名和輸入輸出文件名）C/C++main()int，程序正常結(jié)束時(shí)的返回值必須是0。提交的程序代碼文件的放置位置請(qǐng)參照的具體要求因以上三點(diǎn)而出現(xiàn)的錯(cuò)誤或問題，申訴時(shí)一律不予受理若無特殊說明，結(jié)果的比較方式為全文比較（過濾行末空格及文末回車PAGEPAGE2NUMPAGES122019年CCF非專業(yè)級(jí)軟件能力認(rèn)證第二輪提高 統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為：In (R)Core(TM)i7-8700KCPU3.70GHz，內(nèi)存32GB。上述時(shí)限以此配置為準(zhǔn)。只提供Linux評(píng)測(cè)在當(dāng)前公布的NOILinux下進(jìn)行，各語言的編譯器版本以其為準(zhǔn) 是求和運(yùn)算符 ai的值等于a1+a2+···+an20192019CCFPAGEPAGE3NUMPAGES12Emiya家今天的飯Emiyan種....m種....做菜。為了方便敘述，我們對(duì)烹飪方法從1～n1～m編號(hào)。Emiya做的每道菜都將使用....烹飪方法與....Emiyaai,jij的菜（1in，1≤jm）也意味著Emiya總共會(huì)做 m i=1Emiya今天要準(zhǔn)備一桌飯招待Yazid和Rin這對(duì)好朋友，然而三個(gè)人對(duì)有不同的要求，更具體地，對(duì)于一種包含 道菜的搭配方案而言Emiya不會(huì)讓大家餓肚子，所以將做.....k≥Rin希望品嘗不同烹飪方法做出的菜，因此她要求每道菜的.......Yazid不希望品嘗太多同一食材做出的菜，因此他要求每種至多在.的菜（即?k?道菜）中被使用2–?x?x這些要求難不倒Emiya，但他想知道共有多少種不同的符合要求的搭配方案。兩種方案不同，當(dāng)且僅當(dāng)存在至少一道菜在案中出現(xiàn)，而不在另案中出現(xiàn)。Emiya找到了你，請(qǐng)你幫他計(jì)算，你只需要符合所有要求的搭配方案數(shù)對(duì)質(zhì)998244353從文件meal.in中讀入數(shù)1行兩個(gè)用單個(gè)空格隔開的整數(shù)n,m2n+1mi+1m個(gè)數(shù)依次為ai,1,ai,2,...,ai,m。輸出到文件meal.out998244353121001131ij，Emiya都最多只會(huì)做一道菜，因此我們直接通符合要求的方案包做一道用烹飪方法1、主要食材1的菜和一道用烹飪方法2、主要食材2做一道用烹飪方法1、主要食材1的菜和一道用烹飪方法2、主要食材31322的菜因此輸出結(jié)果為3mod998,244,353=3。超過一半的菜中出現(xiàn)，這不滿Yazid的要求。2312456022Emiya22100。390因此符合要求的方案數(shù)為100+90 【樣 輸入010111111010011034見選 下的meal/meal4.in與meal/meal4.ans5見選 下的meal/meal5.in與meal/meal5.ans測(cè)試點(diǎn)nmai,j122223352435263728323998,244,1≤n≤100，1≤m≤2000，0≤ai,j<99824435320192019CCFday2劃分PAGEPAGE6NUMPAGES12劃分2048年，第三十屆CSP認(rèn)證的考場(chǎng)上，作為選手的打開了第一題。這個(gè)題的n1～n編號(hào)，iai。對(duì)該題設(shè)計(jì)出了一 程序，對(duì)于一組規(guī)模為u的數(shù)據(jù)，該程序的...u2u的數(shù)據(jù)之后，它將在任何一組規(guī)模..的數(shù)據(jù)上運(yùn)行錯(cuò)誤。樣例中的 不一定遞增，但又想在不修改程序的情況下正運(yùn)行樣例，于是決定使用一種非常原始的解決方案：將所有數(shù)據(jù)劃分成若干個(gè)數(shù)據(jù)段，段內(nèi)數(shù)據(jù)編號(hào)..，接著將同一段內(nèi)的數(shù)據(jù)合并成新數(shù)據(jù)，其規(guī)模等于段內(nèi)原數(shù)據(jù)的.... 將讓新數(shù)據(jù)的規(guī)模能夠遞增也就是說，需要找到一些分界點(diǎn)1≤k1<k2<···<kp<n，使

ai

ai≤··· 注意p可以為0且此時(shí)k0=0，也就是可以將所有數(shù)據(jù)合并在一起運(yùn)行。希望他的程序在正確運(yùn)行樣例情況下，運(yùn)行時(shí)間也能盡量小，也就是 (

ai)2+

ai)2+···+

nai，請(qǐng)你求出最優(yōu)劃分方案下，的程序的最小運(yùn)行時(shí)間。從文件partition.in中讀入數(shù)據(jù)................ ai.......第一行兩個(gè)整數(shù)n,type。n的意義見題目描述，type表示輸入方type=0ai....n個(gè)以空格分隔的整數(shù)ai，表示每組數(shù)據(jù)的規(guī)模。type=1ai將....，生成方式見后文。輸入文件接下來：xyzb1b2mmi（1im）行包含三個(gè)以空格分隔的正整數(shù)pi,li,ri。type=12325號(hào)測(cè)試點(diǎn)，ai的生成方式如下：給定整數(shù)x,y,z,b1,b2,m，以及m個(gè)三元組(pi,li,ri)。n2n2?3in，bi=(xbi?1ybi?2z)mod2300p+1PAGEPAGE7NUMPAGES1220192019CCFday2劃分PAGEPAGE8NUMPAGES121≤j≤mi（1≤i≤n）pj?1<i≤pj ai= mod(rj?lj+1)+l................................輸出到文件partition.out中。輸出一行一個(gè)整數(shù)，表示答案。15517911最優(yōu)的劃分方{5,1},{7},{9},{9}。由51≤7≤9≤9知該方案合法(51)2729292247雖然劃分方案{5},{1},{7},{9},{9}對(duì)應(yīng)的運(yùn)247小，但它不是一組合法方案，因?yàn)?>1。{5},{1,7},{9},{9}251247210567746【樣 輸出【樣 解釋最優(yōu)的劃分方案 {5},{6},{7},{7},{4,6,2},{13},{19,9}3112345678912345678934見選 下的 與partition/partition4.ans5見選 下的 與partition/partition5.ans測(cè)試點(diǎn)編naitype1～04～7～10~5×23～4×1所有測(cè)試點(diǎn)滿足：type∈{01},2≤n≤4107,1≤ai≤109,1≤m≤1051liri109,0xyzb1b223020192019CCFday2樹的重心PAGEPAGE10NUMPAGES12樹的重心小簡單正在學(xué)習(xí)離散數(shù)學(xué)，今天的內(nèi)容是圖論基礎(chǔ)，在課上他做了如下兩條筆記：nnn1條無向邊構(gòu)成，且滿足任意兩個(gè)結(jié)點(diǎn)間....一條簡單路徑。在樹中刪去一個(gè)結(jié)點(diǎn)及與它關(guān)聯(lián)的邊，樹將為若干個(gè)子樹；而在樹中刪去一條邊（保留關(guān)聯(lián)結(jié)點(diǎn)，下同，樹將為..兩個(gè)子樹。ncc是該樹的.2c及與它關(guān)聯(lián)的邊后，出的所有子樹的大小均...n?（2是下取整函數(shù)。對(duì)于包含至少一個(gè)結(jié)點(diǎn)的樹，它的重心只可能有1或2個(gè)。nS1n是求出 單獨(dú)刪去每條邊后，出的兩個(gè)子樹的重心編號(hào)和之和。即 x 且x號(hào)點(diǎn)是S′的重 uuv上式中，ES的邊集，(uv)uv號(hào)點(diǎn)的邊。S′與Suv分別表示樹S刪去邊(u,v)后，u號(hào)點(diǎn)與v號(hào)點(diǎn)所在的被出的子樹。從文件centroid.in中讀入數(shù)據(jù)。............T第一行一個(gè)整數(shù)n表示樹S的大小。n?1uivi(uivi)輸出到文件centroid.out后，出的兩個(gè)子樹的重心編號(hào)和之和。12512232435712【樣 輸出1對(duì)于第一刪去邊(1,2)，1號(hào)點(diǎn)所在重心編號(hào)為{1}，2號(hào)點(diǎn)所在重心編號(hào)為{2,3}。刪去邊(2,3)，2號(hào)點(diǎn)所在重心編號(hào)為{2}，3號(hào)點(diǎn)所在重心編號(hào)為{3,5}。刪去邊(2,4)，2號(hào)點(diǎn)所在重心編號(hào)為{2,3}，4號(hào)點(diǎn)所在重心編號(hào)為{4}。刪去邊(3,5)，3號(hào)點(diǎn)所在重心編號(hào)為{2}，5號(hào)點(diǎn)所在重心編號(hào)為{5}。因此答案為1+2+3+2+3+5+2+3+4+2+5=32。2見選 下的centroid/centroid2.in與centroid/centroid2.ans3 下的centroid/centroid3.in與centroid/centroid3.ans。該數(shù)據(jù)滿足特殊性質(zhì)A，具體信息見數(shù)據(jù)范圍中的描述。4 下的centroid/centroid4.in與centroid/centroid