題目鏈接在此??：第 1 場算法雙周賽 - 藍(lán)橋云課
為什么只有前5道題的題解呢？（懂的都懂~??）

第一題 三帶一

考察：簡單邏輯判斷

問題描述

小藍(lán)和小橋玩斗地主，小藍(lán)只剩四張牌了，他想知道是否是“三帶一”牌型。
所胃三帶一”牌型，即四張手牌中，有三張牌一樣，另外一張不與其他牌相同，換種說法，四張手牌經(jīng)過重新排列后，可以組成 AAAB型

輸入格式

第一行輸入一個整數(shù)T，代表斗地主的輪數(shù)。
接下來T行，每行輸入一個長度為 4的字符串，代表小藍(lán)的手牌。
字符{'A’,’2’,‘3’,’4’,’5’,’6’,’7’,’8’,’9,’X’,’J’,’Q’,’K’}對應(yīng)代表牌面{A,2,3,4,5,6,7,8,9,10,J,Q,K}。
牌面中不包含大小王。

輸出格式

輸出行，每行一個字符串，如果當(dāng)前牌是“三帶一”牌型，輸出 Yes，否則輸出 No。

樣例輸入

AAAA
33X3
JQKX
6566
KKKQ

樣例輸出

No
Yes
No
Yes

說明

“四炸”牌型不屬于“三帶一”牌型。

評測數(shù)據(jù)范圍

數(shù)據(jù)范圍：$1\le T\le 50$。

字符中只包含:{A,2,3,4,5,6,7,8,9,X,J,Q,K}。

解題思路

第一題很簡單，就是一個基本的邏輯判斷，小細(xì)節(jié)就是對字符串排序可以減少判斷量

代碼

#include <bits/stdc++.h>
using namespace std;

int t;
string s;
signed main() {
    cin >> t;
    while (t--) {
        cin >> s;
        sort(s.begin(), s.end()); // 使其有序
        if (s[0] != s[3] && s[1] == s[2] && (s[0] == s[1] || s[2] == s[3])) cout << "Yes" << endl; // 說明是三帶一
        else cout << "No" << endl;
    }    
    return 0;
}

第二題 數(shù)樹數(shù)

考察：二叉樹

問題描述

小藍(lán)最近學(xué)了二又樹，他想到了一個問題。
給定一個層數(shù)為n的滿二叉樹，每個點編號規(guī)則如下：

具體來說，二叉樹從上向下數(shù)第p 層，從左往右編號分別為：$1,2,3,\mathrm{4...}{2}^{p?1}$。
小藍(lán)給你一條從根節(jié)點開始的路徑，他想知道到達(dá)的節(jié)點編號是多少。
例如: 路徑是right - left，那么到達(dá)的節(jié)點是1-2-3，最后到了三號點，如下圖所示。

輸入格式

第一行輸入兩個整數(shù)n,q，n 表示完全二樹的層數(shù)， q代表詢問的路徑數(shù)量。
接下來q 行，每行一個字符串 S，S 只包含字符{‘L’, ’R’}，’L’ 代表向左，’R’ 代表向右。

輸出格式

輸出q行，每行輸出一個整數(shù)，代表最后到的節(jié)點編號。

樣例輸入

3 6
R
L
LL
LR
RL
RR

樣例輸出

2
1
1
2
3
4

說明

$2\le n\le 20,1\le q\le 10^3,1\le |S|\le n$
完全二叉樹：一個二叉樹，如果每一個層的結(jié)點數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。
也就是說如果一個二叉樹的層數(shù)為 $k$，且節(jié)點總數(shù)是$2^k?1$，則它就是滿二又樹。

解題思路

考察的是二叉樹的性質(zhì)
順序遍歷路徑S，用一個變量記錄到達(dá)的節(jié)點的id。節(jié)點id的編排規(guī)則：

再用id的值來計算目前所在的行數(shù)和列數(shù)。
如何用id來計算目前處于第幾行的第幾個節(jié)點呢？（這里用x代表id）
$$\begin{gathered} 行數(shù)=?lo{g}_{2}x?+1(?x?表示對x向下取整) \\ 列數(shù)=x?2^{行數(shù)}+1 \end{gathered}$$
~請讀者自行證明??

代碼

#include <bits/stdc++.h>
using namespace std;

int n, q;
string s;
signed main() {
    cin >> n >> q;
    while (q--) {
        cin >> s;
        int id = 1;
        for (char& i : s) { // 遍歷字符串
            if (i == 'L') res *= 2; // 向左子節(jié)點走 -> id乘以2
            else res = res * 2 + 1; // 向右子節(jié)點走 -> id乘以2再加一
        }
        cout << res - (1 << (int)log2(res)) + 1 << endl; // 利用公式輸出結(jié)果
    }
    return 0;
}

第三題 分組

考察：二分答案

問題描述

藍(lán)橋小學(xué)要進(jìn)行彈彈球游戲，二年級一班總共有 n 個同學(xué)，要求分成 k 個隊伍，由于彈彈球游戲要求隊員
的身高差不能太大，小藍(lán)是班長，他對這個事情正在發(fā)愁，他想問你，如何最小化每個組之間的身高極差。
具體的，假設(shè)分成了 k 個組，第 i 組最高的人身高是 $H_{x_i}$，最矮的是 $H_{n_i}$，你被要求最小化表達(dá)式：
$max(H_{t_i}?H_{n_i}),1\le i\le k$。直白來說，你需要將 n 個元素分出 k 組，使得最大的極差盡可能小。你需要輸出這
個最小化化后的值。

輸入格式

第一行輸入兩個整數(shù)n, k。
第二行輸入n 個整數(shù): $h_1,h_2,h_3...h_n$，分別代表 n 個人的身高

輸出格式

輸出一個整數(shù)，代表最小值。

樣例輸入

5 3
8 4 3 6 9

樣例輸出

1

說明

樣例分組情況：{3, 4}, {6}, {8, 9}。

評測數(shù)據(jù)規(guī)模

數(shù)據(jù)范圍: $1\le k\le n\le 10^5,1\le h_i\le 10^9$

解題思路

二分答案其實就是二分+貪心
（不知道為什么出題人總是愛考二分答案~，這種題都有一個特征：要么就是最小值最大化，要么就是最大值最小化，符合某種單調(diào)性）
首先，每一個分組都是身高盡可能接近的同學(xué)，可以證明：每一個分組都是排好序后的連續(xù)的幾位~（因為如果不是這樣，每一組的最大身高差只會增，不會減，最多保持不變）
然后就好說了，先排序，排完序后二分最大身高值，雙指針遍歷數(shù)組（對其分組），如果超過了最大值，就分組加一，如果分組超過了k，說明不行。

代碼

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int n, k, h[N];
bool check(int x) { // 經(jīng)典check函數(shù)（懂的都懂)
    int c = 1; // 分組數(shù)
    for (int l = 0, r = 1; r < n; r++) { // 雙指針
        if (h[r] - h[l] > x) { // 分組結(jié)果是[l, r)
            c++;
            l = r;
            if (c > k) return false; // 需要的分組數(shù)大于k了，不滿足條件
        }
    }
    return true; // 滿足
}
signed main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> h[i];
    sort(h, h + n); // 排序
    int l = 0, r = 1e9; // 二分
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1; // 注意是mid + 1，不然會死循環(huán)
    }
    cout << l; // 結(jié)果
    return 0;
}

第四題 健身

考察：完全背包DP

問題描述

小藍(lán)要去健身，他可以在接下來的 1 ~ n 天中選擇一些日子去健身
他有 m 個健身計劃，對于第 i 個健身計劃，需要連續(xù)的 $2^k$ 天，如果成功完成，可以獲得健身增益$s_i$，如果中斷，得不到任何增益。
同一個健身計劃可以多次完成，也能多次獲得健身增益，但是同一天不能同時進(jìn)行兩個或兩個以上的健身計劃。
但是他的日程表中有 q 天有其他安排，不能去健身，問如何安排健身計劃，可以使得 n 天的健身增益和最大。

輸入格式

第一行輸入三個整數(shù)n,m,q
第二行輸入q個整數(shù)，$t_1,t_2,t_3...t_q$，代表有其他安排的日期
接下來 m 行，每行輸入兩個整數(shù) $k_i,s_i$。代表該訓(xùn)練計劃需要 $2^{k_i}$天，完成后可以獲得 $s_i$的健身增益

輸出格式

一個整數(shù)，代表最大的健身增益和。

樣例輸入

10 3 3
1 4 9
0 3
1 7
2 20

樣例輸出

30

說明

在樣例中2 - 3天進(jìn)行計劃2，5 - 8天進(jìn)行計劃3，10~10天進(jìn)行計劃1。

評測數(shù)據(jù)范圍

解題思路

首先，根據(jù)題意，我們不難發(fā)現(xiàn)必須在有安排的日子的空隙時間來健身，而在這段空隙時間，我們選擇健身項目來健身，對于每一個項目，有時間$2^{k_i}$和收益$s_i$
聰明的小伙伴可能已經(jīng)發(fā)現(xiàn)，這就是一個背包dp問題
由于健身計劃可以重復(fù)多次，所以是完全背包問題，然后用滾動數(shù)組來優(yōu)化空間。
由于要多次dp計算，可以用一個額外數(shù)組記憶化來保存

代碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 5, M = 55;
ll n, m, q, t[N], k[M], s[M];
ll dp[N], mem[N]; // 記憶化數(shù)組
ll calc(int x) { // dp
    memset(dp, 0, n << 2);
    for (int i = 0; i < m; i++)
        for (int j = k[i]; j <= x; j++) { // 從小到大就是完全背包，從大到小是01背包~
            if (dp[j - k[i]] + s[i] > dp[j])
                dp[j] = dp[j - k[i]] + s[i];
        }
    return dp[x];
}
signed main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++) cin >> t[i];
    for (int i = 0; i < m; i++) {
        cin >> k[i] >> s[i];
        k[i] = 1 << k[i]; // 需要花費的時間
    }
    t[q + 1] = n + 1; // 不遺漏最后的空隙時間
    ll res = 0;
    for (int i = 1; i <= q + 1; i++)
        if (t[i] - t[i - 1] - 1 >= 1) { // 有空隙時間
            if (!mem[t[i] - t[i - 1] - 1])
            	mem[t[i] - t[i - 1] - 1] = calc(t[i] - t[i - 1] - 1); // 記憶化
            res += mem[t[i] - t[i - 1] - 1];
        }
    cout << res;
    return 0;
}

Very important?。?！

一定要開long long！一定要開long long！一定要開long long！

第五題 契合匹配

考察：KMP

問題描述

小藍(lán)有很多齒輪，每個齒輪的凸起和凹陷分別用一個字符表示，一個字符串表示一個齒輪

如果兩個齒輪的對應(yīng)位分別是同一個字母的大小寫，我們稱這兩個齒輪是契合的
例: AbCDeFgh 和 aBcdEfGH 就是契合的，但是 abc 和 aBC 不是契合的
這天，小藍(lán)的弟弟小橋從抽屜里拿來了兩個齒輪，小藍(lán)想知道，這倆個齒輪是不是契合的。
特別需要注意的是，齒輪是環(huán)形的，所以是可以旋轉(zhuǎn)的(順時針和逆時針均可)，如果是契合的，小藍(lán)還想
讓你告訴他，最少將第一個齒輪旋轉(zhuǎn)多少位，兩個齒輪可以完全契合在一起
例如: AbbCd 與BcDaB，在將第一個齒輪逆時針旋轉(zhuǎn)兩位后，變成 bCdAb ，兩個齒輪就完全契合在一起了

輸入格式

第一行輸入一個正整數(shù)n，代表兩個齒輪的長度
第二行輸入一個長度為的字符串S，代表第一個齒輪
第三行輸入一個長度為n的字符串T，代表第二個齒輪

輸出格式

第一行輸出一個字符串: Yes 或者 No 。代表兩個齒輪是否契合
如果可以契合，第二行輸出一個整數(shù)，代表需要旋轉(zhuǎn)的位數(shù)。
如果不可以契合，不用多余輸出。

樣例輸入

5
AbbCd
BcDaB

樣例輸出

Yes
2

評測數(shù)據(jù)范圍

數(shù)據(jù)范圍: $1\le n\le 10^6$
保證字符串只包含大小寫字母

解題思路

這題就是判斷T是不是S的循環(huán)同構(gòu)串，沒什么其它好說的，就是很明顯的KMP，直接把模板拿過來用就行了~??
要注意順時針和逆時針旋轉(zhuǎn)都可以，所以從兩種轉(zhuǎn)法中取最小值

代碼

#include <bits/stdc++.h>
using namespace std;

int n;
string s, t;
int Next[1000010]; // Next[i]：以第i個字符結(jié)尾的前綴字符串的最大前后綴字符串長
void getFail(string& p) {
    int plen = p.length();
    Next[1] = Next[0] = 0;
    for (int i = 1; i < plen; i++) {
        int j = Next[i];
        while (j && p[i] != p[j]) j = Next[j];
        Next[i + 1] = p[i] == p[j] ? j + 1 : 0;
    }
}
int kmp(string& s, string& p) {
    int slen = s.length(), plen = p.length();
    int j = 0;
    for (int i = 0; i < slen; i++) {
        while (j && abs(s[i] - p[j]) != 32) j = Next[j]; // 注意匹配的條件
        if (abs(s[i] - p[j]) == 32) j++; // 這里也是
        if (j == plen) return i - j + 1;
    }
    return -1;
}
signed main() {
    cin >> n >> s >> t;
    s += s; // 在尾部再加上一個s后，s的循環(huán)同構(gòu)串就會出現(xiàn)在新的s中
    getFail(t);
    int res = kmp(s, t);
    if (res != -1) cout << "Yes" << endl << min(res, n - res); // 注意順時針和逆時針旋轉(zhuǎn)都可以
    else cout << "No";
    return 0;
}

比賽總結(jié)

前兩道題還算比較順利，但是到了后面瘋狂出錯??，害，都習(xí)慣了
第三題是check函數(shù)寫錯了，兩次都沒檢測出來
第四題剛開始超時了幾次，因為忘了完全背包怎么寫了，用多重背包的思路做的，后面因為沒開long long，又錯了好幾次，有一個地方?jīng)]開long long都不行，唉~，C++永遠(yuǎn)的坑（老是檢查不出來）
第五題是因為沒注意正著轉(zhuǎn)和反著轉(zhuǎn)都行。。。錯了兩次
排名就這樣了，我太菜了??
有什么問題歡迎在評論區(qū)留言~文章來源地址http://www.zghlxwxcb.cn/news/detail-717020.html

到了這里，關(guān)于藍(lán)橋杯 第一場算法雙周賽題解（前五題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！