AKSZ - 第8~10课笔记

陈弘毅

2024-06-19 16:52:44

发布于：广东

9阅读

0回复

0点赞

并查集-使用虚点实现单个点的更改

将所有实点的父亲设置成一一对应的虚点，虚点的父节点是自己
这样所有的操作都会针对虚点，而所有实点都是叶子结点
这样更改单个节点时就不可能影响它子节点原来指向的点，因为它没有子节点
模板：

const int maxn=1e5+5; 
int f[maxn*2];
for (int j=1; j<=n; j++){
	f[j] = j+maxn; 
	f[j+maxn] = j+maxn; 
}
int find(int x){
	if (x==f[x]) return x;
	f[x] = find(f[x]);
	return f[x]; 
}
void merge(int x, int y){
	//之前的笔记写错了，union是关键字，不能用
	f[find(x)] = find(y); 
}
void change(int x, int y){
	f[x] = find(y); 
}

通过字符串哈希判断子串位置

字符串可以视为一个256进制的数组
可以通过类似于进制转换的方式将其转唯int，取模后得到相应的哈希
可以自定义字符串的进制，取模的数来避免出题人卡哈希
使用另一种哈希方式，进行两次哈希判断可以很好的防止被卡

双哈希例子：

const int seed=233;
const int mod=1e9+7; 
const int mmod=998244353; 
long long hash1[205], hash2[205]; 
long long hash1ss, hash2ss, K=1; 
string s, subs; 

for (int k=0; s[k]; k++){
    hash1[k+1]=hash1[k]*seed+s[k];
    hash1[k+1] %= mod; 
    hash2[k+1]=hash2[k] + s[k]*s[k]; 
    hash2[k+1] %= mmod; 
}
for (int k=0; subs[k]; k++){
    hash1ss = hash1ss*seed + subs[k];
    hash1ss %= mod; 
    hash2ss += subs[k]*subs[k];
    hash2ss %= mmod; 
    K *= seed;
    K %= mod; 
} 
for (int k=0; s[k+subs.length()-1]; k++){
    long long h1=hash1[k+subs.length()]-hash1[k]*K;
    h1 = (h1%mod+mod)%mod; 
    long long h2=hash2[k+subs.length()]-hash2[k]+mmod; 
    h2 %= mmod; 
    if (h1%mod == hash1ss && h2%mmod == hash2ss){
        cout << k+1 << endl; 
    }
}

矩阵哈希判断子矩阵

例子：

const int seedW=233;
const int seedH=2337; 
const int mod=1e9+7; 

struct matrix{
	int w, h;
	int f[105][105]; 
}; matrix M, subM; // 判断子矩阵subM在M中出现的位置

long long hashM[105][105];
long long W[105];
long long H[105];
long long Hash=0;

W[0]=1; H[0]=1;
for (int k=1; k<105; k++){
	W[k] = W[k-1]*seedW%mod;
	H[k] = H[k-1]*seedH%mod; 
}
// 计算子矩阵subM的哈希值
long long K=1, KK=1;
for (int j=subM.h; j>=1; j--){
	KK=1; 
	for (int k=subM.w; k>=1; k--){
		Hash += subM.f[j][k]*KK%mod*K%mod;
		Hash %= mod; 
		KK = KK*seedW%mod;
	} K=K*seedH%mod; 
}
// 计算M各个点的哈希值
for (int j=1; j<=M.h; j++){
	for (int k=1; k<=M.w; k++){
		hashM[j][k] = hashM[j][k-1]*seedW+M.f[j][k];
		hashM[j][k] %= mod;
	}
	for (int k=M.w; k>=1; k--){
		hashM[j][k] = hashM[j-1][k]*seedH+hashM[j][k];
		hashM[j][k] %= mod;
	}
}
long long A,B,C,D;
for (int j=a; j<=M.h; j++){
	for (int k=b; k<=M.w; k++){
		A = hashM[a][b];
		B = hashM[a-subM.h][b-subM.w];
		C = hashM[a-subM.h][b];
		D = hashM[a][b-subM.w];
		B = B*H[subM.h]%mod*W[subM.w]%mod;
		C = C*H[subM.h]%mod;
		D = D*W[subM.w]%mod;
		if (((A+B-C-D)%mod+mod)%mod == Hash){
			cout << a-M.h+1 << ' ' << b-M.w+1 << endl;
		}
	}
}

哈希判断最长回文串

对字符串进行正反哈希，判断是否相等，结合二分即可

树状数组

一种用于快速解决区间问题的数据结构
更改/查询复杂度为O(logn)
类似于前缀和

lowbit(x) -> x&-x
获取二进制最低位1代表的数
e.g. lowbit(6) = 2, lowbit(5) = 1, lowbit(8) = 8

模版：

int tree[maxn]; 

int lowbit(int x){
	return x&-x; 
}
void add(int ind, int val){
	for (int x=ind; x<=maxn; x+=lowbit(x)){
		tree[x] += val; 
	}
}
int query(int ind){
	// 返回1-ind中数据的和
	int ret=0; 
	for (int x=ind; x>0; x-=lowbit(x)){
		ret += tree[x]; 
	}
	return ret; 
}

离散化标准写法

int rk[maxn];
int a[maxn]; 

for (int x=1; x<=n; x++){
	cin >> a[x]; 
	rk[x] = a[x]; 
}
sort(a+1, a+1+n); 
int len = unique(a+1, a+1+n)-a-1; 

for (int x=1; x<=n; x++){
	rk[x] = lower_bound(a+1, a+1+len, rk[x])-a;
}

map写法

int a[maxn];
int cnt=1; 
map<int, int> mp; 

for (int x=1; x<=n; x++) cin >> a[x];
sort(a+1, a+1+n);
int len = unique(a+1, a+1+n)-a-1; 

for (int x=1; x<=len; x++){
	mp[a[x]] = cnt; 
	cnt += 1; 
}

线段树

一种高效的区间查询/更新的数据结构，复杂度O(logn)
将数组分割为多个不重叠的区间
储存线段树的数组需要开到4*maxn
lazy tag可以让区间修改的复杂度降到O(logn)
它对修改进行标记，等查询到的时候再修改子区间

模板：

#define lc o*2
#define rc o*2+1
typedef long long ll; 

ll tree[4*maxn]; 
ll lazy[4*maxn]; 
int ql, qr, v; 

void pushup(int o){
    tree[o] = tree[lc]+tree[rc]; 
}
void pushdown(int o, int l, int r){
    if (lazy[o]){
        int mid=l+r>>1; 
        tree[lc] += (mid-l+1)*lazy[o];
        tree[rc] += (r-mid)*lazy[o];
        lazy[lc] += lazy[o];
        lazy[rc] += lazy[o]; 
        lazy[o] = 0; 
    }
}

void build(int o, int l, int r){
    if (l==r) {
        tree[o]=a[l]; 
        return;
    }
    int mid = l+r>>1;
    build(lc, l, mid);
    build(rc, mid+1, r);
    pushup(o);
}
void add(int o, int l, int r){
    if (ql <= l && r <= qr){
        tree[o] += (r-l+1)*v; 
        lazy[o] += v;
        return; 
    }
    int mid=l+r>>1;
    pushdown(o, l, r); 
    if (ql<=mid) add(lc, l, mid);
    if (qr>mid) add(rc, mid+1, r); 
    pushup(o); 
}
ll query(int o, int l, int r){
    if (ql<=l && r<=qr){
        return tree[o]; 
    }
    int mid=l+r>>1;
    pushdown(o, l, r);
    ll ret=0;
    if (ql<=mid) ret+=query(lc, l, mid);
    if (qr>mid) ret += query(rc, mid+1, r);
    return ret; 
}