少兒編程競賽智算之道2020第一二三場初賽全部試題

1、智算之道2020初賽第一場試題TI排隊小A現(xiàn)在站在一個n個人的隊伍里排隊，他們的編號依次為l-n,現(xiàn)在她面前有m個窗 口，其中第i個窗口會給出一個數(shù)字a,然后將隊伍中所有編號為ai倍數(shù)的人帶出隊伍， 請問最后隊伍中還剩下多少個人？輸入格式第一行兩個用空格隔開的整數(shù)分別表示n,m第二行m個用空格隔開的整數(shù)，其中第i個代表a輸出格式輸出一個整數(shù).代表剩下多少個人數(shù)據(jù)規(guī)模與約定對于 30% 的數(shù)據(jù)，IWnW100,IWmWlO對于 60% 的數(shù)據(jù)，IWn1000,lm10對于 IO0%的數(shù)據(jù)，IWnWIOoOOo,1 WmWlo(UWaiWn樣例輸入10 3345樣例輸出3T2開關(guān)小B面前有n個開關(guān)

2、，開始時第i個開關(guān)的狀態(tài)是ai,其中ai = l表示第i個開關(guān)是開 的，a=O表示第i個開關(guān)是關(guān)的?，F(xiàn)在小B獲得了一種魔法，他可以進行若干次操作， 每次操作可以選擇一個數(shù)Xl然后把X號開關(guān)及其之前的所有開關(guān)狀態(tài)反轉(zhuǎn)（開變關(guān)，關(guān) 變開），請問小B最少需要多少次操作才能使所有開關(guān)都變?yōu)殛P(guān)的狀態(tài)。輸入格式第一行一個整數(shù)表示n第二行為一個長度為n的Ol字符串，即每一位只會是0或者1輸出格式輸出一個整數(shù).表示最少需要多少次操作才能使所有開關(guān)都變?yōu)殛P(guān)的狀態(tài)數(shù)據(jù)規(guī)模與約定對于30%的數(shù)據(jù)，1WnW20對于60%的數(shù)據(jù)，IWnW2000對于100%的數(shù)據(jù)，1200000樣例輸入41001樣例輸出3T3字符串給

3、定兩個字符串S和它們都只由小寫字母組成。現(xiàn)在請計算出宇符串S的本質(zhì)不同的 排列中有多少種是字符串T的子串，本質(zhì)不同，就是看起來不同，例如aab有3種本質(zhì)不同的排列aab, aba, baa。輸入格式第一行有一個宇符串S第二行有一個宇符串T輸出格式數(shù)據(jù)規(guī)模與約定對于3(的數(shù)據(jù)，對于60%的數(shù)據(jù)， 對于o的數(shù)據(jù),輸出一個整數(shù)表示字符串S的本質(zhì)不同的排列中有多少種是字符串T的子串1 I S I 5,1 I T I 2001 I S I 2000,1 I T I W2000IW S 200000sl I T I 200000樣例輸入aababacabaa樣例輸出2智算之道2020第二場初賽試題TI聲控

4、燈小明正在上樓梯，當小明逐漸接近某層樓的時候，這層樓的聲控燈檢測到小明的腳步聲便會 亮起來，當小明逐漸遠去的時候，聲控燈由于一段時間內(nèi)沒檢測到聲音又會滅下去。由于小明是勻速上樓的，而且他的速度把控得剛剛好，腳步聲的音量也十分恰當，使得燈的 亮滅呈現(xiàn)出這樣的狀態(tài)：他當前所在的樓層的聲控燈是亮起的，他即將抵達的下一層樓的聲 控燈是亮起的，他剛剛離開的那層樓的聲控燈也是亮起的。現(xiàn)在你站在樓的外面，通過窗戶看到了燈的亮滅狀態(tài)，請推斷小明現(xiàn)在在幾樓？輸入格式每個測試點包含以下內(nèi)容：第一行給出一個整數(shù)T1表示接下來給出T組測試數(shù)據(jù)每組測試數(shù)據(jù)包含兩行第一行包含兩個數(shù)n,m,表示這棟樓一共有n層，當前有m盞

5、燈是亮起的，而其余燈都 是熄滅的第二行包含m個整數(shù)，這些整數(shù)按照從小到大的順序給出亮起的燈的序號保證輸入數(shù)據(jù)是符合實際情況的輸出格式輸出T行，每行包含一個數(shù)字，按照輸入的順序依次給出每組測試數(shù)據(jù)的答案。如果答案 不確定，請輸出-1數(shù)據(jù)規(guī)模與約定對于 50% 的數(shù)據(jù)，lT10,3nl,m=3對于 IO0 的測試點，1T 1000,1 W10°IWmW3樣例輸入25312 3521 2樣例輸出21T2構(gòu)造字符串給定若干個小寫英文字母，請你用這些英文字母組成nnn個字符串，宇符串可以是空串。 要求這nnn個字符串的最長公共前綴最長。求出這個最長的長度，所有宇母都要用完，且每個字母只能用在一

6、個字符串里。名詞解釋前綴,是指一個字符串從第一個字符開始的連續(xù)若干個字符組成的宇符串。前綴可以為空串。 比如宇符串"aab"的前綴有四個，分別是,1 ,a", ,aa,1 ,aab"我們說一個字符串SSS是某些串的公共前綴，當且僅當這個串是每個字符串的前綴。 每一個公共前綴都是一個字符串，是字符串就有長度。當nn個串都確定下來的時候，這 n個串的所有公共前綴也就確定下來了，而且可以證明公共前綴的數(shù)目是有限的，在這 有限個公共前綴中，有一個公共前綴的長度是最長的，這個前綴就是最長公共前綴。舉個例子，假設(shè)現(xiàn)在有三個串：abbcabbdeabbe這個三個串的杲

7、長公共前綴是”abb”，長度為3再舉個例子，假設(shè)現(xiàn)在有四個串：abbdbbdabbdabb那么這四個串的最長公共前綴是：長度為O輸入格式輸入共有兩行第一行是一個整數(shù)n ,表示字符串的數(shù)量第二行包含26個非負整數(shù)。從前往后依次表示你擁有字母a的數(shù)目，字母b的數(shù)目, 字母Z的數(shù)目。輸出格式輸出一個非負整數(shù)，表示答案數(shù)據(jù)規(guī)模與約定對于30%的數(shù)據(jù)，除了字母a之外其它字母的數(shù)目都為0對于IOO的數(shù)據(jù)，210°,每種字母的個數(shù)也不超過10°樣例輸入233000000000000000000000000樣例輸出2樣例解釋在第一個樣例中，你擁有3個字母a和3個字母b可以構(gòu)造這樣的兩個串P

8、baTabbl 這樣最長公共前綴的長度是2o可以證明不存在更優(yōu)秀的方案樣例輸入22IIOOOOOOOOOOOOOOOOOOOOOOOO樣例輸出20樣例解釋2在第二個樣例中，你擁有1個字母a和1個字母b,無論如何構(gòu)造兩個串，都無法產(chǎn)生非 空的公共前綴，因此答案是0T3情報戰(zhàn)現(xiàn)在我方已經(jīng)查明，敵人通信所使用的加密方式依賴于一個長度為n的數(shù)列，只要得知了 這個數(shù)列中每個數(shù)的值，我方便可破解敵方的通信。通過深入敵人內(nèi)部的內(nèi)線人員的艱苦奮斗,我方逐漸獲得了一些有用的情報,通過這些情報, 整個數(shù)列正在被不斷地破解。先后有m條情報被得知，每條情報是以下兩種情況之一：情況1 :知道了數(shù)列中第X個數(shù)的值情況2

9、:知道了數(shù)列中第X個數(shù)和第y個數(shù)的和每得知一條情報，我方都試圖破解數(shù)列中元素的值作為情報部門核心技術(shù)人員的你，請編程實現(xiàn)如下功能：每次得知一條新情報，你都要計算 當前已經(jīng)能夠確定出數(shù)列中的多少個數(shù)了你比較笨，對于情況2這種情報，只能在已知其中一個數(shù)的情況下推岀另一個數(shù)，不能通 過若干情況2的情報列方程求解輸入格式第一行，兩個正整數(shù)n,m接下來m行，每行的第一個數(shù)是typeo如果type=l,則接下來跟著一個整數(shù)x,表示得 知了數(shù)列中第X個數(shù)的值；如果type二2,則接下來跟著兩個空格隔開的整數(shù)x,y表示得知 了第X個數(shù)和第y個數(shù)的和輸出格式輸出m行，每行包含一個非負整數(shù)，第i行的非負整數(shù)表示在

10、得知了前i條情報之后數(shù) 列中已經(jīng)能夠確定的數(shù)的數(shù)量數(shù)據(jù)規(guī)模與約定對于20的數(shù)據(jù)，lWn,rW10,且只有第一種情報對于50 的數(shù)據(jù)，IWn,mW5000對于 IOo)6 的數(shù)據(jù)，lWn,mW3l'可能會有重復的情報，也可能出現(xiàn)x=y的情況樣例輸入54111 22 2 3213樣例輸出1233智算之道2020第三場初賽試題TI水杯小D有一個能顯示溫度的杯子.其原理是杯蓋上的一個傳感器.只有在杯子內(nèi)的水的體積 大于等于某個數(shù)LL的時候傳感器才能顯示水溫，并且如果水溫不在A3內(nèi)傳感器也無法注意，這里溫度對水的體積沒有影響初始水杯為空，有n次操作，操作分為三種：1 X表示把水溫變成X-2x表示

11、把水的體積變成X.3查詢傳感器的顯示情況.如果不能顯示水溫輸岀GG,否則輸岀水溫.輸入格式第一行四個整數(shù)n丄AB含義如題目所示.接下來n行，每行一個整數(shù)OPt或兩個整數(shù)opt,x,表示執(zhí)行操作opt.輸出格式對于所有操作3輸出結(jié)果，每行一個答案.數(shù)據(jù)規(guī)模與約定對于 Io 的數(shù)據(jù)，IWnWlo00,-273WAWBWlO(UWLWloOo,1WOPtW3.對于操作2, -273WXWloo ；對于操作2, lx1000.樣例輸入52 131 52 331 23樣例輸出GG2T3順序安排給定一棵有根樹，對于給定的樹求出對應(yīng)的一種排列使得代價和最小。 對于一種排列計算代價方式如下給定常數(shù)koa的父親在序列中的位置是X, a在序列中的位置是yoa的兒子節(jié)點必須在a之后出現(xiàn)。a的父親在a之前出現(xiàn)，代價是k×(y-)o特殊的，容易看