1、 2013 年藍橋杯（第 4 屆）預賽本科 A 組真題解析 高斯日記 大數(shù)學家高斯有個好習慣：無論如何都要記日記。 他的日記有個與眾不同的地方，他從不注明年月日，而是用一個整數(shù)代替， 比如： 4210 后來人們知道， 那個整數(shù)就是日期， 它表示那一天是高斯出生后的第幾天。 這或許也是 個好習慣，它時時刻刻提醒著主人：日子又過去一天，還有多少時光可以用于浪費呢？ 高斯出生于： 1777 年 4 月 30 日。 在高斯發(fā)現(xiàn)的一個重要定理的日記上標注著： 5343 ，因此可算出那天是： 1791 年 12 月 15 日。 高斯獲得博士學位的那天日記上標著： 8113 請你算出高斯獲得博士學位的年月日

2、。 提交答案的格式是： yyyy-mm -dd, 例如： 1980-03-21 （ 1）答案。 1799-07-16 （ 2）編程思路 1。 從年的角度出發(fā)，先求出 4 月 30 日是 1777 年的第幾天，加到日記標注的 n 上，并將 n 減 1，這樣 n 為從 1777 年 1 月 1 日開始的天數(shù)；再看 n 中有多少年（設為 x），加到 1777 上，并從 n 中減去這 x 年包括的天數(shù)；最后求得剩余天數(shù)在 1777+x 年中的日期。 （ 3）源程序 1。 include int isLeap(int year); int main() int a212 = 31, 28, 31, 30

3、, 31, 30, 31, 31, 30, 31, 30, 31, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31; int n; scanf(%d,&n); int year=1777, month=4,day=30; for (int i = 0; i 0) if(isLeap(year) n -= 366; else n -= 365; year+; if (n 0; i+) day = n; month = i; n -= aisLeap(year)i; printf(%d -%02d -%02dn, year,month + 1,

4、 day); return 0; int isLeap(int year) if(year % 4 = 0 & year % 100 != 0) | (year % 400 = 0) return 1; else return 0; （ 4）編程思路 2。 從月的角度出發(fā)，先將輸入的日志標記天數(shù) n 加 30 減 2，表示從 4 月 1 日開始算；再從 1777 年 4 月開始，逐月從 n 中減去各月的天數(shù)，同時修改對應年份和月份，直到剩余的 n 不足 1 個月的天數(shù)，就可以求得結果。 （ 5）源程序 2。 include int isLeap(int year); int main(

5、) int a212 = 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31; int n; scanf(%d,&n); int year=1777, month=4,day=30; / birth n=n+day -2; day=1; while (n =aisLeap(year)month -1) n -= aisLeap(year)month -1; month+; if (month12) year+; month=1; printf(%d

6、-%02d -%02dn, year,month,day+n); return 0; int isLeap(int year) if(year % 4 = 0 & year % 100 != 0) | (year % 400 = 0) return 1; else return 0; 排它平方數(shù) 小明正看著 203879 這個數(shù)字發(fā)呆。 原來， 203879 * 203879 = 41566646641 這有什么神奇呢？仔細觀察， 203879 是個 6 位數(shù)，并且它的每個數(shù)位上的數(shù)字都是不同的，并且它平方后的所有數(shù)位上都不出現(xiàn)組成它自身的數(shù)字。 具有這樣特點的 6 位數(shù)還有一個，請你

7、找出它！ （ 1）正確答案。 639172 （ 2）編程思路。 對 6 位數(shù)進行窮舉，區(qū)間下限為 定義數(shù)組 used10 記錄數(shù)字 09 123456，上限為 987654。 的使用情況，分離出窮舉的 6 位數(shù)的各位 x，且置 usedx+ ，若每個 usedx 大于 2，則數(shù)字 x 重復出現(xiàn)，不合要求，進行下次窮舉。 另外，由于兩個 6 位數(shù)相乘結果超出了整型數(shù)的表示范圍， 采用兩個數(shù)組元素來保存積。 計 算 6 位 數(shù) i 的 平 方 時 ， 將 i 表 示 為 a*10000+b ， 這 樣 i 的 平 方 等 于 a*a*100000000+2*a*b*10000+b*b ，用數(shù)組元素

8、 x1 保存低 8 位，用 x0 保存高 8 位，具體 方法為： x1=x1+c%10000*10000; x0=x0+c/10000; x0=x0+x1/100000000; x1=x1%100000000; 然后再檢測 x0和 （ 3）源程序。 x1 中的各位數(shù) k 是否已出現(xiàn)，即對應的 usedk 是否為 1 。 #include int check(int x,int used10) do if(usedx%10 0) return 0; else usedx % 10+; while(x /= 10); return 1; int checkpower(int x,int used1

9、0) do if(usedx0%10 0) return 0; while(x0/=10); for (int i=1;i 0) return 0; x1=x1/10; return 1; int main() int i,a,b,c,x2; int k,used10; for(i=123456; i=987654; i+) for (k=0;k=9;k+) usedk=0; if(!check(i,used) continue; a=i/10000; b=i%10000; x0=a*a; x1=b*b; c=2*a*b; x1=x1+c%10000*10000; x0=x0+c/10000;

10、 x0=x0+x1/100000000; x1=x1%100000000; if(!checkpower(x,used) continue; printf(%dn,i); return 0; 振興中華 小明參加了學校的趣味運動會，其中的一個項目是：跳格子。 地上畫著一些格子，每個格子里寫一個字，如下所示： 比賽時，先站在左上角的寫著“從”字的格子里，可以橫向或縱向跳到相鄰的格子里，但不能跳到對角的格子或其它位置。一直要跳到“華”字結束。 要求跳過的路線剛好構成“從我做起振興中華”這句話。 請你幫助小明算一算他一共有多少種可能的跳躍路線呢？ （ 1）答案。 35 （ 2）編程思路。 圖中有 4

11、行 5 列共 20 個格子， 定義數(shù)組 int a45 ，其中元素 aij 保存走到第 i 行第 j 列的格子的方法數(shù)。 由于要求跳過的路線剛好構成“從我做起振興中華”這句話，因此每個格子只能由其正上方或最左邊的格子走過來，因此有： aij = ai 初始時， -1j + aij a0j = 1; a0j = 1; -1; （ 1 i 3， 1 j 4） （ 0 i 3） （ 0 j 4） （ 3）源程序。 # include int main() int i,j; int a45 = 0; for (i=0; i4; i+) ai0 = 1; for (j=0; j5; j+) a0j =

12、1; for (i=1; i4; i+) for (j=1; j5; j+) aij = ai -1j + aij -1; printf(%dn, a34); return 0; 顛倒的價牌 小李的店里專賣其它店中下架的樣品電視機，可稱為：樣品電視專賣店。 其標價都是 4 位數(shù)字（即千元不等） 。 小李為了標價清晰、 方便，使用了預制的類似數(shù)碼管的標價簽， 只要用顏色筆涂數(shù)字就可以了（參見 p1.jpg ）。 這種價牌有個特點， 對一些數(shù)字， 倒過來看也是合理的數(shù)字。 如：1 2 5 6 8 9 0 都可以。 這樣一來，如果牌子掛倒了， 有可能完全變成了另一個價格， 比如：1958 倒著掛就是

13、： 8561 ， 差了幾千元啊 ! 當然，多數(shù)情況不能倒讀，比如， 1110 就不能倒過來，因為 0 不能作為開始數(shù)字。 有一天， 悲劇終于發(fā)生了。 某個店員不小心把店里的某兩個價格牌給掛倒了。 并且這兩 個價格牌的電視機都賣出去了 ! 慶幸的是價格出入不大， 其中一個價牌賠了 2 百多， 另一個價牌卻賺了 8 百多，綜合起 來，反而多賺了 558 元。 請根據(jù)這些信息計算：賠錢的那個價牌正確的價格應該是多少？ （ 1）答案。 9088 （ 2）編程思路。 在 09 這 10 個數(shù)字中， 只有 0,1,2,5,6,8,9 這 7 個數(shù)字（保存到數(shù)組 num1 中）顛倒后有 意義，它們顛倒后對應

14、數(shù)字為 0,1,2,5,9,8,6（保存到數(shù)組 num2 中）。 設 a、b、c、d 分別表示價牌上 4 位數(shù)字的千位、百位、十位和個位，顯然 a、d 位上的 數(shù)字不能取 0。 對 a（ 16）、b（06 ）、c（ 06）、d（ 16）的組合情況進行窮舉，找出這些組合情況中 價差在 -300-200（虧 2 百多）的數(shù)字保存到數(shù)組 price1 中，價差在 800900（賺 8 百多）的 數(shù)字保存到數(shù)組 price2 中。 最后對數(shù)組 price1 和 price2 中的元素進行兩兩匹配，找到價差之和等于 558 的情況。 3）源程序。 include int main() int num17

15、 = 0,1,2,5,6,8,9, num27 = 0,1,2,5,9,8,6; int price110002, price210002; int a, b, c, d, cnt1 = 0, cnt2 = 0; for (a = 1; a =6; a+) for (b = 0; b =6; b+) for (c = 0; c =6; c+) for (d = 1; d -300 & temp2 - temp1 800 & temp2 - temp1 900) price2cnt20 = temp1; price2cnt21 = temp2 - temp1; cnt2+; fo

16、r (a = 0; a cnt1; a+) for (b = 0; b =0 & x0=9) ev.result = x0 -0; ev.n = 1; return ev; v1 = evaluate(x+1); v2 = _; /填空位置 if(x0=+) ev.result = v1.result + v2.result; if(x0=*) ev.result = v1.result * v2.result; if(x0= -) ev.result = v1.result - v2.result; ev.n = 1+v1.n+v2.n; return ev; （ 1）參考答案。 e

17、valuate(x+1+v1.n) 錯誤票據(jù) 某涉密單位下發(fā)了某種票據(jù)，并要在年終全部收回。 每張票據(jù)有唯一的 ID 號。全年所有票據(jù)的 ID 號是連續(xù)的，但 ID 的開始數(shù)碼是隨機選定的。 因為工作人員疏忽，在錄入 ID 號的時候發(fā)生了一處錯誤，造成了某個 ID 斷號，另外一 個 ID 重號。 你的任務是通過編程，找出斷號的 ID 和重號的 ID。 假設斷號不可能發(fā)生在最大和最小號。 要求程序首先輸入一個整數(shù) N(N100)表示后面數(shù)據(jù)行數(shù)。 接著讀入 N 行數(shù)據(jù)。 每行數(shù)據(jù)長度不等， 是用空格分開的若干個 （不大于 100 個）正整數(shù)（不大于 100000 ），請注意行內和行末可能有多余的

18、空格，你的程序需要能處理這些空格。 每個整數(shù)代表一個 ID 號。 要求程序輸出 1 行，含兩個整數(shù) m n，用空格分隔。 其中， m 表示斷號 ID，n 表示重號 ID 例如： 用戶輸入： 2 568119 10129 則程序輸出： 7 9 再例如： 用戶輸入： 6 164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196 172 189 127 107 112 192 103 131 133 169 158 128 102 110 148 139 157 140 195 197 185 15

19、2 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190 149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188 113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119 則程序輸出： 105 120 （ 1）編程思路。 因為作為 ID 號的正整數(shù)不大于 100000 ，因此可以定義一個數(shù)組 int h

20、ash100001 ，其中 hashi 的值表示正整數(shù) i 出現(xiàn)的次數(shù)，初始時元素值全為 0。 在讀入數(shù)據(jù)的過程中，每讀入一個數(shù) num ，使 hashnum 元素值加 1。同時記錄下所讀 min max 完成后，掃描下標為 minmax 之間的 hash 數(shù)組元素，數(shù)組元素值為 0 所對應的下標是所求 的斷號 m，重號 n 即是數(shù)組元素值為 2 所對應的下標。 另外，本題的輸入行數(shù)是確定的， 但每行中數(shù)據(jù)個數(shù)不確定， 因此采用字符串來讀取每 行，然后以空格為分界點進行讀取各個數(shù)字。 需要注意的是： 題目特意強調行內和行末可能 有多余的空格，程序需要能處理這些空格。 （ 2）源程序。 #inc

21、lude #include int hash100001=0; char mess1000000; int main() int N; scanf(%d,&N); getchar(); int max=0,min=100001; while (N -) gets(mess); int num=0; for (int i=0; messi!=0;i+) if (messi!= ) / 讀入數(shù)字進行數(shù)值的轉換 num=num*10+messi -0; else if (num=0) continue; / 前面一定是多余的空格 hashnum+; if (minnum) min=num;

22、if (maxnum) min=num; if (maxnum) max=num; int m=0,n=0; for (int i=min; i=max; i+) if (hashi = 0) m = i; if (hashi = 2) n = i; if (m!=0 & n!=0) break; printf(%d %dn, m, n); return 0; 買不到的數(shù)目 小明開了一家糖果店。 他別出心裁： 把水果糖包成 4 顆一包和 7 顆一包的兩種。 糖果不 能拆包賣。 小朋友來買糖的時候， 他就用這兩種包裝來組合。 當然有些糖果數(shù)目是無法組合出來的， 比如要買 10 顆糖。 你

23、可以用計算機測試一下，在這種包裝情況下，最大不能買到的數(shù)量是 17。大于 17 的 任何數(shù)字都可以用 4 和 7 組合出來。 本題的要求就是在已知兩個包裝的數(shù)量時，求最大不能組合出的數(shù)字。 輸入： 兩個正整數(shù)，表示每種包裝中糖的顆數(shù) (都不多于 1000) 要求輸出： 一個正整數(shù)，表示最大不能買到的糖數(shù) 不需要考慮無解的情況 例如： 用戶輸入： 4 7 程序應該輸出： 17 再例如： 用戶輸入： 3 5 程序應該輸出： 7 數(shù)目 （ 1）編程思路。 采用窮舉法完成。設輸入的兩個正整數(shù)分別為 a 和 b ，且設兩數(shù)的最小公倍數(shù)為 進行糖果組合時，兩種糖果的數(shù)目分別取 i 和 j，則糖果的組合算式

24、為 a*i+b*j i 和 j 進行窮舉，窮舉的下界均為 0，上界分別為 G/b 、G/a 。 G。 。對糖果 定義數(shù)組 int vis1000001=0; ，初始值全為 0。窮舉每種包裝的數(shù)目時，若 a*i+b*j 小 于 G，則置 visa*i+b*j=1 。窮舉完成后，數(shù)組 vis 中元素值為 0 的元素 visk 表示數(shù)量為 k 的 糖果數(shù)買不到。 （ 2）源程序。 #include int vis1000001=0; int gcd(int m,int n) int r=m%n; while (r!=0) m=n; n=r; r=m%n; return n; int main() i

25、nt a, b; scanf(%d%d,&a,&b); int maxn = a * b/gcd(a,b); for (int i = 0; i * a = maxn; i+) for (int j = 0; j * b maxn) break; visi * a + j * b = 1; for(int i = maxn; i 0; i -) if(visi = 0) printf(%dn,i); break; return 0; 實際上，若自然數(shù) a,b 互質，則不能表示成 ax+by（x,y 為非負整數(shù)）的最大整數(shù)是 ab-a-b。 因此本題輸入 a 和 b 后，直接輸出

26、 a*b -a-b 也可以通過測頻系統(tǒng)的。 #include int main() int a, b; scanf(%d%d,&a,&b); printf(%dn,a*b -a-b); return 0; 剪格子 如圖 p1.jpg 所示， 3 x 3 的格子中填寫了一些整數(shù)。 我們沿著圖中的紅色線剪開，得到兩個部分，每個部分的數(shù)字和都是 60。 本題的要求就是請你編程判定： 對給定的 m x n 的格子中的整數(shù)， 是否可以分割為兩個 部分，使得這兩個區(qū)域的數(shù)字和相等。 如果存在多種解答，請輸出包含左上角格子的那個區(qū)域包含的格子的最小數(shù)目。 如果無法分割，則輸出 0 程序輸入輸

27、出格式要求： 程序先讀入兩個整數(shù) m n 用空格分割 (m,n10) 表示表格的寬度和高度 接下來是 n 行，每行 m 個正整數(shù)，用空格分開。每個整數(shù)不大于 10000 程序輸出：在所有解中，包含左上角的分割區(qū)可能包含的最小的格子數(shù)目。 例如： 用戶輸入： 3 3 10152 20301 1 2 3 則程序輸出： 3 再例如： 用戶輸入： 4 3 1111 130802 111100 則程序輸出： 10 （ 1）編程思路。 用深度優(yōu)先搜索從左上角第一個格子開始進行搜索，并同時記錄當前的和 cursum 和當 前的格子個數(shù) cnt ，如果當前和等于總和 sum 的一半，那么就進行相應記錄（若當前

28、的格子 個數(shù) cnt 比答案 ans 小，則更新 ans）。 （ 2）源程序。 #include int n, m; int ans = 100, sum = 0; / 所求的格子最小數(shù)目 ans 不會超過 100 個 int map1010; int visit1010=0; void DFS(int i, int j, int curSum, int cnt) visitij = 1; / 坐標 (i,j) 處的格子已訪問過 curSum += mapij; cnt+; if (2*curSum = sum) if (2*curSum = sum) if (anscnt) ans=cnt;

29、 visitij = 0; / 回溯到上一格子后，坐標 (i,j) 處的格子可被重新訪問 return; if (j+1m & !visitij + 1) DFS(i, j + 1, curSum, cnt); if (i+1=0 & !visitij - 1) DFS(i, j - 1, curSum, cnt); if (i -1=0 & !visiti - 1j) DFS(i - 1, j, curSum, cnt); visitij = 0; / 向右移動 / 向下移動 / 向左移動 / 向上移動 int main() scanf(%d%d,&m,&am

30、p;n); for (int i = 0; i n; +i) for (int j = 0; j m; +j) scanf(%d,&mapij); sum += mapij; if (sum%2!=0) printf(0n); else DFS(0,0,0,0); if (ans = 100) / ans 沒有變化過，說明沒有符合要求的剪法 printf(0n); else printf(%dn,ans); return 0; 大臣的旅費 很久以前， T 王國空前繁榮。為了更好地管理國家，王國修建了大量的快速路，用于連接首都和王國內的各大城市。 為節(jié)省經費， T 國的大臣們經過思考，制

31、定了一套優(yōu)秀的修建方案，使得任何一個大城 市都能從首都直接或者通過其他大城市間接到達。 同時， 如果不重復經過大城市， 從首都到達每個大城市的方案都是唯一的。 J 是 T 國重要大臣，他巡查于各大城市之間，體察民情。所以，從一個城市馬不停蹄地到另一個城市成了 J 最常做的事情。他有一個錢袋，用于存放往來城市間的路費。 聰明的 J 發(fā)現(xiàn)，如果不在某個城市停下來修整，在連續(xù)行進過程中，他所花的路費與他 已走過的距離有關，在走第 x 千米到第 x+1 千米這一千米中（ x 是整數(shù)），他花費的路費是 x+10 這么多。也就是說走 1 千米花費 11，走 2 千米要花費 23。 大臣想知道：他從某一個城

32、市出發(fā)，中間不休息，到達另一個城市，所有可能花費的路費中最多是多少呢？ 輸入格式： 輸入的第一行包含一個整數(shù) n，表示包括首都在內的 T 王國的城市數(shù) 城市從 1 開始依次編號， 1 號城市為首都。 接下來 n -1 行，描述 T 國的高速路（ T 國的高速路一定是 n-1 條） 每行三個整數(shù) Pi, Qi, Di，表示城市 Pi 和城市 Qi 之間有一條高速路，長度為 輸出格式 : 輸出一個整數(shù)，表示大臣 J 最多花費的路費是多少。 樣例輸入 : Di 千米。 5 1 2 2 1 3 1 2 4 5 2 5 4 樣例輸出 : 135 樣例說明 : 大臣 J從城市 4 到城市 5 要花費 13

33、5 的路費。 （ 1）編程思路 1。 先采用 Floyd 算法求出任意兩城市間的最短距離， 由于兩個城市之間僅僅有一種方法到 達，因此再求出這些最短路徑中的最大值就可以。 （ 2）源程序 1。 #include #define INF 110 int map101101; int main() int n,i,j,k; scanf(%d,&n); for (i=1;i=n;i+) for(j=1;j=n;j+) mapij=INF; for (i=1;i=n;i+) mapii=0; for (i=1;in;i+) int a,b,d; scanf(%d%d%d,&a,&b,&d); mapab=d; mapba=d; for (k=1;k=n;k+) for (i=1;i=n;i+) for (j=1;jmapik+mapkj) mapij = mapik+mapkj; int max=0; for (i=1;i=n;i+) for (j=1;j=n;j+) if (mapijmax) max=mapij; printf(%dn,max*10+(1+max)*max/2); return 0; 將源程序 1 提交給練習系統(tǒng)，得分