bzoj 2959 长跑 题解
Description   某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。  为了让同学们更好地监督自己,学校推行了刷卡机制。  学校中有n个地点,用1到n的整数表示,每个地点设有若干个刷卡机。  有以下三类事…
浅谈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 #include<…
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 #include<bits/stdc++.h> #define int long long//不开…
bzoj 1858. [Scoi2010]序列操作 题解
Description 题目链接:BZOJ1858 [Scoi2010]序列操作 给你长度为$n$的$01$串,现有$m$个操作。 区间赋值为$0$区间赋值为$1$区间反转(所有$0$变为$1$,所有$1$变为$0$)区间求和求区间最多有连续的几个$1$ 对于$100\%$的数据,$1\le n,m \le 100000$。 Solution 珂朵…