STL:Map,Set(Multiset & Bitset)
七段第三课: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算法
浅析 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] ...
线段树
线段树($\tt Segment\ Tree$)最好用的数据结构,没有之一。
他可以以 $\log_2{n}$ 的复杂度处理区间和,区间最值,单点修改,区间修改等操作,也是非常的好用,有一些题目你可以直接上一个线段树,然后以比正解略劣的解法过掉。
思想维护一棵树,父亲区间被两个儿子平分,直到分到区间只剩下一个元素(叶子)
假如,我们现在有个 $a$ 数组,要使用线段树完成一些问题。
a[] = {[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]}建成线段树就是这样的:
之后,我们只要是进行单点的操作,就可以顺着叶子把一路上的东西都修改掉,而且由于每次一个点只被分成 $2$ 个儿子,树的层数是 $log_2 n$ 复杂度也有保障。
基本结构想要用数组存储一个上面的线段树,我们首先是要考虑,节点个数。数一数,发现上图一共有 $33$ 个点。经过长达 114514s 的思考,发现刚好是 $2 n - 1$ 。这难道是巧合吗?显然不是。可以给出如下证明:
叶节点数量
非叶子数量
总节点数量
二叉树效果图
1
0
1
2
1
3
...
517编程7段第五课T2
大秦为您打开题目传送门(3/1 题目大意题目的表述十分清楚,他就是让你求字典序最小的最长上升子序列,如果不存在输出 orz 。
注:在某人jdt1010的提示下发现不存在的情况是当 $n=0$ 的时候分值为两分多一点。
3/2 解题思路方法1:$dp[i]$ 表示以 $i$ 结尾的最长上升子序列长度我们阅读题目发现,这道题 $n$ 的数据范围非常大,传统的 $O(n^2)$ 算法肯定是用不了。所以开始思考换一种思路。由于题目数据范围是 $n\le 10^5$ ,所以不难想到使用 $O(n)$ 或者 $O(n\log n)$ 的算法。
我们开始思考:对于一个上升子序列,显然其结尾元素越小,越有利于在后面接其他的元素,也就越可能变得更长。所以,我们新建立一个 $st$ 数组,表示以 $i$ 结尾的最长上升子序列的结尾最小值,显然 $st$ 数组严格单调递增。那么我们实际上就只需要维护这个 $st$ 数组,从而去求出 $dp$ 值。
那么问题就变成了:如何维护这个 $st$ 数组呢?
如果这个 $a[i]$ 直接可以接到我们的LIS后面,那么就直接放到 $st$ 数组后面。
否则,就把 $ ...
洛谷P1990
大秦为您打开题目传送门(3/1 题目大意题目的表述十分清楚,他就是让你用竖着两个方块和 L 形的方块填满一个长 $n$,宽 $2$ 的长方形。方块可以旋转,如下图
1234 ___ ___ 方块2(反)* ______ /__/\ 方块1(横)* ______ /__/__ /__/__/\/__/\/ /__/__/\ /__/__/\ \_/__/\/\__\/ *方块1(竖) \__\__\/ \__\__\/ *方块2(正) \__\/ *此图大大滴形象
3/2 解题思路我们一拿到这道题,读完以后,显而易见的,这是一个编程题递推题。那么一开始我们大都会像下面这样推
设 $dp[i]$ 表示铺满前 $i$ 列的方案数。然后,自己枚举出 $dp[1]=1, dp[2]=2, dp[3]=5,dp[4]=11$ 。之后呢,又推出 $\tt DP$ 方程是 $dp[i]=dp[i-1]+dp[i-2]+dp[i-3 ...
【转】堕落的天蓝色天使
eb44ce4cc1f4aef4a1743005f1d61db38493313ec0cc8411555ac81a8eefebed5c5a6fff6ab506cd748a43244ee95f6a70d5d8d9e5ea8984c657960957aa19e5ea87afd86e705667ae12cb13a7a2934d8c35147cbb2248f694d85fc33eb0a43b036255dc28b1275e7691c051912e370281c1527ef7f8af3400428d6b5801e4d4c0d930dd0a6ff5fa2dae8a81a9e7cd49e709bc303a4c6605fb050d057f787a5593407724b1157c9c0ef698beac96cd37d6b13c1f4eb459ed65382f6c2a9ce65f386db59474d1ea46aa82b4f67c416f686993cb6c8b4ada83d094d2969b51b174038427fb87510510b06d1a4f06b147d73a605a0b2537d3965 ...
【转】破碎的白金色爱恋
bbbf624166adc60d21b5c93a5386e92f3067258d7f09cbf7b9a987184e9d5018650b55d1ad71393fb700b878d1ad94fe01f0032e81f0fb6e3b36c0dfbfeb7b4e11260e2bac987289989dddb01fa74360e590575ab6e224e1cbfe3939e59b5011eb5b54c49cd53875adac180044b57f945e58b0dc45087aeee4e1b822bc106c58795e2010532881ff7d095788ba988b46b5c80d84a49a11f075555b3a282a98dd274c090a23b8851d9311ec1e0576e8f75df049fd94a8f431567c6763f7b84c614fbb8c5ceaefaf8d7ecbfaa26ef2821018b0a2b190acab53acff7864520545e2194b3affcd061521d4071acece137f32945e7d5c924257515 ...