模擬賽noip chenzeyu97系列賽

1、2014-7-18 chenzeyu97 系列賽by hzwer，ndsf，jjs，zhouhebin，chenzeyu97（按照先后順序）共 5 道題目，時(shí)間 3.5 小時(shí)大家盡量多拿分就是了提醒：c+輸出 long long 請(qǐng)使用%I64d 或者 cout輸出時(shí)請(qǐng)注意類型的正確預(yù)祝各位虐場(chǎng)成功評(píng)測(cè)環(huán)境操作系統(tǒng)：Windows XP SP3CPU: Pentium(R) Dual-Core CPU E5300 2.60Ghz(2CPUs)系統(tǒng)內(nèi)存：2GB題目名czy 的后宮 3czy 的后宮 4czy 的后宮 5czy 的后宮 6蒟蒻 czy 又被 D飛了源文件輸入文件輸出文件時(shí)間限制內(nèi)存

2、限制測(cè)試點(diǎn)測(cè)試點(diǎn)分值harem.cpp/c/pasczy.cpp/c/pastask.cpp/c/pasvisit.cpp/c/pasfly.cpp/c/pasharem.inczy.ask.invisit,infly.inharem.ozy.outtask.outvisit.outfly.out1000MS1000MS1000MS1000MS1000MS256MB256MB256MB256MB256MB10101010101010101010（czy 的后宮 1，2 為之前的模擬賽題）1：2：czy 的后宮 3【題目描述】/2530.html/3305.html上次czy 在機(jī)房妥善安排了他

3、的后宮之后，他發(fā)現(xiàn)可以將他的妹子分為 c 種，他經(jīng)常會(huì)考慮這樣一個(gè)問題：在l,r的妹子中間，能挑選出多少不同類型的妹子呢？注意：由于 czy 非常喪尸，所以他要求在所挑選的妹子類型在l,r中出現(xiàn)次數(shù)為正偶數(shù)，你懂得。問題簡(jiǎn)述:n 個(gè)數(shù)，m 次詢問，每次問l,r區(qū)間有多少個(gè)數(shù)恰好出現(xiàn)正偶數(shù)次【輸入格式】第一行 3 個(gè)整數(shù)，表示n,c,m第二行n 個(gè)數(shù)，每個(gè)數(shù) Ai 在1,c之間，表示一個(gè) Ai 類型的妹子接下來m 行，每行兩個(gè)整數(shù)l,r，表示詢問l,r這個(gè)區(qū)間的【輸出格式】有m 行，表示第i 次詢問的【樣例輸入】5 5 31 1 2 2 3【樣例輸出】【數(shù)據(jù)范圍】共有組測(cè)試數(shù)據(jù)1-4 組 n,m

4、=500，2000，5000，10000，c=10005-7 組 n,m=20000，30000，40000，c=100008-10 組 n,m=50000，80000，100000，c=100000數(shù)據(jù)保證隨機(jī)生成czy 的后宮 4【問題描述】czy 有很多妹子，妹子雖然數(shù)量很多，但是質(zhì)量不容樂觀，她們的美麗值全部為負(fù)數(shù)（喜聞樂見）。 czy 每天都要帶N 個(gè)妹子到機(jī)房，她們都有一個(gè)獨(dú)一無二的美麗值，美麗值為-1 到-N 之間的整數(shù)。他想要把這些妹子排成一個(gè)波動(dòng)序列，這樣相對(duì)“漂亮”（美麗值的絕對(duì)值較?。┑拿米涌梢耘c她旁邊的兩個(gè)美麗值的絕對(duì)值較大的妹子形成鮮明的對(duì)比，整個(gè)序列相對(duì)將更加“美觀

5、”（不再那么無法直視）。一個(gè)序列是波動(dòng)序列僅當(dāng)序列中的每個(gè)數(shù)比周圍的兩個(gè)數(shù)都大或都?。ㄈ绻械脑挘，F(xiàn)在 czy 希望知道，長(zhǎng)度為 N 的波動(dòng)序列有多少種。兩種序列 A 和 B 不同當(dāng)且僅當(dāng)存在一個(gè) i，使得 AiBi。由于這個(gè)數(shù)目可能很大，你只對(duì)它除以 P 的余數(shù)感【輸入格式】。輸入文件czy.in 僅含一行，兩個(gè)正整數(shù)N, P。【輸出格式】輸出文件czy.out 僅含一行，一個(gè)非負(fù)整數(shù)，表示你所求的【樣例輸入輸出】czy.in 4 7czy.out3對(duì)P 取余之后的結(jié)果。說明：共有 10 種可能的序列，它們是： 1324 1423 2143 2314 2413 3142 3241 3412

6、 4132 4231(忽略負(fù)號(hào))【數(shù)據(jù)規(guī)模和約定】對(duì)于 20%的數(shù)據(jù)，滿足 N10；對(duì)于 40%的數(shù)據(jù)，滿足 N18；對(duì)于 70%的數(shù)據(jù)，滿足 N550；對(duì)于 100%的數(shù)據(jù)，滿足 3N4200，P109。czy 的后宮 5描述czy 要召集他的妹子，但是由于條件有限，可能每個(gè)妹子不能都去，但每個(gè)妹子都有一個(gè)美麗值，czy 希望來的妹子們的美麗值總和最大（雖然）。czy 有一個(gè)周密的通知網(wǎng)絡(luò)，它其實(shí)就是一棵樹，根結(jié)點(diǎn)為 czy，他可以通知一些妹子（畢竟他不認(rèn)識(shí)他的所有妹子嘛），稱為他的下線（也就是兒子節(jié)點(diǎn)），下線們繼續(xù)通知自己的下線。任何妹子都可以不去，但是任何一個(gè)妹子如果要去，則定要去。上線

7、（也就是父親節(jié)點(diǎn)）一為了使妹子美麗值總和最大，czy 想安排一下，（非強(qiáng)制）讓一些妹子去。但是妹子數(shù)很多，人腦是難以應(yīng)付的，所以他想讓你用電腦解決。輸入格式輸入第一行兩個(gè)整數(shù)n，m 表示有 n 個(gè)妹子，至多只能去 m 個(gè)妹子。(1=m=n)接下來 2*n 行，每?jī)尚写硪粋€(gè)妹子的信息（如果這個(gè)妹子沒有子節(jié)點(diǎn)，就只有一行）。每個(gè)妹子的第一行兩個(gè)整數(shù)p，s，表示這個(gè)妹子美麗值為 p，子節(jié)點(diǎn)個(gè)數(shù) s；(-100=p=100)第二行s 個(gè)整數(shù)，表示這個(gè)妹子的子節(jié)點(diǎn)的對(duì)于 20%數(shù)據(jù) 1=n=10對(duì)于 60%數(shù)據(jù) 1=n=100對(duì)于 100%數(shù)據(jù) 1=n=1000輸出格式。czy 的一定為 1。輸出一個(gè)

8、整數(shù)，表示權(quán)值的最大值。樣例輸入8 5100 2 2 379 24 5czy 的后宮 6題目描述眾所周知的是喪尸czy有很多妹子（雖然很多但是質(zhì)量不容樂觀QAQ），今天czy把n個(gè)妹子排成一行來。但是czy的妹子的質(zhì)量實(shí)在所以czy看不下去了。了第i個(gè)妹子會(huì)增加czyai的腎虛值，他打算在過程中最多休息m次（一開始算0次休息，就是說czy最多可以檢閱m+1次），每次休息過后czy又會(huì)的最大腎虛值最小。猛的繼續(xù)。問怎樣分配才能使得czy在過程中當(dāng)然這么簡(jiǎn)單czy早就會(huì)做啦他原來還想算算滿足腎虛值最小的條件下有幾種方案，但是他太虛了，所以這個(gè)問題也交給你啦。你只要輸出方案數(shù)mod 32123的值即

9、可。輸入格式第一行輸入兩個(gè)正整數(shù)n、m，表示czy的妹子數(shù)、最多的休息次數(shù)接下來2到n+1行每行輸入一個(gè)數(shù)ai，意義見上輸出格式第一行輸出一個(gè)數(shù)s，表示最小的腎虛值第二行輸出一個(gè)數(shù)t，表示方案數(shù)樣例輸入4 23452樣例輸出73樣例解釋最小的腎虛值為7分法有3種：34|5|2，34|52，3|4|52|表示休息數(shù)據(jù)范圍有30%的數(shù)據(jù)，1=n=20另30%的數(shù)據(jù)，1=n=200另30%的數(shù)據(jù)，1=n=5000，1=m=min(n-1,1000)，1=ai=1000另10%的數(shù)據(jù)，1=n=20000，1=m=1000，ai只有1、2保證80%數(shù)據(jù)隨機(jī)生成，在計(jì)算過程中不會(huì)爆109 36 7 810

10、0 0100 0100 0101 0108 0樣例輸出518蒟蒻czy又被D飛了【題目描述】機(jī)房里的各路巨神天天 D 蒟蒻CZY，早已是他們的日常任務(wù)了。（今天的機(jī)房也是很和平呢）這一次他們安排好了式來 D 蒟蒻Czy。每個(gè)人每次都能把 Czy D 飛一個(gè)高度（讓Czy 的高度+ai），由于他們的精力有限（尤其是某些后宮王），要保留體力應(yīng)對(duì)接下來的戰(zhàn)斗，所以他們每個(gè)人只會(huì) D Czy ki次。由于他們每個(gè)人的 D 人能力不同，各有所以他們每個(gè)人都在 Czy 到一定高度 hi以后良心發(fā)現(xiàn)，任由 Czy 自生自滅，回去玩，進(jìn)化島了。(神犇們：計(jì)劃通所以 Czy 想知道他的速度是否能達(dá)到第二宇宙速度，離開這個(gè)可怕的地方。但是 Czy太弱了，所以這個(gè)問題就交給了未來集訓(xùn)隊(duì)的你。但是你這么吊，哪里屑解答 Czy 蒟蒻的問題。 于是你打算只最高會(huì)飛到什么高度， 讓他自己算自己的速度去。（蒟蒻無【輸入格式】 fly.in第 1 行：1 個(gè)整數(shù) N（1=N=100）N 表示機(jī)房里有多少人今天要 D 蒟蒻Czy接下里 N 行，每行描述一個(gè)神犇的信息 ai hi ki【輸出格式】 fl