搜索结果
查询Tags标签： siz，共有 37条记录-
CF603E Pastoral Oddities
CF603E Pastoral Oddities给定一张 \(n\) 个点的无向图，初始没有边。 依次加入 \(m\) 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。 若存在，则还需要最小化边集中的最大边权。 \(n \le 10^5,m \le 3 \times 10^5\)。首先观察题目条件，发现…
2022/8/30 23:25:02 人评论 次浏览 -
SP2420 题解
SP2420 solution给定一颗 \(n\) 个节点的树，在树上找一条长为 \(l\) 的链，使得树上每个节点到链的距离之和最短，求这个最短距离。题解 首先我们思考多个点到一个点距离和怎么计算。可以考虑使用树形 DP，将这个点作为跟，记录 \(siz_u\) 为 \(u\) 点子树的大小，\(sum_…
2022/8/13 23:28:53 人评论 次浏览 -
Fhq-Treap 模板
namespace Fhq_Treap {int ch[N][3], siz[N], val[N], cnt, rnd[N];inline void update(int x); inline int newnode(int x); inline int Kth(int now, int k); inline void split(int now, int k, int &x, int &y); inline int merge(int A, int B);inline void …
2022/8/2 6:23:54 人评论 次浏览 -
点分治
int siz[Z], kid[Z], root, size;//kid[rt]：该点的最大子树的大小 bool vs[Z]; void getroot(int rt, int fa)//求树的重心 {siz[rt] = 1, kid[rt] = 0;for (re i = head[rt]; i; i = e[i].ne){int son = e[i].v;if (vs[son] || son == fa) continue;getroot(son, rt);si…
2022/7/5 0:01:24 人评论 次浏览 -
AT3537 [ARC083D]Collecting Balls 题解
Post time: 2021-09-22 21:55:13 题面 一道图论（树论）综合好题，被亓神扒出来放到了 vc 胡策上。 首先发现球的数量等于机器人的数量，也就是说，每一个机器人都必须要吃掉一个球。感觉上直接做不好做，考虑转化，把每个球当做边，将横纵坐标上的机器人连起来。 连完之后…
2022/4/21 23:12:54 人评论 次浏览 -
SP10707 COT2 - Count on a tree II
\(\text{Solution}\) 统计树上 \(x\) 到 \(y\) 路径不同数的种类数 可以树上莫队 离线的树上莫队就是把树用欧拉序拍下来，然后和序列上的莫队一样即可 \(\text{Code}\) #include <cstdio> #include <algorithm> #include <cmath> #define RE register …
2022/4/7 23:50:07 人评论 次浏览 -
cf1416 C. XOR Inverse（字典树、逆序对、贪心）
题意： 给定数组 \(a[]\)，找一个整数 \(x\)，构造数组 \(b[]\) ，$b_i=a_i \oplus x $使得 \(b[]\) 中的逆序对数最少，其次使得 \(x\) 尽量小。输出最少逆序对数与 \(x\) \(n\le 3e5, 0\le a_i\le 1e9\) 思路： 看到异或就要考虑一下xor字典树！ 贪心从高到低考虑每一位…
2022/3/8 23:15:58 人评论 次浏览 -
【模拟赛】乌拉~~（重链剖分）
背景大家好，我是一名勇敢的俄罗斯士兵，我昨天正在打 CodeForces\tt CodeForcesCodeForces 呢，突然被拉去打仗了。我们已经突入基辅，但因为推进过于迅速，后勤补给未能补上，我们现在急需 143 元来购买一些吃的 一个能替代通信员的老兄来解密一下临时截获的乌克兰电报，…
2022/2/25 23:52:11 人评论 次浏览 -
NOI2014购票
题意: 给出根节点为 \(1\) 的一颗树，\(d_i\) 表示 \(1\) 到 \(i\) 的距离， 每个点 \(i\) 可以跳到距离 \(\leq l_i\) 的点 \(j\) 上，花费是 \((d_i - d_j) \times p_i + q_i\)，求每个点到根节点的最小花费。 dp 方程转移： \[f_i = \min \{f_j + (d_i - d_j) \times p…
2022/2/15 23:13:12 人评论 次浏览 -
学习笔记：树上启发式合并（dsu on tree）
DSU on tree ! 解决树上问题的利器，复杂度虽然没有长链剖分优秀，不过思考简单而且代码优美，是树上维护答案的好帮手。 例题：DSU on tree 应用范围 解决一些子树的离线静态问题，巧妙地将暴力 \(O(n^2)\) 的复杂度优化到 \(O(nlogn)\)。 算法思路回溯整棵树维护子树大小…
2021/12/10 23:16:49 人评论 次浏览 -
学习笔记：树上启发式合并（dsu on tree）
DSU on tree ! 解决树上问题的利器，复杂度虽然没有长链剖分优秀，不过思考简单而且代码优美，是树上维护答案的好帮手。 例题：DSU on tree 应用范围 解决一些子树的离线静态问题，巧妙地将暴力 \(O(n^2)\) 的复杂度优化到 \(O(nlogn)\)。 算法思路回溯整棵树维护子树大小…
2021/12/10 23:16:49 人评论 次浏览 -
[Contest on 2021.9.7] 睡着了，但不完全睡着了
目录$\text{Strange Queries}$解法代码$\text{[TJOI 2013] }$拯救小矮人解法代码$\text{[ICPC World Finals 2019] Hobson }$的火车题目描述解法代码简单题题目描述解法 \(\text{Strange Queries}\) 解法 首先有这样的转移： \[\begin{cases}f(n,0)=f(n-1,1) \\\displayst…
2021/9/9 23:37:26 人评论 次浏览 -
[Contest on 2021.9.7] 睡着了，但不完全睡着了
目录$\text{Strange Queries}$解法代码$\text{[TJOI 2013] }$拯救小矮人解法代码$\text{[ICPC World Finals 2019] Hobson }$的火车题目描述解法代码简单题题目描述解法 \(\text{Strange Queries}\) 解法 首先有这样的转移： \[\begin{cases}f(n,0)=f(n-1,1) \\\displayst…
2021/9/9 23:37:26 人评论 次浏览 -
[攻防世界 - reverse - 新手区] gam
打开exe后发现不需要上ida，直接玩游戏即可相当于一个初始全为0的长度为8的数组，每次操作选一个位置，将其与其相邻共3个数取反（首尾相邻，可看做一个环），一直操作到全部为1。 直接用c++写出搜索脚本 // rg是register，print是自定义的输出 stack<int> s; bool …
2021/8/29 6:09:53 人评论 次浏览 -
[攻防世界 - reverse - 新手区] gam
打开exe后发现不需要上ida，直接玩游戏即可相当于一个初始全为0的长度为8的数组，每次操作选一个位置，将其与其相邻共3个数取反（首尾相邻，可看做一个环），一直操作到全部为1。 直接用c++写出搜索脚本 // rg是register，print是自定义的输出 stack<int> s; bool …
2021/8/29 6:09:53 人评论 次浏览
