第十三屆藍(lán)橋杯C++ B組省賽編程題詳解 第一題：刷題統(tǒng)計(jì) 題目描述

【Tag：枚舉】
小明決定從下周一開(kāi)始努力刷題準(zhǔn)備藍(lán)橋杯競(jìng)賽。

創(chuàng)新互聯(lián)公司-專(zhuān)業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比新密網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式新密網(wǎng)站制作公司更省心,省錢(qián),快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋新密地區(qū)。費(fèi)用合理售后完善，10年實(shí)體公司更值得信賴。

他計(jì)劃周一至周五每天做a道題目，周六和周日每天做b道題目。

請(qǐng)你幫小明計(jì)算，按照計(jì)劃他將在第幾天實(shí)現(xiàn)做題數(shù)大于等于n題？

輸入格式
輸入一行包含三個(gè)整數(shù) a,b 和 n。

輸出格式
輸出一個(gè)整數(shù)代表天數(shù)。

數(shù)據(jù)范圍
對(duì)于 50% 的評(píng)測(cè)用例， 1 ≤ a , b , n ≤ 1 0 6 {1≤a,b,n≤10^6} 1≤a,b,n≤106，
對(duì)于 100% 的評(píng)測(cè)用例， 1 ≤ a , b , n ≤ 1 0 18 {1≤a,b,n≤10^{18}} 1≤a,b,n≤1018。

輸入樣例：

10 20 99

輸出樣例：

8

思路分析

我們可以先統(tǒng)計(jì)出每周刷題數(shù)目s，然后求出有多少個(gè)整周的天數(shù)res。

接著求出我們還要做多少題目n,最后把余數(shù)加起來(lái)即可。

注意：數(shù)據(jù)范圍一定要考慮！！！

實(shí)現(xiàn)

#include#include#include 

using namespace std;

typedef long long LL;

LL a, b, n;

int main()
{
    scanf("%lld%lld%lld", &a, &b, & n);
    
    LL s = 5 * a + 2 * b; //每周的刷題數(shù)
    LL res = n / s * 7; //整周的天數(shù)
    n %= s; //剩余的題目數(shù)量
    
    LL d[] = {a, a, a, a, a, b, b};
    for (int i = 0; n >0; i ++)
    {
        n -= d[i];
        res ++;
    }
    
    printf("%lld\n", res);
    return 0;
}

第二題：修建灌木 題目描述

【Tag：模擬】
愛(ài)麗絲要完成一項(xiàng)修剪灌木的工作。有N棵灌木整齊的從左到右排成一排。

愛(ài)麗絲在每天傍晚會(huì)修剪一棵灌木，讓灌木的高度變?yōu)?code>0厘米。

愛(ài)麗絲修剪灌木的順序是從最左側(cè)的灌木開(kāi)始，每天向右修剪一棵灌木。

當(dāng)修剪了最右側(cè)的灌木后，她會(huì)調(diào)轉(zhuǎn)方向，下一天開(kāi)始向左修剪灌木。

直到修剪了最左的灌木后再次調(diào)轉(zhuǎn)方向。然后如此循環(huán)往復(fù)。

灌木每天從早上到傍晚會(huì)長(zhǎng)高1厘米，而其余時(shí)間不會(huì)長(zhǎng)高。

在第一天的早晨，所有灌木的高度都是0厘米。愛(ài)麗絲想知道每棵灌木最高長(zhǎng)到多高。

輸入格式
一個(gè)正整數(shù) N，含義如題面所述。

輸出格式
輸出 N 行，每行一個(gè)整數(shù)，第 i 行表示從左到右第 i 棵樹(shù)最高能長(zhǎng)到多高。

數(shù)據(jù)范圍
對(duì)于 30% 的數(shù)據(jù)，N≤10，
對(duì)于 100% 的數(shù)據(jù)，1

輸入樣例：

3

輸出樣例：

4
2
4

思路分析

我們可以簡(jiǎn)單的模擬出每棵樹(shù)的高度變化。

每棵樹(shù)的高度：

天數(shù)	第一棵樹(shù)	第二棵樹(shù)	第三棵樹(shù)	第四棵樹(shù)	第五棵樹(shù)
①	1	1	1	1	1
②	1	2	2	2	2
③	2	1	3	3	3
④	3	2	1	4	4
⑤	4	3	2	1	5
⑥	5	4	3	2	1
⑦	6	5	4	1	2
⑧	7	6	1	2	3
⑨	8	1	2	3	4
⑩	1	2	3	4	5
…	…	…	…	…	…

注意：加粗的數(shù)字為我們要修剪的樹(shù)木。

我們可以看出是一個(gè)循環(huán)的序列，總結(jié)出每個(gè)樹(shù)可以長(zhǎng)到的大高度為max(i - 1, n - i ) * 2

實(shí)現(xiàn)

#include#include#include 

using namespace std;
const int N = 10010;
int n, a[N];

int main()
{
    cin >>n;
    
    for (int i = 1; i<= n; i ++ )
    {
        cout<< max(i - 1, n - i) * 2<< endl;
    }
    
    return 0;
}

第三題： X 進(jìn)制減法 題目描述

【Tag：數(shù)學(xué)】
進(jìn)制規(guī)定了數(shù)字在數(shù)位上逢幾進(jìn)一。

X 進(jìn)制是一種很神奇的進(jìn)制，因?yàn)槠涿恳粩?shù)位的進(jìn)制并不固定！

例如說(shuō)某種 X 進(jìn)制數(shù)，最低數(shù)位為二進(jìn)制，第二數(shù)位為十進(jìn)制，第三數(shù)位為八進(jìn)制，則 X 進(jìn)制數(shù)321轉(zhuǎn)換為十進(jìn)制數(shù)為65。

現(xiàn)在有兩個(gè) X 進(jìn)制表示的整數(shù)A和B，但是其具體每一數(shù)位的進(jìn)制還不確定，只知道A和B是同一進(jìn)制規(guī)則，且每一數(shù)位最高為N進(jìn)制，最低為二進(jìn)制。

請(qǐng)你算出A?B的結(jié)果最小可能是多少。

請(qǐng)注意，你需要保證A和B在 X 進(jìn)制下都是合法的，即每一數(shù)位上的數(shù)字要小于其進(jìn)制。

輸入格式
第一行一個(gè)正整數(shù) N，含義如題面所述。

第二行一個(gè)正整數(shù) M a {M_a} Ma?，表示 X 進(jìn)制數(shù) A 的位數(shù)。

第三行 M a {M_a} Ma? 個(gè)用空格分開(kāi)的整數(shù)，表示 X 進(jìn)制數(shù) A 按從高位到低位順序各個(gè)數(shù)位上的數(shù)字在十進(jìn)制下的表示。

第四行一個(gè)正整數(shù) M b {M_b} Mb?，表示 X 進(jìn)制數(shù) B 的位數(shù)。

第五行 M b {M_b} Mb? 個(gè)用空格分開(kāi)的整數(shù)，表示 X 進(jìn)制數(shù) B 按從高位到低位順序各個(gè)數(shù)位上的數(shù)字在十進(jìn)制下的表示。

請(qǐng)注意，輸入中的所有數(shù)字都是十進(jìn)制的。

輸出格式
輸出一行一個(gè)整數(shù)，表示 X 進(jìn)制數(shù) A?B 的結(jié)果的最小可能值轉(zhuǎn)換為十進(jìn)制后再模 1000000007 的結(jié)果。

數(shù)據(jù)范圍
對(duì)于 30% 的數(shù)據(jù)， N ≤ 10 ; M a , M b ≤ 8 {N≤10;M_a,M_b≤8} N≤10;Ma?,Mb?≤8，
對(duì)于 100% 的數(shù)據(jù)， 2 ≤ N ≤ 1000 ; 1 ≤ M a , M b ≤ 100000 ; A ≥ B {2≤N≤1000;1≤M_a,M_b≤100000;A≥B} 2≤N≤1000;1≤Ma?,Mb?≤100000;A≥B。

輸入樣例：

11
3
10 4 0
3
1 2 0

輸出樣例：

94

樣例解釋
當(dāng)進(jìn)制為：最低位 2 進(jìn)制，第二數(shù)位 5 進(jìn)制，第三數(shù)位 11 進(jìn)制時(shí)，減法得到的差最小。

此時(shí) A 在十進(jìn)制下是 108，B 在十進(jìn)制下是 14，差值是 94。

思路實(shí)現(xiàn)：

我們平常所見(jiàn)到的數(shù)字，他的每一位數(shù)的進(jìn)制都是相同的，每位數(shù)字的權(quán)重是 X n {X^n} Xn（n為該位數(shù)字后面的位數(shù)），比如二進(jìn)制1000中首位的1的權(quán)重是 2 3 {2^3} 23=8。

對(duì)于題目中的樣例，某種X進(jìn)制數(shù)，最低數(shù)位為二進(jìn)制，第二數(shù)位為十進(jìn)制，第三數(shù)位為八進(jìn)制，則X進(jìn)制數(shù)321轉(zhuǎn)換為十進(jìn)制數(shù)為65。

使用記次數(shù)的方式理解進(jìn)制

最低位為二進(jìn)制，“逢二進(jìn)一”，最低為為1；

第二位為十進(jìn)制，“逢十進(jìn)一”，計(jì)數(shù)法進(jìn)位會(huì)經(jīng)過(guò)0,1,10,11,20，所以我們數(shù) 2 × 2 {2 × 2} 2×2次便會(huì)得到2。

第三位為八進(jìn)制，“逢八進(jìn)一”，計(jì)數(shù)法進(jìn)位會(huì)經(jīng)過(guò)0,1,10,11,20,21,30,31,40,41,50,51,60,61,70,71,80,81,90,91,100,…310,311,320,321，結(jié)束計(jì)數(shù)，我們會(huì)經(jīng)過(guò) 3 × 10 × 2 {3 × 10 × 2 } 3×10×2次得到3。

由此我們可以看出在本題各位數(shù)字進(jìn)制不同情況下，該位數(shù)字的權(quán)重其實(shí)是后面各位數(shù)字的進(jìn)制的乘積。

進(jìn)制類(lèi)似于蓋大樓，要想高數(shù)位上有數(shù)字，就必須時(shí)底數(shù)位上有數(shù)字，并且滿足條件。

對(duì)于任意一個(gè)P我們可以將其分為兩部分：包含P與不包含P。

所以我們每次取最小值時(shí)，必須滿足每一位進(jìn)制P取最小值即可。
最小值為{a_i+1,b_i+1,2}，這三個(gè)數(shù)取最小值。（此處的+1，與2防止出現(xiàn)1進(jìn)制）。
使用秦九韶算法進(jìn)行進(jìn)制計(jì)算的優(yōu)化

實(shí)現(xiàn)

#include#include#include 

using namespace std;
typedef long long LL;
const int N = 100010, MOD = 1000000007;
int n, m1, m2;
int a[N], b[N];

int main()
{
    cin >>n;
    cin >>m1;
    for (int i = m1 - 1; i >= 0; i -- )  cin >>a[i];//逆序存儲(chǔ)，使得個(gè)位數(shù)字對(duì)齊，便于計(jì)算
    cin >>m2;
    for (int i = m2 - 1; i >= 0; i -- )  cin >>b[i];
    
    int m  = max(m1 , m2);
    int res = 0;
    
    for (int i = m - 1; i >= 0; i -- )
    {
        res = (res * (LL)max({2, a[i] + 1, b[i] + 1}) + a[i] - b[i] ) % MOD;
    }
    
    cout<< res<< endl;
    return 0;
}

第四題：統(tǒng)計(jì)子數(shù)組

【Tag：前綴和， 雙指針】

給定一個(gè) N×M 的矩陣 A，請(qǐng)你統(tǒng)計(jì)有多少個(gè)子矩陣 (最小 1×1，大 N×M) 滿足子矩陣中所有數(shù)的和不超過(guò)給定的整數(shù) K?

輸入格式
第一行包含三個(gè)整數(shù) N,M 和 K。

之后 N 行每行包含 M 個(gè)整數(shù)，代表矩陣 A。

輸出格式
一個(gè)整數(shù)代表答案。

數(shù)據(jù)范圍
對(duì)于 30% 的數(shù)據(jù)，N,M≤20，
對(duì)于 70% 的數(shù)據(jù)，N,M≤100，
對(duì)于 100% 的數(shù)據(jù)，1≤N, M≤500;0≤A_ij≤1000;1≤K≤2.5×10^8。

輸入樣例：

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

輸出樣例：

19

樣例解釋
滿足條件的子矩陣一共有 19，包含：

• 大小為 1×1 的有 10 個(gè)。
• 大小為 1×2 的有 3 個(gè)。
• 大小為 1×3 的有 2 個(gè)。
• 大小為 1×4 的有 1 個(gè)。
• 大小為 2×1 的有 3 個(gè)。

思路描述

我們要求出滿足條件（子矩陣的和不超過(guò)K的矩陣數(shù)量），先使用前綴個(gè)處理出數(shù)組和。然后采用暴力去求解問(wèn)題，發(fā)現(xiàn)每一維都有500的范圍，所以我們的時(shí)間復(fù)雜度會(huì)在 50 0 4 {500^4} 5004左右，會(huì)面臨超時(shí)的風(fēng)險(xiǎn)。

我們使用雙指針進(jìn)行優(yōu)化，我們可以先確定出上下邊界，然后動(dòng)態(tài)去求解左右邊界。

優(yōu)化方法為：

1. 依次枚舉子矩陣的上下邊界i，j；
2. 使用雙指針來(lái)維護(hù)子矩陣的左右邊界l，r，r為快指針，l為慢指針。
3. 求出以i，j為上下邊界，以l，r為左右邊界的子矩陣的和sum；
4. 調(diào)整慢指針l，當(dāng)計(jì)算得到的子矩陣和sum大于K時(shí)，我們讓l向右移動(dòng)。當(dāng)l向右移動(dòng)的時(shí)候，子矩陣和sum必然會(huì)單調(diào)不增。當(dāng)計(jì)算子矩陣和sum不超過(guò)K的時(shí)候，慢指針l移動(dòng)結(jié)束；
5. 最后所有滿足條件的子矩陣數(shù)量為r - l + 1;

優(yōu)化之后時(shí)間復(fù)雜度為 O ( N 3 ) {O(N^3)} O(N3)。

實(shí)現(xiàn)

#include#include#include 
using namespace std;

const int N = 510;
typedef long long LL;
LL a[N][N];
int n, m, K;


int main()
{
    scanf("%d%d%d", &n, &m, &K);
    //輸入A數(shù)組，預(yù)處理前綴和
    for (int i = 1; i<= n; i ++)
        for (int j = 1; j<= m; j ++)
        {
            scanf("%lld", &a[i][j]);
            a[i][j] += a[i - 1][j];
        }
        
    LL res = 0;
    for (int i = 1; i<= n; i ++)
        for (int j = i; j<= n; j ++)
            for (int l = 1, r = 1, sum = 0; r<= m; r ++)    
            {
                sum += a[j][r] - a[i - 1][r];//計(jì)算當(dāng)前子矩陣的和
                while(sum >K) //當(dāng)子矩陣和大于K時(shí)， l++
                {
                    sum -= a[j][l] - a[i - 1][l];
                    l ++;
                }
                res += r - l + 1;
            }
    cout<< res<< endl;
    return 0;
}

第五題：積木畫(huà)

【Tag：DP】
小明最近迷上了積木畫(huà)，有這么兩種類(lèi)型的積木，分別為 I 型（大小為 2 個(gè)單位面積）和 L 型（大小為 3 個(gè)單位面積）：

同時(shí)，小明有一塊面積大小為 2×N 的畫(huà)布，畫(huà)布由 2×N 個(gè) 1×1 區(qū)域構(gòu)成。

小明需要用以上兩種積木將畫(huà)布拼滿，他想知道總共有多少種不同的方式？

積木可以任意旋轉(zhuǎn)，且畫(huà)布的方向固定。

輸入格式
輸入一個(gè)整數(shù) N，表示畫(huà)布大小。

輸出格式
輸出一個(gè)整數(shù)表示答案。

由于答案可能很大，所以輸出其對(duì) 1000000007 取模后的值。

數(shù)據(jù)范圍
1 ≤ N ≤ 1 0 7 {1≤N≤10^7} 1≤N≤107。

輸入樣例：
3
輸出樣例：
5
樣例解釋
五種情況如下圖所示，顏色只是為了標(biāo)識(shí)不同的積木：

思路描述

狀態(tài)壓縮DP類(lèi)型。

狀態(tài)表示：f[i][j]表示前i - 1個(gè)位置已經(jīng)確定，并且第i個(gè)狀態(tài)為j的方案。

狀態(tài)計(jì)算：因?yàn)榇祟}的轉(zhuǎn)換數(shù)量很少，只有16種可能，所以我們進(jìn)行枚舉即可。

實(shí)現(xiàn)

樸素版：時(shí)間高，空間高

#include#include#include 

using namespace std;

const int N = 1e7 + 10, MOD = 1000000007;

int n;

int g[4][4] = {
    {1, 1, 1, 1},
    {0, 0, 1, 1},
    {0, 1, 0, 1},
    {1, 0, 0, 0},
};

int f[N][4];

int main()
{
    scanf("%d", &n);
    
    f[1][0] = 1;
    
    for (int i = 1; i<= n; i ++ )
    {
        for (int j = 0; j< 4; j ++ )
            for (int k = 0; k< 4; k ++ )
                f[i + 1][k] = (f[i + 1][k] + f[i][j] * g[j][k]) % MOD;
    }
    
    printf("%d\n", f[n + 1][0]);
    
    return 0;
}

使用滾動(dòng)數(shù)組優(yōu)化：空間低，時(shí)間高

#include#include#include 

using namespace std;

const int N = 1e7 + 10, MOD = 1000000007;

int n;

int g[4][4] = {
    {1, 1, 1, 1},
    {0, 0, 1, 1},
    {0, 1, 0, 1},
    {1, 0, 0, 0},
};

int f[2][4];

int main()
{
    scanf("%d", &n);
    
    f[1][0] = 1;
    
    for (int i = 1; i<= n; i ++ )
    {
        memset(f[i + 1 & 1], 0, sizeof f[0]);
        for (int j = 0; j< 4; j ++ )
            for (int k = 0; k< 4; k ++ )
                f[i + 1 & 1][k] = (f[i + 1 & 1][k] + f[i & 1][j] * g[j][k]) % MOD;
    }
    
    printf("%d\n", f[n + 1 & 1][0]);
    
    return 0;
}

優(yōu)化常數(shù)：空間低，時(shí)間低

#include#include#include 

using namespace std;

const int N = 1e7 + 10, MOD = 1000000007;

int n;

int g[4][4] = {
    {1, 1, 1, 1},
    {0, 0, 1, 1},
    {0, 1, 0, 1},
    {1, 0, 0, 0},
};

int f[2][4];

int main()
{
    scanf("%d", &n);
    
    f[1][0] = 1;
    
    for (int i = 1; i<= n; i ++ )
    {
        memset(f[i + 1 & 1], 0, sizeof f[0]);
        for (int j = 0; j< 4; j ++ )
            for (int k = 0; k< 4; k ++ )
            if(g[j][k])
                f[i + 1 & 1][k] = (f[i + 1 & 1][k] + f[i & 1][j]) % MOD;
    }
    
    printf("%d\n", f[n + 1 & 1][0]);
    
    return 0;
}

第六題：掃雷

【Tag: 哈希表，搜索】
小明最近迷上了一款名為《掃雷》的游戲。其中有一個(gè)關(guān)卡的任務(wù)如下：

在一個(gè)二維平面上放置著 n 個(gè)炸雷，第 i 個(gè)炸雷 ( x i , y i , r i ) {(x_i,y_i,r_i)} (xi?,yi?,ri?) 表示在坐標(biāo) ( x i , y i ) {(x_i,y_i)} (xi?,yi?) 處存在一個(gè)炸雷，它的爆炸范圍是以半徑為 r i {r_i} ri? 的一個(gè)圓。

為了順利通過(guò)這片土地，需要玩家進(jìn)行排雷。

玩家可以發(fā)射 m 個(gè)排雷火箭，小明已經(jīng)規(guī)劃好了每個(gè)排雷火箭的發(fā)射方向，第 j 個(gè)排雷火箭 ( x j , y j , r j ) {(x_j,y_j,r_j)} (xj?,yj?,rj?) 表示這個(gè)排雷火箭將會(huì)在 ( x j , y j ) {(x_j,y_j)} (xj?,yj?) 處爆炸，它的爆炸范圍是以半徑為 r j {r_j} rj? 的一個(gè)圓，在其爆炸范圍內(nèi)的炸雷會(huì)被引爆。

同時(shí)，當(dāng)炸雷被引爆時(shí)，在其爆炸范圍內(nèi)的炸雷也會(huì)被引爆。

現(xiàn)在小明想知道他這次共引爆了幾顆炸雷？

你可以把炸雷和排雷火箭都視為平面上的一個(gè)點(diǎn)。

一個(gè)點(diǎn)處可以存在多個(gè)炸雷和排雷火箭。

當(dāng)炸雷位于爆炸范圍的邊界上時(shí)也會(huì)被引爆。

輸入格式
輸入的第一行包含兩個(gè)整數(shù) n、m。

接下來(lái)的 n 行，每行三個(gè)整數(shù) x i , y i , r i {x_i,y_i,r_i} xi?,yi?,ri?，表示一個(gè)炸雷的信息。

再接下來(lái)的 m 行，每行三個(gè)整數(shù) x j , y j , r j {x_j,y_j,r_j} xj?,yj?,rj?，表示一個(gè)排雷火箭的信息。

輸出格式
輸出一個(gè)整數(shù)表示答案。

數(shù)據(jù)范圍
對(duì)于 40% 的評(píng)測(cè)用例： 0 ≤ x , y ≤ 1 0 9 , 0 ≤ n , m ≤ 1 0 3 , 1 ≤ r ≤ 10 {0≤x,y≤10^9,0≤n,m≤10^3,1≤r≤10} 0≤x,y≤109,0≤n,m≤103,1≤r≤10，

對(duì)于 100% 的評(píng)測(cè)用例： 0 ≤ x , y ≤ 1 0 9 , 0 ≤ n , m ≤ 5 × 1 0 4 , 1 ≤ r ≤ 10 {0≤x,y≤10^9,0≤n,m≤5×10^4,1≤r≤10} 0≤x,y≤109,0≤n,m≤5×104,1≤r≤10。

輸入樣例：
2 1
2 2 4
4 4 2
0 0 5
輸出樣例：
2

樣例解釋

示例圖如下，排雷火箭 1 覆蓋了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆蓋了炸雷 2，所以炸雷 2 也被排除。

思路描述

手寫(xiě)哈希表+搜索

實(shí)現(xiàn)

#include#include#includeusing namespace std;

const int N = 5e4 + 10, M = 1e6 + 7, X = 1e9 + 1;
int n, m;
struct node {
    int x, y, r;
}b[N];
typedef long long ll;
ll h[M]; // 哈希數(shù)組
bool st[N]; // 判斷是否訪問(wèn)過(guò)
int id[M], res; // id數(shù)組為哈希數(shù)組中key對(duì)應(yīng)的地雷下標(biāo)

ll get_hs(int x, int y) { // 得到每個(gè)坐標(biāo)的哈希值
    return (ll)x * X + y;
}

int find(int x, int y) { // 找到該坐標(biāo)被哈希數(shù)組存儲(chǔ)的下標(biāo)key
    ll hs = get_hs(x, y);
    int key = (hs % M + M) % M; // 映射到哈希數(shù)組內(nèi)部
    // 如果該位置已經(jīng)被占用并且不等于我們要求的哈希值，要在之后找到相應(yīng)位置
    while(h[key] != -1 && h[key] != hs) { 

        key++;
        if(key == M) key = 0; // 哈希表走到末尾，又從0開(kāi)始
    }
    return key;
}

// 判斷x1，y1為圓心，半徑為r的圓是否包含x，y
bool check(int x1, int y1, int r, int x, int y) { 
    int d = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
    return d<= r * r;
}

void bfs(int pos) {
    queueq;
    q.push(pos);
    st[pos] = 1;
    while(q.size()) {
        int t = q.front();
        q.pop();
        int x = b[t].x, y = b[t].y, r = b[t].r;
        for(int xx = x - r; xx<= x + r; xx++) { // 從(x-r, y-r)枚舉到(x+r, y+r)
            for(int yy = y - r; yy<= y + r; yy++) {
                int key = find(xx, yy); // 找到該坐標(biāo)點(diǎn)對(duì)應(yīng)的哈希下標(biāo)
                // 該點(diǎn)是不是地雷，有沒(méi)有被訪問(wèn)過(guò)，能不能炸到 
                if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)) { 
                    int pos = id[key]; // 獲得對(duì)應(yīng)地雷編號(hào)
                    st[pos] = 1;
                    q.push(pos);
                }
            }
        }
    }
}

int main() {
    cin >>n >>m;
    memset(h, -1, sizeof(h));
    int x, y, r;
    for(int i = 1; i<= n; i++) { // 讀入地雷，存入哈希表
        cin >>x >>y >>r;
        b[i] = {x, y, r};
        int key = find(x, y);// 找到該坐標(biāo)點(diǎn)對(duì)應(yīng)的哈希下標(biāo)
        if(h[key] == -1) h[key] = get_hs(x, y); // 如果哈希對(duì)應(yīng)位置為空，則插入

        // id數(shù)組沒(méi)有被標(biāo)記或者找到了同一個(gè)坐標(biāo)點(diǎn)更大半徑的地雷
        if(!id[key] || b[id[key]].r< r) { 
            id[key] = i;
        }
    }
    for(int i = 1; i<= m; i++) { // 枚舉導(dǎo)彈
        cin >>x >>y >>r;
        for(int xx = x - r; xx<= x + r; xx++) {
            for(int yy = y - r; yy<= y + r; yy++) {
                int key = find(xx, yy);

                // 如果該點(diǎn)有地雷，沒(méi)有被訪問(wèn)過(guò)，能被炸到
                if(id[key] && !st[id[key]] && check(x, y, r, xx, yy)) bfs(id[key]);
            }
        }
    }
    // 遍歷每個(gè)地雷，看是否被標(biāo)記
    for(int i = 1; i<= n; i++) {
        int key = find(b[i].x, b[i].y); // 獲得坐標(biāo)點(diǎn)對(duì)應(yīng)哈希下標(biāo)
        int pos = id[key]; // 哈希下標(biāo)對(duì)應(yīng)的地雷編號(hào)
        if(pos && st[pos]) res++; // 如果有地雷并且被訪問(wèn)過(guò)
    }
    cout<< res;
    return 0;
}

第七題：李白打酒加強(qiáng)版

【Tag：DP】
話說(shuō)大詩(shī)人李白，一生好飲。幸好他從不開(kāi)車(chē)。

一天，他提著酒壺，從家里出來(lái)，酒壺中有酒 2 斗。

他邊走邊唱：

無(wú)事街上走，提壺去打酒。

逢店加一倍，遇花喝一斗。

這一路上，他一共遇到店 N 次，遇到花 M 次。

已知最后一次遇到的是花，他正好把酒喝光了。

請(qǐng)你計(jì)算李白這一路遇到店和花的順序，有多少種不同的可能？

注意：壺里沒(méi)酒 (0 斗) 時(shí)遇店是合法的，加倍后還是沒(méi)酒；但是沒(méi)酒時(shí)遇花是不合法的。

輸入格式
第一行包含兩個(gè)整數(shù) N 和 M。

輸出格式
輸出一個(gè)整數(shù)表示答案。由于答案可能很大，輸出模 1000000007 的結(jié)果。

數(shù)據(jù)范圍
對(duì)于 40% 的評(píng)測(cè)用例：1≤N,M≤10。
對(duì)于 100% 的評(píng)測(cè)用例：1≤N,M≤100。

輸入樣例：

5 10

輸出樣例：

14

樣例解釋
如果我們用 0 代表遇到花，1 代表遇到店，14 種順序如下：

010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100

思路描述

動(dòng)態(tài)規(guī)劃題，使用閆氏DP分析法求解。

狀態(tài)表示：f(i,j,k)分別表示為經(jīng)過(guò)第i朵店，第j個(gè)花時(shí)，酒壺中酒的數(shù)量為k。

狀態(tài)屬性：數(shù)量。

狀態(tài)計(jì)算：

分為兩種：

1. f(i - 1, j, k / 2):遇到的是店，說(shuō)明此前遇到店的數(shù)量為i - 1，遇到花的數(shù)量仍然為j，酒壺中酒的數(shù)量為k/2;滿足條件i大于等于1，k能被二整除
2. f(i, j - 1, k + 1):遇到的是花，說(shuō)明此前遇到店的數(shù)量為i，遇到花的數(shù)量為j - 1，酒壺中酒的數(shù)量為k + 1。滿足條件j大于等于1

實(shí)現(xiàn)

#include#include#include 

using namespace std;

const int N = 110, MOD = 1e9 + 7;

int n, m;
int f[N][N][N];

int main()
{
    cin >>n >>m;
    
    //初始化
    f[0][0][2] = 1;
    for (int i = 0; i<= n; i ++ )
        for (int j = 0; j<= m; j ++ )
            for (int k = 0; k<= m; k ++ )
            {
                int& v = f[i][j][k];
                if (i && k % 2 == 0) v = (v + f[i - 1][j][k / 2]) % MOD;
                if (j) v = (v + f[i][j - 1][k + 1]) % MOD;
            }

    cout<< f[n][m - 1][1]<< endl; //輸出最后一步，經(jīng)過(guò)了n個(gè)店，m - 1朵花，酒壺中剩余的酒為1
    return 0;
}

第八題：砍竹子

這天，小明在砍竹子，他面前有n棵竹子排成一排，一開(kāi)始第i棵竹子的高度為 h i {h_i} hi?。

他覺(jué)得一棵一棵砍太慢了，決定使用魔法來(lái)砍竹子。

魔法可以對(duì)連續(xù)的一段相同高度的竹子使用，假設(shè)這一段竹子的高度為 H，那么使用一次魔法可以把這一段竹子的高度都變?yōu)? ? ? H 2 ? + 1 ? ?\sqrt{?\frac {H}{2}?+1}? ??2H??+1 ?? ，其中 ?x? 表示對(duì) x 向下取整。

小明想知道他最少使用多少次魔法可以讓所有的竹子的高度都變?yōu)?1。

輸入格式
第一行為一個(gè)正整數(shù) n，表示竹子的棵數(shù)。

第二行共 n 個(gè)空格分開(kāi)的正整數(shù) hi，表示每棵竹子的高度。

輸出格式
一個(gè)整數(shù)表示答案。

數(shù)據(jù)范圍
對(duì)于 20% 的數(shù)據(jù)，保證 1 ≤ n ≤ 1000 , 1 ≤ h i ≤ 1 0 6 {1≤n≤1000,1≤h_i≤10^6} 1≤n≤1000,1≤hi?≤106 。
對(duì)于 100% 的數(shù)據(jù)，保證 1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ h i ≤ 1 0 18 {1≤n≤2×10^5,1≤h_i≤10^{18}} 1≤n≤2×105,1≤hi?≤1018。

輸入樣例：

6
2 1 4 2 6 7

輸出樣例：

5

樣例解釋
其中一種方案：

2 1 4 2 6 7
→ 2 1 4 2 6 2
→ 2 1 4 2 2 2
→ 2 1 1 2 2 2
→ 1 1 1 2 2 2
→ 1 1 1 1 1 1
共需要 5 步完成。

思路描述

我們現(xiàn)預(yù)處理需要進(jìn)行的大高度。

#include#include#include 
#includetypedef long long LL;

int main()
{
    LL x = 1e18;
    while(x != 1) {
        x = sqrt(x / 2 + 1);
        printf("%lld\n", x);
    }
    return 0;
}

輸出結(jié)果為

707106781
18803
96
7
2
1

可以看出每個(gè)數(shù)大的操作次數(shù)為6次，題目的數(shù)據(jù)量為 1 ≤ n ≤ 2 × 1 0 5 {1≤n≤2×10^5} 1≤n≤2×105,所以我們可以使用暴力法去求解。

我們先對(duì)每個(gè)數(shù)進(jìn)行預(yù)處理，將預(yù)處理后的數(shù)據(jù)存儲(chǔ)起來(lái)，題目中說(shuō)我們可以對(duì)連續(xù)的一段相同高度的竹子進(jìn)行操作，所以我們?cè)谂袛噙B續(xù)的一段竹子的高度是否相等即可。

實(shí)現(xiàn)

#include#include 
#include#includeusing namespace std;
typedef long long LL;
const int N = 200010, M = 10;
int f[N][M];
int n, m;

int main()
{
    scanf("%d", &n);
    LL stk[M];//定義一個(gè)棧
    
    int res = 0;
    for (int i = 0; i< n; i ++)
    {
        LL x;
        int top = 0;
        scanf("%lld", &x);
        
        while(x != 1) stk[++ top] = x, x = sqrt(x / 2 + 1);//對(duì)x進(jìn)行預(yù)處理，每次向棧頂加入x處理后的結(jié)果
        res += top;
        
        m = max(m, top);//m維護(hù)最高的位置
        
        for (int j = 0, k = top; k; j ++, k --)
        {
            f[i][j] = stk[k];//將棧內(nèi)的元素存儲(chǔ)到數(shù)組中
        }
    }
    
    for (int i = 0; i< m; i ++ )
        for (int j = 1; j< n; j ++)
        {
        //判斷是否為連續(xù)的一段
            if(f[j][i] && f[j][i] == f[j - 1][i]) res --;
        }
    printf("%d\n", res);
    return 0;
}

調(diào)研

主要想收集一下，閱讀者對(duì)我書(shū)寫(xiě)文章、題解時(shí)的建議或者看法。

歡迎各位讀者留言，評(píng)論。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱(chēng)：【第十三屆藍(lán)橋杯C++B組省賽編程題詳解】-創(chuàng)新互聯(lián)
URL地址：http://www.yijiale78.com/article22/psgjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、微信公眾號(hào)、網(wǎng)站設(shè)計(jì)、手機(jī)網(wǎng)站建設(shè)、響應(yīng)式網(wǎng)站、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)