ACM

数据结构

KMP

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int ne[N];
int main(){
    int len1,len2;
    string s1,s2;
    cin>>len1>>s1>>len2>>s2;
    s1=' '+s1;
    s2=' '+s2;
    for(int i=2,j=0;i<=len1;i++){
        while(j&&s1[j+1]!=s1[i])j=ne[j];
        if(s1[j+1]==s1[i])j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=len2;i++){
        while(j&&s1[j+1]!=s2[i])j=ne[j];
        if(s1[j+1]==s2[i])j++;
        if(j==len1){
            cout<<i-len1<<' ';
        }
    }
    return 0;
}

Trie - 字符串统计

维护一个字符串集合，支持两种操作：

  1. I x 向集合中插入一个字符串 $x$；
  2. Q x 询问一个字符串在集合中出现了多少次。 共有 $N$ 个操作，所有输入的字符串总长度不超过 $10^5$，字符串仅包含小写英文字母。
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N][26],cnt[N],idx;
void fi(char str[]){
	int m=0;
	for(int i=0;str[i];i++){
		int t=str[i]-'a';
		if(!a[m][t]){
			a[m][t]=++idx;
		}
		m=a[m][t];
	}
	cnt[m]++;
}
void fq(char str[]){
	int m=0;
	for(int i=0;str[i];i++){
		int t=str[i]-'a';
		if(!a[m][t]){
			printf("0\n");
			return;
		}
		m=a[m][t];
	}
    printf("%d\n",cnt[m]);
}
int main(){
	int n;
	char c,str[N];
	cin>>n;
	while(n--){
		cin>>c>>str;
		if(c=='I')fi(str);
		else fq(str);
	}
	return 0;
}

并查集

#include<iostream>

using namespace std;

const int N=100010;
int p[N];//定义多个集合

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(*op=='M') p[find(a)]=find(b);//集合合并操作
        else
        if(find(a)==find(b))
        //如果祖宗节点一样,就输出yes
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

模拟散列表

#include<bits/stdc++.h>
using namespace std;
const int N=100003;
int h[N],e[N],ne[N],idx,f;
int main(){
	int n,x;
	cin>>n;
	string s;
	memset(h,-1,sizeof(h));
	while(n--){
		cin>>s>>x; 
		int k=(x%N+N)%N;
		if(s=="I"){
			e[idx]=x;
			ne[idx]=h[k];
			h[k]=idx;
			idx++;
			continue;
		}
		k=h[k];
		f=1;
		while(k!=-1){
			if(e[k]==x){
				printf("Yes\n");
				f=0;
				break;
			}
			k=ne[k];
		}
		if(f)printf("No\n");
	
	}
	return 0;
}

字符串哈希

给定一个长度为 $n$ 的字符串，再给定 $m$ 个询问，每个询问包含四个整数 $l_1, r_1, l_2, r_2$，请你判断 $[l_1, r_1]$ 和 $[l_2, r_2]$ 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=100010,P=131;
ULL h[N],p[N];
ULL f(int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}
int main(){
	char s[N];
	int n,m,l1,r1,l2,r2;
	scanf("%d%d%s",&n,&m,s+1);
	p[0]=1;
	for(int i=1;i<=n;i++){
		p[i]=131*p[i-1];
		h[i]=h[i-1]*P+s[i];
	}
	while(m--){
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		if(f(l1,r1)==f(l2,r2))printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

树状数组

给定长度为 $N$ 的数列 $A$，然后输入 $M$ 行操作指令。
第一类指令形如 C l r d，表示把数列中第 $l \sim r$ 个数都加 $d$。
第二类指令形如 Q x，表示询问数列中第 $x$ 个数的值。
对于每个询问，输出一个整数表示答案。

树状数组主要解决的是: 单点修改：a[k] 加上一个数。 区间求值： a[l~r]内所有元素和。 本题加上差分即可

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

const int N = 100009;

int n, m, a[N], t[N];

int low_bit(int x) {
    return x & -x;
}

void add(int x,int y) {
    for(;x <= n;x += low_bit(x)) t[x] += y;
    return;
}

int ask(int x) {
    int ans = a[x];
    for(;x;x -= low_bit(x))
        ans += t[x];
    return ans;
}

int main() {
    cin >> n >> m;
    for(int i = 1;i <= n;++ i) cin >> a[i];
    char ch;
    for(int i = 1, l, r, d;i <= m;++ i) {
        cin >> ch;
        if (ch == 'C') {
            cin >> l >> r >> d;
            add(l, d); add(r + 1, -d);
        }
        if (ch == 'Q') {
            cin >> d;
            cout << ask(d) << endl;
        }
    }
    return 0;
}