NOIP2021提高組復(fù)賽題解

1、noip2021提高組復(fù)賽題解 noip2021提高組復(fù)賽題解 noip2021提高組復(fù)賽題解河南省試驗(yàn)中學(xué) 彭勃 noip2021提高組復(fù)賽題解 第一題 笨小猴 * 題目描述：笨小猴的詞匯量很小，所以每次做英語選擇題的時(shí) 候都很頭疼。但是他找到了一種方法，經(jīng)試驗(yàn)證明，用 這種方法去選擇選項(xiàng)的時(shí)候選對(duì)的幾率特別大！ 這種方 法的詳細(xì)描述如下：假設(shè)maxn是單詞中消失次數(shù)最多的 字母的消失次數(shù)，minn是單詞中消失次數(shù)最少的字母的 消失次數(shù)，假如maxn-minn是一個(gè)質(zhì)數(shù)，那么笨小猴就認(rèn) 為這是個(gè)lucky word,這樣的單詞很可能就是正確的答 案。 noip2021提高組復(fù)賽題解 輸入格式

2、：輸入文件word.in只有一行，是一個(gè)單詞，其中只可 能消失小寫字母，并且長度小于100。 * 輸出格式： 輸出文件word.out共兩行，第一行是一個(gè)字符串， 假設(shè)輸入的的單詞是lucky word,那么輸出“l(fā)ucky word”,否則輸出“no answer”; 其次行是一個(gè)整數(shù)， 假如輸入單詞是lucky word,輸出maxn-minn的值，否則 輸出0。 noip2021提高組復(fù)賽題解 樣例1 輸入： error 輸出： lucky word 2 解釋： 單詞error中消失最多的字母r消失了3次，消失 次數(shù)最少的字母消失了1次，3-1=2,2是質(zhì)數(shù)。 noip2021提高組復(fù)賽

3、題解 樣例2 輸入： olymipic 輸出： no answer 0 解釋： 單詞olympic中消失最多的字母i消失了2次，消失次 數(shù)最少的字母消失了1次，2-1=1,1不是質(zhì)數(shù)。 noip2021提高組復(fù)賽題解 思路：統(tǒng)計(jì)單詞中每個(gè)字母的消失次數(shù)，挑出最多的次數(shù)和 最少的次數(shù)(不包括0次),相減推斷是否為質(zhì)數(shù)即可。 推斷質(zhì)數(shù)時(shí)可以寫函數(shù)推斷，也可以把100以內(nèi)的質(zhì)數(shù) 列成常量數(shù)組直接推斷，由于單詞最多只有100個(gè)字母。 需要留意的是輸出時(shí)的lwna四個(gè)字母要大寫。 * 總結(jié)： 這是一道送分題，沒有什么難度，需要留意的細(xì)節(jié)也 不多，所以在競賽中是肯定要拿滿分的。 noip2021提高組復(fù)賽

4、題解 參考樣程#include fstream #include string #include cmath #define i_f word.in #define o_f word.out using namespace std; string s; short ans; void input(); void search(); bool pd(); void output(); int main() input(); search(); output(); return 0; void input() ifstream fin(i_f); fins; fin.close(); void s

5、earch() /統(tǒng)計(jì)字母消失次數(shù) short i, max=0, min=200; short f26=0; for (i=0; is.length(); fsi+-'a'+); for (i=0; i26; i+) if (fi0) if (fimax) max=fi; if (fimin) min=fi; ans=max-min; bool pd() /推斷質(zhì)數(shù) if (ans=1) return false; else if (ans=2) return true; else if (ans%2=0) return false; else for (short i=3;

6、 i=sqrt(dou ble)ans); i+=2) if (ans%i=0) return false; return true; void output() ofstream fout(o_f); if (pd() foutlucky wordnansendl; else foutno answern0n; fout.close(); noip2021提高組復(fù)賽題解 其次題 火柴棒等式 問題描述： 給你n根火柴棍，你可以拼出多少個(gè)形如“a+b=c” 的等式？等式中的a、b、c是用火柴棍拼出的整數(shù) (若該數(shù)非零，則最高位不能是0)。用火柴棍拼 數(shù)字 0-9的拼法如圖所示：(圖略) 留意：

7、1. 加號(hào)與等號(hào)各自需要兩根火柴棍 2. 假如ab,則a+b=c與b+a=c視為不同的等式 (a、b、c=0) 3. n根火柴棍必需全部用上 noip2021提高組復(fù)賽題解 輸入格式： 輸入文件matches.in共一行，有一個(gè)整數(shù)n(n=24)。 * 輸出格式： 輸出文件matches.out共一行，表示能拼成的不同等 式的數(shù)目。 noip2021提高組復(fù)賽題解 樣例1 輸入：14 輸出： 2 解釋： 2個(gè)等式為0+1=1和1+0=1。 noip2021提高組復(fù)賽題解 樣例2 輸入： 18 輸出： 9 解釋： 9個(gè)等式為： 0+4=4、0+11=11、1+10=11、2+2=4、 2+7=9

8、、4+0=4、7+2=9、10+1=11、11+0=11 noip2021提高組復(fù)賽題解 思路： 枚舉兩加數(shù)，計(jì)算所需火柴棒是否等于n。枚舉 范圍01000。 總結(jié)： 這也是比較水的一道題，數(shù)據(jù)規(guī)模較小，算法 簡潔，競賽中這樣的題也應(yīng)當(dāng)拿到滿分。 noip2021提高組復(fù)賽題解 參考樣程#include fstream #define i_f matches.in #define o_f matches.out #define max 1000 using namespace std; const short match10=6,2,5,5,4,5, 6,3,7,6; /10個(gè)數(shù)字所需火柴棒

9、long ans; short n; void input(); int matches(int x); void search(); void output(); int main() input(); search(); output(); void input() ifstream fin(i_f); finn; fin.close(); int matches(int x) /計(jì)算擺出x所需的火柴棒 int t=x,s=0; if (x=0) return 6; else while (t0) s+=matcht%10; t/=10; return s; void search() i

10、nt i,j; n-=4; for (i=0; imax; i+) for (j=0; j=i; j+) /這樣對(duì)于a+b和b+a就只 會(huì)搜尋到一次，可以節(jié)省一半時(shí)間 if (matches(i)+matches(j)+matches(i+j)=n) if (i!=j) ans+=2; else ans+; /output函數(shù)略 noip2021提高組復(fù)賽題解 第三題 傳紙條 問題描述： 小淵和小軒是好伴侶也是同班同學(xué)，他們?cè)谝黄鹂傆姓劜煌?的話題。一次素養(yǎng)拓展活動(dòng)中，班上同學(xué)支配做成一個(gè)m行n列的 矩陣，而小淵和小軒被支配在矩陣對(duì)角線的兩端，因此，他們就 無法直接交談了。幸運(yùn)的是，他們可以通

11、過傳紙條來進(jìn)行溝通。 紙條要經(jīng)由很多同學(xué)傳到對(duì)方手里，小淵坐在矩陣的左上角，坐 標(biāo)(1,1),小軒坐在矩陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的 紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向 上或者向左傳遞。 在活動(dòng)進(jìn)行中，小淵盼望給小軒傳遞一張紙條，同時(shí)盼望小 軒給他回復(fù)。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一 次，也就是說假如此人在小淵遞給小軒紙條的時(shí)候幫忙，那么在 小軒遞給小淵的時(shí)候就不會(huì)再幫忙。反之亦然。 還有一件事情需要留意，全班每個(gè)同學(xué)情愿幫忙的好感度 有高有低(留意：小淵和小軒的好心程度沒有定義，輸入時(shí)用0表 示),可以用一個(gè)0-100的自然數(shù)來表示，數(shù)越大

12、表示越好心。小 淵和小軒盼望盡可能找好心程度高的同學(xué)來幫忙傳紙條，即找到 來回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度只和最大。 現(xiàn)在，請(qǐng)你 關(guān)心小淵和小軒找到這樣的兩條路徑。 noip2021提高組復(fù)賽題解 輸入格式： 輸入文件message.in的第一行有2個(gè)用空格隔開 的整數(shù)m和n,表示班里有m行n列(1=m,n=50)。 接下來的m行是一個(gè)m*n的矩陣，矩陣中第i行j m m*n i j 列的整數(shù)表示坐在第i行j列的同學(xué)的好心程度。每行 的n個(gè)整數(shù)之間用空格隔開。 輸出格式： 輸出文件message.out共一行，包含一個(gè)整數(shù)， 表示來回兩條路上參加傳遞紙條的同學(xué)的好心程度 之和的

13、最大值。 noip2021提高組復(fù)賽題解 樣例 輸入： 33 039 285 570 輸出： 34 數(shù)據(jù)規(guī)模： 30%的數(shù)據(jù)滿意：1=m,n=10 100%的數(shù)據(jù)滿意：1=m,n=50 noip2021提高組復(fù)賽題解 思路： 首先想到搜尋，但是對(duì)于只考慮一條路線來說， 每一步有兩種狀態(tài) 一共要走m+n步，搜尋整棵樹的 時(shí)間簡單度為o(2(m+n),假如兩條路線都考慮的 話，時(shí)間簡單度為o(4(m+n),即使是30%的數(shù)據(jù)， 即m+n=20,4201012,這樣的數(shù)據(jù)規(guī)模也還是太 大了。 noip2021提高組復(fù)賽題解 4維動(dòng)態(tài)規(guī)劃 本題可以使用動(dòng)態(tài)規(guī)劃法解決。 設(shè)fi,j,k,l為第一條線走到

14、(i,j),其次條線走到 (k,l)時(shí)的最優(yōu)值(便利起見，兩條線都看作從左上角 開頭，右下角結(jié)束)。 動(dòng)態(tài)轉(zhuǎn)移方程： fi-1,j,k-1,l (i1) fi,j,k,l=min fi-1,j,k,l-1 (i1) +si,j+sk,l fi,j-1,k-1,l (j1)且(ki+1) fi,j-1,k,j-1 (j1) 同時(shí)，由于兩條線不能交叉，有ki。 noip2021提高組復(fù)賽題解 狀態(tài)壓縮 由于兩條路線長度相等，所以有i+j=k+l,則狀態(tài) 可以壓縮為三維，壓縮后的轉(zhuǎn)移方程為： fi-1,j,k-1 (i1) fi,j,k=min fi-1,j,k (i1) +si,j+sk,i+j-

15、k fi,j-1,k-1 (j1)且(ki+1) fi,j-1,k (j1) 關(guān)于ki+1:當(dāng)k=i+1時(shí)，(i,j-1)和(k-1,i+j-k)是同一點(diǎn)， 由于兩條路線不行交叉，所以兩條路線的狀態(tài)不行 能由同一點(diǎn)進(jìn)展而來。 noip2021提高組復(fù)賽題解 總結(jié)： 這是一道較高難度的動(dòng)規(guī)題，有一個(gè)小陷阱 (假如把兩條線分開做動(dòng)態(tài)規(guī)劃則會(huì)由于兩條線路 可能交叉而出錯(cuò)),邊界條件也較為簡單，并且需 要狀態(tài)壓縮才能拿滿分。在競賽中遇到這種題假如 一時(shí)無法找到合適的算法，最好先做下一題，由于 即使寫搜尋也無法過多少數(shù)據(jù)。同時(shí)在考慮動(dòng)態(tài)轉(zhuǎn) 移方程時(shí)肯定要留意邊界條件，否則極易出錯(cuò)。 noip2021提高

16、組復(fù)賽題解 #include fstream #define i_f message.in #define o_f message.out using namespace std; short n,m; short s6060; long f606060; void input(); long max(long a, long b); void dyna(); void output(); int main() input(); dyna(); output(); return 0; void input() short i,j; ifstream fin(i_f); finnm; for (

17、i=0; in; i+) for (j=0; jm; finsij+); fin.close(); void output() ofstream fout(o_f); foutfn-2m-1n-1endl; /不要輸出fn-1m-1n-1,正確 的方程是不會(huì)計(jì)算這個(gè)狀態(tài)的 fout.close(); long max(long a, long b) if (ab) return a; else return b; void dyna() short i,j,k; for (i=0; in; i+) for (j=0; jm; j+) for (k=i+1; k=i+j; k+) if (k=i+1) /需要非常留意邊界條件 if (i=0) fijk=fij-1k+sij+ski+j-k; else if (j=0) fijk=max