藍橋杯練習-3.10

代碼練習

• 龜兔賽跑

思路

本題的關鍵是當兔子領先烏龜t米時，我們并不需要像傳統一樣的，讓兔子走的路程停止，而烏龜繼續行走s秒。而是可以讓兔子退後v1×s的路程，而當烏龜在s秒内行走的時候，兔子相當于在補之前後退的距離，當s秒過去了，烏龜走了s秒，而兔子剛好回到了原位，這就相當于兔子在這段時間内休息。

代碼實作

#include <iostream>
using namespace std;
int main()
{
    int v1, v2, t, s, l;//兔子的速度是v1，烏龜的速度是v2
    int ans1 = 0;//兔子目前走過的路程
    int ans2 = 0;//烏龜目前走過的路程
    cin >> v1 >> v2 >> t >> s >> l;
    int i = 0;
    while(ans1 < l && ans2 < l)
    {
        ans1 += v1;
        ans2 += v2;
        i++;
        if (ans1 == l || ans2 == l)
            break;
        while(ans1 - ans2 >= t)
        {
            ans1 -= v1 * s;
        }
    }
    if (ans1 > ans2)
    {
        cout << "R" << endl << i;
    }
    else if (ans2 > ans1)
    {
        cout << "T" << endl << i;
    }
    else
        cout << "D" << endl << i;
    return 0;
}
           

❕注意：我剛開始是用傳統的方法來實作代碼的，發現有些測試案例過不了，原因是，烏龜可能在兔子休息的s秒内就已經到達了終點，而我們還在讓時間繼續，烏龜仍然在動，這就導緻結果出錯。

改進：

while(ans1 < l && ans2 < l)
    {
        if (ans1 == l || ans2 == l)
            break;
        ans1 += v1;
        ans2 += v2;
        i++;
        while(ans1 - ans2 >= t)
        {
            for (int j = 1; j <= s; j++)
            {
                ans2 += v2;
                t++;
                if (ans2 == l)
                    break;
            }
        }
    }
           

• C 乘積尾零（第九屆藍橋杯）

Description

如下的10行資料，每行有10個整數，請你求出它們的乘積的末尾有多少個零？

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

注意：需要送出的是一個整數，表示末尾零的個數。不要填寫任何多餘内容。

Input

見上文描述。

思路

本題問的是最後的乘積末尾有多少個0，我們知道，乘以10可以得到1個零，而10是有2乘5得到的，是以我們隻要算出上述資料可以拆分成多少個2和5（有多少個2和5的因子），然後求出其中的最小值，即為最後有多少個零。

#include <iostream>
using namespace std;
int a[105];
int num2 = 0;
int num5 = 0;
int result;
int f2(int n)
{
    int num = 0;
    if(n % 2 == 0)
    {
        while (n % 2 == 0)
        {
            num++;
            n /= 2;
        }
    return num;
    }
    else return 0;
}
int f5(int n)
{
    int num = 0;
    if(n % 5 == 0)
    {
        while (n % 5 == 0)
        {
            num++;
            n /= 5;
        }
    return num;
    }
    else return 0;
}
int main()
{
    for (int i = 1; i <= 100; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= 100; i++)
    {
        num2 += f2(a[i]);
        num5 += f5(a[i]);
    }
    result = min(num2, num5);
    cout << result << endl;
    return 0;
}
           

• D 測試次數

Description

标題：測試次數

x星球的居民脾氣不太好，但好在他們生氣的時候唯一的異常舉動是：摔手機。

各大廠商也就紛紛推出各種耐摔型手機。x星球的質監局規定了手機必須經過耐摔測試，并且評定出一個耐摔指數來，之後才允許上市流通。

x星球有很多高聳入雲的高塔，剛好可以用來做耐摔測試。塔的每一層高度都是一樣的，與地球上稍有不同的是，他們的第一層不是地面，而是相當于我們的2樓。

如果手機從第7層扔下去沒摔壞，但第8層摔壞了，則手機耐摔指數=7。

特别地，如果手機從第1層扔下去就壞了，則耐摔指數=0。

如果到了塔的最高層第n層扔沒摔壞，則耐摔指數=n

為了減少測試次數，從每個廠家抽樣3部手機參加測試。

某次測試的塔高為1000層，如果我們總是采用最佳政策，在最壞的運氣下最多需要測試多少次才能确定手機的耐摔指數呢？

請填寫這個最多測試次數。

注意：需要填寫的是一個整數，不要填寫任何多餘内容。

Input

見上文描述。

Output

代碼實作

#include <iostream>
using namespace std;
int dp[5][10005];//dp[i][j]表示i部手機測試j層樓的最多測試次數
void f(int phone, int floor)
{
    for (int j = 1; j <= floor; j++)
    {
        dp[1][j] = j;//先初始化一部手機，在測試j層樓的最多測試次數，當然一部手機最多測試次數就是從最開始一樓一樓去測，是以次數是樓層高度
    }
    for (int i = 2; i <= phone; i++)//然後從第二部手機開始，循環
    {
        for (int j = 1; j <= floor; j++)//因為是動态規劃，是以我們要知道樓層為j時，每取k為不同值的所有情況，這樣子問題的答案知道，最終答案也可以推出
        {
            for (int k = 1; k < j; k++)//從第k層摔下
            {
                dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1);
            }
        }
    }
}
int main()
{
    f(3, 1000);
    cout << dp[3][1000] << endl;
    return 0;
}
           

觀看部落格

一道關于扔球/扔雞蛋/摔手機的DP問題

以下文字和思路大部分來自以上部落格已經其他的。

題目

一幢 100 層的大樓,給你兩個雞蛋. 如果在第 n 層扔下雞蛋,雞蛋不碎,那麼從前 n-1 層扔雞蛋都不碎.

這兩隻雞蛋一模一樣,不碎的話可以扔無數次. 已知雞蛋在0層扔不會碎.

提出一個政策, 要保證能測出雞蛋恰好會碎的樓層, 并使此政策在最壞情況下所扔次數最少.

❕注意：“最佳政策”，“最壞運氣”，意思應該是把3部手機都摔壞并且是最後一次才測出來耐摔指數的最小次數。這是一個最優解的問題

最佳政策代表整體嘗試放手機在各個層數的最小次數，最壞運氣代表單次放置手機的最大值。

思路

我們不妨這樣思考，假設問題存在最優解，這個最優解的最壞情況嘗試次數是x次。那麼，我們第一次扔雞蛋恰恰是從第x層開始扔。要想盡量樓層跨度大一些，又要保證不超過假設的嘗試次數x，那麼第一次扔雞蛋的最優選擇就是第x層。如果第一次扔雞蛋沒有碎，我們的嘗試次數消耗了一次，問題就轉化成了兩個🥚在100 - x層樓往下扔，要求嘗試次數不得超過x - 1次。由于嘗試次數上限變成了x - 1次，是以第二次嘗試的樓層樓層跨度也是x - 1,第三層樓層跨度是x - 2，可得方程

x + ( x − 1 ) + ( x − 2 ) + . . . . + 1 = 100 x + (x - 1) + (x - 2) + .... + 1 = 100 x+(x−1)+(x−2)+....+1=100

最終x向上取整，得到 x = 14

是以，最優解在最壞情況的嘗試次數是14次。

那麼這個問題可以推廣到一般情況

一般情況

給定N層樓和i個球。用i個球檢測在這N層樓中的某一層t球扔下樓時不碎，而在t+1層球扔下樓時會碎，則t層稱為最高安全層。求用i個球一定可以檢測N層樓的最高安全層的最少扔球次數。（注：球不碎還可以再用）

思路

dp[i] [j]表示i部手機j層樓的最少測試次數

現在給定i個球，j層樓，假設我們在某一層k扔一個球，那麼就會出現兩種情況：

（1）如果球碎了，那我們需要往第k層樓以下的樓層去測試。在第k層我們測試了，是以次數要計數1；還需往下的樓層作測試，這時還有i-1個球去測試k-1層樓，即需計次數 dp[i-1] [k-1]。綜上，在情況（1）下，測試次數為1+dp[i-1] [k-1]。

（2）如果球不碎，那我們需要往第k層樓以上的樓層去測試。在第k層我們測試了，是以次數要計數1；還需往上的樓層作測試，這時還有i個球去測試j-k層樓，即需計次數 dp[i] [j-k]。綜上，在情況（2）下，測試次數為1+dp[i] [j-k]。

在（1）（2）兩種情況中，我們需要取兩者的最大值，因為我們需要保證一定可以測試出最高安全樓層。由上可見，k是一個變量，取值範圍為0<=k<=j。這表明我們需要周遊0j，每次求出（1），（2）兩種情況的最大值，為了簡便，我們将0j周遊所得的最大值記為{m0,m1,m2…mj}，我們還需要在這些值（這些值都是可以保證一定能測試出最高安全樓層）中選出最小值，因為我們需要的是最少的次數。

是以得到狀态轉移方程：

d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , m a x ( d p [ i − 1 ] [ k − 1 ] , d p [ i ] [ j − k ] ) + 1 ) dp[i][j] = min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1) dp[i][j]=min(dp[i][j],max(dp[i−1][k−1],dp[i][j−k])+1)