whix

分类

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 数论(37) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

全部文章（共139篇）

树上差分

1.点差分：求解问题：给一棵树，和一些路径的起点和终点，求树上的每个点被路径经过的次数。求解步骤： 1.假设路径的起点： s s ...

2020-02-09

0 406

2020牛客寒假算法基础集训营3

总的来说，应该是前三场中最难的了。题解 A.牛牛的DRB迷宫I：现在来看，很明显的状态递推，第一次看的是竟然没有想到，一直到最后才突然发现。（棋盘型 d p ...

2020-02-08

0 429

2020牛客寒假算法基础集训营2

G.判正误：牛可乐有七个整数 a , b , ...

2020-02-07

0 368

树链剖分及应用

定义：将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。就是一种技巧，为了方便处理问题。形式：重链剖分，长链剖分等。此处讲述重链剖分。重链剖分：可以将树上的任意一条路径划分成不超过 ...

2020-02-06

0 398

2020牛客寒假算法基础集训营1总结

题目链接 J. u’s的影响【矩阵快速幂+欧拉降幂】首先，先推出前几项： 1 : x ...

2020-02-05

0 412

Can you answer these queries? HDU - 4027【线段树+区间不等更新】

区间每个点的值都开方。由于数据范围，开方的次数较小。一个点开方的次数不超过7次，所以可以做到每个点都修改，同时注意限制修改次数。 #include <bits/stdc++.h>//线段树区间不等更新 using namespace std; const int N=1e5+5;...

2020-02-04

0 420

树的重心

定义： 1.找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。 2.从树中去掉某点以及和该点相连的所有边后，整棵树变为许多"块"。去掉任意一个重心（相比于去掉其他点）可以使得生成的各个"块"...

2020-02-03

0 599

树的直径及应用

树的直径：树的直径指树上距离最远的两点间的距离，它在树上问题上有许多应用，往往通过树的直径的性质可以将一个高时间复杂度的解法变为线性求解。树的直径的性质： ( 1 ...

2020-02-03

0 471

codeforce 1290A-Mind Control【思维】

题意：一串数共 n n n个，排成一列，有 n ...

2020-02-03

0 648

codeforce 1294F-Three Paths on a Tree【树的直径+多源bfs】

一开始认为根节点和深度最深的节点一定要选择（其实是错的），确定了两个点后枚举第三个点，用倍增求深度最深的点和枚举的点的lca,确定第三个点。正解：用两次 d f ...

2020-02-02

0 363