今年廣東省三中游，按New Oj估分，前5題估分17（第1題√，3，4，5題暴力）

第2題（B）dfs寫錯了，第7題（G）并查集，多了個以前沒見過的要求，找不到思路

面向爆零選手

水平有限，將就著看，有空再補(bǔ)充后5題

目錄

??吐槽

??A，2067: [藍(lán)橋杯2023初賽] 幸運(yùn)數(shù)

??B，2068: [藍(lán)橋杯2023初賽] 有獎問答

??AC? DFS

??AC? DP

??C，2069: [藍(lán)橋杯2023初賽] 平方差

??AC? 28%? 暴力

??AC? 92%? O(n)

??AC? 100%? O(1)

??D，2070: [藍(lán)橋杯2023初賽] 更小的數(shù)

??AC? 44%? s.substr

??AC? DP

??AC? 常規(guī)

??E，2071: [藍(lán)橋杯2023初賽] 顏色平衡樹

??AC? 9%? 暴力??

??AC? 按秩合并

??AC? 啟發(fā)式合并

材料

G：并查集，維護(hù)網(wǎng)絡(luò)連通性

?H：異或和之和

??吐槽

先吐槽下，比賽結(jié)束才發(fā)現(xiàn)的技巧 ---- 打表，以前只是知道這個東西，但一直不知道到底是個什么

打表大概就是這么個東西

所謂“暴搜掛著機(jī)，打表出省一”，不是沒道理的，以前的理解還不到位

暴搜就是暴力2層，3層，4層for循環(huán)或者dfs暴力

掛著機(jī)就是程序需要十幾秒甚至幾分鐘才能輸出完（數(shù)據(jù)量大，復(fù)雜度高）

---->?

這么說填空題當(dāng)然可以直接等輸出

編程題也能cout輸出中間過程，然后cout前幾十個數(shù)據(jù)（打表），至少拿30%分，運(yùn)氣好直接靠打表AC也不是沒可能

（所以今年有人靠著打表，做了四五題，哪怕他不會，在看懂樣例的基礎(chǔ)上，就能拿多10~20分）

??A，2067: [藍(lán)橋杯2023初賽] 幸運(yùn)數(shù)

P2067 - [藍(lán)橋杯2023初賽] 幸運(yùn)數(shù) - New Online Judge (ecustacm.cn)

標(biāo)簽：入門題，模擬，枚舉

思路

寫個統(tǒng)計位數(shù)的函數(shù)，保證數(shù)位len % 2 == 0

再寫個計算前半數(shù)位和，以及后半數(shù)位和，判斷相等（這里采取整數(shù)除以(/)，取余(%)的方法）

AC? 代碼

等個5秒才會輸出；；提交時直接cout

#include<iostream>
using namespace std;

int ans, fir, sec, cnt; //fir前半段, sec后半段, cnt當(dāng)前第幾位

//判斷位數(shù)
int lo(int x)
{
    int len = 0;
    while(x) {
        len++;
        x /= 10;
    }
    return len;
}
//判斷前半和后半數(shù)字相加和
void cal(int x)
{
    int y = x;
    while(cnt< lo(y) / 2) {
        fir += x % 10;
        cnt++;
        x /= 10;
    }
    while(cnt < lo(y)) {
        sec += x % 10;
        cnt++;
        x /= 10;
    }
}

int main()
{
    for(int i = 1; i <= 100000000; ++i) {
        fir = 0, sec = 0, cnt = 0;
        cal(i); //得到first和second的值
        if(fir == sec && lo(i) % 2 == 0) { //偶數(shù)且前半 = 后半
            ans++;
        }
    }
    cout<<ans;
    //cout<<4430091;
    return 0;
}

4430091

代碼2? 知識點

to_stirng應(yīng)該也能做，只是代碼跑了5分鐘沒跑出來，就給刪了?

數(shù)字常量（整型，浮點型）轉(zhuǎn)化位字符串，需要用到to_string函數(shù)

如果是 ' ' 里面是單個字符，返回對應(yīng)的ASCII值

(9條消息) C++ to_string()函數(shù)_WeSiGJ的博客-CSDN博客

#include<iostream>
using namespace std;
int main()
{
    string b = to_string('5');
    cout<<b<<endl;
    b = to_string(1 + 10 + 1.5234); //浮點保留6位小數(shù)
    cout<<b<<endl;
    b = to_string('a'); //'a'本就是97, 轉(zhuǎn)化為字符串97而已
    cout<<b<<endl;
    b = to_string(97); 
    cout<<b;
    return 0;
}

53
12.523400
97
97

??B，2068: [藍(lán)橋杯2023初賽] 有獎問答

P2068 - [藍(lán)橋杯2023初賽] 有獎問答 - New Online Judge (ecustacm.cn)

標(biāo)簽：基礎(chǔ)題，深度優(yōu)先搜索，組合數(shù)學(xué)?

當(dāng)時就寫了dfs，還錯了

先分享一下組合數(shù)學(xué)的知識，雖然本題不知道哪里用了組合數(shù)學(xué)

??組合數(shù)學(xué)（來源于Oi-Wiki）

??AC? DFS

詳情看注釋

#include<iostream>
using namespace std;
int ans;

void dfs(int step, int score)
{
    // == 70要放在==100和return;前
    if(score == 70) ans++; //此時不需要return;
    //30題答完或分?jǐn)?shù)達(dá)到100
    if(step == 31 || score == 100) return;
    //分治遞歸
    dfs(step + 1, score + 10); //答對
    dfs(step + 1, 0); //答錯
}

int main()
{
    dfs(1, 0); //第1題, 分?jǐn)?shù)0開始
    cout<<ans;
    return 0;
}

跑個5秒出答案

8335366

DP的方法

本題用dp的話，時間和空間復(fù)雜度都是線性的，效率高，適用于大規(guī)模數(shù)據(jù)的計算

思路

這里我們將每10分變成1分，70分變成7分，100分變成10分，便于計算

1，狀態(tài)確定

dp[i][j]表示第 i 題拿到 j 分的方案數(shù)，30題最多100分 --> 10分，我們聲明 int dp[40][20];

2，遞推式

（1）

由于答錯一題就歸零，不論前面情況如何，7分時，這7分前面一定是 ***** + 錯

（此處*****代表所有情況）（所以答錯一題就繼承上一題所有分?jǐn)?shù)的方案數(shù)和）

然后連續(xù)7題答對，是一種方案數(shù)，dp[i][0] += dp[i - 1][j] (+=是因為，注意看前面描述，“前面所有情況，就是第i - 1題所有得分情況的方案數(shù)的和才是dp[i][0]的方案數(shù)，所以是+=”)

（2）

dp[i][j] = dp[i - 1][j - 1] 則表示第i題答對了，+10分并繼承上一題的方案數(shù)

3，初始化

由遞推式推初始狀態(tài)，顯然，除了dp[0][0]為1，其余設(shè)置為0

因為dp[i][0]表示二維矩陣第1列，也就是每一行第一個都是由上面一行相加得到

而dp[i][j]表示當(dāng) j != 0 時，都是由左上角（i - 1, j - 1）的值得到

dp[0][0] = 1，表示未開始答題且得分為0時，方案數(shù)只有1種

特別解釋下代碼第10，12行

第10行，if(j != 10)，因為dp[i][10]會繼承dp[i - 1][9]的數(shù)據(jù)，當(dāng)分?jǐn)?shù)為100時，會自動停止答題，所以dp[i][10]都應(yīng)該設(shè)為0，如果不用if(j != 10)，第一列的dp[i][0]就會加上上一行第10列的值，進(jìn)而增大了后面dp[i][7]的值，結(jié)果就會偏大

第12行，j != 0為了不超限

??AC? DP

#include<iostream>
using namespace std;
int dp[40][20], ans; //答對一題+1分

int main()
{
    dp[0][0] = 1; //初始化
    for(int i = 1; i <= 30; ++i) //30題
        for(int j = 0; j <= 10; ++j) {//100分
            if(j != 10) //否則j = 10時會得到左上角的方案數(shù)
                dp[i][0] += dp[i - 1][j];
            if(j != 0)
                dp[i][j] = dp[i - 1][j - 1];
        }
    //遍歷每一題70分的方案數(shù)加起來
    for(int i = 0; i <= 30; ++i)
        ans += dp[i][7];
    cout<<ans;
    return 0;
}

8335366

??C，2069: [藍(lán)橋杯2023初賽] 平方差

P2069 - [藍(lán)橋杯2023初賽] 平方差 - New Online Judge (ecustacm.cn)

標(biāo)簽：基礎(chǔ)題，數(shù)論

比賽時暴力了，找了下規(guī)律沒找到

??AC? 28%? 暴力

暴力

#include<iostream>
using namespace std;
int ans;

int main()
{
    int l, r;
    cin>>l>>r;
    for(int k = l; k <= r; ++k) {
        int flag = 0;
        for(int i = 1; i < 3000; ++i) {
            for(int j = 0; j < i; ++j) {
                if(i*i - j*j == k) {
                    flag = 1;
                    ans++;
                    break; //每滿足一次, k就自增
                }
                //剪枝
                if(i*i - (i-1)*(i-1) > k) break;
            }
            if(flag) break; //防止ans重復(fù)自增
        }
    }
    cout<<ans;
    return 0;
}

找規(guī)律

隔1個數(shù)

“容易”發(fā)現(xiàn)1，3，5，7，9......來源于1^2 - 0^2 == 1，2^2 - 1^2 == 3，3^2 - 2^2 == 5......

也就是隔一個數(shù)的平方差可以得到所有奇數(shù)

隔2個數(shù)

“容易”發(fā)現(xiàn)4的倍數(shù)來源于m的平方 - (m - 2)的平方，比如2^2 - 0^2 == 4或者

3^2 - 1^2 == 8或者4^2 - 2^2 == 12...

也就是隔兩個數(shù)的平方差可以得到所有4的倍數(shù)

再一觀察，除了2的倍數(shù)外，是不是齊活了？

因為所有大于0的（奇數(shù) + 偶數(shù)）等于所有正數(shù)（題目中1 <= L <= R）

然后目前得到了所有奇數(shù) + 所有4的倍數(shù)

所以滿足這個條件的x一定是奇數(shù)或者4的倍數(shù)

??AC? 92%? O(n)

數(shù)據(jù)量高達(dá)1e9，顯然就算O(n)也會超時

#include<iostream>
using namespace std;
int main()
{
    int l, r, ans = 0;
    cin>>l>>r;
    for(int i = l; i <= r; ++i) {
        if(i % 2 == 1) ans++; //奇數(shù)
        else if(i % 4 == 0) ans++; //4的倍數(shù)
    }
    cout<<ans;
    return 0;
}

??AC? 100%? O(1)

轉(zhuǎn)化為求[left, right]之間，是2的倍數(shù)不是4的倍數(shù)的個數(shù)ans(wer)，也就是2倍數(shù)的個數(shù) - 4倍數(shù)的個數(shù)

再用[l, r]的個數(shù)(r - l + 1)減去ans即可O(1)，也就不用遍歷了

額外的測試

2 19
9 4
13

3 19
8 4
13

4 19
8 4
12

2 20
10 5
14

AC? 代碼

#include<iostream>
using namespace std;
int main()
{
    int l, r, ans = 0; //ans為不滿足的條件
    cin>>l>>r; 
    int x = r / 2 - (l-1) / 2; //2的倍數(shù)
    int y = r / 4 - (l-1) / 4; //4的倍數(shù)
    ans = x - y; //不滿足條件
    //cout<<x<<" "<<y<<endl;
    cout<<(r - l + 1) - ans; //總數(shù) - 不滿足條件
    return 0;
}

??D，2070: [藍(lán)橋杯2023初賽] 更小的數(shù)

P2070 - [藍(lán)橋杯2023初賽] 更小的數(shù) - New Online Judge (ecustacm.cn)

當(dāng)時也不會，只能用s.substr做了，所幸還挺好做

功能：截取子串

s.substr(i)從下標(biāo)?i?開始到結(jié)尾，s.substr(i, j)從下標(biāo)?i?開始截取?j?個字符

#include<cstring> //s.substr()

string s1 = s.substr(j, i); //下標(biāo)j開始, 截取i個字符
string s2 = s.substr(i); //下標(biāo)i開始，截取到末尾

??AC? 44%? s.substr

比賽時的代碼? -->? 時間超限

#include<iostream>
using namespace std;
int ans;
string s2, s3; //全局變量

//字符串反向函數(shù)
void rever()
{
    for(int i = s2.size() - 1; i >= 0; --i)
        s3 += s2[i];
}

int main()
{
    string s;
    cin>>s;
    for(int i = 0; i < s.size() - 1; ++i)
        for(int j = 2; i + j <= s.size(); ++j) {
            s2 = s.substr(i, j); //原子串
            s3 = ""; //初始化新子串
            rever(); //反向
            if(s3 < s2) ans++;
        }
    cout<<ans;
    return 0;
}

DP? 做法

實際上是區(qū)間dp，還沒學(xué)，但是！dp都一個鳥樣，把四部曲分析清楚就行

（雖然大多數(shù)時候連狀態(tài)都確定不了，或者狀態(tài)確定了，遞推式不會推）

思路

由題目，一個子串反轉(zhuǎn)能否s_new < s，只需要對子串長度和左端下標(biāo)進(jìn)行遍歷

（這就和substr的想法有點像，不過substr每次都要重新比較每一個位置的字符，所以效率低，而動規(guī)直接繼承子問題的數(shù)據(jù)）

右端下標(biāo)可有長度和左端下標(biāo)得出（由題目，顯然長度>=2）

1，

如果發(fā)現(xiàn)左端字符大于右端，顯然這部分子串可以反轉(zhuǎn)，方案數(shù)為1

2，

如果等于，就繼續(xù)往中間遍歷，且方案數(shù)等于下一個下標(biāo)處的方案數(shù)

3，

如果小于，方案數(shù)為0

顯然，子問題重疊，且子問題的最優(yōu)解能代表整個問題的最優(yōu)解，當(dāng)然用動規(guī)

然后注意到數(shù)據(jù)量達(dá)5000，“眾所周知”，32位int全局變量開二維數(shù)組，最大約dp[5050][5050]

直接想到了二維dp，當(dāng)然如果數(shù)據(jù)量增大到1e5

后續(xù)需要轉(zhuǎn)一維，而能否“滾動數(shù)組”，壓到一維，看“當(dāng)前層是否都由上一層推導(dǎo)過來的”

dp四部曲

1，狀態(tài)

dp[l][r]表示區(qū)間[l, r]的子串，也就是子串左端下標(biāo)為l(eft)，右端下標(biāo)為r(ight)

2，遞推式

（1）

if(s[l] > s[r]) dp[l][r] = 1; 表示左端字符 < 右端字符，由于從外向中間遍歷，在這個特定的長度和左右下標(biāo)下，反轉(zhuǎn)滿足方案數(shù)為1

（2）

if(s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1]，向里遍歷，此時判斷不出反轉(zhuǎn)后是否滿足要求，是否滿足取決于下一步

（3）

if(s[l] > s[r]) dp[l][r] = 0，這步可省略，全局變量已經(jīng)初始化為0

3，初始化

考慮到 len（子串長度 len>=2）所以dp[l + 1][r - 1]中的r - 1并不會越界，因為r = l + len - 1

無需特別初始化

4，遍歷方向

一般二維怎么都行，一維得逆序遍歷

??AC? DP

#include<iostream>
using namespace std;
int dp[5010][5010], ans;
int main()
{
    string s;
    cin>>s;
    int n = s.size();
    for(int len = 2; len <= n; ++len) { //len子串長度
        for(int l = 0; l + len <= n; ++l) { //l子串左端下標(biāo)
            int r = l + len - 1; //右端下標(biāo)
            if(s[l] > s[r]) dp[l][r] = 1;
            else if(s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1];
            ans += dp[l][r];
        }
    }
    cout<<ans;
    return 0;
}

??AC? 常規(guī)

2層for循環(huán)遍歷，同時，遇到可以翻轉(zhuǎn)的情況，開始逐層向外遍歷，出現(xiàn)連續(xù)的字符相等的情況，也算一種方案數(shù)

#include<iostream>
using namespace std;

int main()
{
    string s;
    cin>>s;
    int n = s.size(), ans = 0;
    //遍歷
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j) {
            if(s[i] <= s[j]) continue;
            ans++; //反轉(zhuǎn)符合要求
            //翻轉(zhuǎn)后, 外層連續(xù)的相等也符合
            for(int k = 1; i - k >= 0 && j + k < n; ++k) {
                if(s[i - k] == s[j + k]) //由里向外遍歷
                    ans++;
                else
                    break; //剪枝
            }
        }
    cout<<ans;
    return 0;
}

??E，2071: [藍(lán)橋杯2023初賽] 顏色平衡樹

標(biāo)簽：進(jìn)階題，啟發(fā)式合并

比賽時暴力了，下面我展示當(dāng)時暴力的代碼和AC代碼

AC代碼主要2種，一是并查集路徑壓縮 + 按秩合并，而是啟發(fā)式合并(dsu on tree)

啟發(fā)式合并有模板的

??AC? 9%? 暴力??

15 * 0.09 = 1.35（時間超限），四舍五入 = 1分？？？？考場上就1分??

#include<iostream>
#include<cstdio> //scanf()
#include<algorithm> //sort()
#include<cstring> //memset()
using namespace std;
int vis[200010];

struct node
{
    int color, fa; //顏色和父節(jié)點
}a[200010];
bool cmp(node x, node y)
{
    return x.fa < y.fa; //按父節(jié)點從小到大排序
}

int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].color, &a[i].fa);
    sort(a, a + n, cmp);
    //暴力每個節(jié)點的子樹
    for(int i = 0; i < n; ++i) {
        int u = 0, flag = 1;
        memset(vis, 0, sizeof(vis));
        for(int j = i; j < n; ++j) {
            vis[a[j].color]++;
            u = max(u, a[j].color); //出現(xiàn)過顏色中的最大值
        }
        for(int k = 1; k <= u; ++k)
            if(vis[k] != 0 && vis[k] != vis[u]) {
                flag = 0;
                break;
            }
        if(flag) ans++;
    }
    cout<<ans;
    return 0;
}

關(guān)于為什么用啟發(fā)式合并，而不是直接暴力，比如

如果是第一種情況，暴力也沒問題，但是第二種情況

讓大的集合向小的集合合并，時間復(fù)雜度就會很高

知識點

下面講講啟發(fā)式合并

→?樹上啟發(fā)式合并 - OI Wiki (oi-wiki.org)

→?并查集復(fù)雜度 - OI Wiki (oi-wiki.org)

→?DSU on Tree入門 - TheLostWeak - 博客園 (cnblogs.com)

→?(18條消息) 并查集（按秩合并+路徑壓縮）基礎(chǔ)講解_并查集按秩合并_夜幕而已的博客-CSDN博客

每次合并時，都將較少元素的集合合并至較多元素的集合

當(dāng)一個元素轉(zhuǎn)移到另一個集合，新集合的大小至少是原集合2倍

所以一個元素最多被插入logn次，單個元素對時間復(fù)雜度的貢獻(xiàn)為O(logn)

n個元素的時間復(fù)雜度就為O(nlogn)

補(bǔ)充

1，子節(jié)點：根節(jié)點以外的其他節(jié)點

2，重兒子：子節(jié)點重，子樹大小最大的節(jié)點

代碼實現(xiàn)

最常見的是并查集的按秩合并，元素少的集合合并到元素多的集合上，以減少樹的深度

其中秩指的是以某個節(jié)點為根的子樹的深度，或者說高度

const int N = 10010;
int dad[N], deep[N];
//初始化
void init()
{
    for(int i = 0; i < N; ++i) {
        dad[i] = i; //自己是自己的爸爸
        deep[i] = 1; //初始深度都是1
    }
}
//找爸爸
int Find(int x)
{
    if(x != dad[x])
        return dad[x] = Find(dad[x]); //記得return
}
//合并
void join(int x, int y)
{
    int xx = Find(x), yy = Find(y);
    if(xx != yy) {
        if(deep[xx] > deep[yy])
            dad[yy] = xx; //xx更大
        else {
            dad[xx] = yy; //yy更大
            if(deep[xx] == deep[yy])
                deep[xx]++; //隨便一個深度+1
        }
    }
    Find(yy); //路徑壓縮優(yōu)化
}

解釋

疑問1：為什么每次深度只+1呢，如果深度多了更多，不應(yīng)該加更多嗎？?

按秩合并算法中deep[]記錄的不是節(jié)點所在樹的實際深度，而是根據(jù)當(dāng)前節(jié)點的子樹大小估計出來的一個“秩”(rank)，用于優(yōu)化合并操作的效率

具體就是，deep[]越大，其子樹包含的節(jié)點數(shù)越多

這里有道（啟發(fā)式 或?按秩）合并都能做的例題，先放這了??

P3201 [HNOI2009] 夢幻布丁 - 洛谷 | 計算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)

不掙扎了，作業(yè)4天沒寫了，今晚2個ddl，下午還得足球裁判，晚上3節(jié)線代，先這樣吧！文章來源地址http://www.zghlxwxcb.cn/news/detail-414146.html

??AC? 按秩合并

bla...

??AC? 啟發(fā)式合并

bla...

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