祝馀宫

问题：需求有n对元素 $(𝑣_1,𝑤_1),(𝑣_2,𝑤_2), (𝑣_3,𝑤_3), …,(𝑣_𝑛,𝑤_𝑛)$。要求从中挑选出 $k$ 对，使得 $v$ 的和除以 $w$ 的和最大。 解法：分析显然是一道二分题，我们直接二分最大值可得式子：（ $x[i]$ 表示选或不选，值是 $0$ 或 $1$ ） \cfrac{\sum\limits_{i=1}^n{v_i\times x_i}}{\sum\limits_{i=1}^n{w_i\times x_i}} >mid由于浮点精度误差问题，将其改写为乘法形式 \sum\limits_{i=1}^n{(v_i\times x_i)}>mid \times \sum\limits_{i=1}^n{(w_i\times x_i)}接着移项 \sum\limits_{i=1}^n{(v_i\times x_i)}-mid \times \sum\limits_{i=1}^n{(w_i\times x_i)} > 0由于有 $x_i$ 的共因子，所以提取出来 \sum\limits_{i=1}^n{w_i(v_i-mid ...

理论：什么是三分提到三分，首先就要回顾二分，二分是一种可以在单调函数上寻找值的算法，复杂度 $O(\log n)$ 。 三分与二分不一样的地方是，他把要寻找的值域分为三份，目的是寻找单峰函数的极值。 实现：怎么写三分如图： 假设我们要在 $l$ 到 $r$ 中查找最值，先取整个区间的中点。 1double mid = (l + r) / 2; 然后我们再取右半部分的中点 $midr$ 1double midr = (mid + r) / 2; 然后比较 $mid$ 和 $midr$ 哪个更靠近最值，若 $mid$ 更靠近最值，则舍弃右区间，若 $midr$ 更靠近最值则舍弃左区间。 1234if(Check(mid) > Check(midr)) r = midr;else l = mid; 完整代码： 1234567891011double ssearch(double l,double r){ while(l+eps<=r){ double mid = (l + r) / 2; midr = (mid ...

理论：如何设计需求：要解决的问题对于一些题目，他们要求你计算一个区间内的最小值，没有操作，但是询问次数特别多，以至于树状数组和线段树 $O(m\log n)$ 的时间复杂度已经不够优秀，我们需要引入新的数据结构。 构造：寻找合理方案同样的，我们说过，数据结构是时空平衡的，想要把单次询问复杂度降下来，就需要更高的预处理和空间复杂度。根据我们数据结构的根本是分组的思想，我们需要重新修改分组。 我们思考一下，理想状态是什么？理想状态是我们预处理出来的值可以直接拿出来用，或者经过 $1$ 次运算可以得出。我们可以和两个极端比较一下。 预处理 单次 数组 读入 $O(n)$ for 一遍 $O(n)$ 预处理出所有区间最值 $O(n^2)$ $O(1)$ 理想数据结构 不知道 由于查询次数极多，所以必须需要单次 $O(1)$ 的算法 首先我们坑定得是 $1$ 对多的分组方式，我们可以打表看看 对于序列 $a[10] = [ 1, 4, 7, 3, 2, 8, 5, 9, 6, 10 ]$ 可以得出如下表格。 区间 $[l,r]$ 1 2 3 4 5 6 ...

概念：什么是树状数组？需求：发现问题、提出问题在信息学竞赛中，我们经常会遇到求一段区间和的题目。一般来说，我们就只需要使用前缀和数组这是一个预处理时间复杂度 $O(n)$，单次查询 $O(1)$，修改 $O(n)$ 的算法。显而易见，在遇到一些数据范围特别大，修改次数特别多的题目时，就会发生爆炸。而这时我们需要一个可以均衡这个时间复杂度的数据结构。 构造：寻找解决问题的方案那么如何制造一个这样的数据结构呢？我们可以从数据结构的根本考虑，数据结构是一种可以将时间和空间均衡，使得解决题目的东西。对于前缀和无法完成的题目，就需要更好的数据结构。不可能会有时间短，空间小，功能强大的数据结构，想要让时间变少，就得用空间换，想要让空间少，就得用时间换。我们可以对于基本的数据结构经行比较。 单点修改时间复杂度 区间查询时间复杂度 期望效果 数组 $O(1)$显而易见的，对于当前的点经行修改便是 $O(n)$对于区间 for 一遍求解 由于想要使前缀和数组的单点修改复杂度降低、综合数组的区间查询，作为代价，必须要增加这里的时间复杂度 前缀和 $O(n)$当前缀和中一个点修改时，之 ...

七段第三课：STL这篇主要讲了STL中的MAP，SET，MULTISET，BITSET。 Map定义你可以理解成是一个下标可以为任意东西的数组。在 $\tt c++$ 中，你可以以如下方式定义一个 $\tt map$ ： 1map<typename _Key, typename _Tp>mp; 它你可以以如下格式访问它某一个值： 1mp[(_Key) x] = (_Tp) y; // 括号里面的不用写，是注解作用 它表示，在 $\tt mp $ 的下标为 $\tt _Key$ 类型的 $x$ 位置存储着 $\tt _Tp$ 类型的 $y$ 。 使用从某种意义上来讲，$\tt map$ 类型的 $\tt STL$ 可以被称为哈希表。因为它的前面的项没有限制，而之后的也没有限制（只要在对应数据类型范围内）而这一个工具的单次时间复杂度是优秀的 $O(\log n)$ 。 使用的话，除了定义和赋值，还可以以循环的方式查询，而 $\tt map$ 内部的排序默认是按照从小到大排序。（也就是说你可以自定义 $\tt map$ 的排序方式） $\tt for$ 循环的写法如下： 1234 ...

二分图定义二分图，是一种可以将所有点分成两个点集，同点集不连，异点集相连的图，如图： 像这样的图就是二分图。 如何判断二分图显而易见的，想要构造一个不是二分图的图，我们可以通过构造环来看，毕竟从理论上来讲因该是可以从环来推出规律。 先构造一个三个点的奇环：显而易见，不是二分图 再来是四个点的偶环：可能一想不是二分图，但是画出来以后发现是二分图 再来是五个点的奇环：不用画图就显而易见，不是二分图 所以，我们发现其实这个二分图只要没有奇环就可以了 代码实现判断奇环，只需要使用奇偶染色法就可以了，代码如下： 12345678910111213bool Dfs(int u, int c) { // vis : 0 - 未访问 ; 1 - 奇 ; 2 - 偶 vis[u] = c; for(int i = hd[u]; i; i = e[i].nt) { int v = e[i].to; if(vis[v] == c) return false; if(vis[v] == 0 && !Dfs(v, 3 ...

七段第二课：贪心A -【提高组】第二课：最小字典序No.1 - 题目大意每次可以从S的开头或者结尾取出一个字符，放到一个T字符串的尾部。输出T字典序最小的可能。 No.2 - 解题思路如果直接从两头看那个小取肯定是不行的，样例也告诉我们：不可以乱取 123456789101112S : "ACDBCB" T : ""S : "CDBCB" T : "A" // A 小S : "CDBC" T : "AB" // B 小// 方法 1 S : "CDB" T : "ABC" // 取右边的 CS : "CD" T : "ABCB" // B 小S : "D" T : "ABCBC" // C 小S : "" T : "ABCBCD" // 只剩下 D 了/ ...

七段第一课：枚举A - 第一课：按钮变色主要知识点：二进制枚举 No.1 - 题面有一个4x4的网格上面有16个按钮。按钮只有黑(b)白(w)两种颜色。按动任意一个按钮，那么该按钮本身以及其上下左右的按钮（如果有的话）都会改变颜色(由白变黑，由黑变白)。给出初始按钮的状态，输出最少要按多少次按钮才可以让所有按钮变为同一种颜色。 输入输入有4行，每行包括4个字符（‘w’或’b’, ‘w’表示该位置目前为白色按钮，’b’表示该位置为黑色按钮）。 输出输出最少要按多少次才能将所有的按钮变成同一颜色，如果没有办法变成相同颜色，输出 Impossible 。 No.2 - 解题思路一般来讲这一道题第一眼都是广搜，广搜的注意点在于，某些人把数组改了发现不对劲直接 continue 然后忘记改回来了。 但是，这一节课名字叫做枚举，自然是有枚举做法的。我们观察数据范围，发现数据是 $4 \times 4 = 16$ 的矩阵，所以可以直接暴力枚举所有要按的按钮，看看哪个是有解的就可以。 No.3 - 关键代码1234567891011121314151617181920212223242526272 ...

浅析 Tarjan 算法算法简介​ 由 $\tt Robert\ Tarjan$ 发明（useless。 可以求强连通分量、缩点、割点、桥等，大大滴实用。 前置知识 : Dfs 树​ 定义：一个图按照 Dfs 的顺序建立成的生成树。​ 规则就是，按照 Dfs 的顺序，可以走就走，不可以走重复的点，走完为止。 ​ 在树上的边称为树边，不在树上的是非树边。 ​ 如图， $0$ 是根，绿色的是树边，黑色的是返祖边。 ​ ​ 那么实现也很简单，为了完成这样一个功能（区分树边和返祖边）。我们就要标记一个点有没有走过，走到一个没有走过的点，这条边就是树边，走到一个走过的点，那这个就是返祖边（对于无向图）。 12345678910111213void Dfs(int u, int fa) { vis[u] = 1; for(int i = hd[u]; i; i = e[i].nt) { int v = e[i].to; if(!vis[v] ...