洛谷 P3373 【模板】线段树 2 题解 发表于 2019-08-27 | 分类于 题解 | | 热度: ℃ Description给定一个长度为 $n$ 的数列和 $m$ 个操作，支持区间加法、区间乘法、区间求值。 数据范围：$n≤100000$ , $m≤100000$ 阅读全文 »
背包九讲 发表于 2019-08-24 | 分类于 笔记 | | 热度: ℃ 以下是学习背包九讲的学习笔记，只有前八讲。原文链接。 01背包问题Description有 $n$ 件物品，一个容量为 $m$ 的背包。每个物品有价值 $v$ 和重量 $w$。挑选一些物品放入背包，每个物品只能用一次，求最大价值。 阅读全文 »
洛谷 P1197 [JSOI2008]星球大战 题解 发表于 2019-08-23 | 分类于 题解 | | 热度: ℃ Description给你一张 $n$ 个点 $m$ 条边无向图，$k$ 次操作，每次去掉一个点和与其相连的所有边，问每次操作后的联通块个数。 数据范围：$1≤n≤400000 , 1≤m≤200000$ 阅读全文 »
洛谷 P3957 跳房子 题解 发表于 2019-08-23 | 分类于 题解 | | 热度: ℃ Description跳房子的游戏规则如下：在地面上有一个起点，起点右侧有 $n$ 个格子，在同一直线上。每个格子内有一个整数，表示到达该格子能得到的分数。规则规定：玩家每次都必须跳到当前位置右侧的一个格子内，可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。 阅读全文 »
洛谷 P1030 求先序排列 题解 发表于 2019-08-22 | 分类于 题解 | | 热度: ℃ Description给出一棵二叉树的中序与后序排列。求出它的先序排列（树结点用不同的大写字母表示）。 数据范围：长度 $≤8$ 阅读全文 »
洛谷 P1070 道路游戏 题解 发表于 2019-08-21 | 分类于 题解 | | 热度: ℃ Description环形马路上有 $n$ 个工厂，两个相邻工厂由一段马路连接。以某个工厂为起点，按顺时针将这 $n$ 个工厂编号为 $1-n$，第 $n$ 个工厂和第 $1$ 个工厂连接在一起。将连接工厂的 $n$ 段马路编号为 $1-n$，第 $i$ 段马路连接第 $i$ 个工厂和第 $i+1$ 个工厂 $(1≤i<n)$，第 $n$ 段马路连接第 $n$ 个工厂和第 $1$ 个工厂。 阅读全文 »
洛谷 P1886 滑动窗口 题解 发表于 2019-08-21 | 分类于 题解 | | 热度: ℃ Description有一堆共 $n$ 个数字，一个大小为 $k$ 的窗口。窗口从左边开始向右滑动，每次滑动一个单位，求每次滑动后窗口中的最大值和最小值。 数据范围：$n≤10^6$ 阅读全文 »
分块 发表于 2019-08-20 | 分类于 笔记 | | 热度: ℃ 思路分块是一种数据结构，往往把数据分为许多块来处理。让每一个 整块 维护一些信息。暴力区间两个端点的小块。时间复杂度一般带根号。 阅读全文 »
bzoj 2002 [Hnoi2010]Bounce 弹飞绵羊 题解 发表于 2019-08-18 | 分类于 题解 | | 热度: ℃ Description有 $n$ 个排成一行的弹力装置。第 $i$ 个弹力装置的弹力系数是 $k_i$，它会把绵羊弹到第 $i+k_i$ 个装置上。如果不存在第 $i+k_i$ 个装置，绵羊被弹飞。 $m$ 次询问，有两种操作：$opt=1$: 输入一个数 $i$，查询绵羊从第 $i$ 个装置开始需要多少次被弹飞；$opt=2$: 输入两个数 $i$ 和 $j$，表示将装置 $i$ 的弹力系数改为 $j$。 阅读全文 »