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;
}