xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共5篇）

CodeForces 593D Happy Tree Party [LCA+并查集]

题意：给一棵树，每条边有一个权值，给两种操作，第一种是询问y向下整除从a到b的最短路径中每条边的权值后y的值，第二种是改变某条边的权值。思路：y的最大值为1e18，最多除大于等于2的数不超过60次即可将y变为0，先dfs以任意一点为根建树，记录每个点的深度和它的父结点并将边权转化为点权，再搞...

codeforces LCA 并查集 acm 算法

2019-04-08

0 366

codeforces1213G Path Queries 并查集

题意给定n个结点的树，每条边有边权，有m个询问，每个询问给一个\(q_i\)输出树上有多少点对的简单路径上最大的边权不超过\(q_i\)。分析用并查集维护点集，同时维护大小。将所有边按边权排序，考虑每次从小到大加边，图中经过当前边的所有路径一定是以当前边的边权为最大值的，用并查集维护...

并查集

2019-10-23

0 411

Comet OJ - Contest #13 「佛御石之钵 -不碎的意志-」(困难版) 并查集

题意给一个$ n \times m$ 的网格，每个格子里有一个数字，非 \(0\) 即 \(1\)，行从上往下依次编号为 \(1, 2, \cdots, n\)，列从左往右依次编号为 \(1, 2, \cdots, m\)。给 \(q\) 次操作，每次给定一个以 \((x_1,y_1)\) ...

并查集

2019-10-25

0 402

gym-102307 D. Do Not Try This Problem

题意给定一个长度为\(n\)的字符串\(s\)，给定\(q\)个操作，每次操作给定\(i,a,k,c\)，表示将\(s_i,s_{i+a},\dots,s_{i+ka}\)赋值为字符\(c\)，输出经过\(q\)次操作后的字符串\(s\)。分析分类讨论：若\(a>\sqr...

分块并查集

2020-05-01

0 364

CodeForces 593D Happy Tree Party [LCA+并查集]

题意：给一棵树，每条边有一个权值，给两种操作，第一种是询问y向下整除从a到b的最短路径中每条边的权值后y的值，第二种是改变某条边的权值。思路：y的最大值为1e18，最多除大于等于2的数不超过60次即可将y变为0，先dfs以任意一点为根建树，记录每个点的深度和它的父结点并将边权转化为点权，再搞...

codeforces LCA 并查集 acm 算法

2019-04-08

0 479