Acwing 第二章 数据结构
单调队列
154. 滑动窗口
用一个队列维护窗口里面的所有值
当即将入队的队列比队尾元素小时，就让队尾元素出队，循环直到大于等于队尾元素时，停止，因为没有用
求最大值与该思想类似
#include
#include
#include
using namespace std;
const int N = 1e6 + 10;
int n,k;
int a[N];
int q[N];//队列存储的是下标
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i ++ )
{
cin>>a[i];
}
int hh = 0,tt = -1;
for (int i=0;i k) hh++; //维护当前窗口元素个数与k一致
while(hh<=tt && a[i] <= a[q[tt]]) tt--; //删去冗余元素，注意是从队尾删除
q[++tt] = i; //新元素入队
if(i+1>=k) cout< k) hh++;
while(hh<=tt && a[i] >= a[q[tt]]) tt--;
q[++tt] = i;
if(i+1>=k) cout< 字典树(Trie)
835. Trie字符串统计
Trie:高效的存储和查找字符串集合的数据结构
#include
#include
#include
#include
using namespace std;
const int N = 2e4+10;
int son[N][26],idx;//son数组表示字典树，idx表示层数索引
int cnt[N];//以当前结点结尾的单词数量
char x[N];
char op[2];
void insert(char s[])
{
int cur = 0;//表示当前位于第几层
for(int i=0;s[i]!='\0';i++)
{
int t = s[i] - 'a';
if(!son[cur][t]) son[cur][t] = ++idx; //没有路径就创造路径,注意是++idx
//idx是下一字母的层数
cur = son[cur][t];
}
cnt[cur]++;//更新以该结点结尾的单词数量
}
int query(char s[])
{
int cur = 0;//表示当前位于第几层
for(int i=0;s[i]!='\0';i++)
{
int t = s[i] - 'a';
if(!son[cur][t]) return 0;//不存在路径，直接返回0
cur = son[cur][t];
}
return cnt[cur];
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ )
{
cin>>op>>x;
if(op[0] == 'I')
{
insert(x);
}
else cout< 并查集
240. 食物链
带权并查集
#include
#include
#include
using namespace std;
const int N = 50005;
int n,k,c,x,y;
int p[N],d[N];
int ans;
int find(int x)
{
int t = p[x];
if(p[x]!=x)
{
p[x] = find(p[x]);
d[x] += d[t]; //维护距离，find前表示到父节点的距离，find后表示到祖宗结点的距离
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
}
while(k--)
{
cin>>c>>x>>y;
if(x>n||y>n)
{
++ans;
continue;
}
int px = find(x),py = find(y);
if(c==1) //同类，距离取余3为0
{
if(px == py && (d[x] - d[y]) % 3 != 0) ans++; //同一集合但距离mod3不为0，假话
else if(px!=py) //不同集合，则是真话，合并它们并用距离表示同类关系
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else //x吃y，距离取余3为1
{
if(px == py && (d[x] - d[y] - 1) % 3 !=0) ans++; //同一集合但距离mod3不为1，假话
else if(px != py) //不同集合，则是真话，合并它们并用距离表示捕食关系
{
p[px] = py;
d[px] = d[y] - d[x] + 1;
}
}
}
cout< 字符串哈希
841. 字符串哈希
#include
#include
#include
using namespace std;
const int N = 1e5 + 10,P = 131;
typedef unsigned long long ULL;
ULL h[N],p[N];
int n,m;
char str[N];
ULL get(int l,int r)
{
return h[r] - h[l-1] * p[r-l+1]; //取区间字符串的哈希值 h[r] - h[l-1] * p^(r-l+1)
}
int main()
{
scanf("%d%d%s", &n, &m,str+1);
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
p[i] = p[i-1] * P; //预处理P的n次幂
h[i] = h[i-1] * P + str[i]; //计算哈希值
}
while (m -- )
{
int l1,r1,l2,r2;
scanf("%d%d%d%d", &l1, &r1,&l2,&r2);
if(get(l1,r1) == get(l2,r2)) puts("Yes");
else puts("No");
}
return 0;
}