30个题型+代码(冲刺2023蓝桥杯)(上)

最新消息：未更新的题型不会更新在这篇博客，但是会更新在专栏新的文章里。

愿意的可以跟我一起刷，每个类型做1~5题 ，4月前还可以回来系统复习 

AcW需要付费的题，可以考虑上洛谷，New Oj找替代，或者花点钱

目录

🍎注意

🌼前言

🌼一，前缀和

👊（一）3956. 截断数组

🌳Time Limit Exceeded 

🌳Accpted

👊（二）[NewOJ Week 1] 前缀和的因子数

👊（三）P4702 取石子

👊（四）P3056 [USACO12NOV]Clumsy Cows S

🌳栈  AC  12%

🌳栈  AC  75%

🌳栈  AC  100%

🌳前缀和  AC  100%

👊（五）P1147 连续自然数和

🌳AC  56%

🌳AC  100%

 👊（六）P6568 [NOI Online #3 提高组] 水壶

🌼二，差分

👊（一）AcWing 3729. 改变数组元素

👊（二）P2367 语文成绩

👊（三）P8772 [蓝桥杯 2022 省 A] 求和

👊（四）1882: 中位数 II

🌼三，二分

👊（一）1460. 我在哪？

👊（二）1101: 花费（未理解）

👊（三）1137: 灯泡的高度

🌳AC  模板

👊（四）P1918 保龄球

🌼四，双指针（尺取法）

👊（一） 3768. 字符串删减

👊（二） 2008: 三数之和

🌳AC  50%  暴力

🌳AC  100%

👊（三）1373: [蓝桥杯2018初赛]日志统计

🌳AC  38%（大坑！）

🌳AC  100%

🌼五，递推

👊（一）3777. 砖块 

👊（二） 1428: [蓝桥杯]翻硬币

🌼六，递归

👊（一） 1497. 树的遍历

🌳Wrong Answer 

🌳Accpted  加个if

🌳Accpted  map迭代器 

👊（二）P1427 小鱼的数字游戏

👊（三）P3152 正整数序列

👊（四）1103: 地盘划分

👊（五）1104: 分形图

🌼七，并查集

👊（一）1249. 亲戚

👊（二） P8654 [蓝桥杯 2017 国 C] 合根植物

👊（三）P1111 修复公路

🌳AC  10%（常犯错误）

🌳AC  100%

👊（四）2006: 连通图

🌼八，哈希

👊（一）2058. 笨拙的手指

🌳Wrong Answer

🌳Accpted

👊（二）P2957 [USACO09OCT]Barn Echoes G

🌳AC  s.substr()

🌳AC  哈希

👊（三）P3370 【模板】字符串哈希

🌼九，单调队列（留坑）

🍋总结 

🍎注意

写完第8个题型已经32747字了，卡得写不动了，敲完一行字等10秒才显示

每10个题型写一个博客，分为上中下三个博客，12万字收尾

后续再补充剩下两个博客地址

(中) 30个题型+代码(冲刺2023蓝桥杯)(中)_码龄?天的博客-CSDN博客

(下) (2条消息) 30个题型+代码(冲刺2023蓝桥杯)(下)_千帐灯无此声的博客-CSDN博客

🌼前言

前缀和√，差分√，二分√，双指针√，递归√，递推√，BFS√，DFS√，Dijkstra√, Floyd√，质数筛，最大公约数，背包dp，线性dp，区间dp，组合计数，快速幂，哈希√，并查集√，博弈论 

每个类型第一题来自AcWing蓝桥杯集训-每日一题

1，花5块钱

2，上洛谷找替代 / 原题 

题型有

前缀和，差分，二分，双指针，递推，递归，并查集，哈希，单调队列，
KMP，Trie，BFS，DFS，拓扑排序，Dijkstra，Floyd，最小生成树，
最近公共祖先，二分图，筛质数，最大公约数，快速幂，组合计数，博弈论，
背包DP，线性DP，区间DP，树型DP，树状数组，线段树，矩阵乘法 

如果你想冲省一，拿22年A组为例，你得拿60分，也就是2道填空题 + 4道编程题

5 + 5 + 10 + 10 + 15 + 15

省赛需要掌握的有：

前缀和，差分，二分，双指针，递归，递推，BFS，DFS，Dijkstra, Floyd，质数筛，最大公约数，背包dp，线性dp，区间dp，组合计数，快速幂，哈希，并查集，博弈论

围绕省赛需要掌握的类型，针对性地下手

先给大家看个时间复杂度（来源于AcWing）

🌼一，前缀和

👂 多年后再见你 - 乔洋/周林枫 - 单曲 - 网易云音乐

→ 前缀和 & 差分 - OI Wiki (oi-wiki.org)

👊（一）3956. 截断数组

3956. 截断数组 - AcWing题库

类型：枚举，前缀和，中等

还有个坑，虽然10^5 * 10^4 < int，但是由于存在1e5个0的情况，这时答案约等于1e10，就会爆int，所以ans还是开long long 

按着思路枚举，将数组分为3部分，中间部分左边界i游标，右边界j游标

然后在过了所有样例的基础上，再想2组测试，可以就提交

两组测试 

8
7 2 3 2 1 3 10 14
1

7
3 -2 1 5 -3 4 -2
1

🌳Time Limit Exceeded 

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int a[100010], n;
bool check(int i, int j) //i左游标, j右游标
{
    int sum1 = 0, sum2 = 0, sum3 = 0;
    for(int m = 0; m < n; ++m) {
        if(m < i)
            sum1 += a[m];
        else if(m >= i && m <= j)
            sum2 += a[m];
        else
            sum3 += a[m];
    }
    if(sum1 == sum2 && sum2 == sum3)
        return true;
    else
        return false;
}
int main()
{
    int i, j;
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
        scanf("%d", &a[i]); //读入数据
    int ans = 0; //截断方法数量
    for(i = 1; i < n - 1; ++i) //枚举中间部分
        for(j = i; j < n - 1; ++j) {
            if(check(i, j)) ans++;
        }
    cout<<ans;
    return 0;
}

当n = 100000，直接暴力会超时，下面是优化

第一次接触前缀和，本题注意几个点

1，ans开long long

2，三部分都非空

3，数据达到1e5，所以复杂度O(n^2)暴力枚举不行，至少得O(nlogn)

4，代码第17，18行，s[i]表示第一部分前缀和，s[i + 1]表示第二部分前缀和

补充一组测试

8
1 0 1 0 0 0 0 1
10

🌳Accpted

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int s[100010];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) { //从1开始读入
        scanf("%d", &s[i]);
        s[i] += s[i - 1]; //前缀和, s[i]表示前i项的和
    }
    long long cot = 0, ans = 0; //截断方法数量
    if(s[n] % 3 != 0) cout<<0;
    else {
        for(int i = 1; i <= n - 2; ++i) { //整个数组下标从1到n
            if(s[i] == s[n] / 3) cot++; //
            if(s[i + 1] == s[n] / 3 * 2) ans += cot; //
        }
        cout<<ans;
    }
    return 0;
}

解释：cot先自增，ans再加上cot，cot表示第一部分满足三等分的数量，ans表示既满足第一部分三等分，又满足第三部分三等分的情况

👊（二）[NewOJ Week 1] 前缀和的因子数

 P1791 - [NewOJ Week 1] 前缀和的因子数 - New Online Judge (ecustacm.cn)

分类：基础题，欧拉，数论，前缀和 

细心是关键

1，前缀和怎么求要会

2，因数怎么求要会

3，i, j游标别搞反了

AC  代码

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int s[100010];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1;; ++i) {
        s[i] = i;
        s[i] += s[i - 1]; //前缀和
        int sum = 0;
        for(int j = 1; j * j <= s[i]; ++j) { 
            if(s[i] % j == 0 && j * j != s[i])
                sum += 2; //求因数
            else if(s[i] % j == 0 && j * j == s[i])
                sum++;
        }
        if(sum > n) {
            cout<<s[i];
            break;
        }
    }
    return 0;
}

👊（三）P4702 取石子

P4702 取石子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

类型：前缀和，入门

一看，感觉好难，为什么才入门。。看了眼题解。。

确实入门，纯前缀和，只是前面加了个类似贪心的判断

→想要分出输赢，石子必须取完

为什么呢？因为“a0视为0”，所以。。显而易见

AC  代码

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int s[100010];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }
    if(s[n] % 2 == 0) cout<<"Bob";
    else cout<<"Alice";
    return 0;
}

👊（四）P3056 [USACO12NOV]Clumsy Cows S

P3056 [USACO12NOV]Clumsy Cows S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大概意思就是，输入偶数长度的括号，最少修改多少次，使左右匹配，也就是都朝里

第一次我用栈做(4条消息) C++ STL 之stack_buyizhu021的博客-CSDN博客_stack赋值

🌳栈  AC  12%

#include<iostream>
#include<stack> //st.push(), st.pop(), st.top()
using namespace std;
string s;
int main()
{
    stack<char>st;
    cin>>s;
    for(int i = 0; i < s.size(); ++i) {
        if(st.size() == 0)
            st.push(s[i]); //元素不足2个
        else if(st.size() >= 1) {
            if(st.top() == '(' && s[i] == ')') {
                st.pop(); //如果栈顶元素和新的元素匹配
            }
            else
                st.push(s[i]); //不匹配就把新的元素入栈
        }
    }
    cout<<st.size();
    return 0;
}

原来是忘记对结果分类讨论了

如果最后剩下 ))(( 或者 ((((，都需要2次；而剩下 )((( 需要3次

🌳栈  AC  75%

#include<iostream>
#include<stack> //st.push(), st.pop(), st.top()
using namespace std;
string s;
int main()
{
    stack<char>st;
    cin>>s;
    for(int i = 0; i < s.size(); ++i) {
        if(st.size() == 0)
            st.push(s[i]); //元素不足2个
        else if(st.size() >= 1) {
            if(st.top() == '(' && s[i] == ')') {
                st.pop(); //如果栈顶元素和新的元素匹配
            }
            else
                st.push(s[i]); //不匹配就把新的元素入栈
        }
    }
    //分类讨论
    int a = 0, b = 0;
    for(int i = 0; i <st.size(); ++i) {
        if(s[i] == ')') a++;
        if(s[i] == '(') b++;
    }
    int c = min(a, b) + (max(a, b) - min(a, b)) / 2;
    cout<<c;
    return 0;
}

找到问题了，第23，24行，应该用st[i]代替s[i]，无奈栈没有这种用法，应该改用st.top(), st.pop()来操作

🌳栈  AC  100%

#include<iostream>
#include<stack> //st.push(), st.pop(), st.top()
using namespace std;
string s;
int main()
{
    stack<char>st;
    cin>>s;
    for(int i = 0; i < s.size(); ++i) {
        if(st.size() == 0)
            st.push(s[i]); //元素不足2个
        else if(st.size() >= 1) {
            if(st.top() == '(' && s[i] == ')') {
                st.pop(); //如果栈顶元素和新的元素匹配
            }
            else
                st.push(s[i]); //不匹配就把新的元素入栈
        }
    }
    //分类讨论
    int a = 0, b = 0;
    while(!st.empty()) {
        if(st.top() == ')') {
            a++;
            st.pop();
        }
        else if(st.top() == '(') {
            b++;
            st.pop();
        }
    }
    int c;
    if(a % 2 == 1) c = 2 + (a + b - 2) / 2;
    else c = (a + b) / 2;
    cout<<c;
    return 0;
}

补充

有同学说他不理解最后这几行

我来解释一下，首先，经过前面stack的操作，左右匹配的括号全部没了

然后a统计朝左的括号，b统计朝右的括号，我们分2种情况讨论，看图

显而易见，可能存在的，最多只有一组 ")("，需要操作2次才能匹配

其他的不论是"(("还是"))"，都只需要1次操作就能匹配

当 a % 2 == 1

a或b是奇数，此时存在1组需要操作2次的

所以 c = (a + b - 2) / 2 + 2，表示 (总数 - 那一组的2个括号) / 2，这部分是一次操作的，所以➗2

+2则是加上唯一的")("，需要2次操作

当 a % 2 == 0 

此时不存在需要操作2次的一组括号，所有括号都是"))(("或者"))))"这样的，1次操作就能让2个括号匹配，所以只用➗2 

------------ 

常犯错误了，栈就要用栈的表达，不要老想着什么st[i]，日后多多复盘

#include<stack>
int main()
{
    stack<char>st;
    st.push();
    st.top();
    st.pop();
    if(!st.empty())
    ......
    
    return 0;
}

🌳前缀和  AC  100%

说实话，怎么用前缀和我没想清楚，不过你可以用))((, ((((, ))))三个例子去模拟以下就知道了

#include<iostream>
using namespace std;
string s;
int main()
{
    cin>>s;
    int m = 0, n = 0;
    for(int i = 0; i < s.size(); ++i) {
        if(s[i] == '(') m++;
        else m--;
        if(m == -1) {
            n++;
            m = 1;
        }
    }
    cout<<n + m / 2;
    return 0;
}

👊（五）P1147 连续自然数和

P1147 连续自然数和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：普及-，前缀和，双指针 

真的就前缀和 + 双指针

🌳AC  56%

最后三个样例TLE(Time Limit Exceeded)超时了 

想法是，把第8，9行代码去掉，放到第二部分里算前缀和，这样就少一个O(n)的复杂度

毕竟题目是2e6的数据？

#include<iostream>
using namespace std;
int s[10010];
int main()
{
    int n, i, j;
    cin>>n;
    for(i = 1; i <= 10010; ++i)
        s[i] = i + s[i - 1]; //前缀和
    for(i = 0, j = 2; i <= n / 2;) {
        if(s[j] - s[i] == n) {
            cout<<i + 1<<" "<<j<<endl;
            i++; //漏了会无限循环
        }
        if(s[j] - s[i] > n) //尺取法
            i++; //左指针
        if(s[j] - s[i] < n)
            j++; //右指针
    }
    return 0;
}

我们用sum代替前缀和的差值，注意 sum += j 和 sum -= i 与 j++ 和 i++ 的相对位置关系

🌳AC  100%

#include<iostream>
using namespace std;
int s[10010];
int main()
{
    int n, i, j, sum = 3;
    cin>>n;
    for(i = 0, j = 2; i <= n / 2;) {
        if(sum == n) {
            cout<<i<<" "<<j<<endl;
            sum -= i;
            i++; //漏了会无限循环
        }
        if(sum > n) {//尺取法
            sum -= i;
            i++; //左指针
        }
        if(sum < n) {
            j++; //右指针
            sum += j;
        }
    }
    return 0;
}

 👊（六）P6568 [NOI Online #3 提高组] 水壶

P6568 [NOI Online #3 提高组] 水壶 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：贪心，前缀和，NOI，普及-

思路

1，贪心：显而易见，要让某个水壶里的水最多，由题意，就是让一个长度k + 1的连续区间

的总水量最大

2，所以，维护一个长度为k + 1的区间，遍历得到最大值

3，所以需要前缀和

4，10^6的数据量，单个数据最大10^3，所以int不会超限，数组大小开到1000010

5，数据量较大，考虑用scanf()读入

额外测试

8
3
100 200 300 1000 150 200 360 1010
1720

AC  代码

#include<iostream>
#include<cstdio> //scanf()
using namespace std;
int n, k, ans, a[1000010];
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]); //下标从0开始
    //维护一个长度为k + 1的连续区间, 通过前缀和找到该区间最大值sum
    int sum = 0, cnt = 0;
    for(int i = 0; i < n; ++i) {
        cnt++;
        sum += a[i];
        if(cnt == k + 1) { //第k + 1个元素
            ans = max(ans, sum); //更新最大值
            sum -= a[i - k];
            cnt--;
        }
    }
    cout<<ans;
    return 0;
}

🌼二，差分

👂  自在的少年 - 要不要买菜 - 单曲 - 网易云音乐

→ 差分算法介绍_木木夕夕山的博客-CSDN博客_差分算法 

→ (1条消息) 算法笔记（六）：差分法_G鸦青的博客-CSDN博客_差分法 

→ 前缀和 & 差分 - OI Wiki (oi-wiki.org)

→ 前缀和、二维前缀和与差分的模板小总结 - AcWing 

概以括之

差分是前缀和的逆运算，假设有两个数组a[], b[]，数组a是数组b的前缀和

即a[i] = b[1] + b[2] + ... + b[i]，那么数组b就是a的差分数组

差分算法有什么用呢，比如给定数组a有n个元素，要求在[left, right]上，每个元素 +c，这时你可能会想，遍历一次，加c不就好了，可是这样时间复杂度达到O(n)，而采用差分只有O(1)的复杂度

如果进行m次区间[left, right] +c 或 -c 的操作呢，这时遍历m次的复杂度为O(nm)，而差分只需O(m)

在数据量达到1e5的情况下，直接遍历会TLE，对于OI赛制只能拿到10%~50%的分，ACM赛制0分

所以学习差分还是有必要的 

具体操作 

给定数组a，n个元素，我们创建数组b，为数组a的差分数组

令b[i] = a[i] - a[i - 1]，因为a是b的前缀和数组 

模板 

#include<iostream>
using namespace std;
int n;
int a[10010], b[10010];
//插入函数
void insert(int l, int r, int c)
{
        b[l] += c;
        b[r + 1] -= c;
}
int main()
{
    cin>>n;
    //输入数据
    for(int i = 1; i <= n; ++i)
        cin>>a[i];
    //差分后的数组b
    for(int i = 1; i <= n; ++i)
        insert(i, i, a[i]);
    //执行操作
    int l, r, c;
    cin>>l>>r>>c;
    insert(l, r, c);
    //输出操作后数组
    for(int i = 1; i <= n; ++i) {
        b[i] += b[i - 1]; //前缀和
        cout<<b[i]<<" ";
    }
    return 0;
}

执行m次只需在“执行操作”那里，加个while(m--)，不过我更习惯while(m){ ......m--; }

8
1 2 3 4 5 6 7 8
2 5 3
1 5 6 7 8 6 7 8

先记套路，你可以假设1 3 5 7的数组a，经过insert()函数后，得到的数组b就是1 2 2 2，数组b的前缀和就是原来的数组a 

👊（一）AcWing 3729. 改变数组元素

3729. 改变数组元素 - AcWing题库

标签：中等，差分，区间合并

题目没给初始数组，所以我们只需要差分数组b

第二是，我们假定初始长度就为n，用一个for(int i = 1; i <= n; ++i)循环遍历1~n

如果输入的x大于等于当前的长度 i ，就对所有元素执行insert操作

如果输入的x小于 i ，只需要insert(i - x + 1, i)，i 表示最后一个元素

#include<iostream>
#include<cstdio> //scanf(), printf()
#include<cstring> //memset()
using namespace std;
int b[200010]; //题目中没有给定初始数组，所以不需要数组a
void insert(int l, int r)
{
    b[l] += 1;
    b[r + 1] -= 1; //套路
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t) {
        scanf("%d", &n);
        memset(b, 0, sizeof(b)); //初始化
        //执行操作
        for(int i = 1; i <= n; ++i) {
            int x;
            scanf("%d", &x); //每输入一个数, 就操作一次
            if(x == 0) continue; //跳过本次
            else if(x >= i) insert(1, i); //全部操作一次
            else insert(i + 1 - x, i);
        }
        for(int i = 1; i <= n; ++i)
            b[i] += b[i - 1]; //前缀和得到操作后的数组
        for(int i = 1; i <= n; ++i) {
            if(b[i] <= 1) printf("%d ", b[i]);
            else printf("1 "); //如果大于1就输出1
        }
        printf("\n");
        t--;
    }
    return 0;
}

👊（二）P2367 语文成绩

P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：普及/提高-

这是一道最简单模板题，不需要变形，直接套模板就能AC

不开O2优化就AC  80%，开了AC  100%  

能直接套模板的题，基本一次过，而且耗时才几分钟

#include<iostream>
#include<cstdio> //scanf(), printf()
using namespace std;
int a[5000010], b[1000010];
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c; //模板
}
int main()
{
    int n, p;
    scanf("%d%d", &n, &p);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]); //初始分数
    for(int i = 1; i <= n; ++i)
        insert(i, i, a[i]); //逆前缀和
    while(p) { //p次操作
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
        p--;
    }
    for(int i = 1; i <= n; ++i)
        b[i] += b[i - 1]; //前缀和
    int Min = 1e9;
    for(int i = 1; i <= n; ++i)
        Min = min(Min, b[i]); //找最小值
    printf("%d", Min);
    return 0;
}

👊（三）P8772 [蓝桥杯 2022 省 A] 求和

P8772 [蓝桥杯 2022 省 A] 求和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：普及-，前缀和，差分 

虽然标签有差分，但我觉得，它只考了前缀和 

temp = 数组a[i]的前缀和，然后用a[i] * temp。暴力的话只能AC  70%

temp = a[1],  sum += a[2] * a[1]

temp = a[1] + a[2],  sum += a[3] * (a[1] + a[2])

temp = a[1] + a[2] + a[3],  sum += a[4] * (a[1] + a[2] + a[3])

......

#include<iostream>
using namespace std;
int a[200010];
int main()
{
    int n;
    cin>>n;
    for(int i = 1; i <= n; ++i)
        cin>>a[i];
    long long sum = 0, temp = a[1];
    for(int i = 2; i <= n; ++i) {
        sum += temp * a[i];
        temp += a[i]; //前缀和
    }
    cout<<sum;
    return 0;
}

👊（四）1882: 中位数 II

P1882 - 中位数 II - New Online Judge (ecustacm.cn)

标签：基础题，差分，USACO

赛前回顾，对一个区间操作最快的方法（目前会的来说）

额外的测试

先在草稿纸得到答案，加上程序中打表，确定每一个元素都是想要的样子

9 5
3 4
4 5
2 6
1 7
4 6
0 0 1 1 2 3 3 4 5
2

AC  代码

n为奇数，不用分类讨论

#include<iostream>
#include<cstdio> //scanf()
#include<algorithm> //sort()
using namespace std;
int b[1000010]; //差分数组
void insert(int l, int r, int k)
{
    b[l] += k;
    b[r + 1] -= k ;
}

int main()
{
    int n, k, x, y;
    scanf("%d%d", &n, &k);
    //k次操作
    for(int i = 0; i < k; ++i) {
        scanf("%d%d", &x, &y);
        insert(x, y, 1); //[x, y]区间+1
    }
    //前缀和得到原数组
    for(int i = 2; i <= n; ++i)
        b[i] += b[i - 1];
    //排序
    sort(b + 1, b + n + 1); //下标从1开始
    //n为奇数
    cout<<b[(n + 1) / 2];
    return 0;
} 

🌼三，二分

👂 活着 - 郝云 - 单曲 - 网易云音乐

→ 二分算法学习_码龄?天的博客-CSDN博客

→ OI Wiki - OI Wiki (oi-wiki.org) 

模板 

int binary_search(int left, int right, int key) 
{
    int ret = -1; //未搜索到数据返回-1下标
    int mid;
    while(left <= right) {
        mid = left + ((right - left) >> 1); //避免溢出,用该算法
        if(key > a[mid]) left = mid + 1;
        else if(key < a[mid]) right = mid - 1;
        else { //最后检测相等
            ret = mid;
            break;
        }
    }
    return ret; //单一出口
}

要用二分算法，首先判断

1，能不能用， 即是不是一个有序数组，这里的“有序”是广义的有序，也就是一个数组中，某个点左侧或右侧都满足某一条件，而另一侧不满足

2，其次判断，左右边界是什么，就是left(l), right(r)要自己设或者求出合适的值

3，check()函数怎么写，相当于模板里的key > a[mid]或者 <

👊（一）1460. 我在哪？

1460. 我在哪？ - AcWing题库

标签：简单，二分，哈希

原文是“最小的K值，使任意连续K个，唯一”，比如样例ABCDABC中，有人问为什么CD确定不了2呢，因为任意2个里面，包含AB，而AB的位置显然不是唯一的，3个的话也存在ABC重复，所以只能4个

方法一：二分 + 哈希 ，但是我不会哈希，想了半小时只用二分没结果

方法二：利用set中，元素不重复的特点，但是没想明白怎么做

方法三：考虑到数据量不大，还是暴力 + s.substr()  + s.find()

(9条消息) C++中s.find()和s.rfind()的用法_暖风有凉意的博客-CSDN博客_s.find

1，s.find(str)或s.find(str, pos)要与 != string::npos连用，最后没有找到子串的话，会返回

string::npos 

2，s.substr(i)从下标 i 开始到结尾，s.substr(i, j)从下标 i 开始截取 j 个字符

string s1 = s.substr(j, i);
if(s.find(s1, j + 1) == string::npos)
//没有找到子串, 返回string::npos

if(s.find(s1, j + 1) != string::npos)
//找到子串

#include<iostream>
#include<cstring> //s.substr(), s.find()
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i = 1; i <= n; ++i) { //i表示截取长度
        int flag = 1;
        for(int j = 0; j < n - i; ++j) { //j为截取起始坐标
            string s1 = s.substr(j, i); //下标j开始截取i个字符
            if(s.find(s1, j + 1) != string::npos) //j + 1
                flag = 0;
        }
        if(flag) {
            cout<<i;
            break;
        }
    }
    return 0;
}

👊（二）1101: 花费（未理解）

P1101 - 花费 - New Online Judge (ecustacm.cn)

标签：基础题，二分 

这道题还挺难的。。。做了3个小时。。。😟 还是没做出来

只好模仿答案写一遍，不是很理解

很多人喜欢用cnt，是count计数的意思

本题代码中，主函数中二分查找的复杂度是O(logn)，check()函数里的复杂度是O(n) 

所以本题总的复杂度是O(nlogn)

#include<iostream>
#include<cstdio> //scanf(), printf()
typedef long long LL;
using namespace std;
LL n, m, l = 0, r = 0;
LL a[100010];
bool check(LL mid)
{
    LL sum = 0, c = 1;
    for(LL i = 0; i < n; ++i) {
        sum += a[i];
        if(sum > mid) {
            sum = a[i];
            c++;
        }
    }
    return c <= m;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for(LL i = 0; i < n; ++i) {
        scanf("%lld", &a[i]);
        l = max(l, a[i]); //左边界
        r += a[i]; //右边界
    }
    while(l < r) { //二分
        LL mid = l + ((r - l) >> 1); //外面记得加上括号
        if(!check(mid))
            l = mid + 1;
        else
            r = mid;
    }
    cout<<l;
    return 0;
}

👊（三）1137: 灯泡的高度

P1137 - 灯泡的高度 - New Online Judge (ecustacm.cn)

标签：基础题，二分

思路

1，在二分模板里加了个for循环，根据给定的公式，从左往右推，直到第n个灯泡

2，注意，除了n和flag是int，其他都声明为double（最大10^308，小数上似乎可以到1e-16）

3，初始要设置一个精度eps

4，关于精度eps和右边界r的设置，你们可以尝试下，r = 1e3只能AC95%，而eps = 1e-4只能AC55%

分析

🌳AC  模板

明显的二分模板

#include<iostream>
#include<iomanip> //setprecision(), setiosflags(ios::fixed)
#include<cstdio> //printf()
using namespace std;
const double eps = 1e-8; //精度
double ans;
int main()
{   //注意, 除了n, flag是int, 其他都是double
    int n;
    double a;
    cin>>n>>a;
    double l = 0, r = 1e10; //left,right 左右边界
    //二分
    while(r - l > eps) {
        double mid = (l + r) / 2;
        double pre1 = a, pre2 = mid;
        int flag = 1;
        for(int i = 2; i < n; ++i) { //最后到下一位, 所以i到n - 1
            double temp = pre2;
            pre2 = pre2 * 2 - pre1 + 2; //pre2前进一位
            pre1 = temp; //pre1前进一位
            if(pre2 < eps) {
                flag = 0;
                break; //不满足高度大于0条件
            }
        }
        if(flag) { //B可能的答案, 但B仍需变小
            ans = pre2;
            r = mid; //右边界左移
        }
        else //出现了高度小于0的情况
            l = mid; //左边界右移
    }
    //cout<<setprecision(2)<<setiosflags(ios::fixed)<<ans;
    printf("%.2f", ans);
    return 0;
}

我尝试将代码第14，29，32行按模板常规做法修改，输出的不是最小值了

while(r - l > eps) --> while(r - l > 0)
r = mid; --> r = mid - 1;
l = mid; --> l = mid + 1;

8 15
10.19

而正确答案应该是9.75，先记套路吧

👊（四）P1918 保龄球

P1918 保龄球 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：模拟，二分，普及-

2个月没碰二分，又忘光了，，所幸经过这题的回顾，又记起来了

思路

刚开始做，忘记结构体和排序了，，，难怪那么多能找到的都输出了0，，太久没做了实在是

1，结构体int value, id; 将编号和对应的值联系起来

2，对数组升序排序

3，套二分模板，当然具体的left < right还是<=，以及left = mid + 1，right = mid - 1还是

left = mid，right = mid，需要自己多测几组数据（包含奇偶数）

额外的测试

7 4 3 8 16 20 13 82 17 34 50 1
12
7
1
4
2
3
3
8
4
16
5
1
12
50
11
34
10
17
9
82
8
13
7
20
6

AC  代码

#include<iostream>
#include<cstdio> //scanf()
#include<algorithm> //sort()
using namespace std;
struct node
{
    int v, id; //value和id
}a[1000010];

bool cmp(node x, node y)
{
    return x.v < y.v;
}
int main()
{
    int n, q;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {//下标1开始
        scanf("%d", &a[i].v);
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp); //对1~n按value升序排序
    scanf("%d", &q);
    int num;
    for(int i = 0; i < q; ++i) {
        scanf("%d", &num);
        int flag = 1;
        //二分
        int l = 1, r = n; //左右边界
        while(l <= r) {
            int mid = (l + r) / 2;
            if(num < a[mid].v) r = mid - 1;
            else if(num > a[mid].v) l = mid + 1;
            else if(num == a[mid].v) {
                cout<<a[mid].id<<endl;
                flag = 0; //有解
                break;
            }
        }
        if(flag) cout<<0<<endl;
    }
    return 0;
}

🌼四，双指针（尺取法）

 👂 就是我 - 林俊杰 - 单曲 - 网易云音乐 

歌词：躺在星空下的草地上，衣服全部脱光让你看😂

→ 算法基础----尺取法（双指针）_jkaliang的博客-CSDN博客

→ 尺取法（图文解析、初学推荐）_小白小郑的博客-CSDN博客_尺取法

→ 双指针 - OI Wiki (oi-wiki.org)

做双指针前

首先判断能否用双指针

再判断，通过同向扫描还是反向扫描（同向移动，相向移动）来维护区间

👊（一） 3768. 字符串删减

3768. 字符串删减 - AcWing题库

 标签：简单，双指针

这题用不上双指针

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans = 0, flag = 0, now = 0;
    for(int i = 0; i < n; ++i) {
        if(s[i] == 'x') now++;
        else if(s[i] != 'x' && now >= 3) {
            ans += now - 2;
            now = 0;
            continue;
        }
        else
            now = 0;
    }
    if(now >= 3) ans += now - 2; //补充最后来不及加上的
    cout<<ans;
    return 0;
}

👊（二） 2008: 三数之和

P2008 - 三数之和 - New Online Judge (ecustacm.cn)

分类：双指针，枚举 

 数据量非常小，不用考虑int, long long或者map等等

来暴力枚举

🌳AC  50%  暴力

#include<iostream>
#include<algorithm> //sort()
using namespace std;
int a[5010];
int main()
{
    int n, m, i, j, k;
    cin>>n>>m;
    for(i = 0; i < n; ++i)
        cin>>a[i];
    sort(a, a + n); //排序
    int ans = 0;
    for(i = 0, j = 1; i < j; ++i)
    {
        j = i + 1; //这步很重要
        while(j < n - 1) {
            for(k = j + 1; k < n; ++k)
                if(a[i] + a[j] + a[k] == m)
                    ans++;
            j++;
        }
    }
    cout<<ans;
    return 0;
}

下面这个是别人的答案

1，不排序，采用了桶的概念

2，最后的ans要开long long

🌳AC  100%

#include<iostream>
using namespace std;
int a[5010], b[10010]; //b类似桶排序
int main()
{
    int n, m, i, j;
    cin>>n>>m;
    for(i = 1; i <= n; ++i) {
        cin>>a[i];
        b[a[i] + 2000]++; //防止下标 < 0
    }
    //不要排序
    long long ans = 0; //会爆int
    for(i = 1; i <= n; ++i) {
        for(j = i + 1; j <= n; ++j) {
            int tmp = m - a[i] - a[j];
            int now = b[2000 + tmp];
            if(a[i] == tmp) now--;
            if(a[j] == tmp) now--;
            if(now > 0) ans += now;
        }
    }
    cout<<ans / 3;
    return 0;
}

👊（三）1373: [蓝桥杯2018初赛]日志统计

P1373 - [蓝桥杯2018初赛]日志统计 - New Online Judge (ecustacm.cn)

标签：基础题，双指针 

 结构体将编号 id 和 ts 时刻统一在一起

🌳AC  38%（大坑！）

#include<iostream>
#include<algorithm> //sort()
#include<cstdio> //scanf()
using namespace std;
int flag[100010], num[100010]; //标记热帖和点赞数
struct good
{
    int ts, id;
};
int cmp(good x, good y)
{
    return x.ts < y.ts; //时间从小到大排序
}
int main()
{
    struct good a[100010];
    int n, d, k;
    scanf("%d%d%d", &n, &d, &k);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].ts, &a[i].id);
    sort(a, a + n, cmp); //排序
    for(int i = 0, j = 0; i < n; ++i) {
        num[a[i].id]++; //点赞数+1
        if(a[i].ts - a[j].ts >= d) {//时间达到d
            num[a[j].id]--; //取消左边界获赞
            j++; //左边界右移
        }
        if(num[a[i].id] == k) //这里是a[i]
            flag[a[i].id] = 1; //标记热帖
    }
    for(int i = 0; i < n; ++i)
        if(flag[i] == 1) //被标记过
            cout<<i<<endl;
    return 0;
}

对拍错误样例

10 100 2
0 4
99 4
5 17
102 17
6 5
9 6
10 11
20 15
25 20
30 30
4
   

少输出了个17

忘记对拍了，，白白浪费2小时找原因，对拍1分钟找到错误原因

不是没用pair的原因，。。。代码最后输出时，第31行

for(int i = 0; i < n; ++i)改成for(int i = 0; i <= 100000; ++i)即可，原来输出少了。。。

n只是日志行数，不是帖子总数。。。。

输出少了，看了3小时才看出来🤦‍ 粗心是时间杀手

🌳AC  100%

(3条消息) C++ pair用法及使用sort函数对pair数据进行排序_一记绝尘的博客-CSDN博客_c++ pair排序

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

const int N = 1e5 + 10;
int flag[N]; //标记热帖
int num[N]; //点赞数
struct good
{
    int ts, id;
};
int cmp(good x, good y)
{
        return x.ts < y.ts; //时间从小到大排序
}
int main()
{
    struct good a[N];
    int n, d, k;
    cin >> n >> d >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i].ts >> a[i].id;

    sort(a, a + n, cmp);

    for (int i = 0, j = 0; i < n; i++)
    {
        num[a[i].id]++;
        if (a[i].ts - a[j].ts >= d)
            num[a[j].id]--, j++;
        if (num[a[i].id] == k)
            flag[a[i].id] = true;
    }
    for (int i = 0; i < N; i++)
        if (flag[i] == 1)
            cout << i << endl;
    return 0;
}

🌼五，递推

👂 菲菲 - 沈以诚 - 单曲 - 网易云音乐 

→ c++ 递推算法 - 张其勋 - 博客园 (cnblogs.com)

一种做法是找到递推式，类似f(n) = f(n - 1) + f(n - 2)这种

第二种是，通过递推的思路做题，但不用找到递推式

👊（一）3777. 砖块 

3777. 砖块 - AcWing题库

首先，我们学习下vector

 → (2条消息) c++ vector详解_~不羁的博客-CSDN博客 

vector能代替数组，而且能操作更大的数据量，比如1e7的数据量哪怕放全局数组也会超限

但是放vector可以

发现stl很多操作，和python很像，还是得赶紧掌握stl，以后做题难度直线下降 

补充： s.back()表示字符串s末尾得字符

两种情况都要讨论到，就是全转化为'B'或全转化为'W' 

代码中的check(char& c)我一开始写成check(char c)

结果没有达到预期效果 

→ C与C++关于*与&的传参解析 (baidu.com) 

AC  代码 

#include<iostream>
#include<vector> //res.push_back
using namespace std;
int n;
void change(char& c) //&
{
    if(c == 'W') c = 'B';
    else c = 'W'; //修改
}
bool check(string s, char c)
{
    vector<int>res; //result, 局部变量, 不影响函数外
    for(int i = 0; i + 1 < n; ++i)
        if(s[i] != c) {
            res.push_back(i + 1); //读入操作位置
            change(s[i]);
            change(s[i + 1]); //一次改2个
        }
    if(s[0] != s[n - 1]) return false;
    cout<<res.size()<<endl;
    for(int i = 0; i < res.size(); ++i)
        cout<<res[i]<<" "; //输出操作位置
    if(res.size() != 0)
        cout<<endl;

    return true;
}
int main()
{
    int t;
    string s;
    cin>>t;
    while(t) {
        cin>>n>>s;
        //有一个真则不执行另一个
        if(!check(s, 'B') && !check(s, 'W'))
            cout<<-1<<endl;
        t--;
    }
    return 0;
}

4
8
BWWWWWWB
3
2 4 6
4
BWBB
-1
5
WWWWW
0
3
BWB
2
1 2
    

👊（二） 1428: [蓝桥杯]翻硬币

P1428 - [蓝桥杯]翻硬币 - New Online Judge (ecustacm.cn)

标签：基础题，递推 

做这题之前，我们先来回忆下字符串操作函数

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string s1, s2, s3;
    cin>>s1>>s2;
    cout<<endl;

    cout<<"s2的值赋给s1"<<endl;
    s1 = s2;
    cout<<s1<<" "<<s2<<endl;

    cout<<endl<<"+号拼接s1, s2得到s3"<<endl;
    s3 = s1 + s2;
    cout<<s3<<endl;

    cout<<endl<<"初始化s4为指定元素"<<endl;
    string s4(3, 'A');
    cout<<s4<<endl;

    cout<<endl<<"判等"<<endl;
    if(s1 == s2) cout<<"s1 == s2"<<endl;
    if(s3 != s4) cout<<"s3 != s4"<<endl;

    cout<<endl<<"s4追加到s3后"<<endl;
    s3.append(s4);
    cout<<s3<<endl;

    cout<<endl<<"下标1开始截取s3的4个字符"<<endl;
    cout<<s3.substr(1, 4)<<endl;

    cout<<endl<<"输出s3第3 + 1个字符"<<endl;
    cout<<s3[3]<<endl;

    cout<<endl<<"删除s3下标2开始的3个字符"<<endl;
    s3.erase(2, 3);
    cout<<s3<<endl;

    return 0;
}

ACm Oi

s2的值赋给s1
Oi Oi

+号拼接s1, s2得到s3
OiOi

初始化s4为指定元素
AAA

判等
s1 == s2
s3 != s4

s4追加到s3后
OiOiAAA

下标1开始截取s3的4个字符
iOiA

输出s3第3 + 1个字符
i

删除s3下标2开始的3个字符
OiAA

嗯。。第一次花了一个小时敲出来，只过了样例。。第二次在网上搜题解

突然发现这题没有递推把？？就是个贪心

怎么贪心法呢，比如有x1, x2, x3, x4，四个位置的字符不同

1，按照顺序翻转，次数t1 = x2 - x1 + x4 - x3

2， 两边凑一对翻转，次数t2 = x4 - x1 + x3 - x2

显然t1 < t2，所以按顺序翻转可以得到最小的翻转次数

而且首先可以明确的是，两字符串不一样的字符一定是偶数个，所以不用纠结万一不能翻转成一样怎么办

AC  代码

#include<iostream>
using namespace std;
int main()
{
    string s1, s2;
    cin>>s1>>s2;
    int ans = 0, flag = 0, m; //flag = 0放循环外
    for(int i = 0; i < s1.size(); ++i) {
        if(s1[i] != s2[i]) {
            if(flag == 1) { //按顺序第2个不同的字符
                flag = 0;
                ans += i - m;
            }
            else if(flag == 0) { //按顺序第1个不同的字符
                flag = 1; //第15行记得用else if
                m = i;
            }
        }
    }
    cout<<ans;
    return 0;
}

🌼六，递归

👂 ▶ 小宇 (163.com) 

→ 关于递归中return的理解（最浅显易懂）_Pledgee的博客-CSDN博客_递归函数return怎么理解 

→ 三道题套路解决递归问题 | lyl's blog (lyl0724.github.io) 

→ 递归 & 分治 - OI Wiki (oi-wiki.org) 

👊（一） 1497. 树的遍历

1497. 树的遍历 - AcWing题库

标签：简单?，树的遍历，递归，哈希表，PAT甲级，BFS 

说实话，难到我了。。哈希还没学，树的四种遍历顺序（前序，中序，后续，层序）也没学。。BFS也不是很熟练，先滚去学习了

先开2倍速看完y总的视频，了解到，

还需要学习：1，哈希表，2，树的前序中序后续层序遍历（二叉树）

还需要巩固：1，BFS

建议都看一遍，取精去糟  

树的四种遍历 

→ 

【二叉树初阶】前中后序遍历+层序遍历+基础习题_二叉树的先序,中序,后序遍历例题_寄一片海给你的博客-CSDN博客

→ 二叉树的四种遍历方式_孤单网愈云的博客-CSDN博客_本题要求给定二叉树的4种遍历。

→ 二叉树的四种遍历方式 - 洛沐辰 - 博客园 (cnblogs.com)

→ 树的遍历（四种全）｜C++_世一渔的博客-CSDN博客_树的遍历

→ 树基础 - OI Wiki (oi-wiki.org)

→

二叉树：前序遍历、中序遍历、后序遍历，BFS，DFS - 蔡子CaiZi - 博客园 (cnblogs.com)

哈希表 + BFS

哈希表是一种数据结构，内部通过哈希算法实现 

→ 《啊哈算法第四章之bfs》（17张图解）_码龄?天的博客-CSDN博客

→  哈希算法原理和实现_非常规自我实现的博客-CSDN博客_hash原理和实现方式

→  哈希算法详解_qq_16570607的博客-CSDN博客_哈希算法

→  来吧！一文彻底搞定哈希表！_庆哥Java的博客-CSDN博客_哈希表怎么画

→  (八):哈希表+二叉树_bupt_01的博客-CSDN博客_哈希表和二叉树

→  字符串哈希 - OI Wiki (oi-wiki.org)

→  哈希表 - OI Wiki (oi-wiki.org)

本题考察的点较多，属于面试热门考点，思路是：

1，利用给出的后续中序遍历，构造出二叉树（其中需要哈希表存储树）

2，用BFS按层遍历二叉树

嗯，二叉树遍历的文章看完了，可是看完了也不会啊，哈希表懒得看了

所幸这时从网上发现了一种不需要哈希和bfs的方法

看这里！ 

先讲讲根据后序，中序得到前序的方法，这是推出层序的基础

1，根据后序得到根节点，然后在中序里找到根节点，根节点左边就是左子树，右边右子树 

（后序最后一个就是根节点）

2，写一个pre推出前序的函数，函数类似快排，找到根节点后，分别对左子树和右子树递归

快排长这样子

void quick_sort(int left, int right, int a[])
{
    if(left >= right) return;
    int i, j, base;
    i = left, j = right, base = a[left];
    while(i < j) {
        while(i < j && a[j] >= base) j--;
        while(i < j && a[i] <= base) i++;
        if(i < j) {
            a[i] = a[i]^a[j];
            a[j] = a[i]^a[j];
            a[i] = a[i]^a[j]; //异或交换两数
        }
    }
    a[left] = a[j]; //左端与i,j指向元素交换
    a[j] = base;
    quick_sort(left, j - 1, a); //递归左边
    quick_sort(j + 1, right, a); //递归右边
}

推出前序的长这个样子

#include<iostream>
using namespace std;
int in[] = {3,2,4,1,6,5}; //中序
int post[] = {3,4,2,6,5,1}; //后序
void pre(int root, int start, int End)
{
    if(start > End) return;
    int i = start;
    while(i < End && in[i] != post[root]) i++;
    cout<<post[root]<<" "; //输出当前根节点
    pre(root - (End - i) - 1, start, i - 1); //递归左子树
    pre(root - 1, i + 1, End); //递归右子树
}
int main()
{
    pre(5, 0 ,5);
    return 0;
}

return; 和 左右递归那里，是不是很像

具体解释下第11，12行pre()函数对左右子树的递归

int in[] = {3,2,4,1,6,5}; //中序
int post[] = {3,4,2,6,5,1}; //后序

结合代码和图好理解 

首先明确，这里下标从0开始（如果从1开始会有所变化）

1，第11行

（1）左子树根节点在后序中的下标为root - (End - i) - 1

root 为当前部分节点数（不算根节点）

(End - i) 为当前部分右子树的节点数

所以节点数 - 右子树部分 = 左子树节点数，因为是算下标，所以再 - 1

（2）左子树在中序中的起点为start，终点为 i - 1

2，第12行

（1）右子树根节点在后序中的下标为 root - 1

（2）右子树在中序中的起点为 i + 1，终点为 End

前序说到这里，那怎么在这个过程中，推出层序呢？

首先，编号（下标）从0开始的话，根节点为k，那么左子树根节点为2*k + 1，右子树根节点为2*k + 2，我们建个一维数组m，在pre中增加个index作为下标即可，最后按顺序输出自然就是层序

参考博客：

已知后序与中序输出前序（先序） – 柳婼 の blog (liuchuo.net)

AcWing 1497. 树的遍历（无须建树，简单易懂） - AcWing

emm...第一次把代码敲出来，样例没过，因为题目给的是二叉树，不一定是完全二叉树，如果题目说明给的是完全二叉树（或满二叉树），我的代码就对了

🌳Wrong Answer 

#include<cstdio> //scanf(), printf()
int m[100], in[100], post[100];
void pre(int root, int start, int End, int index)
{
    if(start > End) return;
    int i = start;
    while(i < End && in[i] != post[root]) //这里是while
        i++; //自增到根节点的下标
    m[index] = post[root]; //保存前序的值
    //递归左子树
    pre(root - (End - i) - 1, start, i - 1, 2*index + 1);
    //递归右子树
    pre(root - 1, i + 1, End, 2*index + 2);
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &post[i]); //后序
    for(int i = 0; i < n; ++i)
        scanf("%d", &in[i]); //中序
    pre(n - 1, 0, n - 1, 0);
    for(int i = 0; i < n; ++i)
        printf("%d ", m[i]); //输出层序
}

比如，给来一个完全二叉树，√ 

6
3 4 2 6 5 1
3 2 4 1 6 5
1 2 5 3 4 6

给来一个更普遍的二叉树，×

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
4 1 6 0 3 5 7

那怎么办呢，这就需要map的迭代器了，让我们学习新知识

map会按键从小到大自动排序 

C++ map的常用用法（超详细）(*^ｰ^)人(^ｰ^*)_c++ map使用_Curz酥的博客-CSDN博客

关于为什么说不是完全二叉树就不行，可以看看这个图

虽然依旧是按层序排列的输出，但由于不符合（0开始）左子树2*k+1，右子树2*k+2，所以会多输出很多0

比如我们将Wrong Answer中最后输出到 i < n改为 i < 2*n，就会出现下面的情况

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
4 1 6 0 3 5 7 0 0 2 0 0 0 0

想明白为什么不是完全二叉树就不行，我们可以加个if(m[i] != 0)的判断，当然，这里你要取到

1.1 * 10^6，否则哪怕取到1e6也是满足不了最后一组数据的，因为最后一组数据就是一条链

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

当然，1.1 * 10^6我试了很多次，，1.11*10^6的全局都超限了，所以会迭代器的话，还是用迭代器把

🌳Accpted  加个if

#include<cstdio> //scanf(), printf()
int m[1100000], in[1100000], post[1100000];
void pre(int root, int start, int End, int index)
{
    if(start > End) return;
    int i = start;
    while(i < End && in[i] != post[root]) //这里是while
        i++; //自增到根节点的下标
    m[index] = post[root]; //保存前序的值
    //递归左子树
    pre(root - (End - i) - 1, start, i - 1, 2*index + 1);
    //递归右子树
    pre(root - 1, i + 1, End, 2*index + 2);
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &post[i]); //后序
    for(int i = 0; i < n; ++i)
        scanf("%d", &in[i]); //中序
    pre(n - 1, 0, n - 1, 0);
    for(int i = 0; i < 1100000; ++i)
        if(m[i] != 0)
            printf("%d ", m[i]); //输出层序
}

🌳Accpted  map迭代器 

#include<iostream> //map
#include<cstdio> //scanf(), printf()
#include<map> //map
using namespace std; //map
int in[100], post[100];
map<int, int>m;
void pre(int root, int start, int End, int index)
{
    if(start > End) return;
    int i = start;
    while(i < End && in[i] != post[root]) //这里是while
        i++; //自增到根节点的下标
    m[index] = post[root]; //保存前序的值
    //递归左子树
    pre(root - (End - i) - 1, start, i - 1, 2*index + 1);
    //递归右子树
    pre(root - 1, i + 1, End, 2*index + 2);
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &post[i]); //后序
    for(int i = 0; i < n; ++i)
        scanf("%d", &in[i]); //中序
    pre(n - 1, 0, n - 1, 0);
    for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it)
        printf("%d ", it->second);
}

第1，3，4，6，28，29行，是迭代器需要的，注意几个点： 

1, 迭代器需要的

#include<iostream>
#include<map>
using namespace std;
map<int, int>m;
for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it) //迭代器
    printf("%d ", it->second);

2,

代码第28行，不要写成 it < m.end()，要写成 it != m.end()，否则报错

error: no match for operator...

👊（二）P1427 小鱼的数字游戏

P1427 小鱼的数字游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：入门，递归，栈 

最简单的栈的使用

→ C++的栈 - 一杯明月 - 博客园 (cnblogs.com)

→ (2条消息) C++ 栈_雪易的博客-CSDN博客_c++栈

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    int n;
    stack<int>m;
    while(cin>>n) {
        if(n == 0) break;
        m.push(n);
    }
    while(!m.empty()) {
        cout<<m.top()<<" ";
        m.pop();
    }
    return 0;
}

👊（三）P3152 正整数序列

P3152 正整数序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：数学，递归，普及-

思考方法1

（当前最大值）8 --> 4 --> 2 --> 1 --> 0                                        9 --> 4 --> 2 --> 1 --> 0 

15 --> 7 --> 3 --> 1 --> 0 

发现规律了吗

#include<iostream>
using namespace std;
int main()
{
    int n, ans = 0;
    cin>>n;
    while(n) {
        n /= 2;
        ans++;
    }
    cout<<ans;
    return 0;
}

思考方法2 

假设当前最大值为maxn，每次大于等于maxn / 2 + 1的数，都减去maxn / 2 + 1，所以答案=log2(n) + 1

#include<iostream>
#include<cmath> //log2(n)
using namespace std;
int main()
{
    int n, ans = 0;
    cin>>n;
    ans = log2(n) + 1;
    cout<<ans;
    return 0;
}

👊（四）1103: 地盘划分

P1103 - 地盘划分 - New Online Judge (ecustacm.cn)

标签：基础题，递归

一道非常典型的递归题 

 我写个递归函数即可，设一个终止条件m % n == 0

看图

第一次递归取3个，第二次取1个，第三次取2个

#include<iostream>
using namespace std;
long long ans;
void sim(int n, int m) //不是最简就递归
{ //最简的意思是 m % n == 0
    if(n > m) {
            n = n^m;
            m = n^m;
            n = n^m; //异或交换两数
        } //n小m大
    ans += m / n;
    if(m % n == 0)
        cout<<ans<<endl;
    else
        sim(n, m % n);
}
int main()
{
    long long n, m;
    while(cin>>n>>m) {
        ans = 0;
        sim(n, m);
    }
    return 0;
}

👊（五）1104: 分形图

P1104 - 分形图 - New Online Judge (ecustacm.cn)

标签：基础题，递归 

很典型 

en，看了20分钟貌似没有非常明确的思路，所以还是学习别人的优秀代码吧 

如果蓝桥杯遇到这类题，自己又不会，可以把前3个暴力出来，然后拿30%的分也好 

思路 

1，建个num()函数，得到sum * sum矩阵中sum的值

2，写个dfs()递归函数

3，主函数中二维数组初始化为空格

注意 

具体解释下第21~25行的递归，

这里把整个分形图视作整体的3行3列，我们只需考虑当前这步该怎么做

无论s多大，在当前这步都只代表一列或一行的占位，

所以，显而易见，左上角直接dfs(cur - 1, x, y)，对应的右上角，中间，左下，右下，

只需加上对应的1个或2个 s 即可，比如右下角，可以认为在整体的第3行第3列

所以是dfs(cur - 1, x + 2*s, y + 2*s)

坑  

1，由于下标从1开始，第0列依旧是空格，所以输出需要cout<<a[i] + 1；

在二维数组里，a[i]表示列地址，a表示行地址，所以a[i] + 1表示第i行从第1列开始输出 

2，代码第36行的 a[i][s + 1] = '\0'; 很有必要，防止输出方阵外的空格

3，声明数组为char a[1000][1000]，防止超限，因为3^6 = 729

AC  代码 

#include<iostream>
#include<cstring> //memset()
using namespace std;
char a[1000][1000]; //字符型二维数组

int num(int n) //sum * sum 的方阵
{
    int sum = 1;
    for(int i = 1; i < n; ++i)
        sum *= 3;
    return sum;
}

void dfs(int cur, int x, int y) //递归得到5个位置的分形图
{ //cur, current 表示当前层数
    if(cur == 1) {
        a[x][y] = 'X';
        return; //回溯
    }
    int s = num(cur - 1); //取上一层级的长度
    dfs(cur - 1, x, y); //递归左上角
    dfs(cur - 1, x, y + 2*s); //递归右上角
    dfs(cur - 1, x + s, y + s); //递归正中间
    dfs(cur - 1, x + 2*s, y); //递归左下角
    dfs(cur - 1, x + 2*s, y + 2*s); //递归右下角
}

int main()
{
    int n;
    cin>>n;
    int s = num(n);
    memset(a, ' ', sizeof(a)); //初始化为空格
    dfs(n, 1, 1);
    for(int i = 1; i <= s; ++i)
        a[i][s + 1] = '\0'; //字符串结束符, 防止输出后续空格
    for(int i = 1; i <= s; ++i)
        cout<<a[i] + 1<<endl; //防止输出第0列的空格
    return 0;
}

嘿！6个类型写了2.3万字 

🌼七，并查集

👂hello, world! 世界 你好 - 刘至佳 - 单曲 - 网易云音乐

1，为了学习并查集，我花2.5个小时写了一篇博客

→ 并查集(13张图解)--擒贼先擒王_码龄?天的博客-CSDN博客

2，Oi-Wiki的代码我不太会，主要是看它的图解，比如两棵树的合并，路径压缩等（Oi-Wiki关于并查集有4道例题的链接，时间多的也可以去练练） 

→ 并查集 - OI Wiki (oi-wiki.org)

3，再来一篇加深理解 

→ 【算法与数据结构】—— 并查集_酱懵静的博客-CSDN博客_并查集

👊（一）1249. 亲戚

1249. 亲戚 - AcWing题库

标签：并查集，简单

思路

1，一看数据量那么大，最多可达2*10^4个亲戚，输入10^6个关系，再询问10^6次，必须用scanf()，因为scanf()比cin快，不用的话，在本题就会时间超限

2，注意，这个是找亲戚，只要他们在同一群就行了，也就是有同一个“祖亲戚”

所以代码第35行很关键，要用Find(a[c]) == Find(a[d]) √

而不是a[c] == a[d] ×

3，注意数组名与变量名冲突，我第一次写就冲突了，然后报错：

error: invalid types 'int[int]' for array subscript

AC  代码

#include<cstdio> //scanf(), printf()
int a[20010];
int Find(int x) //找亲戚
{
    if(a[x] == x)
        return x;
    else {
        a[x] = Find(a[x]);
        return a[x];
    }
}
void join(int x, int y) //合并两伙亲戚
{
    int mm, nn;
    mm = Find(x); nn = Find(y);
    if(mm != nn)
        a[nn] = mm;
}
int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    for(int i = 1; i < m; ++i)
        a[i] = i; //初始化, 自己是自己的亲戚
    int aa, b;
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &aa, &b);
        join(aa, b);
    }
    int q;
    scanf("%d", &q);
    int c, d;
    for(int i = 0; i < q; ++i) {
        scanf("%d%d", &c, &d);
        if(Find(a[c]) == Find(a[d])) //注意用Find()
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

👊（二） P8654 [蓝桥杯 2017 国 C] 合根植物

P8654 [蓝桥杯 2017 国 C] 合根植物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：并查集，普及-，2017蓝桥杯国赛

注意用scanf()，其他好像没什么坑 

并查集就是个一维数组，加个（1行代码）路径压缩 

AC  代码

居然第一次就过了，那么顺畅是没想到的，以前做简单题都得卡半小时

#include<cstdio> //scanf(), printf()
int plant[1000010];
int Find(int x) //找相连
{
    if(plant[x] == x) return x;
    else {
        plant[x] = Find(plant[x]);
        return plant[x];
    }
}
void join(int x, int y)
{
    int xx = Find(x), yy = Find(y);
    if(xx != yy)
        plant[yy] = xx;
}
int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= m*n; ++i)
        plant[i] = i; //初始化, 和自己相连
    int k;
    scanf("%d", &k);
    int a, b;
    for(int i = 0; i < k; ++i) { //k组相连
        scanf("%d%d", &a, &b);
        join(a, b); //合并两株相连植物
    }
    int ans = 0;
    for(int i = 1; i <= m*n; ++i)
        if(plant[i] == i)
            ans += 1;
    printf("%d", ans);
    return 0;
}

👊（三）P1111 修复公路

P1111 修复公路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：并查集，排序，普及- 

一开始想复杂了，老是习惯想复杂，总是能把普及-的题目想象成省选-，把简单题想象成困难题--

原文是“在时间t时能修复完成这条路”，意思应该是，一开始就计时，这个时间是总的

而非每条路都要重新计时

思路

1，用结构体联系两个村庄和修路时间

2，按时间排序（是对修路时间排序，所以是m，是m，是m-_-不是n，n是村庄个数😟）

3，套并查集模板 

4，除了结构体数组外，我们还需多声明个全局数组，相当于并查集模板里的一维数组

注意  sort()需要using namespace std;

卡了好几次才AC  100%，目前只会做纯模板的并查集。结合不同算法的题有待练习 

🌳AC  10%（常犯错误）

第一次做出来，测试了下样例，就10%

早知道多测试几组。。。蓝桥杯可不敢这样

不然就是你以为你AC了六七题，妥妥的省一，最后发现自己省三都没有

#include<cstdio> //scanf(), printf()
#include<algorithm> //sort()
using namespace std; //sort()
int access[1010]; //一维数组
int n, m;

struct village { //结构体
    int x, y, t;
};

int cmp(village x, village y)
{
    return x.t < y.t; //按时间从小到大
}

int Find(int x)
{
    if(access[x] == x) return x;
    else return access[x] = Find(access[x]); //路径压缩
}

void join(int x, int y) //合并
{
    int xx = Find(x), yy = Find(y);
    if(xx != yy)
        access[yy] = xx;
}

bool check() //检查是否全部连通
{
    int num = 0;
    for(int i = 1; i <= n; ++i) {
        if(access[i] == i)
            num += 1;
        if(num > 1) return false;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    //初始化, 只能通自己
    for(int i = 1; i <= n; ++i)
        access[i] = i;

    struct village road[m]; //m条路
    for(int i = 0; i < m; ++i)
        scanf("%d%d%d", &road[i].x, &road[i].y, &road[i].t);

    sort(road, road + n, cmp); //排序

    int flag = 1;
    for(int i = 0; i < m; ++i) {
        join(road[i].x, road[i].y); //修x和y之间的路
        if(check()) {
            printf("%d", road[i].t);
            flag = 0;
            break;
        }
    }
    if(flag) printf("-1");
    return 0;
}

/(ㄒoㄒ)/~~   原来是一个字母写错的原因。。。老是这样丢分，类似 1 + 1 = 3这样的错误

应该多想几组测试数据 

错在哪里呢？代码第51行排序

sort(road, road + n, cmp); 改成  sort(road, road + m, cmp);即可，

它是n个村庄，但我们现在是对修每条路的时间排序，是每条路。。。

敲的时候还再三确定了，到底是m还是n，没想到还是粗心了

🌳AC  100%

嗯。。。没必要看了，和AC  10%几乎一模一样，只是错了个字母。。

#include<cstdio> //scanf(), printf()
#include<algorithm> //sort()
using namespace std; //sort()
int access[1010]; //一维数组
int n, m;
struct village { //结构体
    int x, y, t;
};
int cmp(village x, village y)
{
    return x.t < y.t; //按时间从小到大
}
int Find(int x)
{
    if(access[x] == x) return x;
    else return access[x] = Find(access[x]); //路径压缩
}
void join(int x, int y) //合并
{
    int xx = Find(x), yy = Find(y);
    if(xx != yy)
        access[yy] = xx;
}
bool check()
{
    int num = 0;
    for(int i = 1; i <= n; ++i) {
        if(access[i] == i)
            num += 1;
        if(num > 1) return false;
    }
    return true;
}
int main()
{
    scanf("%d%d", &n, &m);
    //初始化, 只能通自己
    for(int i = 1; i <= n; ++i)
        access[i] = i;
    struct village road[m]; //m条路
    for(int i = 0; i < m; ++i)
        scanf("%d%d%d", &road[i].x, &road[i].y, &road[i].t);
    sort(road, road + m, cmp); //排序！！！！！
    int flag = 1;
    for(int i = 0; i < m; ++i) {
        join(road[i].x, road[i].y); //修x和y之间的路
        if(check()) {
            printf("%d", road[i].t);
            flag = 0;
            break;
        }
    }
    if(flag) printf("-1");
    return 0;
}

把空行删掉后只剩56行，实际和65行那个一样 

👊（四）2006: 连通图

P2006 - 连通图 - New Online Judge (ecustacm.cn)

标签：并查集，构造

第一次敲出来，样例对了，于是再想2组测试数据，模拟是对的才能提交

测试数据

6 1
1 2
//第一组测试

7 4
2 5
1 4
6 7
4 5
//第二组测试

经过测试

6 1
1 2
4
1 3
1 4
1 5
1 6

7 4
2 5
1 4
6 7
4 5
2
1 3
1 6

两组测试都正确，提交！AC了

AC  代码

注意要用scanf()

同时，建个ans数组，保存每一堆的老大，然后输出即可

#include<cstdio> //scanf(), printf()
int fa[100010]; //一维数组
int ans[100010]; //保存答案
int Find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return fa[x] = Find(fa[x]); //路径压缩
}
void join(int x, int y)
{
    int xx = Find(x), yy = Find(y);
    if(xx != yy)
        fa[yy] = x; //合并
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        fa[i] = i; //初始化, 自己连通自己
    int a, b;
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &a, &b);
        join(a, b); //合并
    }
    int num = 0, j = 0;
    for(int i = 1; i <= n; ++i) {
        if(fa[i] == i) {
            num += 1;
            ans[j++] = i;
        }
    }
    printf("%d\n", j - 1);
    if(j >= 2)
        for(int i = 1; i < j; ++i)
            printf("%d %d\n", ans[0], ans[i]);
    return 0;
}

🌼八，哈希

👂 阿衣莫 - 阿吉太组合 - 单曲 - 网易云音乐 

杂牌解释：（建议都看，将自己能看懂的部分整合在一起 ）

→ 哈希表（Hash Table） - 知乎 (zhihu.com)

→ 第三章 哈希表_51CTO博客_哈希表

→ 哈希表 - OI Wiki (oi-wiki.org)

→ 字符串哈希 - OI Wiki (oi-wiki.org)

→ 【C++修炼之路】22.哈希_每天都要进步呀~的博客-CSDN博客 

看得懂的：（相对通俗易懂，讲的也明白一些）

→ 哈希算法详解_qq_16570607的博客-CSDN博客

→ 哈希（hash）理解 - 知道了呀~ - 博客园 (cnblogs.com)

→ (1条消息) 算法学习笔记15-哈希算法_哈希排序小于链表长度的最大质数_立志要成为海贼王的男人的博客-CSDN博客

→ 【算法】哈希表_指针不指南吗的博客-CSDN博客

整了个误区，做哈希的题，上面这几个博客讲的都是底层实现，也就是手写，而如果你奔着拿部分分或者AC部分题去，只需要掌握stl的#include<unordered_set>即可，即哈希表

👊（一）2058. 笨拙的手指

2058. 笨拙的手指 - AcWing题库

标签：枚举，进位制，哈希表

思路来源于AcW视频：AcWing 2058. 笨拙的手指（蓝桥杯集训·每日一题） - AcWing

重点是掌握stl的unorder_set，也就是哈希表，手写的话暂时没必要学习，时间太紧

🌳Wrong Answer

#include<iostream>
#include<unordered_set>
using namespace std;
int deci(string s, int b) //b进制转10进制
{
    int ten = 0;
    for(int i = 0; i < s.size(); ++i)
        ten = ten * b + s[i] - '0';
    return ten;
}
int main()
{
    string x, y;
    cin>>x>>y;
    unordered_set<int>Hash;
    for(int i = 0; i < x.size(); ++i) {
        string s = x;
        s[i] = s[i]^1; //0->1或1->0
        int ten = deci(s, 2);
        Hash.insert(ten); //将修改后的十进制插入哈希表
    }
    for(int i = 0; i < y.size(); ++i) {
        for(int j = 0; j < 3; ++j) { //遍历剩下两种可能
            string s = y;
            if(s[i] - '0' != j) {
                s[i] = j + '0'; //j转ASCII值
                int ten = deci(s, 3);
                if(Hash.count(ten)) //判断是否在哈希表里
                    cout<<ten;
            }
        }
    }
    return 0;
}

这个代码没有判断前导0，比如

//输入
0000
02

//输出
81

//标准答案
8

没有判断前导0，所以存在原来是0001和01的情况，但显然，原来正确的二进制和三进制，不存在前导0，所以需要加个if判断

知识点

#include<set>和#include<unordered_set>的区别：

1，

set能自动排序，不含重复元素，只能通过迭代器访问，插入st.insert(i)

→ C++中set使用详细说明_c++ set_想去的远方的博客-CSDN博客

2， 

unordered_set是哈希表(hash-table)，不能自动排序，不包含重复元素，st.count(i)搜索是否出现，出现返回1，没有返回0；

插入st.insert(i)

→ 哈希表之哈希集和哈希映射详解(c++)，包括hash.count()和hash.fine()的使用。_渴望年薪百万的博客-CSDN博客

→ C++常用语法——unordered_set_unordered_set 头文件_还没想好~的博客-CSDN博客

👇👇但注意有个点容易粗心， 第19，28行排除前导0，需要放在第18，27行后

也就是先修改一位，再排除前导0（先变成可能的正确答案，再对正确答案判断）

🌳Accpted

#include<iostream>
#include<unordered_set>
using namespace std;
int deci(string s, int b) //b进制转10进制
{
    int ten = 0;
    for(int i = 0; i < s.size(); ++i)
        ten = ten * b + s[i] - '0';
    return ten;
}
int main()
{
    string x, y;
    cin>>x>>y;
    unordered_set<int>Hash;
    for(int i = 0; i < x.size(); ++i) {
        string s = x;
        s[i] = s[i]^1; //0->1或1->0
        if(s.size() > 1 && s[0] == '0') continue; //排除前导0
        int ten = deci(s, 2);
        Hash.insert(ten); //将修改后的十进制插入哈希表
    }
    for(int i = 0; i < y.size(); ++i) {
        for(int j = 0; j < 3; ++j) { //遍历剩下两种可能
            string s = y;
            if(s[i] - '0' != j) {
                s[i] = j + '0'; //j转ASCII值
                if(s.size() > 1 && s[0] == '0') continue; //前导0
                int ten = deci(s, 3);
                if(Hash.count(ten)) //判断是否在哈希表里
                    cout<<ten;
            }
        }
    }
    return 0;
}

👊（二）P2957 [USACO09OCT]Barn Echoes G

P2957 [USACO09OCT]Barn Echoes G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：字符串，哈希，前缀和，USACO 

为什么第一时间想到的是字符串操作函数呢？

1，截取子串

s.substr(i)从下标 i 开始到结尾，s.substr(i, j)从下标 i 开始截取 j 个字符

哈哈！掌握对应函数真的很好做，读题目花了7分钟，敲代码花了5分钟(18行代码)

🌳AC  s.substr()

#include<iostream>
#include<cstring> //s.substr(i, j), s.substr(i)
using namespace std;
int main()
{
    string x, y;
    cin>>x>>y;
    int len = min(x.size(), y.size());
    int ans = 0;
    for(int i = 1; i <= len; ++i) {
        if(x.substr(0, i) == y.substr(y.size() - i))
            ans = max(ans, i);
        if(y.substr(0, i) == x.substr(x.size() - i))
            ans = max(ans, i);
    }
    cout<<ans;
    return 0;
}

🌳AC  哈希

看了洛谷的题解，没有一篇用unordered_set的，要么连哈希也懒得用，要么除留取余法，取余一个尽可能大的质数，但是经过观察没看到哈希冲突怎么解决的。。所以

blabla...

👊（三）P3370 【模板】字符串哈希

P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

标签：哈希，普及-

本题采用最常用的哈希方法，进制哈希

→ 字符串哈希（进制哈希）_SPI_DER的博客-CSDN博客

这里有个坑，不建议用scanf()输入string类字符串，最好用cin，真想用scanf()输入字符串就用char声明

用unordered_set做完后，样例过了的基础上，我又测试了一组，尽可能包含所有情况（大小写字符 + 打乱顺序 + 数字）

8
abcc
ddt
abcc
bacc
ccab
ccab
66AA
AAab
6

提交后AC了！

AC  代码

#include<iostream>
#include<cstdio> //scanf()
#include<cstring> //strlen(s)
#include<unordered_set>
using namespace std;
typedef unsigned long long ull; //记住格式
ull base = 131, prime = 211317, mod = 237135701740117301; //base与mod互质
ull Hash(char s[]) //prime是大质数
{
    ull ten = 0;
    for(int i = 0; i < strlen(s); ++i)
        ten = ((ten * base + (ull)s[i]) % mod) + prime;
    return ten;
}
int main()
{
    int n;
    scanf("%d", &n);
    unordered_set<ull>h; //哈希表
    for(int i = 0; i < n; ++i) {
        char s[2020];
        scanf("%s", s);
        h.insert(Hash(s));
    }
    cout<<h.size();
    return 0;
}

分析：

1，不要用scanf()读入string类字符串

2，记住131(进制)这个数字好了，prime是个大质数，我随便编了个2*10^5大小的质数，mod是一个接近unsigned long long范围的质数

3，注意声明unsigned long long，可达18*10^18，而long long 只能达到9*10^18

4，这里用unordered_set能少敲10行代码，因为unordered_set本身就是哈希表，不包含重复元素

且插入，删除，查找操作的时间复杂度都为O(1)，这点比set快很多

当然如果需要排序还是选set

补充：unordered_set底层为哈希表，set底层为红黑树

unordered_set三种操作

#include<iostream>
#include<unordered_set>
using namespace std;
int main()
{
    unordered_set<int>Hash;
    int n;

    //增
    for(int i = 0; i < 6; ++i) {
        cin>>n;
        Hash.insert(n);
    }

    //删
    Hash.erase(66);
    Hash.erase(55);

    //查
    if(Hash.count(11) == 1)
        cout<<"有这个元素"<<endl;
    if(Hash.count(55) == 0)
        cout<<"没有这个元素";
    return 0;
}

11 22 33 44 55 66
有这个元素
没有这个元素

🌼九，单调队列（留坑）

👂 Way Back Into Love (Demo) - Hugh Grant/Drew Barrymore - 单曲 - 网易云音乐 

→ [投稿]2019年4月11日单调队列讲义 - AcWing

→ 单调队列 - OI Wiki (oi-wiki.org)

→ 【单调队列】数据结构之单调队列详解_c++单调队列_行码棋的博客-CSDN博客

→ 【C++】单调队列 详解_c++单调队列_Ornamrr的博客-CSDN博客

↑↑↑↑↑↑↑  先学习知识点

只是省赛我不打算掌握这个,而且有些简单的单调队列貌似能用优先队列或者双指针做出来,等蓝桥杯结束了,有时间再回来学把

🍋总结 

大一参加蓝桥杯注定无法取得好成绩，因为数据结构是大二上才学，先不谈数据结构，单就算法来说，大一能掌握一半的基础算法都不错了，只是一半的基础算法，最多也就C++A组省二

1，对拍，找bug很棒的方法

2，s.find(), s.substr() 

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

string s1 = s.substr(j, i); //下标j开始, 截取i个字符
if(s.find(s1, j + 1) == string::npos)
//没有找到子串, 返回string::npos

if(s.find(s1, j + 1) != string::npos)
//找到子串

3，map的迭代器

#include<iostream>
#include<map>
using namespace std;
map<int, int>m;
for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it) //迭代器
    printf("%d ", it->second);

4，蓝桥杯技巧

不论是比赛还是平时，OI赛制都要懂得自己设计样例来测试代码，不要只是过了样例就提交

也许有些简单的错误是样例测试不出来的

样例过了后，再想2~5组数据，都过了再提交，没过就好好检查下为什么信心满满的代码不行，总能揪出错误

5，O2优化

洛谷或者AcW里少数的题会卡O2（就是用了就AC），起到常数优化的效果

代码第一行加上：#pragma GCC optimize(2)

#pragma GCC optimize(2)

蓝桥杯是可以用的

6，数组超限

是个大坑，比如201 * 201的二维平面，你得开到40401以上，而不是40001以上，因为 201 * 201 = 40401，心算不好就拿🖊算，要么就多开个几千

7，测试后忘删cout

不论OI还是IOI，ACM赛制，写完代码过了样例后，利用cout再测多一组数据，并观察过程是否正确，都是好习惯

然而，你经常忘了删cout，导致AC  100%变成了AC  0%，要注意

8，关于scanf()和printf()

大量输入时，用scanf()，不用cin

大量输出时，用printf()，不用cout

9，关于stl

参加蓝桥杯，天梯赛等比赛，它们是支持C++11的，一定要学stl，不会stl是硬伤，现在所有的二分还是别的算法，我都是现场手写的，虽说对打基础 / 以后的面试题，有帮助

但是比赛谁给你那么多时间？所以我很多比赛有些会的题，就没时间看了

一是熟练度不够，二是没学过stl

目前stl接触过的只有sort()，#include<queue>和<stack>最基础的两三个操作，其他完全没见过

等23年蓝桥杯结束应该好好学学stl，外加对应题目的练习文章来源地址https://www.toymoban.com/news/detail-414129.html

到了这里，关于30个题型+代码(冲刺2023蓝桥杯)(上)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！