2015年第六届蓝桥杯C/C++程序设计本科B组决赛
1.積分之謎(枚舉)
2.完美正方形
3.關聯賬戶(并查集)
4.密文搜索
5.居民集會
6.模型染色
?
1.積分之迷
小明開了個網上商店,賣風鈴。共有3個品牌:A,B,C。
為了促銷,每件商品都會返固定的積分。
小明開業第一天收到了三筆訂單:
第一筆:3個A + 7個B + 1個C,共返積分:315
第二筆:4個A + 10個B + 1個C,共返積分:420
第三筆:A + B + C,共返積分....
你能算出第三筆訂單需要返積分多少嗎?
答案:105
#include<iostream> #include<stdio.h> using namespace std;int main(){int A,B,C;int sum1,sum2;int sum3;for(A=0;A<500;++A){for(B=0;B<500;++B){for(C=0;C<500;++C){sum1=3*A+7*B+C;sum2=4*A+10*B+C;if(sum1==315&&sum2==420){sum3=A+B+C;printf("%d\n",sum3);//return 0; }}}}return 0; } View Code?
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,
你能計算出緊貼著下邊沿的是哪幾個正方形嗎?
請提交緊貼著下邊沿的正方形的邊長,從左到右,用空格分開。
答案:50 33 30 41
?
3.關聯賬戶
為增大反腐力度,某地警方專門支隊,對若干銀行賬戶展開調查。
如果兩個賬戶間發生過轉賬,則認為有關聯。如果a,b間有關聯, b,c間有關聯,則認為a,c間也有關聯。
對于調查范圍內的n個賬戶(編號0到n-1),警方已知道m條因轉賬引起的直接關聯。
現在希望知道任意給定的兩個賬戶,求出它們間是否有關聯。有關聯的輸出1,沒有關聯輸出0
小明給出了如下的解決方案:
答案:if(m[i]==qID)m[i]=pID;
s.并查集
#include <stdio.h> #define N 100int 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++)if(m[i]==qID)m[i]=pID;//____________;//填空位置 }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; } View Code?
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 <xxx>, 不能通過工程設置而省略常用頭文件。
提交時,注意選擇所期望的編譯器類型。
?
s.因為要求每行密碼的所有排列在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;char str[1024*1024+10],s[10]; int a[1024*1024+10][26],b[26];int main() {int n;int len,len2;int sum;int i,j,k;memset(a,0,sizeof(a));scanf("%s", str);len=strlen(str);len-=8;for(i=0; i<=len; i++)for(j=i; j<=i+7; j++)a[i][str[j]-'a']+=1;scanf("%d",&n);sum=0;for(k=0; k<n; k++){int flag;memset(b,0,sizeof(b));scanf("%s",s);len2=strlen(s);for(i=0; i<len2; i++)b[s[i]-'a']+=1;for(i=0; i<=len; i++){flag=1;for(int j=0; j<26; j++){if(a[i][j]!=b[j]){flag=0;break;}}if(flag==1)sum++;}}printf("%d\n",sum);return 0; } View Code?
?
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 <xxx>, 不能通過工程設置而省略常用頭文件。
提交時,注意選擇所期望的編譯器類型。
?
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 <xxx>, 不能通過工程設置而省略常用頭文件。
提交時,注意選擇所期望的編譯器類型。
?
轉載于:https://www.cnblogs.com/bofengyu/p/5518677.html
總結
以上是生活随笔為你收集整理的2015年第六届蓝桥杯C/C++程序设计本科B组决赛的全部內容,希望文章能夠幫你解決所遇到的問題。
                            
                        - 上一篇: 梦到老人晕倒是什么意思
 - 下一篇: 做梦梦到怀孕又流产预示着什么