藍橋杯2015年第六屆決賽C_C 程式設計本科B組

藍橋杯2015年第六屆決賽C_C  程式設計本科B組

1. 積分之迷

小明開了個網上商店,賣風鈴。共有3個品牌:A,B,C。 為了促銷,每件商品都會返固定的積分。 小明開業第一天收到了三筆訂單: 第一筆:3個A
7個B 1個C,共返積分:315 第二筆:4個A 10個B 1個C,共返積分:420 第三筆:A B C,共返積分…. 你能算出第三筆訂單需要返積分多少嗎?


2. 完美正方形

如果一些邊長互不相同的正方形,可以恰好拼出一個更大的正方形,則稱其為完美正方形。
歷史上,人們花了很久才找到了若干完美正方形。比如:如下邊長的22個正方形
2 3 4 6 7 8 12 13 14 15 16 17 18 21 22 23 24 26 27 28 50 60
如【圖1.png】那樣組合,就是一種解法。此時,
緊貼上邊沿的是:60 50
緊貼下邊沿的是:26 28 17 21 18
22階完美正方形一共有8種。下面的組合是另一種:
2 5 9 11 16 17 19 21 22 24 26 30 31 33 35 36 41 46 47 50 52 61
如果告訴你該方案緊貼著上邊沿的是從左到右依次為:47 46 61,
你能計算出緊貼著下邊沿的是哪幾個正方形嗎?
請提交緊貼著下邊沿的正方形的邊長,從左到右,用空格分開。

這裡寫圖片描述

我們先建立一個二維陣列代表這個正方形,陣列中每個單元填寫所屬於的小正方形的邊長,由於一開始已經知道了上邊沿的三個正方形的位置,因此我們可以先把上邊沿的三個正方形對應陣列單元中的數字都填寫進去,通過一個set函式來實現填充功能,然後就可以開始搜尋了,我搜尋的方式是按照行來進行的,通過函式find實現,從第一行開始搜尋,如果搜到當前行有空缺的位置,則記下空缺的長度,在未選擇的正方形中依次選擇一個可以放進去的正方形執行set函式,完成後進行深一層的遞迴,重新掃描當前行繼續填充,如果發現已經填滿,則列印結果,如果未填滿而且沒有可以放進去的正方形,則回溯到上一層重新搜尋。

#include<iostream>
#include<stdio.h>
using namespace std;
int number[22]={2,5,9,11,16,17,19,21,22,24,26,30,31,33,35,36,41,46,47,50,52,61};
int choose[22]={0};//記錄當前的22個正方形是否已經使用
int ju[154][154]={0};//代表大正方形
int wcx=0,wcy=0,wclen=0;//代表查詢出的最近的空缺位置的起始點和結束點
void set(int x,int y,int len,int t){
int i,j;
for(i=x;i<x len;i  ){
for(j=y;j<y len;j  ){
ju[i][j]=t;
}
}
}
void find(int x){//搜尋空缺位置
int i,j,t=0;
wclen=0;
for(i=x;i<154;i  ){
for(j=0;j<154;j  ){
if(t==0&&ju[i][j]==0){
wcx=i;
wcy=j;
t=1;
}
if(t==1&&ju[i][j]){
return;
}
if(t) wclen  ;
}
}
}
void f(int n,int cx,int cy,int clen){//遞迴的方式記錄每一層的空缺位置的起始點和結束點以及長度
int i;
if(n==22){//全部放進去後表明填充成功
for(i=0;i<154;i  ) cout<<ju[153][i]<<" ";
cout<<endl<<endl;
//50 33 30 41
return;
}
for(i=21;i>=0;i--){//一個一個放進去進行嘗試
if(choose[i]==0&&clen>=number[i]){
choose[i]=1;
set(cx,cy,number[i],number[i]);
find(cx);
f(n 1,wcx,wcy,wclen);
set(cx,cy,number[i],0);//取消填充
choose[i]=0;
}
}
}
int main(){
//47 46 61
int i;
set(0,0,47,47);
set(0,47,46,46);
set(0,93,61,61);
choose[17]=choose[18]=choose[21]=1;
f(3,46,47,46);
//for(i=0;i<154;i  ) cout<<ju[46][i]<<" ";
return 0;
}

dfs

int N,vis[60];  
int d[]={2,5,9,11,16,17,19,21,22,24,26,30,31,33,35,36,41,50,52,46,47,61};  
int G[155][155];  
bool inside(int x,int y,int n)  
{  
if(!(x n<=155&&y n<=155)) return false;  
for(int i=x;i<n x;i  )  
for(int j=y;j<n y;j  )  
if(G[i][j]) return false;  
return true;  
}  
void Fill(int x,int y,int n,int m)  
{  
for(int i=x;i<x n;i  )  
for(int j=y;j<y n;j  )  
G[i][j]=m;  
}  
void Get(int& x,int& y)  
{  
for(int i=1;i<=154;i  )  
for(int j=1;j<=154;j  )  
if(!G[i][j]) {  
x=i;  
y=j;  
return ;  
}  
}  
bool solved()  
{  
for(int i=1;i<=154;i  )  
for(int j=1;j<=154;j  )  
if(!G[i][j]) return false;  
return true;  
}  
bool dfs(int x,int y)  
{  
if(solved()) {  
return true;  
}  
else   
{  
Get(x,y);  
for(int k=0;k<19;k  )  
{  
if(inside(x,y,d[k]))  
{  
if(!vis[k])  
{  
Fill(x,y,d[k],d[k]);  
vis[k]=1;  
if(dfs(x,y d[k])) return true;  
Fill(x,y,d[k],0);  
vis[k]=0;  
}  
}  
else break;  
}  
}  
return false;  
}  
int main()  
{  
int a[30];  
memset(vis,0,sizeof(vis));  
memset(G,0,sizeof(G));  
Fill(1,1,47,47);  
Fill(1,48,46,46);  
Fill(1,94,61,61);  
sort(d,d 19);  
dfs(1,1);  
for(int i=1;i<=154;i  )  
cout<<G[154][i]<<' ';  
return 0;  
}   

3. 關聯賬戶

為增大反腐力度,某地警方專門支隊,對若干銀行賬戶展開調查。 如果兩個賬戶間發生過轉賬,則認為有關聯。如果a,b間有關聯,
b,c間有關聯,則認為a,c間也有關聯。 對於調查範圍內的n個賬戶(編號0到n-1),警方已知道m條因轉賬引起的直接關聯。
現在希望知道任意給定的兩個賬戶,求出它們間是否有關聯。有關聯的輸出1,沒有關聯輸出0 小明給出瞭如下的解決方案:

#include <stdio.h>
#define N 100
int connected(int* m, int p, int q)
{
return m[p]==m[q]? 1 : 0;
}
void link(int* m, int p, int q)
{
int i;
if(connected(m,p,q)) return;
int pID = m[p];
int qID = m[q];
for(i=0; i<N; i  ) _____________________________________;  //填空位置
}
int main()
{
int m[N];
int i;
for(i=0; i<N; i  ) m[i] = i; //初始狀態,每個節點自成一個連通域
link(m,0,1); //新增兩個賬戶間的轉賬關聯
link(m,1,2); 
link(m,3,4); 
link(m,5,6); 
link(m,6,7); 
link(m,8,9); 
link(m,3,7); 
printf("%d ", connected(m,4,7));
printf("%d ", connected(m,4,5));
printf("%d ", connected(m,7,9));
printf("%d ", connected(m,9,2));
return 0;
}

分析:該題目主要思路是並查集,判斷無向圖任意兩個點是否連通。

answer: 
for(i=0; i<N; i  )  
m[i]= (m[i]==pID) ? qID : m[i];  
/* 
等價於: 
if(m[i]==pID) 
m[i]=qID;  
把一個連通圖的前驅全都改成另一個連通圖的前驅  
*/   

4.密文搜尋

福爾摩斯從X星收到一份資料,全部是小寫字母組成。
他的助手提供了另一份資料:許多長度為8的密碼列表。
福爾摩斯發現,這些密碼是被打亂後隱藏在先前那份資料中的。
請你編寫一個程式,從第一份資料中搜尋可能隱藏密碼的位置。要考慮密碼的所有排列可能性。
資料格式:
輸入第一行:一個字串s,全部由小寫字母組成,長度小於1024*1024
緊接著一行是一個整數n,表示以下有n行密碼,1<=n<=1000
緊接著是n行字串,都是小寫字母組成,長度都為8
要求輸出:
一個整數, 表示每行密碼的所有排列在s中匹配次數的總和。

例如:
使用者輸入:
aaaabbbbaabbcccc
2
aaaabbbb
abcabccc
則程式應該輸出:
4
這是因為:第一個密碼匹配了3次,第二個密碼匹配了1次,一共4次。
資源約定:
峰值記憶體消耗 < 512M
CPU消耗 < 3000ms
請嚴格按要求輸出,不要畫蛇添足地列印類似:“請您輸入…” 的多餘內容。
所有程式碼放在同一個原始檔中,除錯通過後,拷貝提交該原始碼。
注意: main函式需要返回0
注意: 只使用ANSI C/ANSI C 標準,不要呼叫依賴於編譯環境或作業系統的特殊函式。
注意: 所有依賴的函式必須明確地在原始檔中 #include , 不能通過工程設定而省略常用標頭檔案。
提交時,注意選擇所期望的編譯器型別。


思路:因為要求每行密碼的所有排列在s中匹配次數的總和,所以可以統計每行密碼中所包含的各個字母的個數,然後選取主串中的長度為8的區間,比較是否與密碼中包含的各個字母的個數相等。在選取主串中長度為8的區間時,實際上只有只有主串長度-7個長度為8的區間。

例如: 0 1 2 3 4 5 6 7 8 9 10 主串長度為11

則長度為8的區間只有0–7 1– 8 2–9 3–10這4個,即11-4個。

#include <iostream>  
#include <stdio.h>  
#include <cstring>  
using namespace std;  
int main()  
{  
int n;  
char str[1005],s[10];  
int  a[1005][26],b[26];  
memset(a,0,sizeof(a));  
scanf("%s", str);  
for(int i=0; i<=(strlen(str)-8); i  )  
for(int j=i; j<=i 7; j  )  
a[i][str[j]-'a'] =1;  
scanf("%d",&n);  
int sum=0;  
for(int k=0; k<n; k  )  
{  
int flag;  
memset(b,0,sizeof(b));  
scanf("%s", s);  
for(int i=0; i<strlen(s); i  )  
b[s[i]-'a'] =1;  
for(int i=0; i<=strlen(str)-8; i  )  
{  
flag=1;  
for(int j=0; j<26; j  )  
{  
if(a[i][j]!=b[j])  
{  
flag=0;  
break;  
}  
}  
if(flag==1)  
sum  ;  
}  
}  
cout<<sum<<endl;  
return 0;  
}  

5. 居民集會

藍橋村的居民都生活在一條公路的邊上,公路的長度為L,每戶家庭的位置都用這戶家庭到公路的起點的距離來計算,第i戶家庭距起點的距離為di。
每年,藍橋村都要舉行一次集會。今年,由於村裡的人口太多,村委會決定要在4個地方舉行集會,其中3個位於公路中間,1個位最公路的終點。
已知每戶家庭都會向著遠離公路起點的方向去參加集會,參加集會的路程開銷為家庭內的人數ti與距離的乘積。
給定每戶家庭的位置di和人數ti,請為村委會尋找最好的集會舉辦地:p1, p2, p3, p4 (p1<=p2<=p3<=p4=L),使得村內所有人的路程開銷和最小。
【輸入格式】
輸入的第一行包含兩個整數n, L,分別表示藍橋村的家庭數和公路長度。
接下來n行,每行兩個整數di, ti,分別表示第i戶家庭距離公路起點的距離和家庭中的人數。
【輸出格式】
輸出一行,包含一個整數,表示村內所有人路程的開銷和。
【樣例輸入】
6 10
1 3
2 2
4 5
5 20
6 5
8 7
【樣例輸出】
18
【樣例說明】
在距起點2, 5, 8, 10這4個地方集會,6個家庭需要的走的距離分別為1, 0, 1, 0, 2, 0,總的路程開銷為1*3 0*2 1*5 0*20 2*5 0*7=18。
【資料規模與約定】
對於10%的評測資料,1<=n<=300。
對於30%的評測資料,1<=n<=2000,1<=L<=10000,0<=di<=L,di<=di 1,0<=ti<=20。
對於100%的評測資料,1<=n<=100000,1<=L<=1000000,0<=di<=L,di<=di 1,0<=ti<=1000000。
資源約定:
峰值記憶體消耗 < 512M
CPU消耗 < 5000ms
請嚴格按要求輸出,不要畫蛇添足地列印類似:“請您輸入…” 的多餘內容。
所有程式碼放在同一個原始檔中,除錯通過後,拷貝提交該原始碼。
注意: main函式需要返回0
注意: 只使用ANSI C/ANSI C 標準,不要呼叫依賴於編譯環境或作業系統的特殊函式。
注意: 所有依賴的函式必須明確地在原始檔中 #include , 不能通過工程設定而省略常用標頭檔案。
提交時,注意選擇所期望的編譯器型別。

const int maxn=10000 5;   
int d[maxn],t[maxn],n,L;  
int w[maxn][maxn];  
int solve(int x,int y,int cur)  //[x,y] 還能分cur次   
{  
if(!cur) return w[x][y];  
int ML,MR,M;  
M=2*w[0][L];  
for(int m=x 1;m<y;m  )  
{  
ML=solve(x,m,cur-1);  //分為兩個區間   
MR=solve(m,y,cur-1);  
M=min(M,ML MR);  
}  
return M;  
}  
int main()  
{  
scanf("%d%d",&n,&L);  
for(int i=0;i<n;i  )  
scanf("%d%d",&d[i],&t[i]);  
for(int i=0;i<=L;i  )  //[i,j] w[i][j]為區間i~j所需的開銷   
for(int j=i;j<=L;j  )  
{  
for(int k=0;k<n;k  )  
{  
if(d[k]>i&&d[k]<j)  
{  
w[i][j] =(j-d[k])*t[k];  
}  
}  
}  
cout<<solve(0,L,2);  
return 0;  
}  

6.模型染色

在電影《超能陸戰隊》中,小巨集可以使用他的微型機器人組合成各種各樣的形狀。
現在他用他的微型機器人拼成了一個大玩具給小朋友們玩。為了更加美觀,他決定給玩具染色。
小巨集的玩具由n個球型的端點和m段連線這些端點之間的邊組成。下圖給出了一個由5個球型端點和4條邊組成的玩具,看上去很像一個分子的球棍模型。
由於小巨集的微型機器人很靈活,這些球型端點可以在空間中任意移動,同時連線相鄰兩個球型端點的邊可以任意的伸縮,這樣一個玩具可以變換出不同的形狀。在變換的過程中,邊不會增加,也不會減少。
小巨集想給他的玩具染上不超過k種顏色,這樣玩具看上去會不一樣。如果通過變換可以使得玩具變成完全相同的顏色模式,則認為是本質相同的染色。現在小巨集想知道,可能有多少種本質不同的染色。
【輸入格式】 輸入的第一行包含三個整數n, m, k, 分別表示小巨集的玩具上的端點數、邊數和小巨集可能使用的顏色數。端點從1到n編號。
接下來m行每行兩個整數a, b,表示第a個端點和第b個端點之間有一條邊。輸入保證不會出現兩條相同的邊。 【輸出格式】
輸出一行,表示本質不同的染色的方案數。由於方案數可能很多,請輸入方案數除10007的餘數。 【樣例輸入】 3 2 2 1 2 3 2
【樣例輸出】 6 【樣例說明】 令(a, b,
c)表示第一個端點染成a,第二個端點染成b,第三個端點染成c,則下面6種本質不同的染色:(1, 1, 1), (1, 1, 2), (1,
2, 1), (1, 2, 2), (2, 1, 2), (2, 2, 2)。 而(2, 1, 1)與(1, 1, 2)是本質相同的,(2,
2, 1)與(2, 1, 2)是本質相同的。 【資料規模與約定】 對於20%的評測資料,1<=n<=5, 1<=k<=2。
對於50%的評測資料,1<=n<=10, 1<=k<=8。 對於100%的評測資料,1<=n<=10, 1<=m<=45,
1<=k<=30。 資源約定: 峰值記憶體消耗 < 512M CPU消耗 < 5000ms
請嚴格按要求輸出,不要畫蛇添足地列印類似:“請您輸入…” 的多餘內容。 所有程式碼放在同一個原始檔中,除錯通過後,拷貝提交該原始碼。 注意:
main函式需要返回0 注意: 只使用ANSI C/ANSI C 標準,不要呼叫依賴於編譯環境或作業系統的特殊函式。 注意:
所有依賴的函式必須明確地在原始檔中 #include , 不能通過工程設定而省略常用標頭檔案。