分类:oi

113 篇文章

浅谈Link Cut Tree
前言 Link Cut Tree 可真是好用呢~ 刚入门的各位不需要担心,LCT其实十分简单。 陈指导写的LCT也不过10几行,我这个菜鸡打的模板也只有50+行。 所以LCT码量很小 好了,步入正题。 正文 简介 A link/cut tree is a data structure for represen…
IOI国家集训队1999-2019年论文集 (文末附下载链接)
国家集训队论文列表(1999-2019) 1999 陈 宏 -《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》 来煜坤 -《把握本质,灵活运用——动态规划的深入探讨》 齐 鑫 -《搜索方法中的剪枝优化》 邵 铮 -《数学模型的建立、比较和应用》 石润婷 -《隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性》 杨 帆 -…
Luogu P2617 Dynamic Rankings 题解
Description 题目链接 给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$​,需要支持两种操作: Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数C x y 表示将 $a_x$​ 改为 $y$ Solution 树状数组套主席树 Code [crayon-5f3…
loj 6062 「2017 山东一轮集训 Day2」Pair 题解
Description 题目链接 给出一个长度为 $n$ 的数列 $\{a_i\}$ 和一个长度为 $m$ 的数列 $\{b_i\}$,求 $\{a_i\}$ 有多少个长度为 $m$ 的连续子数列能与 $\{b_i\}$ 匹配。 两个数列可以匹配,当且仅当存在一种方案,使两个数列中的数可以两两配对,两个数可以配对当且仅当它们的和不小于 $h$。 对…
bzoj 3653 谈笑风生 题解
Description 题目链接 设T 为一棵有根树,我们做如下的定义: 设a和b为T 中的两个不同节点。如果a是b的祖先,那么称“a比b不知道高明到哪里去了”。 设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数x,那么称“a 与b 谈笑风生”。 给定一棵n个节点的有根树T,节点的编号为1 到 n,根节点为1…
bzoj 3209 & Luogu P4317 花神的数论题 题解
题目链接:bzoj Luogu Description 求$1$到$n$每个数的$1$的个数之积。 对于$ 100\% $的数据,$n\leq 10^15$ Solution 数位$DP$。 可以先把$n$拆成二进制,然后$DFS$。 Code [crayon-5f3003c7acdee740774203/]
bzoj 1858. [Scoi2010]序列操作 题解
Description 题目链接:BZOJ1858 [Scoi2010]序列操作 给你长度为$n$的$01$串,现有$m$个操作。 区间赋值为$0$区间赋值为$1$区间反转(所有$0$变为$1$,所有$1$变为$0$)区间求和求区间最多有连续的几个$1$ 对于$100\%$的数据,$1\le n,m \le 100000$。 Solution 珂朵…
珂朵莉树 学习笔记
什么是珂朵莉树? 珂朵莉树,又称$ODT(Old Driver Tree)$,是一个基于$std::set$的暴力、玄学数据结构。 什么时候使用珂朵莉树? 如果有一题涉及到区间赋值(即把区间内所有的数全部赋值成同一个量)的操作,且数据随机,就可以考虑使用珂朵莉树。 下面以一道例题CF896来详解珂朵莉树。 Description 给你$n$个数,要…
bzoj1774. [Usaco2009 Dec]Toll 过路费 题解
Describe 一句话题意:给你一个有点权$n$与边权$m$的图,询问$q$次,问两个点间最短路长度。(最短路定义为路径上的边权和+路径上的点权的最大值) $1\leq n\leq 250,1\leq m\leq 10000,1\leq q\leq 10000$ Solution 考虑到点的数量小于$250$,所以可以$Floyed$求出任意两点…
bzoj3137 [Baltic2013]tracks 题解
Describe 给定一片长方形的草地,有2种动物:兔子和狐狸。兔子走过草地会留下R,狐狸走过草地会留下F。每只动物从左上角进入草地,从右下角走出草地。其间,它可以上下左右乱跳(可以重复),经过的格子会被覆盖上它的脚印。每次草地上最多只有一只动物。 给你地图,问最少有多少只动物走过了草地。 Solution 先将每一个边缘点加入$queue$,再每…