第十四次CCF-CSP認(rèn)證考試真題2018.9

1、.1. 賣菜時(shí)間限制：1.0s內(nèi)存限制： 256.0MB問題描述在一條街上有n 個(gè)賣菜的商店，按1 至 n 的順序排成一排，這些商店都賣一種蔬菜。第一天， 每個(gè)商店都自己定了一個(gè)價(jià)格。店主們希望自己的菜價(jià)和其他商店的一致，第二天， 每一家商店都會(huì)根據(jù)他自己和相鄰商店的價(jià)格調(diào)整自己的價(jià)格。具體的， 每家商店都會(huì)將第二天的菜價(jià)設(shè)置為自己和相鄰商店第一天菜價(jià)的平均值（用去尾法取整）。注意，編號(hào)為 1 的商店只有一個(gè)相鄰的商店2，編號(hào)為 n 的商店只有一個(gè)相鄰的商店n-1 ，其他編號(hào)為i 的商店有兩個(gè)相鄰的商店i-1和 i+1 。給定第一天各個(gè)商店的菜價(jià)，請(qǐng)計(jì)算第二天每個(gè)商店的菜價(jià)。輸入格式輸入的第一

2、行包含一個(gè)整數(shù)n，表示商店的數(shù)量。第二行包含n 個(gè)整數(shù)，依次表示每個(gè)商店第一天的菜價(jià)。輸出格式輸出一行，包含n 個(gè)正整數(shù)，依次表示每個(gè)商店第二天的菜價(jià)。樣例輸入8413165179樣例輸出2213491013數(shù)據(jù)規(guī)模和約定對(duì)于所有評(píng)測(cè)用例， 2 n 1000 ，第一天每個(gè)商店的菜價(jià)為不超過10000 的正整數(shù)。2. 買菜1 / 9.時(shí)間限制：1.0s內(nèi)存限制： 256.0MB問題描述小 H 和小 W來到了一條街上， 兩人分開買菜， 他們買菜的過程可以描述為， 去店里買一些菜然后去旁邊的一個(gè)廣場(chǎng)把菜裝上車， 兩人都要買 n 種菜，所以也都要裝 n 次車。具體的，對(duì)于小 H 來說有 n 個(gè)不相交的

3、時(shí)間段a 1,b 1 ,a2,b 2.an,b n 在裝車，對(duì)于小W來說有 n個(gè)不相交的時(shí)間段c 1,d 1,c2,d 2.cn,d n 在裝車。其中，一個(gè)時(shí)間段s, t表示的是從時(shí)刻 s 到時(shí)刻 t 這段時(shí)間，時(shí)長(zhǎng)為t-s 。由于他們是好朋友，他們都在廣場(chǎng)上裝車的時(shí)候會(huì)聊天，他們想知道他們可以聊多長(zhǎng)時(shí)間。輸入格式輸入的第一行包含一個(gè)正整數(shù)n，表示時(shí)間段的數(shù)量。接下來 n 行每行兩個(gè)數(shù)ai ，bi ，描述小H 的各個(gè)裝車的時(shí)間段。接下來 n 行每行兩個(gè)數(shù)ci ，di ，描述小W的各個(gè)裝車的時(shí)間段。輸出格式輸出一行，一個(gè)正整數(shù)，表示兩人可以聊多長(zhǎng)時(shí)間。樣例輸入41 35 69 1314 152

4、45 710 1113 14樣例輸出3數(shù)據(jù)規(guī)模和約定對(duì)于所有的評(píng)測(cè)用例，1 n 2000, ai< b i < a i+1 ， ci < d i < c i+1 , 對(duì)于所有的i(1 i n) 有， 1 a i , b i , c i , d i 1000000 。3. 元素選擇器2 / 9.時(shí)間限制：1.0s內(nèi)存限制： 256.0MB3 / 9.4 / 9.5 / 9.4.再賣菜6 / 9.時(shí)間限制：1.0s內(nèi)存限制： 256.0MB問題描述在一條街上有n 個(gè)賣菜的商店，按1 至 n 的順序排成一排，這些商店都賣一種蔬菜。第一天， 每個(gè)商店都自己定了一個(gè)正整數(shù)的價(jià)格。

5、店主們希望自己的菜價(jià)和其他商店的一致， 第二天， 每一家商店都會(huì)根據(jù)他自己和相鄰商店的價(jià)格調(diào)整自己的價(jià)格。具體的，每家商店都會(huì)將第二天的菜價(jià)設(shè)置為自己和相鄰商店第一天菜價(jià)的平均值（用去尾法取整）。注意，編號(hào)為 1 的商店只有一個(gè)相鄰的商店2，編號(hào)為 n 的商店只有一個(gè)相鄰的商店n-1 ，其他編號(hào)為i 的商店有兩個(gè)相鄰的商店i-1和 i+1 。給定第二天各個(gè)商店的菜價(jià)，可能存在不同的符合要求的第一天的菜價(jià)，請(qǐng)找到符合要求的第一天菜價(jià)中字典序最小的一種。字典序大小的定義：對(duì)于兩個(gè)不同的價(jià)格序列(a 1, a2, .,an) 和 (b 1, b2, b3, .,bn) ，若存在 i (i>=1

6、),使得 ai <bi ，且對(duì)于所有j<i ， aj =bj ，則認(rèn)為第一個(gè)序列的字典序小于第二個(gè)序列。輸入格式輸入的第一行包含一個(gè)整數(shù)n，表示商店的數(shù)量。第二行包含n 個(gè)正整數(shù)，依次表示每個(gè)商店第二天的菜價(jià)。輸出格式輸出一行，包含n 個(gè)正整數(shù)，依次表示每個(gè)商店第一天的菜價(jià)。樣例輸入82213491013樣例輸出2221651610數(shù)據(jù)規(guī)模和約定對(duì)于 30%的評(píng)測(cè)用例，2<=n<=5，第二天每個(gè)商店的菜價(jià)為不超過10 的正整數(shù)；對(duì)于 60%的評(píng)測(cè)用例，2<=n<=20，第二天每個(gè)商店的菜價(jià)為不超過100 的正整數(shù)；對(duì)于所有評(píng)測(cè)用例，2<=n<=300，第二天每個(gè)商店的菜價(jià)為不超過100 的正整數(shù)。請(qǐng)注意，以上都是給的第二天菜價(jià)的范圍，第一天菜價(jià)可能會(huì)超過此范圍。7 / 9.5.線性遞推式時(shí)間限制：1.0s內(nèi)存限制： 256.0MB問題樣例輸入描3 3 6述：2 0 4樣例輸出123280208樣例說明樣例輸入21118 / 9.1 1樣例輸出123581321345589144樣例說明樣例輸入10 10 20532737790 634932889 335818534 101179174 977780682695192541 779962395 295668292 157661238 325351676樣例輸出11