[2021.8纪中集训Day5]

2024-01-10 10:08:28

目录

[2021.8纪中集训Day5] 

前言

今天的题都比较水,T1直接模拟,T2是比较基础的树形DP,T3大暴力,T4相关的内容学过也不难,简单的题解不说具体思路了

4764. 【NOIP2016提高A组模拟9.9】Brothers

题目

[2021.8纪中集训Day5]

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

const int N = 110 , M = 110;
int n , m , p , k;
int map[N][M];
int tmp[N][M];

const int f[4][2] = {0,1 , 0,-1 , 1,0 , -1,0};
int main() {
	p = read() , n = read() , m = read() , k = read();
	for(int i = 1 ; i <= n ; i++)
		for(int j = 1 ; j <= m ; j++)
			map[i][j] = read();
	
	for(int _ = 1 ; _ <= k ; _++) {
		memcpy(tmp , map , sizeof(map));
		for(int i = 1 ; i <= n ; i++)
			for(int j = 1 ; j <= m ; j++)
				for(int l = 0 ; l < 4 ; l++) {
					int x = i + f[l][0] , y = j + f[l][1];
					if(map[x][y] == (map[i][j] + 1) % p)
						tmp[x][y] = map[i][j];
				}
		memcpy(map , tmp , sizeof(map));
	}
	
	for(int i = 1 ; i <= n ; i++) {
		for(int j = 1 ; j <= m ; j++)
			printf("%d " , tmp[i][j]);
		putchar('\n');
	}
	return 0;
}

4765. 【NOIP2016提高A组模拟9.9】Crisis

题目

[2021.8纪中集训Day5]

思路

设\(f_i\)表示第\(i\)个人递交申请需要的工人递交申请的数量的最小值,特殊地,如果\(i\)是叶子结点(工人),\(f_i=1\).显然,对于其他结点,直接将按子结点的\(f\)排序,选最小的若干个,使其至少占子节点数量的\(T\%\)即可,\(f_i\)就是这些选出来的\(f\)的和.

如果输入是一条链,是会爆栈的,因此我用了类似拓扑排序的方法枚举点.

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

const int N = 100010;

struct EDGE {
	int to , nxt;
}son[N];
int head[N];
void addson(int fa , int s) {
	static int cnt = 0;
	++cnt;
	son[cnt].to = s , son[cnt].nxt = head[fa] , head[fa] = cnt;
}

int n , t;
int ind[N];
int f[N];

int tmp[N] , sonnum;
int fa[N];
int main() {
	n = read() , t = read();
	for(int i = 1 ; i <= n ; i++) {
		addson(fa[i] = read() , i);
		++ind[fa[i]];
	}
	
	
	queue <int> q;
	for(int i = 0 ; i <= n ; i++)
		if(ind[i] == 0)
			q.push(i);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		if(head[u] == 0)
			f[u] = 1;
		else {
			sonnum = 0;
			for(int i = head[u] ; i ; i = son[i].nxt) {
				int v = son[i].to;
				tmp[++sonnum] = f[v];
			}
			sort(tmp + 1 , tmp + sonnum + 1);
			for(int i = 1 ; i <= sonnum ; i++) {
				f[u] += tmp[i];
				if(1.0 * i / sonnum >= t * 0.01)
					break;
			}
		}
		
		--ind[fa[u]];
		if(ind[fa[u]] == 0)
			q.push(fa[u]);
	}
	
	cout << f[0];
	return 0;
}

4766. 【NOIP2016提高A组模拟9.9】Word

题目

[2021.8纪中集训Day5]

代码

这个代码没经过后期优化,跑得比较慢,故开了火车头,不会有人卡常吧,不得不说,火车头真的快,7s直接降到1s

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}


typedef unsigned long long ulint ;
typedef vector<ulint> VecTy;
const int N = 40 , LEN = 60;

inline ulint hash_(char* s , int len) {
	ulint key = 0;
	for(int i = 0 ; i < len ; i++)
		key = key * 131 + (int)s[i];
	return key;
}
void trans(char *s , int len , int d , VecTy &vec) {
	if(d >= 0)
		vec.push_back(hash_(s , len));
	if(d >= 1) {
		for(int i = 0 ; i < len ; i++) {
			for(int j = 'a' ; j <= 'z' ; j++)
				if(s[i] != j) {
					int tmp = s[i];
					s[i] = j;
					vec.push_back(hash_(s , len));
					s[i] = tmp;
				}
		}
	}
	if(d >= 2) {
		for(int i = 0 ; i < len ; i++)
			for(int j = i + 1 ; j < len ; j++)
				for(int x = 'a' ; x <= 'z' ; x++)
					for(int y = 'a' ; y <= 'z' ; y++)
						if(s[i] != x && s[j] != y) {
							int tmp1 = s[i] , tmp2 = s[j];
							s[i] = x , s[j] = y;
							vec.push_back(hash_(s , len));
							s[i] = tmp1 , s[j] = tmp2;
						}
	}
}

void print(char *s , int len) {
	for(int i = 0 ; i < len ; i++)
		putchar(s[i]);
	putchar('\n');
}
void unhash(char *s , int len , int d , ulint key) {
	if(d >= 0) {
		if(hash_(s , len) == key)	print(s , len);
	}
	if(d >= 1) {
		for(int i = 0 ; i < len ; i++) {
			for(int j = 'a' ; j <= 'z' ; j++)
				if(s[i] != j) {
					int tmp = s[i];
					s[i] = j;
					if(hash_(s , len) == key)	print(s , len);
					s[i] = tmp;
				}
		}
	}
	if(d >= 2) {
		for(int i = 0 ; i < len ; i++)
			for(int j = i + 1 ; j < len ; j++)
				for(int x = 'a' ; x <= 'z' ; x++)
					for(int y = 'a' ; y <= 'z' ; y++)
						if(s[i] != x && s[j] != y) {
							int tmp1 = s[i] , tmp2 = s[j];
							s[i] = x , s[j] = y;
							if(hash_(s , len) == key)	print(s , len);
							s[i] = tmp1 , s[j] = tmp2;
						}
	}
}

int l , d;
int n;
char s[N][LEN];
int len[N];

int main() {
	cin >> l >> d >> n;
	for(int i = 1 ; i <= n ; i++) {
		s[i][++len[i]] = getchar();
		while((s[i][len[i]] < 'a' || s[i][len[i]] > 'z') && s[i][len[i]] != ' ')
			s[i][len[i]] = getchar();
		while(s[i][len[i]] >= 'a' && s[i][len[i]] <= 'z' || s[i][len[i]] == ' ')
			s[i][++len[i]] = getchar();
		--len[i];
	}

	VecTy key;
	for(int j = 1 ; j + l - 1 <= len[1] ; j++)
		trans(s[1] + j , l , d , key);

	for(int i = 2 ; i <= n ; i++) {
		VecTy cur , tmp;
		for(int j = 1 ; j + l - 1 <= len[i] ; j++)
			trans(s[i] + j , l , d , cur);

		sort(cur.begin() , cur.end());
		unique(cur.begin() , cur.end());

		int size = key.size();
		for(int j = 0 ; j < size ; j++) {
			int left = 0 , r = cur.size() - 1;
			bool find = false;
			while(left <= r) {
				int mid = (left + r) / 2;
				if(cur[mid] == key[j]) {
					find = true;
					break;
				} else if(cur[mid] < key[j])
					left = mid + 1;
				else
					r = mid - 1;
			}
			if(find)
				tmp.push_back(key[j]);
		}
		key.clear();
		key = tmp;
	}

	for(int i = 0 ; i < key.size() ; i++) {
		for(int j = 1 ; j + l - 1 <= len[1] ; j++)
			unhash(s[1] + j , l , d , key[i]);

	}
	return 0;
}

4769. 【GDOI2017模拟9.9】graph

题目

[2021.8纪中集训Day5]

思路

首先,题目要我们判定二分图,那我们就从二分图的判定入手尝试解决这的问题

二分图的判定-带权并查集

学二分图的时候我们用染色法可以判断二分图,但我们不可能每次都跑一遍全图,但书上应该还有一句话

一张无向图是二分图,当且仅当图中不存在寄环(长度为奇数的环).

这样判定比染色法容易维护得多.

加入一条边,图中是否形成一个环,用普通并查集就可以.

寄环呢? 同样,首先要在加入新边之前边的两个端点本来就连通,如果这两个点的原来距离是偶数,那加入该边后,就会出现奇环.

那如何判断两点距离是否为偶数呢?

我们引入带权并查集.

设\(dist_i\)表示图中\(i\)到\(father_i\)的距离的奇偶性,如果为\(1\),说明距离为奇数,为\(0\)则是偶数.

所以,加边的时候:

//UF:Union-Find,ed:要加入的边
namespace UF {
	int fa[N];
	int dep[N];
	int dist[N];
	void init() {
		memset(dist , 0 , sizeof(dist));
		memset(stack , 0 , sizeof(stack));
		top = 0;
		for(int i = 1 ; i <= n ; i++)
			fa[i] = i;
	}
	int findroot(int x) {//不能路径压缩(后面要支持加删边操作)
		return fa[x] == x ? x : findroot(fa[x]);
	}
	int DistToRoot(int x) {
		return fa[x] == x ? 0 : dist[x] ^ DistToRoot(fa[x]);
	}
	void uni(int x , int y , int dis) {
		fa[x] = y;
		dist[x] = dis;
	}
}
//加边时
			int u = UF::findroot(ed.u) , v = UF::findroot(ed.v);
			int dist = UF::DistToRoot(ed.u) ^ UF::DistToRoot(ed.v) ^ 1;
			if(u != v)
				UF::uni(u , v , dist);

加删边操作-CDQ分治&并查集的撤销

CDQ分治

设边类型:

struct EDGE {
	int u , v , l , r;//u,v连接的两个点, l,r边的有效时间为[l,r]
};

有效时间:

加入边在第\(i\)次操作被加入,在第\(j\)​次被删除,则l=i , r=j-1,把边按\(l,r\),像线段树一样下传就好.

其实这也是本蒟蒻第一次写CDQ分治,所以代码上可能会有问题.

并查集的撤销

既然要撤销,那一次并查集操作就不能涉及到多个点的修改,所以路径压缩是不行的,那我们就按秩合并,用栈记录修改的结点.

namespace UF {
	int fa[N];
	int dep[N];
	int dist[N];
	int stack[N] , top;
	void init() {
		memset(dist , 0 , sizeof(dist));
		memset(stack , 0 , sizeof(stack));
		top = 0;
		for(int i = 1 ; i <= n ; i++)
			fa[i] = i;
	}
	
	int findroot(int x) {
		return fa[x] == x ? x : findroot(fa[x]);
	}
	int DistToRoot(int x) {
		return fa[x] == x ? 0 : dist[x] ^ DistToRoot(fa[x]);
	}
	
	void uni(int x , int y , int dis) {
		if(dep[x] > dep[y])
			swap(x , y);
		if(dep[x] == dep[y])
			++dep[y] , stack[++top] = -y;//正负数表示不同的修改类型,这里负数表示该点深度加了1,整数表示该点父节点发生了变化(深度肯定也要跟着变)
		fa[x] = y;
		dist[x] = dis;
		stack[++top] = x;
	}
	void earse(int now) {//撤销now到top的所有操作,now是栈的某个位置
		for( ; top > now ; --top) {
			if(stack[top] < 0)
				--dep[-stack[top]];
			else
				fa[stack[top]] = stack[top] , dep[stack[top]] = 0;
		}
	}
}

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int read() {
	int re = 0;
	bool negt = false;
	char c = getchar();
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

const int N = 300010;

struct EDGE {
	int u , v , l , r;
};
EDGE make_edge(int u , int v , int l , int r) {
	EDGE tmp;
	tmp.u = u , tmp.v = v , tmp.l = l , tmp.r = r;
	return tmp;
}

int n , m;
namespace UF {
	int fa[N];
	int dep[N];
	int dist[N];
	int stack[N] , top;
	void init() {
		memset(dist , 0 , sizeof(dist));
		memset(stack , 0 , sizeof(stack));
		top = 0;
		for(int i = 1 ; i <= n ; i++)
			fa[i] = i;
	}
	
	int findroot(int x) {
		return fa[x] == x ? x : findroot(fa[x]);
	}
	int DistToRoot(int x) {
		return fa[x] == x ? 0 : dist[x] ^ DistToRoot(fa[x]);
	}
	
	void uni(int x , int y , int dis) {
		if(dep[x] > dep[y])
			swap(x , y);
		if(dep[x] == dep[y])
			++dep[y] , stack[++top] = -y;
		fa[x] = y;
		dist[x] = dis;
		stack[++top] = x;
	}
	void earse(int now) {
		for( ; top > now ; --top) {
			if(stack[top] < 0)
				--dep[-stack[top]];
			else
				fa[stack[top]] = stack[top] , dep[stack[top]] = 0;
		}
	}
}

bool ans[N];
void CDQ_divide(int l , int r , vector<EDGE> edset) {
	int mid = (l + r) / 2;
	int now = UF::top;
	vector<EDGE> Ledge , Redge;
	for(int i = 0 , size = edset.size() ; i < size ; i++) {
		EDGE ed = edset[i];
		if(ed.l <= l && ed.r >= r) {
			int u = UF::findroot(ed.u) , v = UF::findroot(ed.v);
			int dist = UF::DistToRoot(ed.u) ^ UF::DistToRoot(ed.v) ^ 1;
			if(u != v)
				UF::uni(u , v , dist);
			else if(dist & 1) {//加入ed边后出现寄环,不能构成二分图
				for(int j = l ; j <= r ; j++)
					ans[j] = false;
				UF::earse(now);
				return;
			}
		} else {
			if(ed.r <= mid && ed.r >= l)
				Ledge.push_back(ed);
			else if(ed.l > mid && ed.l <= r)
				Redge.push_back(ed);
			else
				Ledge.push_back(ed) , Redge.push_back(ed);
				
		}
	}
	if(l != r)
		CDQ_divide(l , mid , Ledge) , CDQ_divide(mid + 1 , r , Redge);
	UF::earse(now);
}

int main() {
	freopen("graph.in" , "r" , stdin);
	freopen("graph.out" , "w" , stdout);
	
	n = read() , m = read();
	vector <EDGE> edset;
	for(int i = 1 ; i <= m ; i++) {
		if(read() == 1) {
			int u = read() + 1 , v = read() + 1;
			edset.push_back(make_edge(u , v , i , m));
		} else {
			edset[read()].r = i - 1;
		}
	}
	
	
	UF::init();
	for(int i = 1 ; i <= m ; i++)
		ans[i] = true;
	CDQ_divide(1 , m , edset);
	
	for(int i = 1 ; i <= m ; i++)
		puts(ans[i] ? "YES" : "NO");
	return 0;
}
上一篇：day5


下一篇：DAY5