2015年第六屆藍橋杯本科B組C  省賽個人題解

結果填空題:

解題技巧:對於藍橋杯的結果填空題,不管用什麼方式求解,只要能求出正確的結果就好。所以,這類題大部分都可以用暴力解決,有些題甚至直接手算就可以了。參考下面真題給出的題解就能體會得到。

1、獎券數目

有些人很迷信數字,比如帶“4”的數字,認為和“死”諧音,就覺得不吉利。
雖然這些說法純屬無稽之談,但有時還要迎合大眾的需求。某抽獎活動的獎券號碼是5位數(10000-99999),要求其中不要出現帶“4”的號碼,主辦單位請你計算一下,如果任何兩張獎券不重號,最多可發出獎券多少張。

請提交該數字(一個整數),不要寫任何多餘的內容或說明性文字。

程式設計思想:暴力或推公式。

1、暴力法如下:

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int i,j,k,l,m,ans;
ans=0;
for(i=1;i<=9;i  )
{
if(i==4) continue;
for(j=0;j<=9;j  )
{
if(j==4) continue;
for(k=0;k<=9;k  )
{
if(k==4) continue;
for(l=0;l<=9;l  )
{
if(l==4) continue;
for(m=0;m<=9;m  )
{
if(m==4) continue;
ans  ;
}
}
}
}
} 
printf("%d\n",ans);
return 0;
}

2、推公式:最高位不能為0和4,故從0-9中能選擇的數有8個,後4位能選0-9中除了4之外的任意一個數,能選擇的數有9個,故滿足的種類數目為8*9*9*9*9=52488。

答案:52488

2、星系炸彈

在X星系的廣袤空間中漂浮著許多X星人造“炸彈”,用來作為宇宙中的路標。
每個炸彈都可以設定多少天之後爆炸。
比如:阿爾法炸彈2015年1月1日放置,定時為15天,則它在2015年1月16日爆炸。
有一個貝塔炸彈,2014年11月9日放置,定時為1000天,請你計算它爆炸的準確日期。

請填寫該日期,格式為 yyyy-mm-dd  即4位年份2位月份2位日期。比如:2015-02-19
請嚴格按照格式書寫。不能出現其它文字或符號。

有兩種方法:

1、常規解法:手算。

2、巧妙解法:用Excel工具計算。輸入起始日期,然後輸入公式(原來日期的值 1000),回車後得到結果就是答案了,詳見下面截圖。

最後填寫答案時要注意題目所要求輸出答案的日期格式。

答案:2017-08-05

注意:Excel只能對公元1990年(包括1900年)以後的日期進行計算。

3、三羊獻瑞

觀察下面的加法算式:

      祥 瑞 生 輝
    三 羊 獻 瑞
——————-
   三 羊 生 瑞 氣

(如果有對齊問題,可以參看【圖1.jpg】)

其中,相同的漢字代表相同的數字,不同的漢字代表不同的數字。

請你填寫“三羊獻瑞”所代表的4位數字(答案唯一),不要填寫任何多餘內容。

圖1.jpg

程式設計思想:暴力。

暴力code:

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int a,b,c,d,e,f,g,h,s1,s2,sum;
for(a=1;a<=9;a  )//祥 
{
for(b=0;b<=9;b  )//瑞 
{
for(c=0;c<=9;c  )//生 
{
for(d=0;d<=9;d  )//輝 
{
e=1;//三(這裡推出“三”等於1是因為兩個一位數相加能得到的最大進位只能是1) 
for(f=0;f<=9;f  )//羊 
{
for(g=0;g<=9;g  )//獻
{
for(h=0;h<=9;h  )//氣
{
if(a!=b&&a!=c&&a!=d&&a!=e&&a!=f&&a!=g&&a!=h 
&& b!=c&&b!=d&&b!=e&&b!=f&&b!=g&&b!=h && 
c!=d&&c!=e&&c!=f&&c!=g&&c!=h && d!=e&&d!=f
&&d!=g&&d!=h && e!=f&&e!=g&&e!=h && f!=g&&f!=h 
&& g!=h
){
s1=a*1000 b*100 c*10 d;//祥瑞生輝
s2=e*1000 f*100 g*10 b;//三羊獻瑞
sum=e*10000 f*1000 c*100 b*10 h;//三羊生瑞氣
if(s1 s2==sum)
{
printf("%d%d%d%d\n",e,f,g,b);//三羊獻瑞
}
} 
} 
} 
}
}
}
}
}
return 0;
}

答案:1085

程式碼填空題:

4、格子中輸出

StringInGrid函式會在一個指定大小的格子中列印指定的字串。
要求字串在水平、垂直兩個方向上都居中。
如果字串太長,就截斷。
如果不能恰好居中,可以稍稍偏左或者偏上一點。

下面的程式實現這個邏輯,請填寫劃線部分缺少的程式碼。

#include <stdio.h>
#include <string.h>

void StringInGrid(int width, int height, const char* s)
{
int i,k;
char buf[1000];
strcpy(buf, s);
if(strlen(s)>width-2) buf[width-2]=0;

printf(” “);
for(i=0;i<width-2;i ) printf(“-“);
printf(” \n”);

for(k=1; k<(height-1)/2;k ){
printf(“|”);
for(i=0;i<width-2;i ) printf(” “);
printf(“|\n”);
}

printf(“|”);

printf(“%*s%s%*s”,_____________________________________________);  //填空
         
printf(“|\n”);

for(k=(height-1)/2 1; k<height-1; k ){
printf(“|”);
for(i=0;i<width-2;i ) printf(” “);
printf(“|\n”);
}

printf(” “);
for(i=0;i<width-2;i ) printf(“-“);
printf(” \n”);
}

int main()
{
StringInGrid(20,6,”abcd1234″);
return 0;
}

對於題目中資料,應該輸出:
——————
|                  |
|     abcd1234     |
|                  |
|                  |
——————

(如果出現對齊問題,參看【圖1.jpg】)

注意:只填寫缺少的內容,不要書寫任何題面已有程式碼或說明性文字。

圖1.jpg

code:

#include <stdio.h>
#include <string.h>
void StringInGrid(int width, int height, const char* s)
{
int i,k;
char buf[1000];
strcpy(buf, s);
if(strlen(s)>width-2) buf[width-2]=0;
printf(" ");
for(i=0;i<width-2;i  ) printf("-");
printf(" \n");
for(k=1; k<(height-1)/2;k  ){
printf("|");
for(i=0;i<width-2;i  ) printf(" ");
printf("|\n");
}
printf("|");
printf("%*s%s%*s",(width-strlen(buf)-2)/2," ",buf,(width-strlen(buf)-2)/2 (width-strlen(buf)-2)%2," ");  //填空(使空格“ ”分別佔據寬為(width-strlen(buf)-2)/2和(width-strlen(buf)-2)/2 (width-strlen(buf)-2)%2的空間且右對齊)
printf("|\n");
for(k=(height-1)/2 1; k<height-1; k  ){
printf("|");
for(i=0;i<width-2;i  ) printf(" ");
printf("|\n");
} 
printf(" ");
for(i=0;i<width-2;i  ) printf("-");
printf(" \n");
}
int main()
{
StringInGrid(20,6,"abcd1234");
return 0;
}

答案:(width-strlen(buf)-2)/2,” “,buf,(width-strlen(buf)-2)/2 (width-strlen(buf)-2)%2,” ”

5、九陣列分數

1,2,3…9 這九個數字組成一個分數,其值恰好為1/3,如何組法?

下面的程式實現了該功能,請填寫劃線部分缺失的程式碼。

#include <stdio.h>

void test(int x[])
{
int a = x[0]*1000 x[1]*100 x[2]*10 x[3];
int b = x[4]*10000 x[5]*1000 x[6]*100 x[7]*10 x[8];

if(a*3==b) printf(“%d / %d\n”, a, b);
}

void f(int x[], int k)
{
int i,t;
if(k>=9){
test(x);
return;
}

for(i=k; i<9; i ){
{t=x[k]; x[k]=x[i]; x[i]=t;}
f(x,k 1);
_____________________________________________ // 填空處
}
}

int main()
{
int x[] = {1,2,3,4,5,6,7,8,9};
f(x,0);

return 0;
}

注意:只填寫缺少的內容,不要書寫任何題面已有程式碼或說明性文字。

程式設計思想:考察深搜演算法裡對回溯的運用。

答案:{t=x[k]; x[k]=x[i]; x[i]=t;}

6、加法變乘法

我們都知道:1 2 3 … 49 = 1225
現在要求你把其中兩個不相鄰的加號變成乘號,使得結果為2015

比如:
1 2 3 … 10*11 12 … 27*28 29 … 49 = 2015
就是符合要求的答案。

請你尋找另外一個可能的答案,並把位置靠前的那個乘號左邊的數字提交(對於示例,就是提交10)。

注意:需要你提交的是一個整數,不要填寫任何多餘的內容。

程式設計思想:暴力。

暴力code:

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int a,b;
for(a=1;a<=48;a  )
{
for(b=a 1;b<=48;b  )
{
if(1225-a-(a 1)-b-(b 1) a*(a 1) b*(b 1)==2015)
{
printf("%d %d\n",a,b);
}
}
}
return 0;
}

答案:16


程式設計題目:


7、牌型種數

小明被劫持到X賭城,被迫與其他3人玩牌。
一副撲克牌(去掉大小王牌,共52張),均勻發給4個人,每個人13張。
這時,小明腦子裡突然冒出一個問題:
如果不考慮花色,只考慮點數,也不考慮自己得到的牌的先後順序,自己手裡能拿到的初始牌型組合一共有多少種呢?

請填寫該整數,不要填寫任何多餘的內容或說明文字。

程式設計思想:暴力或動態規劃。

1、暴力 code:

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int a[13],ans;
ans=0;
for(a[0]=0;a[0]<=4;a[0]  )
{
for(a[1]=0;a[1]<=4;a[1]  )
{
for(a[2]=0;a[2]<=4;a[2]  )
{
for(a[3]=0;a[3]<=4;a[3]  )
{
for(a[4]=0;a[4]<=4;a[4]  )
{
for(a[5]=0;a[5]<=4;a[5]  )
{
for(a[6]=0;a[6]<=4;a[6]  )
{
for(a[7]=0;a[7]<=4;a[7]  )
{
for(a[8]=0;a[8]<=4;a[8]  )
{
for(a[9]=0;a[9]<=4;a[9]  )
{
for(a[10]=0;a[10]<=4;a[10]  )
{
for(a[11]=0;a[11]<=4;a[11]  )
{
for(a[12]=0;a[12]<=4;a[12]  )
{
if(a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12]==13)
{
ans  ;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
printf("%d\n",ans);
return 0;
}

2、DP code:

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int dp[14][14];
int main()
{
int i,j,k,ans;
memset(dp,0,sizeof(dp));
ans=0;
dp[1][0]=dp[1][1]=dp[1][2]=dp[1][3]=dp[1][4]=1;
for(i=2;i<=13;i  )
{
for(j=0;j<=13;j  )
{
for(k=0;k<=4;k  )
{
if(j-k>=0)
{
dp[i][j] =dp[i-1][j-k];
}
}
}
}
ans=dp[13][13];
printf("%d\n",ans);
return 0;
}

答案:3598180

8、移動距離

X星球居民小區的樓房全是一樣的,並且按矩陣樣式排列。其樓房的編號為1,2,3…
當排滿一行時,從下一行相鄰的樓往反方向排號。
比如:當小區排號寬度為6時,開始情形如下:

1  2  3  4  5  6
12 11 10 9  8  7
13 14 15 …..

我們的問題是:已知了兩個樓號m和n,需要求出它們之間的最短移動距離(不能斜線方向移動)

輸入為3個整數w m n,空格分開,都在1到10000範圍內
w為排號寬度,m,n為待計算的樓號。
要求輸出一個整數,表示m n 兩樓間最短移動距離。

例如:
使用者輸入:
6 8 2
則,程式應該輸出:
4

再例如:
使用者輸入:
4 7 20
則,程式應該輸出:
5

資源約定:
峰值記憶體消耗 < 256M
CPU消耗  < 1000ms

請嚴格按要求輸出,不要畫蛇添足地列印類似:“請您輸入…” 的多餘內容。

所有程式碼放在同一個原始檔中,除錯通過後,拷貝提交該原始碼。

注意: main函式需要返回0
注意: 只使用ANSI C/ANSI C 標準,不要呼叫依賴於編譯環境或作業系統的特殊函式。
注意: 所有依賴的函式必須明確地在原始檔中 #include <xxx>, 不能通過工程設定而省略常用標頭檔案。

提交時,注意選擇所期望的編譯器型別。

程式設計思想:計算幾何(求房子間的曼哈頓距離)

code:

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int w,m,n,r1,c1,r2,c2,ans;
while(scanf("%d%d%d",&w,&m,&n)!=EOF)
{
r1=m/w;
c1=m%w;
if(c1!=0)
{
r1  ;
if(r1%2==0)
{
c1=w-c1 1;
}
}
r2=n/w;
c2=n%w;
if(c2!=0)
{
r2  ;
if(r2%2==0)
{
c2=w-c2 1;
}
}
ans=abs(r2-r1) abs(c2-c1);
printf("%d\n",ans);
}
return 0;
}

9、壘骰子

賭聖atm晚年迷戀上了壘骰子,就是把骰子一個壘在另一個上邊,不能歪歪扭扭,要壘成方柱體。
經過長期觀察,atm 發現了穩定骰子的奧祕:有些數字的面貼著會互相排斥!
我們先來規範一下骰子:1 的對面是 4,2 的對面是 5,3 的對面是 6。
假設有 m 組互斥現象,每組中的那兩個數字的面緊貼在一起,骰子就不能穩定的壘起來。 
atm想計算一下有多少種不同的可能的壘骰子方式。
兩種壘骰子方式相同,當且僅當這兩種方式中對應高度的骰子的對應數字的朝向都相同。
由於方案數可能過多,請輸出模 10^9 7 的結果。

不要小看了 atm 的骰子數量哦~

「輸入格式」
第一行兩個整數 n m
n表示骰子數目
接下來 m 行,每行兩個整數 a b ,表示 a 和 b 數字不能緊貼在一起。

「輸出格式」
一行一個數,表示答案模 10^9 7 的結果。

「樣例輸入」
2 1
1 2

「樣例輸出」
544

「資料範圍」
對於 30% 的資料:n <= 5
對於 60% 的資料:n <= 100
對於 100% 的資料:0 < n <= 10^9, m <= 36

資源約定:
峰值記憶體消耗 < 256M
CPU消耗  < 2000ms

請嚴格按要求輸出,不要畫蛇添足地列印類似:“請您輸入…” 的多餘內容。

所有程式碼放在同一個原始檔中,除錯通過後,拷貝提交該原始碼。

注意: main函式需要返回0
注意: 只使用ANSI C/ANSI C 標準,不要呼叫依賴於編譯環境或作業系統的特殊函式。

程式設計思想:矩陣快速冪。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define LL long long
#define MAXN 1000010
using namespace std;
const int INF=0x3f3f3f3f;
//----以下為矩陣快速冪模板-----// 
//const int mod=3;//模3,故這裡改為3即可 
int mod;
const int NUM=12;//定義矩陣能表示的最大維數 
int N;//N表示矩陣的維數,以下的矩陣加法、乘法、快速冪都是按N維矩陣運算的 
struct Mat{//矩陣的類
LL a[NUM][NUM];
void init()//將其初始化為單位矩陣  
{
memset(a,0,sizeof(a));
for(int i=0;i<NUM;i  )
{
a[i][i]=1;
}
}
};
Mat add(Mat a,Mat b)//(a b)%mod  矩陣加法  
{
Mat ans;
for(int i=0;i<N;i  )
{
for(int j=0;j<N;j  )
{
ans.a[i][j]=(a.a[i][j]%mod) (b.a[i][j]%mod);
ans.a[i][j]%=mod;
}
}
return ans;
}
Mat mul(Mat a,Mat b) //(a*b)%mod  矩陣乘法  
{
Mat ans;
for(int i=0;i<N;i  )
{
for(int j=0;j<N;j  )
{
ans.a[i][j]=0;
for(int k=0;k<N;k  )
{
ans.a[i][j]=(ans.a[i][j]%mod) (a.a[i][k]%mod)*(b.a[k][j]%mod);
}
ans.a[i][j]%=mod;
}
}
return ans;
}
Mat power(Mat a,int num)//(a^n)%mod  矩陣快速冪 
{
Mat ans;
ans.init();
while(num)
{
if(num&1)
{
ans=mul(ans,a);
}
num>>=1;
a=mul(a,a);
}
return ans;
}
Mat pow_sum(Mat a,int num)//(a a^2 a^3.... a^n)%mod 矩陣的冪和
{
int m;
Mat ans,pre;
if(num==1)
return a;
m=num/2;
pre=pow_sum(a,m);
ans=add(pre,mul(pre,power(a,m)));
if(num&1)
ans=add(ans,power(a,num));
return ans;
}
void output(Mat a)//輸出矩陣 
{
for(int i=0;i<N;i  )
{
for(int j=0;j<N;j  )
{
printf("%lld%c",a.a[i][j],j==N-1?'\n':' ');
}
}
}
//----以上為矩陣快速冪模板-----// 
int v[6][6];
int main()
{
Mat A,B;
int i,j,k,n,m,x,y,sum;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<6;i  )
{
for(j=0;j<6;j  )
{
v[i][j]=1;	
}	
}
for(i=1;i<=m;i  )	
{
scanf("%d%d",&x,&y);
v[x-1][(y 2)%6]=0;
v[y-1][(x 2)%6]=0;
}
N=6;
mod=1e9 7;
for(i=0;i<6;i  )
{
for(j=0;j<6;j  )
{
A.a[i][j]=v[i][j]*4;
}
}
for(i=0;i<6;i  )
B.a[i][0]=4;
A=power(A,n-1);
Mat ans;
for(i=0;i<N;i  )
{
for(j=0;j<1;j  )
{
ans.a[i][j]=0;
for(k=0;k<N;k  )
{
ans.a[i][j]=(ans.a[i][j]%mod) (A.a[i][k]%mod)*(B.a[k][j]%mod);
}
ans.a[i][j]%=mod;
}
}
sum=0;
for(i=0;i<N;i  )
{
sum=(sum ans.a[i][0])%mod;
}
printf("%d\n",sum);
}
return 0;
}

10、生命之樹

在X森林裡,上帝建立了生命之樹。

他給每棵樹的每個節點(葉子也稱為一個節點)上,都標了一個整數,代表這個點的和諧值。
上帝要在這棵樹內選出一個非空節點集S,使得對於S中的任意兩個點a,b,都存在一個點列 {a, v1, v2, …, vk, b} 使得這個點列中的每個點都是S裡面的元素,且序列中相鄰兩個點間有一條邊相連。

在這個前提下,上帝要使得S中的點所對應的整數的和儘量大。
這個最大的和就是上帝給生命之樹的評分。

經過atm的努力,他已經知道了上帝給每棵樹上每個節點上的整數。但是由於 atm 不擅長計算,他不知道怎樣有效的求評分。他需要你為他寫一個程式來計算一棵樹的分數。

「輸入格式」
第一行一個整數 n 表示這棵樹有 n 個節點。
第二行 n 個整數,依次表示每個節點的評分。
接下來 n-1 行,每行 2 個整數 u, v,表示存在一條 u 到 v 的邊。由於這是一棵樹,所以是不存在環的。

「輸出格式」
輸出一行一個數,表示上帝給這棵樹的分數。

「樣例輸入」
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

「樣例輸出」
8

「資料範圍」
對於 30% 的資料,n <= 10
對於 100% 的資料,0 < n <= 10^5, 每個節點的評分的絕對值不超過 10^6 。

資源約定:
峰值記憶體消耗 < 256M
CPU消耗  < 3000ms

請嚴格按要求輸出,不要畫蛇添足地列印類似:“請您輸入…” 的多餘內容。

所有程式碼放在同一個原始檔中,除錯通過後,拷貝提交該原始碼。

注意: main函式需要返回0
注意: 只使用ANSI C/ANSI C 標準,不要呼叫依賴於編譯環境或作業系統的特殊函式。
注意: 所有依賴的函式必須明確地在原始檔中 #include <xxx>, 不能通過工程設定而省略常用標頭檔案。

提交時,注意選擇所期望的編譯器型別。
注意: 所有依賴的函式必須明確地在原始檔中 #include <xxx>, 不能通過工程設定而省略常用標頭檔案。

提交時,注意選擇所期望的編譯器型別。

程式設計思想:樹形DP。

code:

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
#define LL long long
#define MAXN 1000010
#define INF 0x3f3f3f3f
using namespace std;
struct node{
int from;
int to;
int w;
int next;
}Edge[MAXN];
int n,m,tot;
int head[MAXN],dp[MAXN][2],w[MAXN];
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
void add(int from,int to,int w)
{
Edge[tot].from=from;
Edge[tot].to=to;
Edge[tot].w=w;
Edge[tot].next=head[from];
head[from]=tot  ;
}
void dfs(int p,int fa)
{
for(int i=head[p];i!=-1;i=Edge[i].next)
{
int v=Edge[i].to;
if(v==fa)
continue;
dfs(v,p);
dp[p][0]=max(dp[v][0],dp[v][1]);
dp[p][1]=max(dp[v][1] dp[p][1],dp[p][1]);
}
}
int main()
{
int i,j,u,v,ans;
while(scanf("%d",&n)!=EOF)
{
memset(dp,-INF,sizeof(dp));
for(i=1;i<=n;i  )
{
scanf("%d",&w[i]);
dp[i][1]=w[i];
}
init();
for(i=1;i<=n-1;i  )
{
scanf("%d%d",&u,&v);
add(u,v,0);
add(v,u,0);
}
dfs(1,-1);
ans=max(dp[1][0],dp[1][1]);
printf("%d\n",ans);
}
return 0;
}