2018-4-14

感覺藍(lán)橋杯的風(fēng)格變了，以前都是暴力搜索類的題目比較多，然而這次并不是…

1.第幾天
2000年的1月1日，是那一年的第1天。
那么，2000年的5月4日，是那一年的第幾天？
注意：需要提交的是一個整數(shù)，不要填寫任何多余內(nèi)容。

這個題目還是比較好寫的：
1.手動計算
2.用excel將兩個日期相減即可。

2.明碼
漢字的字形存在于字庫中，即便在今天，16點陣的字庫也仍然使用廣泛。
16點陣的字庫把每個漢字看成是16x16個像素信息。并把這些信息記錄在字節(jié)中。
一個字節(jié)可以存儲8位信息，用32個字節(jié)就可以存一個漢字的字形了。
把每個字節(jié)轉(zhuǎn)為2進(jìn)制表示，1表示墨跡，0表示底色。每行2個字節(jié)，
一共16行，布局是：
第1字節(jié)，第2字節(jié)
第3字節(jié)，第4字節(jié)
….
第31字節(jié), 第32字節(jié)
這道題目是給你一段多個漢字組成的信息，每個漢字用32個字節(jié)表示，這里給出了字節(jié)作為有符號整數(shù)的值。
題目的要求隱藏在這些信息中。你的任務(wù)是復(fù)原這些漢字的字形，從中看出題目的要求，并根據(jù)要求填寫答案。
這段信息是（一共10個漢字）：
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0
16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0
0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4
4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64
16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128
0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0
2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0
1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0
0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0
注意：需要提交的是一個整數(shù)，不要填寫任何多余內(nèi)容。

主要的思想還是數(shù)的二進(jìn)制表示，每一個二進(jìn)制位直接和1相 ’ & ’ 即可。

#include<iostream> using namespace std;void cal(int p){int i;for (i=7;i>=0;i--){if (p&(1<<i)) cout<<'.';else cout<<' ';} }int main(){for (int i=0;i<10;i++){for (int j=0;j<16;j++){int a,b;cin>>a>>b;cal(a);cal(b);cout<<endl;}}long long int res=1;for (int i=0;i<9;i++){res*=9;}cout<<res<<endl;return 0; }

顯示的為 ” 九的九次方等于多少？” ，我們寫個for循環(huán)就可以計算出來了！

結(jié)果為：387420489

3.如下的10行數(shù)據(jù)，每行有10個整數(shù)，請你求出它們的乘積的末尾有多少個零？
5650 4542 3554 473 946 4114 3871 9073 90 4329
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899
1486 5722 3135 1170 4014 5510 5120 729 2880 9019
2049 698 4582 4346 4427 646 9742 7340 1230 7683
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649
6701 6645 1671 5978 2704 9926 295 3125 3878 6785
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074
689 5510 8243 6114 337 4096 8199 7313 3685 211
注意：需要提交的是一個整數(shù)，表示末尾零的個數(shù)。不要填寫任何多余內(nèi)容。

末尾為零只能由2*5來得到，雖然說4*5也可以得到0，但是歸根結(jié)底還是2的作用，我們只要計算出所有數(shù)因子為2和因子為5的最小值即可。

#include<iostream> using namespace std;int main(){int cnt1=0,cnt2=0,n;for (int i=0;i<100;i++){cin>>n;int p=n,q=n;while (p%2==0){cnt1++;p/=2;}while (q%5==0){cnt2++;q/=5;}}cout<<min(cnt1,cnt2)<<endl;return 0; }

結(jié)果為：31

4.測試次數(shù)
x星球的居民脾氣不太好，但好在他們生氣的時候唯一的異常舉動是：摔手機(jī)。
各大廠商也就紛紛推出各種耐摔型手機(jī)。x星球的質(zhì)監(jiān)局規(guī)定了手機(jī)必須經(jīng)過耐摔測試，并且評定出一個耐摔指數(shù)來，之后才允許上市流通。
x星球有很多高聳入云的高塔，剛好可以用來做耐摔測試。塔的每一層高度都是一樣的，與地球上稍有不同的是，他們的第一層不是地面，而是相當(dāng)于我們的2樓。
如果手機(jī)從第7層扔下去沒摔壞，但第8層摔壞了，則手機(jī)耐摔指數(shù)=7。
特別地，如果手機(jī)從第1層扔下去就壞了，則耐摔指數(shù)=0。
如果到了塔的最高層第n層扔沒摔壞，則耐摔指數(shù)=n

為了減少測試次數(shù)，從每個廠家抽樣3部手機(jī)參加測試。
某次測試的塔高為1000層，如果我們總是采用最佳策略，在最壞的運(yùn)氣下最多需要測試多少次才能確定手機(jī)的耐摔指數(shù)呢？
請?zhí)顚戇@個最多測試次數(shù)。
注意：需要填寫的是一個整數(shù)，不要填寫任何多余內(nèi)容。

答案是：19

現(xiàn)在還是不是很懂這個答案，當(dāng)時比賽的時候?qū)懙?0，用二分法的思想，每部手機(jī)只需要10次即可，總共需要30次，但是這是錯誤的…

5.快速排序。
以下代碼可以從數(shù)組a[]中找出第k小的元素。
它使用了類似快速排序中的分治算法，期望時間復(fù)雜度是O(N)的。
請仔細(xì)閱讀分析源碼，填寫劃線部分缺失的內(nèi)容。

#include <stdio.h> #include <time.h> #include <stdlib.h> int quick_select(int a[], int l, int r, int k) { int p = rand() % (r - l + 1) + l; int x = a[p]; {int t = a[p]; a[p] = a[r]; a[r] = t;} int i = l, j = r; while(i < j) { while(i < j && a[i] < x) i++; if(i < j) { a[j] = a[i]; j--; } while(i < j && a[j] > x) j--; if(i < j) { a[i] = a[j]; i++; } } a[i] = x; p = i; if(i - l + 1 == k) return a[i]; if(i - l + 1 < k) return quick_select(a,i+1,r,k-i+l-1); //填空 else return quick_select(a, l, i - 1, k); } int main() { int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12}; printf("%d\n", quick_select(a, 0, 14, 14)); return 0; }

當(dāng)時比賽寫的應(yīng)該是a,i+1,r,k-i+1，但是我在把k的初始值改為14的時候怎么也計算不出來，當(dāng)時沒有考慮太多，直接就提交上去了，后來想明白了！這里的k表示的是當(dāng)前l(fā)~r區(qū)間的第k小的數(shù)，如果說在右邊的區(qū)間的話，我們應(yīng)該用k減去左邊區(qū)間的長度，也就是k-(i-l)-1即可。

6.遞增三元組
給定三個整數(shù)數(shù)組
A = [A1, A2, … AN],
B = [B1, B2, … BN],
C = [C1, C2, … CN]，
請你統(tǒng)計有多少個三元組(i, j, k) 滿足：
1. 1 <= i, j, k <= N
2. Ai < Bj < Ck
【輸入格式】
第一行包含一個整數(shù)N。
第二行包含N個整數(shù)A1, A2, … AN。
第三行包含N個整數(shù)B1, B2, … BN。
第四行包含N個整數(shù)C1, C2, … CN。

對于30%的數(shù)據(jù)，1 <= N <= 100
對于60%的數(shù)據(jù)，1 <= N <= 1000
對于100%的數(shù)據(jù)，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

【輸出格式】
一個整數(shù)表示答案
【樣例輸入】
3
1 1 1
2 2 2
3 3 3
【樣例輸出】
27
資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 1000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內(nèi)容。
注意：
main函數(shù)需要返回0;
只使用ANSI C/ANSI C++ 標(biāo)準(zhǔn);
不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
所有依賴的函數(shù)必須明確地在源文件中 #include
不能通過工程設(shè)置而省略常用頭文件。
提交程序時，注意選擇所期望的語言類型和編譯器類型。

最容易想到的解法應(yīng)該是暴力吧，直接三個for循環(huán)即可，但是給我們的數(shù)據(jù)最大可以到100000，顯然這是會超時的！

我當(dāng)時寫的是先對三個數(shù)組進(jìn)行排序，然后在找c的時候就可以直接加上后續(xù)所有的了（因為后面的一定比當(dāng)前的值要大）

#include<iostream> #include<algorithm> using namespace std;const int N = 100000; int a[N+1],b[N+1],c[N+1]; int n;int main(){cin>>n;for (int i=0;i<n;i++){cin>>a[i];}for (int i=0;i<n;i++){cin>>b[i];}for (int i=0;i<n;i++){cin>>c[i];}sort(a,a+n);sort(b,b+n);sort(c,c+n);int cnt=0;for (int i=0;i<n;i++){for (int j=0;j<n;j++){if (a[i]>=b[j]) continue;for (int k=0;k<n;k++){if (b[j]<c[k]){cnt+=n-k;break;}}} }cout<<cnt<<endl;return 0; }

我們還可以這么寫：三個數(shù)組排序，暴力b[]中的每一個數(shù)字，然后二分a[]有多少個比它小的，c[]有多少個比它大的，相乘加在一起就是答案，我覺得這個大概應(yīng)該就是標(biāo)準(zhǔn)答案了吧。

7.螺旋折線

如圖p1.png所示的螺旋折線經(jīng)過平面上所有整點恰好一次。

對于整點(X, Y)，我們定義它到原點的距離dis(X, Y)是從原點到(X, Y)的螺旋折線段的長度。

例如dis(0, 1)=3, dis(-2, -1)=9
給出整點坐標(biāo)(X, Y)，你能計算出dis(X, Y)嗎？
【輸入格式】
X和Y

對于40%的數(shù)據(jù)，-1000 <= X, Y <= 1000
對于70%的數(shù)據(jù)，-100000 <= X， Y <= 100000
對于100%的數(shù)據(jù), -1000000000 <= X, Y <= 1000000000
【輸出格式】
輸出dis(X, Y)
【樣例輸入】
0 1
【樣例輸出】
3

我當(dāng)時是用的switch語句寫的，最后結(jié)果也出來了，但是可能不是最優(yōu)解！

8.日志統(tǒng)計
小明維護(hù)著一個程序員論壇。現(xiàn)在他收集了一份”點贊”日志，日志共有N行。其中每一行的格式是：
ts id
表示在ts時刻編號id的帖子收到一個”贊”。
現(xiàn)在小明想統(tǒng)計有哪些帖子曾經(jīng)是”熱帖”。如果一個帖子曾在任意一個長度為D的時間段內(nèi)收到不少于K個贊，小明就認(rèn)為這個帖子曾是”熱帖”。
具體來說，如果存在某個時刻T滿足該帖在[T, T+D)這段時間內(nèi)(注意是左閉右開區(qū)間)收到不少于K個贊，該帖就曾是”熱帖”。
給定日志，請你幫助小明統(tǒng)計出所有曾是”熱帖”的帖子編號。
【輸入格式】
第一行包含三個整數(shù)N、D和K。
以下N行每行一條日志，包含兩個整數(shù)ts和id。
對于50%的數(shù)據(jù)，1 <= K <= N <= 1000
對于100%的數(shù)據(jù)，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
【輸出格式】
按從小到大的順序輸出熱帖id。每個id一行。
【輸入樣例】
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
【輸出樣例】
1
3

9.全球變暖
你有一張某海域NxN像素的照片，”.”表示海洋、”#”表示陸地，如下所示：
…….
.##….
.##….
….##.
..####.
…###.
…….
其中”上下左右”四個方向上連在一起的一片陸地組成一座島嶼。例如上圖就有2座島嶼。
由于全球變暖導(dǎo)致了海面上升，科學(xué)家預(yù)測未來幾十年，島嶼邊緣一個像素的范圍會被海水淹沒。具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)，它就會被淹沒。
例如上圖中的海域未來會變成如下樣子：
…….
…….
…….
…….
….#..
…….
…….
請你計算：依照科學(xué)家的預(yù)測，照片中有多少島嶼會被完全淹沒。
【輸入格式】
第一行包含一個整數(shù)N。 (1 <= N <= 1000)
以下N行N列代表一張海域照片。
照片保證第1行、第1列、第N行、第N列的像素都是海洋。
【輸出格式】
一個整數(shù)表示答案。
【輸入樣例】
7
…….
.##….
.##….
….##.
..####.
…###.
…….
【輸出樣例】
1

10.乘積最大
給定N個整數(shù)A1, A2, … AN。請你從中選出K個數(shù)，使其乘積最大。
請你求出最大的乘積，由于乘積可能超出整型范圍，你只需輸出乘積除以1000000009的余數(shù)。
注意，如果X<0， 我們定義X除以1000000009的余數(shù)是負(fù)(-X)除以1000000009的余數(shù)。
即：0-((0-x) % 1000000009)
【輸入格式】
第一行包含兩個整數(shù)N和K。
以下N行每行一個整數(shù)Ai。

對于40%的數(shù)據(jù)，1 <= K <= N <= 100
對于60%的數(shù)據(jù)，1 <= K <= 1000
對于100%的數(shù)據(jù)，1 <= K <= N <= 100000 -100000 <= Ai <= 100000
【輸出格式】
一個整數(shù)，表示答案。
【輸入樣例】
5 3
-100000
-10000
2
100000
10000
【輸出樣例】
999100009
再例如：
【輸入樣例】
5 3
-100000
-100000
-2
-100000
-100000
【輸出樣例】
-999999829

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的2018年第九届蓝桥杯—C/C++程序设计省赛解题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。