虚树学习笔记

2016-12-20
概述 在 OI 比赛中,有这样一类题目:给定一棵树,另有多次询问,每个询问给定一些关键点,需要求这些关键点之间的某些信息。询问数可能很多,但满足所有询问中关键点数量的总和与树的大小同阶。 由于询问数可以非常多,每次无法遍历整棵树,这类题目看似没有办法做,但实际上,我们可以用一种叫做 虚树(virtual tree) 的技术来解决这一问题。 介绍 简单来说,虚树是对一颗有根树中......

CodeChef CHEFBOOK - Chefbook

2016-12-17
题目地址 描述 PDF 传送门 分析 这道题目,每一次修改都会影响到很多位置,我们没办法直接求解。考虑建立出约束关系(最大化的值中没有写常数项,只需要最后加上即可): ......

BZOJ 2445 - 最大团

2016-12-13
题目地址 描述 一个 n ( n ≤ 2 ⋅ 1 0 9 ) n(n\le 2\cdot 10^9) n ( n ≤ 2 ⋅ 1 0 ​ 9 ​ ​ ) 个点的无向图被叫做是一个 symmetric labeled cliquer 当且仅当该图的任意一个连通子图......

BZOJ 4591 - [Shoi2015]超能粒子炮·改

2016-12-12
描述 曾经发明了脑洞治疗仪 & 超能粒子炮的发明家 SHTSC 又公开了他的新发明:超能粒子炮·改——一种可以发射威力更加强大的粒子流的神秘装置。超能粒子炮·改相比超能粒子炮,在威力上有了本质的提升。 它有两个参数 n , k ( k ≤ n ≤ 1 0 1 8 ) n, k(k\le n\le {10}^{18}) ......

线性基学习笔记

2016-12-12
先说明一点, a i a_i a ​ i ​ ​ 表示一个标量,而加粗的 a i \mathbf{a}_i a ​ i ​ ​ 表示一个向量,以便于区分。 概述 基(basis) 是线性代数中的一个概念,它是......

BZOJ 3811 - 玛里苟斯

2016-12-11
题目地址 描述 魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心,于是他想了一道数学题。 S S S 是一个可重集合, 。 等概率随机取 S ......

Codeforces 741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

2016-12-07
题目地址 描述 给定一棵 n ( 1 ≤ n ≤ 5 ⋅ 1 0 5 ) n(1\le n\le 5 \cdot {10}^5) n ( 1 ≤ n ≤ 5 ⋅ 1 0 ​ 5 ​ ​ ) 的有根树,根结点为 1 1 ......

Codeforces 735E - Ostap and Tree

2016-12-05
题目地址 描述 在一个含有 n ( n ≤ 1 0 0 ) n(n\le 100) n ( n ≤ 1 0 0 ) 个节点的树中,你可以将每个节点涂成黑色或者白色,请问有多少种涂色方案,能够使得对于任意节点,都有一个黑色节点与其距离不超过 K ( K ≤ min ( 2 0 , n......

BZOJ 1770 - [Usaco2009 Nov]lights 灯

2016-12-04
题目地址 描述 贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏! 牛棚中一共有 n ( 1 ≤ n ≤ 3 5 ) n(1 \le n......

BZOJ 3640 - JC的小苹果

2016-12-02
题目地址 描述 让我们继续 JC 和 DZY 的故事。 “你是我的小丫小苹果,怎么爱你都不嫌多!” “点亮我生命的火,火火火火火!” 话说 JC 历经艰辛来到了城市 B,但是由于他的疏忽 DZY 偷走了他的小苹果!没有小苹果怎么听歌!他发现邪恶的 DZY 把他的小苹果藏在了一个迷宫里。JC 在经历了之前的战斗后他还剩下 h p ( h p ≤ 1......