暑假三期集训总结

        2021年8月9号：今天上午学习一下哈希表和字符串哈希，并敲了下板子，下午补了几道上期集训结训赛的题，晚上学习了一下种类并查集。

//字符串哈希模板
//其中P(进制数)常取131或13331

# include<iostream>
# include<string.h>

using namespace std;

typedef unsigned long long ULL; 

const int maxn = 1e5 + 5;
const int P = 131;

char str[maxn];
ULL Hash[maxn];
ULL p[maxn];

ULL get(int l, int r){
	return Hash[r] - (Hash[l - 1] * p[r - l + 1]);
}

int main(){
	int n, m;
	scanf("%d%d%s", &n, &m, str);
	p[0] = 1;
	for(int i = 1; i <= n; i++){
		p[i] = p[i - 1] * P;
		Hash[i] = str[i - 1] + Hash[i - 1] * P;
	}
	while(m--){
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >>  l2 >> r2;
		if(get(l1, r1) == get(l2, r2))
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}

洛谷P1525

//种类并查集模板

# include<iostream>
# include<string.h>
# include<algorithm>
# define ll long long

using namespace std;

const int maxn = 1e5 + 5;

int fa[maxn << 1];

struct node{
	int a, b, c;
}pre[maxn << 1];

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

void combine(int x, int y){
	int fx = find(x);
	int fy = find(y);
	if(fx != fy)
		fa[fx] = fy;
}

bool cmp(node a, node b){
	return a.c > b.c; 
}

int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n << 1; i++)
		fa[i] = i;
	for(int i = 1; i <= m; i++)
		cin >> pre[i].a >> pre[i].b >> pre[i].c;
	sort(pre + 1, pre + m + 1, cmp);
	for(int i = 1; i <= m; i++){
		if(find(pre[i].a) == find(pre[i].b)){
			cout << pre[i].c << endl;
			return 0;
		}
		combine(pre[i].a, pre[i].b + n);
		combine(pre[i].b, pre[i].a + n);
	}
	cout << "0" << endl;
	return 0;
}

2021年8月10号：今天和学长们一起打了一场比赛，感觉整体比较难受，几乎全场在罚坐，晚上去补了下几道比赛题。此外，今天还学习到了floor函数的使用方法，复习了一下逆元以及除法取余的操作。

floor函数：

int /double / .... = floor(x);

功能：返回一个小于传入参数的最大整数

参数：x为将来被处理的数

返回值：返回不大于x的最大整数、

2021年8月12号：

        今天早上学习了一下怎么使用random()生成随机数据，然后帮同学调试了下vscode。下午补了道昨天比赛的题，然后去看了下皮克定理，晚上组织打了场比赛，复习了下欧拉筛。