首页 > 其他分享 >24/04/25 图论

24/04/25 图论

时间：2024-04-25 22:33:49浏览次数：26  
标签：24 25 return 04 fa int res dep sz

\(\color{purple}(1)\) P5478 [BJOI2015] 骑士的旅行

  • 给定一颗 \(n\) 个节点的树。有 \(m\) 个骑士，最开始第 \(i\) 个骑士在 \(p_i\) 节点上，武力值为 \(f_i\)。接下来有 \(q\) 次操作 \((t_i, x_i, y_i)\)：
    • \(t_i = 1\)，输出树上 \(x_i, y_i\) 路径上的前 \(k\) 大骑士的武力值。
    • \(t_i = 2\)，\(p_{x_i} \gets y_i\)；
    • \(t_i = 3\)，\(f_{x_i} \gets y_i\)。
  • \(n, m \le 4 \times 10^4\)，\(q \le 8 \times 10^4\)，\(\color{red}k \le 20\)。

显然需要树链剖分，将树上问题转化成序列上问题。

发现 \(k\) 很小，所以我们可以用线段树维护前 \(k\) 大，并用 \(\mathcal O(k)\) 的时间复杂度 pushup。

注意可用 multiset 存储每个叶子节点上的骑士编号和骑士武力值。

$\color{blue}\text{Code}$ 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 800010;

int n, m, f[N], p[N], q, k;
int id[N], idx, pos[N];
vector<int> vec[N];

vector<int> calc(vector<int> t) {
	vector<int> res;
	sort(t.begin(), t.end(), greater<int>());
	for (int i = 0; i < t.size() && i < k; ++ i ) res.push_back(t[i]);
	return res;
}

struct Node {
	int l, r;
	vector<int> V;
	multiset<int, greater<int> > S;
}tr[N << 2];

struct Segment_Tree {
	void pushup(int u) {
		vector<int> res;
		for (int t : tr[u << 1].V) res.push_back(t);
		for (int t : tr[u << 1 | 1].V) res.push_back(t); 
		tr[u].V = calc(res);
	}
	
	void build(int u, int l, int r) {
		tr[u].l = l, tr[u].r = r;
		if (l == r) {
			l = pos[l];
			for (int i = 0; i < vec[l].size(); ++ i ) {
				tr[u].S.insert(vec[l][i]);
				tr[u].V.push_back(vec[l][i]);
			}
			tr[u].V = calc(tr[u].V);
		}
		else {
			int mid = l + r >> 1;
			build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
			pushup(u);
		}
	}
	
	void modify(int u, int x, int d) {
		if (tr[u].l == tr[u].r) {
			if (d > 0) tr[u].S.insert(d);
			else {
				tr[u].S.erase(tr[u].S.find(-d));
			}
			int cnt = 0;
			tr[u].V.clear();
			for (int t : tr[u].S) {
				++ cnt;
				if (cnt > k) break;
				tr[u].V.push_back(t);
			}
		}
		else {
			int mid = tr[u].l + tr[u].r >> 1;
			if (x <= mid) modify(u << 1, x, d);
			else modify(u << 1 | 1, x, d);
			pushup(u);
		}
	}
	
	vector<int> query(int u, int l, int r) {
		if (tr[u].l >= l && tr[u].r <= r) return tr[u].V;
		int mid = tr[u].l + tr[u].r >> 1;
		vector<int> res;
		if (l <= mid) {
			for (int t : query(u << 1, l, r)) res.push_back(t);
		}
		if (r > mid) {
			for (int t : query(u << 1 | 1, l, r)) res.push_back(t);
		}
		return calc(res);
	}
}S;

struct Tree {
	vector<int> g[N];
	void add(int a, int b) { g[a].push_back(b); }
	int fa[N], dep[N], sz[N], son[N], top[N];
	
	void dfs1(int u, int f) {
		fa[u] = f;
		dep[u] = dep[f] + 1;
		sz[u] = 1;
		for (int v : g[u]) {
			if (v == f) continue;
			dfs1(v, u);
			sz[u] += sz[v];
			if (sz[v] > sz[son[u]]) son[u] = v;
		}
	}
	
	void dfs2(int u, int f) {
		top[u] = f;
		id[u] = ++ idx;
		pos[idx] = u;
		if (son[u]) {
			dfs2(son[u], f);
			for (int v : g[u])
				if (v != fa[u] && v != son[u])
					dfs2(v, v);
		}
	}
	
	vector<int> query(int a, int b) {
		vector<int> res;
		while (top[a] != top[b]) {
			if (dep[top[a]] < dep[top[b]]) swap(a, b);
			for (int t : S.query(1, id[top[a]], id[a])) res.push_back(t);
			res = calc(res);
			a = fa[top[a]];
		}
		if (dep[a] > dep[b]) swap(a, b);
		for (int t : S.query(1, id[a], id[b])) res.push_back(t);
		return calc(res);
	}
	
	void modify(int x, int y) {
		S.modify(1, id[x], y);
	}
}T;

signed main() {
	cin >> n;
	for (int i = 1, u, v; i < n; ++ i ) {
		cin >> u >> v;
		T.add(u, v), T.add(v, u);
	}
	cin >> m;
	for (int i = 1; i <= m; ++ i ) {
		cin >> f[i] >> p[i];
		vec[p[i]].push_back(f[i]);
	}
	
	cin >> q >> k;
	T.dfs1(1, 0), T.dfs2(1, 0);
	S.build(1, 1, n);
	
	while (q -- ) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t == 1) {
			auto res = T.query(x, y);
			if (res.empty()) cout << "-1\n";
			else {
				for (int t : res) cout << t << ' ';
				cout << '\n';
			}
		}
		else if (t == 2) {
			T.modify(p[x], -f[x]);
			T.modify(y, f[x]);
			p[x] = y;
		}
		else {
			T.modify(p[x], -f[x]);
			T.modify(p[x], y);
			f[x] = y;
		}
	}
	return 0;
}

\(\color{blue}(2)\) P6374 「StOI-1」树上询问

  • 给定一棵 \(n\) 个点的无根树，有 \(q\) 次询问。

    每次询问给一个参数三元组 \((a,b,c)\) ，求有多少个 \(i\) 满足这棵树在以 \(i\) 为根的情况下 \(a\) 和 \(b\) 的 LCA 为 \(c\) 。

  • \(n \le 5 \times 10^5\)，\(q \le 2 \times 10^5\)。

模拟可知答案为当这棵树以 \(c\) 为根时除 \(a, b\) 所在子树内的点的数量，即 \(n - size_a - size_b\)。以及当 \(c\) 不在树上 \(a \sim b\) 的路径上时答案为 \(0\)。

所以我们需要解决两个问题：

  1. 判断 \(c\) 是否在 \(a \sim b\) 的路径上：

    首先求出 \(\operatorname{lca}(a, b) = p\)。那么此时我们需要判断的就是是否 \(c\) 在 \(a \sim p\) 的路径上或 \(b \sim p\) 的路径上。即：

    bool chk(int a, int b, int c) {
	int p = lca(a, b);
	return (lca(a, c) == c || lca(b, c) == c) && lca(c, p) == p;
}

  2. 求当以 \(c\) 为根时，\(a\) 所在子树的大小：

    分类讨论：

    1. 当 \(c\) 原来就是 \(a\) 的祖先时，做法是类似于 lca 的倍增往上跳，跳到某个点使得这个点的父亲是 \(a\)；
    2. 否则，显然整棵树中，除了 \(c\) 所在的子树外，每个点都是 \(a\) 所在的子树，即答案为 \(n - size_c\)。

    即：

    int F(int a, int b) {
	for (int k = 19; ~k; -- k )
		if (dep[fa[b][k]] > dep[a]) b = fa[b][k];
	return b;
}

int calc(int a, int b) {
	if (a == b) return 0;
	if (lca(a, b) == b) return sz[F(b, a)];
	return n - sz[b];
}
$\color{blue}\text{Code}$ 
#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int n, q;
vector<int> g[N];
int sz[N], fa[N][20], dep[N];

void dfs(int u, int f) {
	dep[u] = dep[f] + 1, sz[u] = 1;
	for (int v : g[u])	
		if (v != f) {
			fa[v][0] = u;
			for (int k = 1; k < 20; ++ k ) fa[v][k] = fa[fa[v][k - 1]][k - 1];
			dfs(v, u);
			sz[u] += sz[v];
		}
}

int lca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	for (int k = 19; ~k; -- k )
		if (dep[fa[a][k]] >= dep[b]) a = fa[a][k];
	if (a == b) return a;
	for (int k = 19; ~k; -- k )
		if (fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
	return fa[a][0];
}

bool chk(int a, int b, int c) {
	int p = lca(a, b);
	return (lca(a, c) == c || lca(b, c) == c) && lca(c, p) == p;
}

int F(int a, int b) {
	for (int k = 19; ~k; -- k )
		if (dep[fa[b][k]] > dep[a]) b = fa[b][k];
	return b;
}

int calc(int a, int b) {
	if (a == b) return 0;
	if (lca(a, b) == b) return sz[F(b, a)];
	return n - sz[b];
}

int main() {
	cin >> n >> q;
	for (int i = 1, a, b; i < n; ++ i ) {
		cin >> a >> b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	dfs(1, 0);
	while (q -- ) {	
		int a, b, c;
		cin >> a >> b >> c;
		int res = 0;
		if (!chk(a, b, c)) res = 0;
		else res = n - calc(a, c) - calc(b, c);
		cout << res << '\n';
	}
	return 0;
}

\(\color{green}(3)\) CF173B Chamber of Secrets

  • 给定一张 \(n\times m\) 的包含 # 和 . 的图，现有一束激光从左上角往右边射出。

    每次遇到 #，你可以选择光线改变为上下左右四个方向之一，也可以不改变。

    求至少需要改变几次方向，可以使激光从第 \(n\) 行向右射出。

  • \(n, m \le 10^3\)。

显然总共有 \(4nm\) 种状态，即在每个位置有 \(4\) 种当前面对的方向。

发现转移是类似于图上的边，且边权仅有 \(0\) 和 \(1\)。所以 01bfs 即可。

$\color{blue}\text{Code}$ 
#include <bits/stdc++.h>

const int N = 1010, M = 10000100;

int n, m;
char g[N][N];

struct Node {
	int a, b, dx, dy;
	bool operator <(const Node &h) const {
		if (a == h.a) {
			if (b == h.b) {
				if (dx == h.dx) return dy < h.dy;
				return dx < h.dx;
			}
			return b < h.b;
		}
		return a < h.a;
	}
};

std::deque<Node> q;
int dis[N][N][3][3];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i ) scanf("%s", g[i] + 1);
	
	memset(dis, 0x3f, sizeof dis);
	
	q.push_back({1, 1, 0, 1});
	dis[1][1][1][2] = 0;
	
	const std::vector<int> tx({1, 0, -1, 0}), ty({0, -1, 0, 1});
	
	while (!q.empty()) {
		int x = q.front().a, y = q.front().b, dx = q.front().dx, dy = q.front().dy;
		q.pop_front();
		if (g[x][y] == '#') {
			for (int i = 0; i < 4; ++ i ) {
				if (dis[x][y][tx[i] + 1][ty[i] + 1] > 1e9) {
					dis[x][y][tx[i] + 1][ty[i] + 1] = dis[x][y][dx + 1][dy + 1] + 1;
					q.push_back({x, y, tx[i], ty[i]});
				}
			}
		}
		if (x + dx >= 1 && x + dx <= n && y + dy >= 1 && y + dy <= m && dis[x + dx][y + dy][dx + 1][dy + 1] > 1e9) {
			dis[x + dx][y + dy][dx + 1][dy + 1] = dis[x][y][dx + 1][dy + 1];
			q.push_front({x + dx, y + dy, dx, dy});
		}
	}
	
	printf("%d\n", dis[n][m][1][2] < 1e9 ? dis[n][m][1][2] : -1);
	
	return 0;
}

\(\color{orange}(4)\) CF1063B Labyrinth

  • 给定一张 \(n\times m\) 的包含 * 和 . 的图，* 是不能经过的障碍。

    给定你的起点 \((r,c)\)，每次你可以往上下左右四个方向之一移动一步。

    限制了你的向左移动的次数不超过 \(x\) 和向右移动的次数不超过 \(y\)，求你能到达多少个格子。

  • \(n, m \le 2 \times 10^3\)。

枚举终点。可以发现如果确定了往右走的步数和最终到达的与起点的列数的差，就可以轻易的求出需要往左走的步数。

所以我们可以预处理出从起点到达每个点所需要的最小的往左次数，然后枚举终点判断合法即可。

$\color{blue}\text{Code}$ 
#include <bits/stdc++.h>

const int N = 2024;

int n, m, sx, sy, x, y;
char g[N][N];
int f[N][N];		// 到达 (i, j) 的最小向左次数 

const std::vector<int> dx({0, 1, 0, -1}), dy({1, 0, -1, 0});

signed main() {
	scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &x, &y);
	for (int i = 1; i <= n; ++ i ) scanf("%s", g[i] + 1);
	memset(f, 0x3f, sizeof f);
	std::list<std::pair<int, int> > q;
	q.push_back({sx, sy});
	f[sx][sy] = 0;
	while (q.size()) {
		int x = q.front().first, y = q.front().second;
		q.pop_front();
		for (int i = 0; i < 4; ++ i ) {
			int a = x + dx[i], b = y + dy[i];
			if (a >= 1 && a <= n && b >= 1 && b <= m && g[a][b] == '.' && f[a][b] > f[x][y] + (i == 2)) {
				f[a][b] = f[x][y] + (i == 2);
				if (i == 2) q.push_back({a, b});
				else q.push_front({a, b});
			}
		}
	}
	int res = 0;
	for (int i = 1; i <= n; ++ i )
		for (int j = 1; j <= m; ++ j )
			if (g[i][j] == '.' && f[i][j] < 1e9)
				res += f[i][j] <= x && j - (sy - f[i][j]) <= y;
	printf("%d\n", res);
	return 0;
}

标签：24,25,return,04,fa,int,res,dep,sz
From： https://www.cnblogs.com/2huk/p/18158770

相关文章

  • 联合省选2024 做题总结
    D1T1季风心梗题。设\(sx_i=\sum\limits_{j\lei}x_j\)，\(sy_i\)同理。枚举\(r=m\bmodn\)，设\(m=p\cdotn+r\)，那么当\(|x-(p\cdotsx_n+sx_r)|+|y-(p\cdotsy_n+sy_r)|\)不超过\((p\cdotn+r)k\)，一定存在合法的方案，即解关于\(p\)的绝对值不等式：\[|x-(p\cdotsx_n+sx_r......
  • 4.25
    优化了密码系统因为有的□□找不到生日在哪现在《密码》可以直接点开优化了自我介绍处理方式与之前一样Ciallo～(∠・ω<)⌒☆Ciallo～(∠・ω<)⌒☆Ciallo～(∠・ω<)⌒☆Ciallo～(∠・ω<)⌒☆Ciallo～(∠・ω<)⌒☆Ciallo～(∠・ω<)⌒☆Ciallo～(∠・ω<)⌒☆Cia......
  • 4 25spring Task
    由spring框架提供的定时处理任务的 websocket:使得客户端浏览器跟服务端双向传递数据    ......
  • 04、数据保护技术
    数据保护技术1.磁盘镜像制作1.1.Windows磁盘镜像制作及恢复GetDataForeniscImager该工具安装后，可将安装后的文件复制出来（类似绿色运行）使用（需要管理员运行）：https://getdataforensics.com/product/fex-imager/ DataNumenDiskImage1.2.Linux磁盘镜像制作（命令行）lsblk：查......
  • Ubuntu 16.04 LTS 升级到 Ubuntu 18.04 LTS
    Ubuntu从16.04升级到18.04版本_ubuntu16upgrade了18的库-CSDN博客......
  • 4.24
    已经往数据库插入图片了，现在可以去除图片了，这里我用的是游标package你的包名;importandroidx.appcompat.app.AppCompatActivity;importandroid.content.Intent;importandroid.database.Cursor;importandroid.database.sqlite.SQLiteDatabase;importandroid.database.sqlit......
  • 2024.4
    感觉本地编辑器有点卡了就先放到博客园上1.ccpc2023深圳M3Sum先取模，就是第\(x\)位加给\(x\bmodK\)位，\(\mathcal{O}(len)\)复杂度。然后就只有相加为\(0,M,2M\)这三种情况，找几个模数进行check就行。2.ccpc2023深圳ETwoinOne考虑俩颜色咋做。先想想答案......
  • mysql系列04---索引及性能分析
    1、索引的结构 mysql索引的数据结构，对经典的B+Tree进行了优化，在原B+Tree上增加了一个指向相邻叶子结点的链表指针，就形成了一个带有顺序指针的B+Tree,提高了区间访问的性能。 选择B+Tree的优点：a、相对于二叉树，层级更少，搜索效率更高b、相对于B-Tree,B+Tree只在叶子节点上存储......
  • nginx1.24配置logrotate日志切割
    安装logrotate（如果尚未安装）：yuminstalllogrotate#CentOS/RHEL配置logrotate：通常，logrotate的配置文件位于/etc/logrotate.conf，并且可以包含指向其他配置文件的引用。这些其他配置文件通常位于/etc/logrotate.d/目录中。创建Nginx的logrotate配置文件：vim/etc/lo......
  • 4-25 WP整理
    AliyunCTF2024-帕鲁情绪管理nc链接上去过掉proof看到如下交互sha256(("zqonds929lsi1d19ayrm6xdxogid"+"????").encode())=447dedc4395aae3f6344689b6fdeadc71d7759c3d9b5071ce318267ed587ce97Pleaseinputtheanswer:Doyouwanttotraining?(y/n)ysentim......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99