藍(lán)橋杯決賽題答案.docVIP

2011年暑假藍(lán)橋杯決賽題附答案1 四方定理數(shù)論中有著名的四方定理：所有自然數(shù)至多只要用四個數(shù)的平方和就可以表示。我們可以通過計算機驗證其在有限范圍的正確性。對于大數(shù)，簡單的循環(huán)嵌套是不適宜的。下面的代碼給出了一種分解方案。請仔細(xì)閱讀，填寫空缺的代碼（下劃線部分）。注意：請把填空的答案（僅填空處的答案，不包括題面）存入考生文件夾下對應(yīng)題號的“解答.txt”中即可。直接寫在題面中不能得分。#include #include using namespace std; int f(int n, int a, int idx) if(n=0) return 1; / 填空1 if(idx=4) return 0; for(int i=(int)sqrt(double)n); i=1; i-) aidx = i; if(f(n-i*i,a,idx+1) return 1; / 填空2 return 0; int main(int argc, char* argv) for(;) int number; printf(輸入整數(shù)(110億)：); scanf(%d,&number); int a = 0,0,0,0; int r = f(number, a, 0); printf(%d: %d %d %d %dn, r, a0, a1, a2, a3); return 0; 2 加密在對文本進(jìn)行簡單加密的時候，可以選擇用一個n位的二進(jìn)制數(shù)，對原文進(jìn)行異或運算。解密的方法就是再執(zhí)行一次同樣的操作。加密過程中n位二進(jìn)制數(shù)會循環(huán)使用。并且其長度也可能不是8的整數(shù)倍。下面的代碼演示了如何實現(xiàn)該功能。請仔細(xì)閱讀，填寫空缺的代碼（下劃線部分）。注意：請把填空的答案（僅填空處的答案，不包括題面）存入考生文件夾下對應(yīng)題號的“解答.txt”中即可。直接寫在題面中不能得分。#include #include #include using namespace std; void f(char* buf, unsigned char* uckey, int n) int i; for(i=0; in; i+) bufi = bufi uckeyi; int main(int argc, char* argv) char p = abcd中國人123; / 待加密串 char* key = 11001100010001110; /以串的形式表達(dá)的密匙，運算時要轉(zhuǎn)換為按位存儲的形式。 int np = strlen(p); int nk = strlen(key); unsigned char* uckey = (unsigned char*)malloc(np); / 密匙串需要按位的形式循環(huán)拼入 uckey中 int i; for(i=0; inp*8; i+) if(keyi%nk=1) uckeyi/8=uckeyi/8|(1(i%nk); / 填空1 else uckeyi/8=uckeyi/8&(1(i%nk); / 填空2 f(p, uckey, strlen(p); printf(%sn, p); f(p, uckey, strlen(p); printf(%sn, p); free(uckey); return 0; 3 公倍數(shù)為什么1小時有60分鐘，而不是100分鐘呢？這是歷史上的習(xí)慣導(dǎo)致。但也并非純粹的偶然：60是個優(yōu)秀的數(shù)字，它的因子比較多。事實上，它是1至6的每個數(shù)字的倍數(shù)。即1,2,3,4,5,6都是可以除盡60。我們希望尋找到能除盡1至n的的每個數(shù)字的最小整數(shù)。不要小看這個數(shù)字，它可能十分大，比如n=100, 則該數(shù)為：69720375229712477164533808935312303556800請編寫程序，實現(xiàn)對用戶輸入的 n （n100）求出1n的最小公倍數(shù)。例如：用戶輸入：6程序輸出：60用戶輸入：10程序輸出：2520要求考生把所有函數(shù)寫在一個文件中。調(diào)試好后，存入與考生文件夾下對應(yīng)題號的“解答.txt”中即可。相關(guān)的工程文件不要拷入。 對于編程題目，要求選手給出的解答完全符合ANSI C標(biāo)準(zhǔn)，不能使用c+特性；不能使用諸如繪圖、中斷調(diào)用等硬件相關(guān)或操作系統(tǒng)相關(guān)的API。#include #include #include using namespace std; int main() int num101; int result45; int n; while(scanf(%d,&n)&n0) memset(result,0,sizeof(result); for (int i=1;i101;+i) numi=i; for (int i=2;in+1;+i) for (int j=1;ji-1;+j) if (numi%numj=0) numi/=numj; result1=6; for (int i=4;in+1;+i) for (int j=1;j43;+j) resultj*=numi; for (int j=1;j0;-i) if (resulti!=0) k=i; break; for (int i=k;i0;-i) printf(%d,resulti); printf(n); return 0; 4 地鐵換乘為解決交通難題，某城市修建了若干條交錯的地鐵線路，線路名及其所屬站名如stations.txt所示。線1蘋果園.四惠東線2西直門車公莊.建國門線4.其中第一行數(shù)據(jù)為地鐵線名，接下來是該線的站名。當(dāng)遇到空行時，本線路站名結(jié)束。下一行開始又是一條新線.直到數(shù)據(jù)結(jié)束。如果多條線擁有同一個站名，表明：這些線間可以在該站換車。為引導(dǎo)旅客合理利用線路資源，解決交通瓶頸問題，該城市制定了票價策略：1. 每條線路可以單獨購票，票價不等。2. 允許購買某些兩條可換乘的線路的聯(lián)票。聯(lián)票價格低于分別購票。單線票價和聯(lián)合票價如 price.txt 所示。線1 180.線13 114線1,線2 350線1,線10 390.每行數(shù)據(jù)表示一種票價線名與票價間用空格分開。如果是聯(lián)票，線名間用逗號分開。聯(lián)票只能包含兩條可換乘的線路?，F(xiàn)在的問題是：根據(jù)這些已知的數(shù)據(jù)，計算從A站到B站最小花費和可行的換乘方案。比如，對于本題目給出的示例數(shù)據(jù)如果用戶輸入：五棵松,奧體中心程序應(yīng)該輸出：-(線1,線10)-線8 = 565如果用戶輸入：五棵松,霍營程序應(yīng)該輸出：-線1-(線4,線13) = 440可以看出，用戶輸入的數(shù)據(jù)是：起始站，終到站，用逗號分開。程序輸出了購票方案，在括號中的表示聯(lián)票，短橫線(-)用來分開乘車次序。等號后輸出的是該方案的花費數(shù)值。請編程解決上述問題。注意：1. 我們測試您的程序時，所用數(shù)據(jù)與題目中的示例數(shù)據(jù)不同，但格式完全一樣。2. 當(dāng)多個方案有相同的最小花費，輸出任意一個方案即可。要求考生把所有函數(shù)寫在一個文件中。調(diào)試好后，存入與考生文件夾下對應(yīng)題號的“解答.txt”中即可。相關(guān)的工程文件不要拷入。 對于編程題目，要求選手給出的解答完全符合ANSI C標(biāo)準(zhǔn)，不能使用c+特性；不能使用諸如繪圖、中斷調(diào)用等硬件相關(guān)或操作系統(tǒng)相關(guān)的API。文件price.txt內(nèi)容如下：線1 180線2 250線4 160線5 270線8 175線10 226線13 114線1,線2 350線1,線10 390線1,線5 410線1,線4 330線10,線13 310線2,線5 390線4,線10 370線4,線13 260文件station.txt內(nèi)容如下：線1蘋果園古城路八角游樂園八寶山玉泉路五棵松萬壽路公主墳軍事博物館木樨地南禮士路復(fù)興門西單天安門西天安門東王府井東單建國門永安里國貿(mào)大望路四惠四惠東線2西直門車公莊阜成門復(fù)興門長椿街宣武門和平門前 門崇文門北京站建國門朝陽門東四十條東直門雍和宮安定門鼓樓大街積水潭線4公益西橋角門西馬家堡北京南站陶然亭菜市口宣武門西單靈境胡同西四平安里新街口西直門動物園國家圖書館魏公村人民大學(xué)海淀黃莊中關(guān)村北京大學(xué)東門圓明園西苑北宮門安河橋北線5天通苑北天通苑天通苑南立水橋立水橋南北苑路北大屯路東惠新西街北口惠新西街南口和平西橋和平里北街雍和宮北新橋張自忠路東四燈市口東單崇文門磁器口天壇東門蒲黃榆劉家窯宋家莊線8森林公園南門奧林匹克公園奧體中心北土城線10巴溝蘇州街海淀黃莊知春里知春路西土城牡丹園健德門北土城安貞門惠新西街南口芍藥居太陽宮三元橋亮馬橋農(nóng)業(yè)展覽館團結(jié)湖呼家樓金臺夕照國貿(mào)雙井勁松線13西直門大鐘寺知春路五道口上地西二旗龍澤回龍觀霍營立水橋北苑望京西芍藥居光熙門柳芳東直門5 連通問題in.bmp 文件如下：t1.bmp文件如下：BMP是常見的圖像存儲格式。如果用來存黑白圖像（顏色深度=1），則其信息比較容易讀取。與之相關(guān)的數(shù)據(jù)：（以下偏移均是從文件頭開始）偏移：10字節(jié), 長度4字節(jié)： 圖像數(shù)據(jù)真正開始的位置。偏移：18字節(jié), 長度4字節(jié)： 位圖的寬度，單位是像素。偏移：22字節(jié), 長度4字節(jié)： 位圖的高度，單位是像素。從圖像數(shù)據(jù)開始處，每個像素用1個二進(jìn)制位表示。從圖片的底行開始，一行一行向上存儲。Windows規(guī)定圖像文件中一個掃描行所占的字節(jié)數(shù)必須是4字節(jié)的倍數(shù)，不足的位均以 0 填充。例如，圖片寬度為45像素，實際上每行會占用8個字節(jié)?？梢酝ㄟ^Windows自帶的畫圖工具生成和編輯二進(jìn)制圖像。需要在“屬性”中選擇“黑白”，指定為二值圖像?？赡苄枰ㄟ^ 查看 | 縮放 | 自定義. 把圖像變大比例一些，更易于操作。圖像的左下角為圖像數(shù)據(jù)的開始位置。白色對應(yīng)1，黑色對應(yīng)0我們可以定義：兩個點距離如果小于2個像素，則認(rèn)為這兩個點連通。也就是說：以一個點為中心的九宮格中，圍繞它的8個點與它都是連通的。如：t1.bmp 所示，左下角的點組成一個連通的群體；而右上角的點都是孤立的。程序的目標(biāo)是：根據(jù)給定的黑白位圖，分析出所有獨立連通的群體，輸出每個連通群體的面積。所謂面積，就是它含有的像素的個數(shù)。輸入數(shù)據(jù)固定存在in.bmp中。如示例的in.