第一节
1、链表与邻接表
2、栈与队列
3、Kmp
一、链表
1、单链表 ： 邻接表
邻接表作用 存储图和树
2、双链表 用来优化某些问题
e[N] 某个点的值
ne[N] 某个节点的next指针
他们用下标关联起来
最后一个元素的next指针指向空集 ne[n-1]=-1
单链表只能找到一个节点的下一个数，无法找到上一个数
注意：下标是从0开始的，0是第一个插入的点
第k个插入的点的下标是k-1
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
//head 表示头节点的next指针
//e[i]表示节点i的值
//ne[i]表示节点i的next指针
//idx是指针 表示当前已经用到了哪个点的空间
int head,e[N],ne[N],idx;
void init(){
head=-1;
idx=0;
}
//将x插到头节点的位置
void add_to_head(int x){
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
//将x插入到下标是k的点后面
void add(int k,int x){
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//将下标是k的后一个点删掉
void remove(int k){
ne[k]=ne[ne[k]];
}
int main()
{
int m;
cin>>m;
init();
while(m--){
char c;
int k,x;
cin>>c;
if(c=='H'){
cin>>x;
add_to_head(x);
}
else if(c=='D'){
cin>>k;
if(k==0)
head=ne[head]; //删除头节点
else remove(k-1);
}
else if(c=='I'){
cin>>k>>x;
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i])
cout<<e[i]<<" ";
cout<<endl;
return 0;
}
二、双链表
l[N] 指向 N 前面的节点
r[N] 指向 N 后面的节点
e[N] 表示这个点的值
让下标是0 的点为head
下标为1的点为最后一个点
#include<bits/stdc++.h>
using namespace std;
int m;
const int N=1e5+10;
int e[N],l[N],r[N],idx;
void init(){
r[0]=1;//0表示左端点，l表示右端点
l[1]=0;
idx=2;
}
//在下标为k的右边插入一个点x
//若要在下标为k的左边插入一个点x
//只需要调用 l[k] c就可以
void add(int k,int c){
e[idx]=c;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
//删除第k个点
void remove(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
int main()
{
cin>>m;
init();
while(m--)
{
string op;
cin>>op;
if(op=="L"){
int x;
cin>>x;
add(0,x); //在最左侧的右侧插入一个点
} //左端点是0
else if(op=="R"){
int x;
cin>>x;
add(l[1],x);//在最右侧的左侧
} //最右侧端点的是1 插入l[1]后面
else if(op=="D"){
int k;
cin>>k;
remove(k+1);//idx从2开始 所以是k+1
}
else if(op=="IL"){
int k,x;
cin>>k>>x;
add(l[k+1],x);//k+1
}
else if(op=="IR"){
int k,x;
cin>>k>>x;
add(k+1,x);
}
}
for(int i=r[0];i!=1;i=r[i]){
cout<<e[i]<<" ";//左端点不输出
return 0;//从左端点的右侧输出
//i！=-1就没遍历到右端点
} //i=r[i] i每次变为右侧的点
三、邻接表
n个单链表
把每个表的所有邻边都存起来
###四、模拟栈
int stk[N],tt;
stk[++tt]=x;//插入
tt--; //弹出
if(tt>0) not empty
else empty
stk[tt];//栈顶
//int stk[N],tt;
//stk[++tt]=x;//插入
//tt--; //弹出
//if(tt>0) not empty
//else empty
//stk[tt];//栈顶
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int main(){
int stack[N],tt;
int m;
cin>>m;
while(m--){
string op;
cin>>op;
int k,x;
if(op=="push"){
cin>>x;
stack[++tt]=x; //插入x
}
else if(op=="pop"){
tt--;//弹出栈顶元素
}
else if(op=="query"){
cout<<stack[tt]<<endl;//tt是栈顶
}
else if(op=="empty"){
if(tt>0)//tt大于0 则stack不为空
cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
return 0;
}
五、模拟队列
////在队尾插入元素，在队头弹出元素
//int q[N],hh,tt=-1;
////插入
//q[++tt]=x;
////弹出
//h++;
////判断是否为空
//if(hh<=tt)not empty
//else empty
////去除队头元素
//q[hh]; 队头
//q[tt];队尾
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int q[N],hh,tt=-1;
int main(){
int m;
cin>>m;
string op;
while(m--){
cin>>op;
int x,k;
if(op=="push"){
cin>>x;
q[++tt]=x; //在队尾加入一个元素
}
else if(op=="pop"){
hh++; //队头++ 就是弹出队头
}
else if(op=="query"){
cout<<q[hh]<<endl; //输出队头
}
else if(op=="empty"){
if(hh<=tt) //如果队头是小于等于队尾的 就非空
cout<<"NO"<<endl;
else cout<<"YES"<<endl;//否则为空
}
}
return 0;
}
```
###六.单调栈
对暴力`进行优化
题型 找到左边或者右边,第一个比它大或者比他小的数
```
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],s[N]; //s为栈
int tt=0;
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(tt&&s[tt]>=a[i])tt--;//tt代表栈不为空
if(tt)cout<<s[tt]<<" "; //s[tt]>=a[i]当前栈顶元素大于当前元素则把他弹出
else cout<<-1<<' '; //操作后如果栈不为空则栈顶元素就是第一个小于当前元素的元素
s[++tt]=a[i];//再把当前元素入栈
}
return 0;
}
七. 单调队列
同样是对暴力进行优化
应用: 求滑动窗口中的最大值和最小值
栈和队列就是删除没有用的元素,维护一个单调性
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N];
int tt=-1,hh;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
if(hh<=tt&&i-k+1>q[hh])hh++;
//队列不为空,如果起点>q[hh] 队列中存的是下标
//则需要将窗口向后移动一个 h++;
while(hh<=tt&&a[q[tt]]>=a[i])tt--;
//队列不为孔二 且队尾下标对应元素大于a[i]则弹出
q[++tt]=i;//操作结束把新下标入队
if(i-k+1>=1)cout<<a[q[hh]]<<" ";
//从第一个窗口开始输出 队头就是最小值
}
cout<<endl;
tt=-1,hh=0;
for(int i=1;i<=n;i++){
if(hh<=tt&&i-k+1>q[hh])hh++;
//队列不为空,如果起点>q[hh] 队列中存的是下标
//则需要将窗口向后移动一个 h++;
while(hh<=tt&&a[q[tt]]<=a[i])tt--;
//队列不为孔二 且队尾下标对应元素大于a[i]则弹出
q[++tt]=i;//操作结束把新下标入队
//注意先把这个树加进去再输出
if(i-k+1>=1)cout<<a[q[hh]]<<" ";
//从第一个窗口开始输出 队头就是最小值
}
cout<<endl;
return 0;
}
KMP 算法
S[N] P[M] S长串 P 短串
寻找原串中包含子串的数目
next[N];
next[N] 只和字串有关 预处理子串
以某一点为中点的后缀和前缀 最长相等的长度是多少
1 j i
p[1~j] = p[i-j+1~i];
*/
//7. KMP
//求Next数组：
// s[]是模式串，p[]是模板串, n是s的长度，m是p的长度
//for (int i = 2, j = 0; i <= m; i++)
//{
// while (j && p[i] != p[j + 1]) j = ne[j];
// if (p[i] == p[j + 1]) j++;
// ne[i] = j;
//}
// 匹配
//for (int i = 1, j = 0; i <= n; i++)
//{
// while (j && s[i] != p[j + 1]) j = ne[j];
// if (s[i] == p[j + 1]) j++;
// if (j == m)
// {
// j = ne[j];
// 匹配成功后的逻辑
// }
//}
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=10010,M=100010;
char p[N],s[M];
int ne[N];
int ans;
int main()
{
cin>>n>>p+1>>m>>s+1;
for(int i=2;i<=n;i++){
while(j&&p[i]!=p[j+1])
j=ne[j];
if(p[i]==p[j+1])
j++;
ne[i]=j;
}
for(int i=1;i<=n;i++){
while(j&&s[i]!=p[j+1])
j=ne[j];
if(p[i]==p[j+1])
j++;
if(j==n){
cout<<i-n+1-1<<endl;
j=ne[j];
}
}
return 0;
}
trie 字典树
在一个集合中快速查找和存储一些字符串
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//son[N][27] 表示一共有N 个节点 每个节点最多
//有 26 个儿子 所以二维的值是27
//cnt[N] 表示以某个字母为结尾的单词数量
//idx 表示当前创建的空间
int son[N][27],cnt[N],idx;
int n;
string str;
void Insert() {
int len = str.size();
int p = 0;
for (int i = 0; i < str.size(); i++) {
int u = str[i] - 'a';
//如果没有这个字母就创建一个
if (!son[p][u])son[p][u]=++idx;
//创建后改变p 的值 增加节点数
p = son[p][u];
}
//单词全部存储完毕 则将cnt++
cnt[p]++;
}
int Que() {
int len = str.size();
int p = 0;
for (int i = 0; i < str.size(); i++) {
int u = str[i] - 'a';
//如果找到某个字母时发现没有 则return0
if (!son[p][u])return 0;
//将p变成他的儿子
else p = son[p][u];
}
return cnt[p];//返回这个单词的数量
}
int main()
{
cin >> n;
while (n--) {
char c;
cin >> c>>str;
if (c == 'I') {
Insert();
}
else if (c == 'Q') {
int ans=Que();
cout << ans << endl;
}
}
system("PAUSE");
return 0;
}
最大异或对
将一个数的二进制逐个插入字典树
从最高位开始找 每次找这个数相反的支路
如果没有相反的支路就走本支路
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M=31e5+10;
int son[M][2],a[N],idx;
int n,ans=-0x3f3f3f3f;
void Insert(int x)
{
int p = 0;
for (int i = 30; i >=0; i--)
{
if (!son[p][x >> i & 1]) {
//x>>i&1 分离出一个数的每个二进制位
son[p][x >> i & 1] = ++idx;
//如果没有则开建立一个儿子节点
}
p = son[p][x >> i & 1];
//如果有则p变成他的儿子节点
}
}
int Search(int x)
{
int p = 0;
long long res=0;
for (int i = 30; i >= 0; i--) {
if (son[p][!(x>>i&1)]) {
//如果有与他相反的那个支路走这条
p = son[p][!(x>>i&1)];
//结果加上 1左移动i位
res += 1 << i;
}
else p = son[p][x>>i&1];
//如果没有相反的则走这条相同的路
//异或后为0 res 不变
}
return res;
}
int main()
{
/*int a = 1, b = 2,c;
c = a ^ b;
cout << c << endl;*/
//cout << M << endl;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
Insert(a[i]);//插入字典树
}
for (int i = 1; i <= n; i++)
{
ans=max(ans,Search(a[i]));
//搜索每个元素异或最大的支路值
}
cout << ans << endl;
system("PAUSE");
return 0;
}
并查集
1、将两个集合合并
2、询问两个元素是否在一个集合当中
基本原理：
用树的形式来维护一个集合。
每个树的根节点的编号为这个集合的编号
每一个节点都存储一下其父亲节点是谁P[x]表示x的父节点
问题1：如何判断树根？ 若P[X]=x 则x是树根
问题2：如何求x的集合编号 while(p[x]!=x)x=p[x];
问题3：如何合并两个集合：若px是x集合的编号，py是y集合的编号
则 p[x]=y 把x集合合并到y集合当中
并查集的优化 ： 路径压缩
遍历后 将所有的儿子节点都指向根节点
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], idx;
int n, m;
int find(int x) {
if (p[x] != x) //如果还没找到根节点 则继续往上找
p[x]=find(p[x]);//找到后赋值给p[x]并且返回
// 注意找到后·赋值给p[x] 顺便做了路劲压缩
//for (int i = 1; i <= n; i++)
// cout << p[i] << " ";
//cout << endl;
return p[x];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
p[i] = i; //起初的时候每个数字是一个集合
//初始化他们的根节点为本身
}
while (m--)
{
char c;
int a, b;
cin >> c >> a >> b;
if (c == 'M') {
p[find(a)] = find(b); //将a 直接并入b中
}
else if (c == 'Q') {
if (find(a) == find(b))//如果a b的根节点相同则属于一个集合
cout << "Yes" << endl;
else cout << "No" << endl;
}
}
//system("PAUSE");
return 0;
}
连通块中点的数量 837
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], cnt[N];
int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
p[i] = i;
cnt[i]++;
}
while (m--) {
string op;
int a, b;
cin >> op;
if (op =="C") {
cin >> a >> b;
if (find(a) != find(b))
{
int num = cnt[find(a)];
p[find(a)] = find(b);
cnt[find(b)] += num;
}
}
else if (op == "Q1") {
cin >> a >> b;
if (find(a) == find(b))
cout << "Yes" << endl;
else cout << "No"<<endl;
}
else if (op == "Q2") {
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}
费解的开关
1、 按的顺序可以任意
2、 按偶数次是不变的所以每个格子最多按一次按两次没用
3、从第一行开始 第一行操作完不改变 则 第二行被第一行唯一确定
核心：每一行开关的操作完全被上一行灯的亮灭状态所决定
问题
1；如何枚举第一行的操作
位运算二进制枚举
2^5=0~31
00000 00001
....~11111 16+8+4+2+1=31
for(int i=0;i<32;i++)
{
看第k位是否需要操作
i >> K[HTML_REMOVED]
}
2: turn(x,y)
根据偏移量 写开关变换的状态
3：时间复杂度
#include<bits/stdc++.h>
using namespace std;
string s[6],back_up[6];
const int N=6;
//char s[N][N],back_up[N][N];
int n;
int dx[5]={0,-1,0,1,0};//枚举五个方向
int dy[5]={-1,0,1,0,0};
void turn(int x,int y)
{
for(int i=0;i<5;i++){
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0||xx>4||yy<0||yy>4)
continue;
if(back_up[xx][yy]=='0')
back_up[xx][yy]='1';
else back_up[xx][yy]='0';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
while(n--){
string s[5];
for(int i=0;i<5;i++)
cin>>s[i];
int ans=10;
for(int op=0;op<32;op++){ //注意这里枚举的是操作数目 而不是第一行的状态
//memcpy(back_up,s,sizeof(s));
for(int i=0;i<5;i++)
back_up[i]=s[i]; //用一个数组作为拷贝数组 用来改变原数据
int step=0;
for(int i=0;i<5;i++){
if(op>>i&1)
{
step++;
turn(0,i);
}
}
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
if(back_up[i][j]=='0'){
step++; //这一行的为0 下一行必须改变
turn(i+1,j);
}
}
}
bool dark=false;
for(int i=0;i<5;i++){
if(back_up[4][i]=='0')
{
dark=true;
break;
}
}
if(!dark)
ans=min(ans,step);
for(int i=0;i<5;i++)
back_up[i]=s[i];
}
if(ans>6)
cout<<-1<<endl;
else cout<<ans<<endl;
}
return 0;
}
飞行员兄弟
- 每个开关只按一次
2.顺序是没有关系的
解题思路
1、枚举所有方案
2、按照方案对所有灯泡进行操作
3、判断是否全亮->记录方案
#include<bits/stdc++.h>
using namespace std;
const int N = 5;
char g[N][N], backup[N][N];
typedef pair<int, int> PII;
int get(int x, int y) {
return x * 4 + y; // 将 二维数组下标 转化为 0~15
}
void turn_one(int x, int y) {
if (g[x][y] == '+')
g[x][y] = '-';
else g[x][y] = '+';
}
void turn_all(int x, int y) {
for (int i = 0; i < 4; i++) {
turn_one(x, i);// 行操作
turn_one(i, y);//列操作
}
turn_one(x, y);// 由于x y 这个点操作了 两次 所以再操作一次 将其恢复为操作一次
}
int main()
{
for (int i = 0; i < 4; i++)
cin >> g[i];
vector<PII> res; //记录最终答案res
for (int op = 0; op < (1 << 16); op++) {//枚举每一种状态 一共2^16种 1表示要按下这个开关一次
vector<PII> temp;//每次枚举新建一共存储方案
memcpy(backup, g, sizeof(g));//拷贝保留原数据
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (op >> get(i, j) & 1) { //二维枚举 每当遇到一共1 就是一次操作
temp.push_back(make_pair(i, j));//没操作一次 记录再方案中
turn_all(i, j); //进行操作
}
}
}
bool has_closed = false; //判断结果
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (g[i][j] == '+')
has_closed = true;
}
}
if (has_closed == false) {
//起初的res 是空的 所以要加入这个条件 让此时的res被temp赋值
//后面如果res的操作数是比temp多的 则更新 res
if (res.empty() || res.size() > temp.size())
res = temp;
}
memcpy(g, backup, sizeof(g));
}
cout << res.size() << endl;
vector<PII>::iterator iter = res.begin(); //迭代器 遍历输出res
for (iter; iter != res.end(); ++iter)
cout << iter->first + 1 << ' ' << iter->second + 1 << endl;
return 0;
}
/*
翻硬币
开始用了DFS 只能过一半
后来发现了规律，每个硬币反两次则无效
只需要从头到尾枚举一遍 不一样就翻一次 就可
*/
#include<bits/stdc++.h>
using namespace std;
string s1, s2;
int len;
int ans = 0x3f3f3f3f;
void turn(int num)
{
if (s1[num] == '*')
s1[num] = 'o';
else s1[num] = '*';
if (s1[num + 1] == '*')
s1[num + 1] = 'o';
else s1[num + 1] = '*';
}
int main()
{
cin >> s1 >> s2;
len = s1.length();
string backup = s1;
int step = 0;
for (int i = 0; i < len - 1; i++)
{
if (s1[i] != s2[i])
{
turn(i);
step++;
}
if (s1 == s2)
break;
}
cout << step << endl;
system("PAUSE");
return 0;
}
食物链
余1： 可以吃根节点
余2： 可以被根节点吃
余0：与根节点同类
余2吃余1 余0吃余2
所以%3余数相同的则是同一类 （关键）
带权并查集精髓总结：只要两个元素在一个集合里面，通过它们与根节点的距离就能知道它们的相对关系。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int n,k;
int p[N],d[N];
int find(int x) {
if (p[x] != x) {
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
cin >> n >> k;
int res = 0;
for (int i = 1; i <= n; i++)
p[i] = i;
while (k--)
{
int t, x, y;
cin >> t >> x >> y;
if (x > n || y > n)res++; //如果有的点大于了n 则是假话
else {
int px = find(x), py = find(y);// px 是x的根节点 y同理
if (t == 1) {
if (px == py && (d[x] - d[y]) % 3 != 0)//px==py 则x y 在同一个集合中
d[x]%3 应该 和d[y]%3 相等 这样x y 才是同类 -> (d[x]-d[y])%3==0
res++;
else if (px != py) {
p[px] = py; //如果不等则x y不在一个集合中
d[px] = d[y] - d[x];//d[x]+? %3 =d[y]%3 -> ?(d[px])=d[y]-d[x] 要使x y是同类则满足这个方程
}//可以画图
}
else {
if (px == py && (d[x] - d[y] - 1) % 3)res++;//如果px=py 则x y在同一集合 x吃y 则d[x]%3 -d[y]%3==1 ->(d[x]-d[y]-1)%3=0;
else if (px != py) {
p[px] = py; //如果不在同一集合 则把x并入y集合中 (d[px]+? )%3=d[y]%3+1;
d[px] = d[y] + 1 - d[x];
}
}
}
}
cout << res << endl;
system("PAUSE");
return 0;
}
堆: 手写堆
一.堆操作
1. 插入一个数
2.求这个集合当中的最小值
3.删除最小值
上面三个是STL 中可以实现的
4. 删除任意一个元素
5.修改任意一个元素
后两个操作只有手写堆才可以实现
二.堆描述
堆是完全二叉树 除了最后一层节点之外 上面所有节点都是满的
最后一个节点从左到右排布
三.堆的构造:
堆的一个点小于等于左右儿子(左右儿子大小不一定)
根节点为堆的最小值
注意下标从1开始
四.堆存储
使用一个一维数组存储
x的做儿子: 2x
x的右儿子:2x+1;
五.核心操作
down
up
heap 堆 size 堆的大小
1. 插入操作
heap[++size]=x; up(size);
2.求当前堆的最小值
heap[1] ,堆顶一定是最小的
3. 删除最小值
用整个堆的最后一个元素覆盖掉堆顶元素 size-- 再down
(因为一维数组删除头非常困难,但是删除尾部很容易)
heap[1]=heap[size];size--; dowx(1);
4. 删除任意一个元素
heap[k]=heap[size];size--;down(k);up(k); //只会执行down up 其中一个
5.修改任意一个元素
heap[k]=x;down(k);up(k);
void down(int u){
int t=u;
如果有左儿子 且 左儿子小于顶点 则把左儿子变成顶点
if(u*2<=size&&h[u*2]<h[t])t=u*2;
如果有右儿子 且 右儿子小于顶点 则把右儿子变成顶点
if(u*2+1<=size&&h[u*2+1]<h[t])t=u*2+1;
如果 u改变了 交换当前最小值和u的值 便且再down一下t
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
void up(int u)
{
//u/2 同时包括了左二字和有儿子 2/2=1 3/2=1;
while(u/2&&h[u/2]>h[u]){
swap(h[u/2],h[u]);// 如果大了就交换
u/=2; //每次u往上走
}
}
例1 堆排序
ph[]从下标到堆里 hp[]从堆到下标里
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],size1;
int n,m;
void down(int u)
{
int t=u;
if(u*2<=size1&&h[u*2]<h[t])t=u*2;
if(u*2+1<=size1&&h[u*2+1]<h[t])t=u*2+1;
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>h[i];
size1=n;
for(int i=n/2;i;i--)
down(i);
while(m--)
{
cout<<h[1]<<" ";
h[1]=h[size1];
size1--;
down(1);
}
return 0;
}
例2: 模拟堆
#include<bits/stdc++.h>
using namespace std;con1
const int N=100010;
int h[N],ph[N],hp[N],cnt;
void heap_swap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void down(int u){
int t=u;
if(u*2<=cnt&&h[u*2]<h[t])t=u*2;
if(u*2+1<=cnt&&h[u*2+1]<h[t])t=u*2+1;
if(u!=t){
heap_swap(u,t);
down(t);
}
}
void up(int u)
{
while(u/2&&h[u]<h[u/2]){
heap_swap(u,u/2);
u/=2;
}
}
int main()
{
int n,m=0;//m当前第几个插入的数
cin>>n;
while(n--){
string op
int k,x;
cin>>op;
int k,x;
if(op=="I"){
cin>>x;
cnt++;
m++;
ph[m]=cnt;
hp[cnt]=m;
h[cnt]=x;
up(cnt);
}
else if(op=="PM")cout<<h[1]<<endl;
else if(op=="DM"){
heap_swap(1,cnt);
cnt--;
down(1);
}
else if(op=="D")
{
cin>>k;
k=ph[k];
heap_swap(k,cnt);
cnt--;
up(k);
down(k);
}else {
cin>>k>>x;
k=ph[k];
h[k]=x;
up(k);
down(k);
}
return 0;
}
哈希表 （散列表）
一、 存储结构
1.开放寻址法
2.拉链法
二、 字符串哈希方式
大范围的集合 映射到 从0~N
x mod 1e5 模要取一个质数 （冲突的概率小）
可能会产生冲突
1.拉链法：开一个一维数组 存储哈希的值
添加 找h(x) 插入到链上
查找 找h(x) 遍历链看有没有
- 开放寻址法
1.添加 先找到h[k] 如果h[k] 有人 则往后找 直到没有人
2.查找 第k个坑位开始 从前往后找
如果当前位置有人，是x 则找到
如果当前位置有人，不是x 则继续找下一个
如果当前位置没人，则x不存在
hash表的删除一般不会直接删除 一般都是 把删除的元素做特殊的标记
而且一般不会用到删除操作
开放寻址法的核心操作
find函数：如果x在hash表中存在，则返回x的位置
如果x不存在则返回x应该存储的位置
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int mod=2e5+3;
int null =0x3f3f3f3f;
int h[N];
int find(int x)
{
int t=(x%mod+mod)%mod;//为了防止余数是负数
while(h[t]!=null&&h[t]!=x){//如果这个坑是空了 就不存在x了
//如果这个坑==x了 那就找到了
t++; //继续找下一个坑
if(t==N) //如果到末尾了 那就从头开始找
t=0;
}
return t; //返回值是 x应该放的位置 或者是找到x的位置
}
int main()
{
int n;
cin>>n;
memset(h,0x3f,sizeof(h));//首先将数组置为null 作为判断是否为空的标志
while(n--){
string op;
int x;
cin>>op>>x;
if(op=="I"){
// h[x]=find(x);
h[find(x)]=x; // 返回的是x应该放的位置 让哈希表中的这个位置=x
}
else {
if(h[find(x)]==null)//返回的值如果是空 则没有找到
cout<<"No"<<endl;
else cout<<"Yes"<<endl;//否则就是找到了 不存在别的情况
}
}
return 0;
}
二. 字符串哈希
字符串前缀哈希法
核心 在p 进制的角度将一个字符串看成是一个数字
如何来定义每一个前缀的哈希
将字符串看成是P进制数
不要某一个字符映射成0 因为0的p进制还是0
假定不存在冲突 不考虑冲突
经验值 p进制为 p=131, mod 为2^64;
这里用usigned long long 来实现 溢出就是对mod取模
核心操作:
1.hash的处理
h[i]=h[i-1]p+str[i];
2.求 l 到 r 之间的字符串
h[R]-h[L]p^(R-L+1)
R-L+1=R-1-(L-2);
h[L-1] 从 p^0 ~ p^(L-2)
h[R] 从 p^0 ~p^(R-1)
预处理一个数的n次方
int p[N];
p[0]=1; //p的0次方为1;
for(int i=1;i<=n;i++)
p[i]=p[i-1]*p;
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int p=131;// 131 是 经验值
const int N=1e5+10;
ull pow1[N],h[N];// unsigned long long 溢出 就是mod 2^64
char str[N];
ull hash1(int l,int r)
{
return h[r]-h[l-1]*pow1[r-l+1]; //核心操作
//求出l~r 区间内的hash值
}
int main()
{
int n,m;
cin>>n>>m>>str+1;//注意从下标1开始存储字符
pow1[0]=1; // p的零次幂等于1
for(int i=1;i<=n;i++)
{
pow1[i]=pow1[i-1]*p;//对p的次方 进行预处理操作
}
for(int i=1;i<=n;i++)
{
h[i]=h[i-1]*p+str[i];//核心操作 得到每个字符的hash值
}
while(m--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(hash1(l1,r1)==hash1(l2,r2))//如果两个区间的hash值相等 则两个字符串相同
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
重点 C++的STL
vector
变长数组
倍增的思想
系统为某一程序分配空间时,所需时间与空间大小无关
与申请次数有关
#include<vector>
int main()
{
vector<int> a;// 定义一个vector
vector<int> a(10);//定义一个长度为10的vector
vector<int> a(10,3);//长度为10 每个元素为3
vector<int> a[10];//定义一个vector数组
注意 size();和empty();是所有容器都有的函数
时间复杂度为O(1);
a.size();//vector中元素的个数
a.empty();//vector是否为空
并不是所有容器都有clear();比如队列就没有
a.clear(); //清空vector
a.front(); //返回vector的第一个数 .
a.back();//返回vector的第二个数
a.push_back();//向vctor的最后插入一个树
a.pop_back();//删除vector的最后一个树
//迭代器
a.begin();// vector的第0个数 a[0]
a.end();//vector的最后一个数的后面一个数a[a.size()];
遍历方式
for(int i=0;i<10;i++)a.push_back(i);
1.for(int i=0;i<a.size();i++)cout<<a[i]<<" ";
cout<<endl;
2.for(vector<int>::iterator iter=a.begin();i!=a.end();i++)
cout<<*i<<" ";
cout<<endl;
3.范围遍历(C++11)
for(auto x:a)cout<<x<<' ';
cout<<endl;
vector 同样支持比较 大于小于等于 按照字典序
vector<int> a(10,3);//长度为10 每个元素为3
vector<int> b(10,3);
if(a==b)
cout<<"a=b"<<endl;
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
return 0; }
pair
pair<int,string> p;
p.first;//取得第一个元素
p.second;//取得第二个元素
支持比较运算 按照字典序 以 first 为第一关键字,以second为第二关键字
p=make_pair(10,"yxc");
C++11 :p={20,"abc"};
pair<int,pair<int,int> > //有三个属性时
与结构体相比 可以自带比较函数
string
字符串
size();
empty();
clear();
length();// 作用和size一模一样
支持加减
string a="WD";
a+="def";//加上一段字符串
a+="b"; //加上一个字符
cout<<a.substr(1,3)<<endl;
cout<<substr(1,3)<<endl;
substr(); 功能返回字符串的一个字串
第一个参数: 字符串中的一个下标
第二个参数:从这个下标开始多少长度
第二个参数可以省略,返回到末尾的字串
使用printf输出
printf("%s\n",a.c_str());
c_str();返回字符串存储的第一个地址
queue
队列
push();//向队尾插入元素
front();//返回队头元素
back();//返回队尾元素
pop(); //弹出队头元素
size();
empty();
无clear();函数
如果想1清空一个q 直接重新构造一个 q=queue<int>();
priority_queue
优先队列(堆)
push();//向堆中插入一个元素
top();//返回堆顶元素
pop();//弹出堆顶元素
一般默认大根堆
也无clear函数
priority_queue<int> pq;
如果小变成小根堆
1. 插入的时候直接插入-x
2. 定义直接定义成小根堆
priority_queue<int,vector<int>,greater<int> >pq;
stack
栈
也无clear 函数
push();//向栈顶插入一个元素
top();//返回栈顶元素
pop(); //弹出栈顶元素
deque 加强版的vector
双端队列
队头队尾都可以插入删除
(加强版的vector)
size();
empty();
clear();
front();//查询第一个元素
back();//查询最后一个元素
push_back();//向队尾插入一个元素
pop_back();//弹出队尾元素
push_front();//向队首插入一个元素
pop_front();//弹出队首元素
支持随机寻址
begin();
end();
deque功能十分强大 但是速度比较慢
set,map,multiset,multimap
基于红黑树实现的,动态的维护一个有序的序列
红黑树是平衡二叉树的一种
set<int> s;//不可语有重复元素
multiset<int> ms; 可以有重复元素
size();
empty();
clear();
insert();//插入一个数
find();//查找一个数
count();//返回一个数的个数 set为1
erase():
(1)如果输入一个数x 则删除所有x
(2)如果输入一个迭代器,则删除这个迭代器
set的核心操作:
lower_bound();返回大于等于x的最小的迭代器
upper_bound(); 返回大于x的最小的迭代器
如果没有则返回end();
map
multimap
insert();//输入的参数是一个pair
erase();//输入的参数是pair或者迭代器
可像数组一样使用map
map<string,int> m;
a["WD"]=1;
cout<<a["WD"]<<endl;
支持lower_bound();upper_bound();
unordered_set
unordered_map
unordered_multiset
unordered_multimap
哈希表实现
内部无序
和上面操作一样 时间复杂度是o(1),比上面速度快
不支持 lower_bound();upper_bound();
不支持 迭代器的++ --;
bitset 位存储
压位
bitset<10000> s;
~,&^|;
>>,<<
==,!=;
[];
count();返回有多少个1
set(); 把所有为置为1
set(k,v); 把第k位变成v
reset();把所有位置0
