蓝桥杯刷题冲刺 | 倒计时3天

这篇具有很好参考价值的文章主要介绍了蓝桥杯刷题冲刺 | 倒计时3天。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.数的三次方根

题目

链接： 790. 数的三次方根 - AcWing题库
给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围

−10000≤n≤10000

输入样例：
```
1000.00
```
输出样例：
```
10.000000
```

第一次 AC 9/14

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


int main()
{
    double n;
    scanf("%lf",&n);
    
    if(n<0)
    {
        cout<<'-';
        n=-n;
    }
    
    double l=0,r=n;
    
    while(r-l>1e-8)
    {
        double mid=(r+l)/2;
        
        if(mid*mid*mid>n)   r=mid;
        else l=mid;
    }
    
    printf("%.6f",l);
    
    return 0;
}

刚开始没有注意负数，后来调式的时候发现错误，但写出来处理负数，逻辑发生错误

第二次 AC 100%

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


int main()
{
    double n;
    scanf("%lf",&n);
   
    double l=-1000,r=1000;
   
    while(r-l>1e-8)
    {
        double mid=(r+l)/2;
        
        if(mid*mid*mid>=n) r=mid;
        else l=mid;   
    }
    
    printf("%.6f",l);
    
    return 0;
}

另一种做法直接调用函数

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


int main()
{
    double n;
    scanf("%lf",&n);
   
    printf("%f",cbrt(n));  //cbrt开立方根函数，printf默认输出6位小数
    
    return 0;
}

2.模拟散列表

题目

链接： 840. 模拟散列表 - AcWing题库
维护一个集合，支持如下几种操作：
1. I x，插入一个数 x；
2. Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤N≤ $10^5$
− $10^9$ ≤x≤ $10^9$

输入样例：
```
5
I 1
I 2
I 3
Q 2
Q 5
```
输出样例：
```
Yes
No
```

第一次 AC 100%

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

map<int,int> m;

int n;

int main()
{
    scanf("%d",&n);
    
    char op[2];
    int x;
    
    while(n--)
    {
        scanf("%s%d",op,&x);
        
        if(op[0]=='I')
        {
            m[x]=1;
        }else{
            m[x]==1?puts("Yes"):puts("No");
        }
    }
    
    return 0;
}

我体会到了 map 的快乐

2.字符串哈希

题目

链接： 841. 字符串哈希 - AcWing题库
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1]和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 11 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤ $10^5$

输入样例：
```
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
```
输出样例：
```
Yes
No
Yes
```

第一次 AC 11/13 TLE

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

int main()
{
    int n,m;
    string s;
    cin>>n>>m>>s;
    
    string t,u;
    
    while(m--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        
        t=s.substr(a-1,b-a+1);
        
        u=s.substr(c-1,d-c+1);  //注意后面这个参数 是要截取字串的长度，长度+1，也要记住!
        
        t==u?puts("Yes"):puts("No");
    }
    
    return 0;
}

字符串截取函数 substr 真不错

第二次哈希字符串公式法

#include<iostream>
#include<cstdio>#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5+5,P = 131;//131 13331
ULL h[N],p[N];

// h[i]前i个字符的hash值
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或  13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
ULL query(int l,int r){
    return h[r] - h[l-1]*p[r-l+1];
}
int main(){
    int n,m;
    cin>>n>>m;
    string x;
    cin>>x;

    //字符串从1开始编号，h[1]为前一个字符的哈希值
    p[0] = 1;
    h[0] = 0;
    for(int i=0;i<n;i++){
        p[i+1] = p[i]*P;            
        h[i+1] = h[i]*P +x[i];      //前缀和求整个字符串的哈希值
    }

    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1) == query(l2,r2)) printf("Yes\n");
        else printf("No\n");

    }
    return 0;
}