是晓毅

分类

学习笔记(2) 未归档(5) 树链剖分(1) 算法(1)

/ 注册

全部文章（共9篇）

约瑟夫问题

推荐一个博客:约瑟夫环问题详解约瑟夫问题约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程)的算法中，类似问题又称为约瑟夫环。人们站在一个等待被处决的圈子里。计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。在跳过指定数量的人之后，执行下一个人。对...

数学

2019-07-20

0 959

Beatty's theory

定理当正无理数、满足下列式子时会有,,使得集合P和集合Q正好是的一个划分,即、. 证明 1.一个正整数在集合P或集合Q中至多出现一次因为、，所以不会存在相同的正整数，亦然。 2. 反证法来一手，假设有正整数n、m、k使得，即转化一下两式相加再转化一下因为n、m是正整数，所以不符合，所以...

数学

2019-07-19

0 847

BZOJ 2243 题解（树链剖分）

题目传送门题意给n个点，每个点有自己的初始节点颜色，有n-1条边连起来，多个操作：将a到b的链的节点染成颜色c；查询a到b的链，上有多少中颜色。题解树链剖分，线段树维护颜色数量、还有左右端点的颜色。利用左右端点的颜色判断合并区间后的颜色数量即可。 #include <...

树链剖分

2019-02-18

0 653

POJ - 3237 题解（树链剖分）

题目传送门题意给n个点，有n-1条边连起来，每条边有自己的权值，多个操作：改变第i条边的权值；将a到b的链的边的权值取相反数；查询a到b的链上最大的权值。题解树链剖分，维护最大最小值，要取相反数的时候，最大最小值交换，再取相反数即可。 #include <algorithm...

2019-02-18

0 726

POJ 2763 题解 (树链剖分维护边权)

目录题目题意题解代码题目传送门题意给n个点，n-1条边，初始点为s，q个询问，操作0是s到u的距离，操作1是改变第i条边的权值为w。 (边权模板题) 题解将每条边的权值存到更深的点上，跑树链剖分即...

2019-02-17

0 866

HDU 3966 题解（树链剖分维护点权）

题意：给定个营地，营地i有个敌人，有条边将个营地连起来。总共有p个操作，I操作是在C1到C2的链上的每个营地都增加K个敌人；D操作是在C1到C2的链上的每个营地都减少K个敌人；Q操作是在C营地上有多少个敌人。树链剖分模板题，树链剖分后，用线段树或者树状数组维护即可。线段树写得有点丑...

2019-02-17

0 703

Inverse-Element

逆元定义 a = 1 b ...

2018-12-28

0 557

Binary-Index-Tree

注意!!!:这不是树状数组的详解,而是利用树状数组做区间修改的方法,当然能区间修改了也能单点修改先来个简单的树状数组啊功能: 单点更新区间查询(单点查询也就是特殊的区间查询啦) int n; int a[100005]; void add(int x...

2018-12-28

0 461

Gym-101955C题解

题目传送门C - Insertion Sort 不重复题意了，直接写解的过程，场上推不出来，赛后看题解才推出来的网上题解说存在 k ≥ ...

2018-12-28

1 683