• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 2018第九屆藍橋杯省賽C/C++ B組題解

    第一題: 第幾天

    2000年的1月1日,是那一年的第1天。
    那么,2000年的5月4日,是那一年的第幾天?
    
    注意:需要提交的是一個整數,不要填寫任何多余內容。
    

    解析:

    這題要注意兩個地方,一是2000年不是2010年; 二是2000年的1月1日,是那一年的第1天,所以答案不是兩個日記相減,而是
    兩個日歷相減的結果加上1。
    

    方法一: 最簡單的方法是用Excel算:
    =DATE(2000,5,4) - DATE(2000,1,1) + 1
     (或者寫 "=DATE(2000,5,4) - DATE(2000,1,0)" 也可)
    

    方法二: 右下角的日歷
    看日歷知答案為31+29+31+30+4,用計算器算出125。
    

    方法三: 敲代碼
    特別閑的話還是可以考慮敲敲代碼的: 
    
    #include <iostream>
    using namespace std;
    inline int isLeap(int year) {
        return 0 == year % 4 || year % 100 && 0 == year % 400;
    }
    const int Day[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    int main() {
        int year = 2000, month = 5, day = 4;
        int ans = (isLeap(year) && month > 2) + day;
        for (int i = 1; i < month; ++i)
            ans += Day[i];
        cout << ans << endl;
        return 0;
    }


    答案: 125


    第二題: 明碼

    漢字的字形存在于字庫中,即便在今天,16點陣的字庫也仍然使用廣泛。
    16點陣的字庫把每個漢字看成是16x16個像素信息。并把這些信息記錄在字節中。
    
    一個字節可以存儲8位信息,用32個字節就可以存一個漢字的字形了。
    把每個字節轉為2進制表示,1表示墨跡,0表示底色。每行2個字節,
    一共16行,布局是:
    
        第1字節,第2字節
        第3字節,第4字節
        ....
        第31字節, 第32字節
    
    這道題目是給你一段多個漢字組成的信息,每個漢字用32個字節表示,這里給出了字節作為有符號整數的值。
    
    題目的要求隱藏在這些信息中。你的任務是復原這些漢字的字形,從中看出題目的要求,并根據要求填寫答案。
    
    這段信息是(一共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 
    
    
    注意:需要提交的是一個整數,不要填寫任何多余內容。
    

    解析:

    這題沒看到提交的是一個整數,最后交了"九的九次方等于多少?"上去。尷尬......
    
    會把數字轉為二進制就好了。
    

    參考代碼:

    #include <iostream>
    using namespace std;
    void changeToTwo(int x) {
        if (x < 0) cout << "*";
        else cout << " ";
        for (int i = 6; i >= 0; --i)
            if (x & (1 << i)) cout << "*";
            else cout << " ";
    }
    int main() {
        int a, b;
        while (cin >> a >> b) {
            changeToTwo(a);
            changeToTwo(b);
            cout << endl;
            for (int i = 1; i < 16; ++i) {
                cin >> a >> b;
                changeToTwo(a);
                changeToTwo(b);
                cout << endl;
            }
            cout << endl;
        }
        return 0;
    }

    最后看到:

    九的九次方等于多少?
    

    計算器算算就好了。


    答案: 387420489


    第三題: 乘積尾零

    如下的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 
    
    注意: 需要提交的是一個整數,表示末尾零的個數。不要填寫任何多余內容。
    

    解析:

    數學做法: 因為2 * 5 = 10,所以分解100個數,求出這100個數中總共有多少個2和5的因子,最后取最小值即為答案。
    
    參考代碼: 
    
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int cntNum(int x, int k) {
        int cnt = 0;
        while (0 == x % k) {
            ++cnt; x /= k;
        }
        return cnt;
    }
    int main() {
        int cntTwo = 0, cntFive = 0;
        int tmp;
        while (cin >> tmp) {
            cntTwo += cntNum(tmp, 2);
            cntFive += cntNum(tmp, 5);
        }
        cout << min(cntFive, cntTwo);
        return 0;
    }

    用高精度算法也可以:

    #include <iostream>
    using namespace std;
    const int X = 1e9;
    const int maxn = 105;
    int num[maxn], len = 1;
    int cntZero(int x) {
        int cnt = 0;
        while (0 == x % 10) {
            ++cnt; x /= 10;
        }
        return cnt;
    }
    int main() {
        num[0] = 1;
        long long tmp;
        while (cin >> tmp) {
            long long carry = 0;
            for (int i = 0; i < len; ++i) {
                carry += tmp * num[i];
                num[i] = carry % X;
                carry /= X;
            }
            if (carry) num[len++] = carry;
        }
        int find = -1, ans = 0;
        while (!num[++find]) ans += 9;
        cout << ans + cntZero(num[find]) << endl;
        return 0;
    }


    答案: 31


    第四題: 測試次數

    x星球的居民脾氣不太好,但好在他們生氣的時候唯一的異常舉動是: 摔手機。
    各大廠商也就紛紛推出各種耐摔型手機。x星球的質監局規定了手機必須經過耐摔測試,并且評定出一個耐摔指數來,之后才
    允許上市流通。
    
    x星球有很多高聳入云的高塔,剛好可以用來做耐摔測試。塔的每一層高度都是一樣的,與地球上稍有不同的是,他們的第一
    層不是地面,而是相當于我們的2樓。
    
    如果手機從第7層扔下去沒摔壞,但第8層摔壞了,則手機耐摔指數=7。
    特別地,如果手機從第1層扔下去就壞了,則耐摔指數=0。
    如果到了塔的最高層第n層扔沒摔壞,則耐摔指數=n
    
    為了減少測試次數,從每個廠家抽樣3部手機參加測試。
    
    某次測試的塔高為1000層,如果我們總是采用最佳策略,在最壞的運氣下最多需要測試多少次才能確定手機的耐摔指數呢?
    
    請填寫這個最多測試次數。
    
    注意: 需要填寫的是一個整數,不要填寫任何多余內容。
    

    解析:

    方法一: dp

    設在第n層樓還剩k個手機可以用的話,f(n, k)為在最壞的運氣下最多需要測試多少次能確定手機的耐摔指數。(注: n >= 0,k >= 1)
    易知:

    f(n, 1) = n(由第1層樓開始測試一直試到第n層)

    f(0, n) = 1(第0層樓不管你有多少部手機都不需要測試就能確定手機的耐摔指數)

    (假設從第i層樓扔手機,若摔壞了,那就是i-1層樓剩下k-1個手機要測試的次數;若沒有摔壞,那么前面i層樓都不需要測試,就變成n-i層樓k個手機要測試的次數。因為考慮的是最壞的運氣下最多需要測試多少次能確定手機的耐摔指數,那么取兩個最大值就好了。因此從第1層樓嘗試,到第n層樓,求其最小值并加上1就為答案(加1是因為在第i層樓嘗試了一次))

    參考代碼:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn = 10005, inf = 1e9;
    int f[maxn][5];
    int main() {
        int n = 1000;
        f[0][1] = f[0][2] = f[0][3] = 0;
        for (int i = 1; i <= n; ++i)
            f[i][1] = i;
        for (int i = 1; i <= n; ++i) {
            f[i][2] = inf;
            for (int j = 1; j <= i; ++j)
                f[i][2] = min(1 + max(f[j - 1][1], f[i - j][2]), f[i][2]);
        }
        for (int i = 1; i <= n; ++i) {
            f[i][3] = inf;
            for (int j = 1; j <= i; ++j)
                f[i][3] = min(1 + max(f[j - 1][2], f[i - j][3]), f[i][3]);
        }
        cout << f[1000][3] << endl;
        return 0;
    }

    方法二: 用數學方法求出下面的結論:

    假設k次嘗試,最多能測出耐摔指數為k * (k * k+ 5) / 6高度。

    根據上面的結論用二分查找求解答案。

    參考代碼:

    #include <iostream>
    using namespace std;
    int main() {
        int n = 1000;
        int srt = 1, end = 1000;
        while (srt < end) {
            long long mid = ((end + srt) >> 1);
            if (mid * (mid * mid + 5) / 6 >= n) end = mid;
            else srt = mid + 1;
        }
        cout << srt << endl;
        return 0;
    }


    答案: 19


    第五題: 快速排序

    以下代碼可以從數組a[]中找出第k小的元素。
    
    
    它使用了類似快速排序中的分治算法,期望時間復雜度是O(N)的。
    
    
    請仔細閱讀分析源碼,填寫劃線部分缺失的內容。
    
    #include <stdio.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( _____________________________ ); //填空
        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, 5));
        return 0;
    }
    注意: 只填寫劃線部分缺少的代碼,不要抄寫已經存在的代碼或符號。
    

    解析:

    吐槽一下題目代碼連<stdlib.h>頭文件都沒有!!!
    注意時間復雜度為O(n)。
    當i - l + 1 < k時,我們知道這i - l + 1個數必然為前i - l + 1小的數。由于要找第k小的數,故可以排除掉這
    i - l + 1個數。
    即在a數組的[i + 1, r]里找第k- (i - l + 1)小的數就好。
    


    答案: a, i + 1, r, k - (i - l + 1) (或k - i + l - 1)


    第六題: 遞增三元組

    給定三個整數數組
    A = [A1, A2, ... AN], 
    B = [B1, B2, ... BN], 
    C = [C1, C2, ... CN],
    請你統計有多少個三元組(i, j, k) 滿足: 
    1. 1 <= i, j, k <= N  
    2. Ai < Bj < Ck  
    
    【輸入格式】 
    第一行包含一個整數N。
    第二行包含N個整數A1, A2, ... AN。
    第三行包含N個整數B1, B2, ... BN。
    第四行包含N個整數C1, C2, ... CN。
    
    對于30%的數據,1 <= N <= 100  
    對于60%的數據,1 <= N <= 1000 
    對于100%的數據,1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000 
    
    【輸出格式】
    一個整數表示答案
    
    【樣例輸入】
    3
    1 1 1
    2 2 2
    3 3 3
    
    【樣例輸出】
    27 
    
    
    資源約定: 
    峰值內存消耗(含虛擬機) < 256M
    CPU消耗  < 1000ms
    

    解析:

    b從1到99999枚舉,答案就是:

    時間復雜度: O(n)

    代碼:

    #include <iostream>
    const int maxn = 1e5 + 5;
    long long cntA[maxn], cntB[maxn], cntC[maxn];
    using namespace std;
    int main() {
        int n, tmp;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            ++cntA[tmp];
        }
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            ++cntB[tmp];
        }
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            ++cntC[tmp];
        }
        for (int i = 1; i <= 100000; ++i) {
            //算出A, C數組中0-i內共多少個數
            cntA[i] += cntA[i - 1];
            cntC[i] += cntC[i - 1];
        }
        long long ans = 0;
        for (int i = 1; i <= 100000; ++i)
            //cntC[100000] - cntC[i]即C數組中i+1到100000有多少個數
            ans += cntA[i - 1] * cntB[i] * (cntC[100000] - cntC[i]);
        cout << ans << endl;
        return 0;
    }


    第七題: 螺旋折線

    如圖p1.png所示的螺旋折線經過平面上所有整點恰好一次。  
    對于整點(X, Y),我們定義它到原點的距離dis(X, Y)是從原點到(X, Y)的螺旋折線段的長度。  
    
    例如dis(0, 1)=3, dis(-2, -1)=9  
    
    給出整點坐標(X, Y),你能計算出dis(X, Y)嗎?
    
    【輸入格式】
    X和Y  
    
    對于40%的數據,-1000 <= X, Y <= 1000  
    對于70%的數據,-100000 <= X, Y <= 100000  
    對于100%的數據, -1000000000 <= X, Y <= 1000000000  
    
    【輸出格式】
    輸出dis(X, Y)  
    
    
    【樣例輸入】
    0 1
    
    【樣例輸出】
    3
    
    
    資源約定: 
    峰值內存消耗(含虛擬機) < 256M
    CPU消耗  < 1000ms
    
    
    請嚴格按要求輸出,不要畫蛇添足地打印類似: “請您輸入...” 的多余內容。
    
    注意: 
    main函數需要返回0;
    只使用ANSI C/ANSI C++ 標準;
    不要調用依賴于編譯環境或操作系統的特殊函數。
    所有依賴的函數必須明確地在源文件中 #include <xxx>
    不能通過工程設置而省略常用頭文件。
    
    提交程序時,注意選擇所期望的語言類型和編譯器類型。
    

    解析:

    關鍵是看出規律: 
    (-m, 0)時, dis = 1+2+2+2+3+4+4+4+5+6+6+6+…+2m-1
                   = 2+2+2+2+4+4+4+4+6+6+6+6+…+2m-2+2m-(1+1+1+1+…+1)
                   = 4*(2+2m-2)*(m-1)/2+2m-m
                   = 4 * m * m - 3 * m
    因此(0, m)時   dis = dis(-m, 0) + 2m = 4 * m * m - m
        (m, 0)時  dis = dis(0, m) + 2m = 4 * m * m + m
        (0, -m)時 dis = dis(m, 0) + 2m = 4 * m * m + 3 * m
    然后把點移到這四點其中一點就容易計算了。
    注: 我是規定在線1的點移到(-m,0),在線2的點移到(0,m),在線3的點移到(m,0),在線4的點移到(0,-m)
    

    時間復雜度: O(1)

    參考代碼:

    #include <iostream>
    using namespace std;
    int whichLine(long long x, long long y) {
        if (x < 0 && y >= x + 1 && y < -x) return 1;
        else if (y > 0 && x >= -y && x < y) return 2;
        else if (x > -y) return 3;
        else return 4;
    }
    long long ans(long long x, long long y) {
        switch (whichLine(x, y)) {
        case 1: return 4 * x * x + 3 * x + y;
        case 2: return 4 * y * y - y + x;
        case 3: return 4 * x * x + x - y;
        case 4: return 4 * y * y - 3 * y - x;
        }
    }
    int main() {
        long long x, y;
        cin >> x >> y;
        cout << ans(x, y) << endl;
        return 0;
    }

    第八題: 日志統計

    小明維護著一個程序員論壇。現在他收集了一份"點贊"日志,日志共有N行。其中每一行的格式是: 
    
    ts id
    
    表示在ts時刻編號id的帖子收到一個"贊"。
    
    現在小明想統計有哪些帖子曾經是"熱帖"。如果一個帖子曾在任意一個長度為D的時間段內收到不少于K個贊,小明就認為這個
    帖子曾是"熱帖"。  
    
    具體來說,如果存在某個時刻T滿足該帖在[T, T+D)這段時間內(注意是左閉右開區間)收到不少于K個贊,該帖就曾是"熱帖"。
    
    給定日志,請你幫助小明統計出所有曾是"熱帖"的帖子編號。
    
    【輸入格式】
    第一行包含三個整數N、D和K。  
    以下N行每行一條日志,包含兩個整數ts和id。  
    
    對于50%的數據,1 <= K <= N <= 1000  
    對于100%的數據,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  
    
    0 1
    9 1
    10 1
    100 3
    100 3
    0 10
    10 10
    【輸出樣例】
    1  
    3  
    
    
    資源約定: 
    峰值內存消耗(含虛擬機) < 256M
    CPU消耗  < 1000ms
    
    
    請嚴格按要求輸出,不要畫蛇添足地打印類似: “請您輸入...” 的多余內容。
    
    注意: 
    main函數需要返回0;
    只使用ANSI C/ANSI C++ 標準;
    不要調用依賴于編譯環境或操作系統的特殊函數。
    所有依賴的函數必須明確地在源文件中 #include <xxx>
    不能通過工程設置而省略常用頭文件。
    
    提交程序時,注意選擇所期望的語言類型和編譯器類型。
    

    解析:

    先用sort排序,排序依據先由id從小到大排,若id相等則由ts從小到大排列。
    接著用i,j兩個變量去遍歷數組。
    若有
    1. msg[i].id == msg[j].id
        (1) msg[i].ts + d < msg[j].ts
            a. j – i + 1 == k            --> msg[i].id是熱門的id,j跳過所有id等于msg[i].id的元素,然后i = j
            b. j – i + 1 < k             --> msg[i].id還不是熱門的id,++j
        (2) msg[i].ts + d >= msg[j].ts   --> i跳過所有符合msg[i].ts + d >= msg[j].ts的元素
    2.  msg[i].id != msg[j].id           --> i = j 就行了
    

    時間復雜度: O(nlogn)

    參考代碼:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct Msg {
        int id, ts;
    };
    bool cmp(Msg a, Msg b) {
        if (a.id != b.id) return a.id < b.id;
        return a.ts < b.ts;
    }
    const int maxn = 100005;
    Msg msg[maxn];
    int n, d, k;
    int main() {
        cin >> n >> d >> k;
        for (int i = 0; i < n; ++i)
            cin >> msg[i].ts >> msg[i].id;
        sort(msg, msg + n, cmp);
        int i = 0, j = 0;
        while (j < n) {
            cout << "i = " << i << ", j = " << j << endl;
            if (msg[i].id != msg[j].id)
                i = j;
            else if (msg[j].ts < msg[i].ts + d) {
                if (j - i + 1 == k) {
                    cout << msg[i].id << endl;
                    while (j < n && msg[j].id == msg[i].id)
                        ++j;
                    i = j;
                }
                else ++j;
            }
            else while (msg[j].ts >= msg[i].ts + d)
                ++i;
        }
        return 0;
    }

    第九題: 全球變暖

    你有一張某海域NxN像素的照片,"."表示海洋、"#"表示陸地,如下所示:
    
    .......
    .##....
    .##....
    ....##.
    ..####.
    ...###.
    .......
    
    其中"上下左右"四個方向上連在一起的一片陸地組成一座島嶼。例如上圖就有2座島嶼。  
    
    由于全球變暖導致了海面上升,科學家預測未來幾十年,島嶼邊緣一個像素的范圍會被海水淹沒。具體來說如果一塊陸地像   
    素與海洋相鄰(上下左右四個相鄰像素中有海洋),它就會被淹沒。  
    
    例如上圖中的海域未來會變成如下樣子:
    
    .......
    .......
    .......
    .......
    ....#..
    .......
    .......
    
    請你計算:依照科學家的預測,照片中有多少島嶼會被完全淹沒。  
    
    【輸入格式】
    第一行包含一個整數N。  (1 <= N <= 1000)  
    以下N行N列代表一張海域照片。  
    
    照片保證第1行、第1列、第N行、第N列的像素都是海洋。  
    
    【輸出格式】
    一個整數表示答案。
    
    【輸入樣例】
    7 
    .......
    .##....
    .##....
    ....##.
    ..####.
    ...###.
    .......  
    
    【輸出樣例】
    1  
    
    
    
    資源約定:
    峰值內存消耗(含虛擬機) < 256M
    CPU消耗  < 1000ms
    
    
    請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入...” 的多余內容。
    
    注意:
    main函數需要返回0;
    只使用ANSI C/ANSI C++ 標準;
    不要調用依賴于編譯環境或操作系統的特殊函數。
    所有依賴的函數必須明確地在源文件中 #include <xxx>
    不能通過工程設置而省略常用頭文件。
    
    提交程序時,注意選擇所期望的語言類型和編譯器類型。
    

    解析:

    3個過程: 找島 --> 毀島 --> 找島
    找島用bfs,毀島遍歷所有陸地的上下左右有海的話毀掉, 再找島時應該找之前的島還在不在,而不是重新用bfs找島
    答案即為第一次找島的個數 - 最后一次找島的個數
    注意下面的數據答案為0:
    7
    .......
    .......
    ..#.#..
    .#####.
    ..#.#..
    .......
    .......
    

    時間復雜度: O(n2)

    參考代碼:

    #include <cstdio>
    #include <queue>
    using namespace std;
    const int maxn = 1010;
    const int f[] = { 1, -1, 0, 0 };
    const int g[] = { 0, 0, 1, -1 };
    char a[maxn][maxn];
    int map[maxn][maxn];
    int n;
    bool isVisit[maxn / 2];
    queue<int> P, Q;
    bool isRight(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }
    void BelongIsland(int x, int y, int tot) {
        bool ok = isRight(x, y) && a[x][y] == '#' && !map[x][y];
        if (ok) { P.push(x); Q.push(y); map[x][y] = tot; }
    }
    void Destroy(int x, int y) {
        if (isRight(x, y) && a[x][y] == '.')
            map[x][y] = 0;
    }
    int main() {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%s", a + i);
        //1. 找島, 共tot個島
        int tot = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!map[i][j] && a[i][j] == '#') {
                    map[i][j] = ++tot;
                    P.push(i); Q.push(j);
                    while (!P.empty()) {
                        int x = P.front(), y = Q.front();
                        for (int k = 0; k < 4; ++k)
                            BelongIsland(x + f[k], y + g[k], tot);
                        P.pop(); Q.pop();
                    }
                }
            }
        }
    
        //2. 毀島
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (a[i][j] == '#')
                    for (int k = 0; k < 4; ++k)
                        Destroy(i + f[k], j + g[k]);
    
        //3. 找島, 剩余rest個島
        int rest = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (map[i][j] && !isVisit[map[i][j]])
                    { isVisit[map[i][j]] = true; ++rest; }
    
        printf("%d\n", tot - rest);
        return 0;
    }


    第十題: 乘積最大

    給定N個整數A1, A2, ... AN。請你從中選出K個數,使其乘積最大。  
    
    請你求出最大的乘積,由于乘積可能超出整型范圍,你只需輸出乘積除以1000000009的余數。  
    
    注意,如果X<0, 我們定義X除以1000000009的余數是負(-X)除以1000000009的余數。
    即:0-((0-x) % 1000000009)
    
    【輸入格式】
    第一行包含兩個整數N和K。  
    以下N行每行一個整數Ai。  
    
    對于40%的數據,1 <= K <= N <= 100  
    對于60%的數據,1 <= K <= 1000  
    對于100%的數據,1 <= K <= N <= 100000  -100000 <= Ai <= 100000  
    
    【輸出格式】
    一個整數,表示答案。
    
    
    【輸入樣例】
    5 3 
    -100000   
    -10000   
    2   
    100000  
    10000  
    
    【輸出樣例】
    999100009
    
    再例如:
    【輸入樣例】
    5 3 
    -100000   
    -100000   
    -2   
    -100000  
    -100000
    
    【輸出樣例】
    -999999829
    
    
    資源約定:
    峰值內存消耗(含虛擬機) < 256M
    CPU消耗  < 1000ms
    
    
    請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入...” 的多余內容。
    
    注意:
    main函數需要返回0;
    只使用ANSI C/ANSI C++ 標準;
    不要調用依賴于編譯環境或操作系統的特殊函數。
    所有依賴的函數必須明確地在源文件中 #include <xxx>
    不能通過工程設置而省略常用頭文件。
    
    提交程序時,注意選擇所期望的語言類型和編譯器類型。
    

    解析:

    分類討論
    1. 0的個數多于n - k --> 答案為: 0
    2. k % 2 == 1
        (1) 沒有一個正整數
            a. 存在一個0 --> 答案為: 0
            b. 沒有0    --> 答案為: k個最小的負數的乘積 MOD 1000000009
        (2) 存在一個正整數 --> 答案為: 最大的正整數乘于[k / 2](向下取整)對乘積最大的數 MOD 1000000009
    3. k % 2 == 0 --> 答案為: (k / 2)對乘積最大的數 MOD 1000000009
    

    時間復雜度: O(nlogn)

    參考代碼:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn = 100005;
    const int X = 1000000009;
    long long pos[maxn], neg[maxn];
    int k;
    int cntPos = 0, cntNeg = 0, cntZero = 0;
    bool cmp(long long a, long long b) {
        return a > b;
    }
    long long fun() {
        sort(neg, neg + cntNeg);
        sort(pos, pos + cntPos, cmp);
        long long ans = (k % 2) ? pos[0] : 1;
        int i = 0, j = k % 2;
        for (int cnt = 0; cnt < (k >> 1); ++cnt) {
            long long x = 0, y = 0;
            if (i + 1 < cntNeg) x = neg[i] * neg[i + 1];
            if (j + 1 < cntPos) y = pos[j] * pos[j + 1];
            if (x > y) { i += 2; ans = ((x % X) * ans) % X; }
            else { j += 2; ans = ((y % X) * ans) % X; }
        }
        return ans;
    }
    int main() {
        int tmp, n;
        cin >> n >> k;
        for (int i = 0; i < n; ++i) {
            cin >> tmp;
            if (!tmp) ++cntZero;
            else if (tmp > 0) pos[cntPos++] = tmp;
            else neg[cntNeg++] = tmp;
        }
        if (cntZero > n - k) cout << 0 << endl;
        else if (k % 2 && !cntPos) {
            if (cntZero) cout << 0 << endl;
            else {
                sort(neg, neg + cntNeg, cmp);
                long long ans = 1;
                for (int i = 0; i < k; ++i)
                    ans = (ans * neg[i]) % X;
                cout << ans << endl;
            }
        }
        else cout << fun() << endl;
        return 0;
    }
    版權聲明:本文為Dragon_fxl原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/Dragon_fxl/article/details/79884912

    智能推薦

    Unity_Shader高級篇_13.1_Unity Shader入門精要

    13.4 再談邊緣檢測 在12.3中,我們曾使用Sobel算子對屏幕圖像進行邊緣測試,實現描邊的效果。但是,這種直接利用顏色信息進行邊緣檢測的方法會產生很對我們不希望得到的邊緣線,如圖13.8所示。 可以看出,物體的紋理、陰影等位置也被描上黑邊,而這往往不是我們希望看到的。在本節中,我們將學習如何在深度和法線上進行邊緣檢測,這些圖像不會受紋理和光照的影響,而僅僅保存了當前渲染物體的模型信息,通過這...

    Seata AT 模式 原理詳解

    目錄 前提 整體機制 寫隔離 讀隔離 工作機制 一階段 二階段-回滾 二階段-提交 附錄 回滾日志表 前提 基于支持本地 ACID 事務的關系型數據庫。 Java 應用,通過 JDBC 訪問數據庫。 整體機制 兩階段提交協議的演變: 一階段:業務數據和回滾日志記錄在同一個本地事務中提交,釋放本地鎖和連接資源。 二階段: 提交異步化,非常快速地完成。 回滾通過一階段的回滾日志進行反向補償。 寫隔離 ...

    Python爬蟲 | 滑動驗證碼**

    極驗驗證碼:需要手動拼合滑塊來完成的驗證,相對圖形驗證碼識別難度上升了幾個等級。下面用程序識別并通過極驗驗證碼的驗證,其中有分析識別思路、識別缺口位置、生成滑塊拖動、模擬實現滑塊拼合通過驗證等步驟。需要用到Chrome 瀏覽器,并配置 ChromeDriver ,要用到的 Python 庫是 Selenium。 1、 對極驗驗證碼了解   極驗驗證碼官網:http://www.geetest.co...

    MobaXterm root用戶連接虛擬機時出現Access denied

    1.linux打開ssh服務 2.新建連接 首先在romote host中填入要連接的主機ip specify username中填入連接的用戶名 port為連接端口默認為22 輸入連接用戶的密碼 linux默認不顯示密碼 發現密碼正確但是連接不上 問題解決 /etc/ssh/sshd_config 配置問題: #PermitRootLogin prohibit-password將該行改為Perm...

    Linux C 預處理命令

    預處理命令 一、宏定義 C語言標準允許在程序中用一個標識符來表示一個字符串,成為宏。標識符為宏名 ,在編譯預處理時,將程序中所有的宏名用相應的字符串來替換,這個過程稱為宏替換,宏分為兩種:無參數的宏和有參數的宏。 1.無參數的宏 無參數宏定義的一般形式為:#define 標識符字符串 “#”代表本行是編譯預處理命令。define是宏定義的關鍵詞,標識符是宏名。字符串是宏名所...

    猜你喜歡

    有意思的算法(一)----冒泡排序

        冒泡排序的基本思想是:每次比較兩個相鄰的元素,如果它們的順序錯誤就把他們交換過來。     下面舉一個具體的例子來介紹一下冒泡排序。     有12,35,99,18,76五個數進行從大到小的排序,既然是從大到小排序,也就是說越小的越靠后,可不要把這句當成廢話,這可是最關...

    cordova學習筆記_創建一個cordova項目

    環境和工具 webstorm Node.js JDK git 打開git bash,進入你要創建項目的目錄,鍵入以下命令 進入cordovaDemo這個文件夾: 添加Android平臺 cordova platforms add android platforms中已經有了一個Android平臺 下面打開webstorm,然后file - open 找到cordovaDemo打開 現在在webst...

    TensorFlow識別圖片數字

    一、 第一步是先用tensorflow官網(http://www.tensorfly.cn/tfdoc/get_started/introduction.html)的手寫體數字識別例子訓練好一個模型,訓練完準確率一般能達到99%,然后保存訓練好的模型。 二、 主文件 完整代碼地址...

    spring boot項目搭建helloworld(一)

    備注:本文僅限快速啟動spring boot項目(尤其初學者了解spring boot框架) 結果展示: 工具: 編譯器:myeclipse2014  JDK:jdk1.8(1.8以下也可以但不可低于1.5,但會在項目上報小感嘆號(不影響運行)) maven:maven-3.5.3(myeclipse自帶maven也可以,但官網要求3.2或以上) spring boo...

    基于jquery Stellar.js實現 網站視差滾動效果

    stellar.js是一個 jQuery插件,能很容易地給網站添加視差滾動效果。 雖然已經停止了維護,但它非常穩定,與最新版本的jQuery兼容。 http://markdalgleish.com/projects/stellar.js/ 官網 1.引用js 包 2.引用html 3.引用css 4.js函數調用 常用參數:...

    精品国产乱码久久久久久蜜桃不卡