@P2Oileen 2017-08-07T02:17:41.000000Z 字数 5752 阅读 2379

松神集训笔记

弱

day1

指针

int a=1;
int *p=&a;
则(*p)==a;
a[0]==*a;
a[i]==*(a+1);
void* 无类型指针

结构体

struct name
{
    int a;
    int b;
    double c;
}

www.cplusplus.com

<vector>
<queue>
<set>
<algorithm>
<iostream>//输入输出流

大O记号

big O notation//大O记号
f(x)对于每一个x有唯一的一个y与它对应
T(n)=O(f(n))
存在C,N>0,使得对于任意n>N,总有T(n)<=c*f(n);
O(1) O(logn) O(n^c) O(2^n)
维基百科
时间复杂度T(n);
空间复杂度S(n);
best worst average amortized expected

P	NP	NPC	NP-Hard
多项式时间内能够解决的问题	多项式时间内能够验证的问题	目前不能用多项式时间解决的问题，但是我们还不能证明这个问题不能用多项式解决	不知道，不管了

排序

基于比较的排序：

比较大小然后交换
O：比较次数+交换次数

稳定性：两个相同元素排序后的相对位置不发生改变，则稳定

//选择排序【不稳定】 O(n^2)
selection sort
{
   for(int i=0;i<n;i++)
   {
        for(int j=i+1;j<n;j++)
            if(a[i]>a[j]) swap(a[i],a[j]);
   }
}

//插入排序【稳定】 O(n^2)
insertion sort
{
    for(int i=0;i<n;i++)
    {
        for(int j=i;j>0;j--)
        {
            if(a[j]<a[j-1]) swap(a[j],a[j-1]);
            else break;
        }
    }
}

//冒泡排序【稳定】 O(n^2)
bubble sort
{
    for(int i=n;i>=0;i--)
    {
        for(int j=1;j<i;j++) if(a[j-1]>a[j]) swap(a[j-1],a[j]);
    }
}

逆序对：i < j且a[i] > a[j]；

//归并排序 O(nlogn)
//懒得写代码了，就是归归归并并并……

归并排序的过程中可以求逆序对的对数。属于分治算法。
每当后段的数组元素提前时，记录提前的距离。

不是基于比较的排序

计数排序（数据量大，数据本身小） O(n+m)m:数字的值域

//基数排序 
radix sort
{
    for(int i=0;i<m;i++) cnt[i]=0;
    for(int i=0;i<n;i++) cnt[key[i]]++;
    for(int i=1;i<m;i++) cnt[i]+=cnt[i-1];
    for(int i=n-1;i<=0;i--) dest[--cnt[key[i]]]=a[i];
}

数据结构（1）

向量。可以理解成一个数组，支持：

push_back()//末尾插入元素 O(n)
pop_back()//末尾弹出元素
empty()//返回是否为空 O(1)
size()//返回大小 O(1)
insert()//插入元素
delete()//删除元素
reverse()//调转

链表
详情参照去年我写的zybuluo帖子

<list>

队列
< queue>

双向队列
< deque>

图论（1）

有向图
无向图
自环
重边
简单图
度 degree（有多少条边连接了这个节点）
入度
出度
链式前向星==邻接表
路径 path：一个边的序列，且相邻两条边首尾相连
简单路径：同一条边只经过一次的路径（简单路径上可能有相同的节点）
环 cycle：一个起点和终点相同的路径
简单环：是简单路径，还是环
连通 connected：如果无向图中两个节点是连通的，则存在从a->b的路径
可达：有向图中
一个无向图是连通的，当无向图中任何两个节点都连通。
有向图没有连通的概念。
弱连通：把有向图所有边改成无向的，则该有向图弱连通。
强连通:有向图中任意两个节点可达
子图 subgraph：在一张图中选择一个边的子集和节点的子集，形成的一张新图，一个图本身是自己的子图。
生成子图：节点和原图相同，只删边的子图
导出子图：选出节点的子集，并将与该图中两端都有节点的边加入
边导出子图：选出边集，再选出相连的节点集合
连通子图：对于无向图来说的连通的子图
连通分量 connected component：对于无向图来说，是一个无向图中的极大的连通子图。即再加入一个点，该图不连通。
稀疏图：m=θ(n);
稠密图：m=θ(n^2);
完全图：任何两个节点之间都有边（对于无向图），m=n*(n-1)/2的简单图；
路径的长度：路径上边的长度和
最短路径：当不存在负环时存在。
树：有n个节点，n-1条边的连通无向图。
树：一个无向，无环的连通图。
树：任意两个节点之间有且只有一条简单路径的简单无向图。
森：每一个连通分量都是一棵树的图。每棵树都是森
生成树：是一个生成子图，也是一棵树。
有根树：在一棵树上选定一个节点作为根，则为有根树；
无根树：没根的树。
点的深度：当前节点到根节点的距离。根节点深度=0
树的深度：根节点儿子的深度的最大值
叶子节点：度为0或1的点
父亲：在有根树上，某结点到根的路径上的第二个节点即为父亲节点
祖先：到根路径上除了本身以外的所有节点
儿子/子节点/孩子/child/children：如果u是v的父亲，则v是u的儿子。
兄弟：同一个父亲的多个子节点之间为兄弟关系。
后代/子孙：儿子和儿子的后代们。
子树：删去该节点和该节点父亲之间的点之后该节点所在的连通分量。
一种树：一条链。
第二种树：菊花。
二叉树binary tree：每个节点最多有两个子节点的有根树。
左儿子：左边的儿子。
右儿子：右边的儿子。
真二叉树proper：每个点要么有2个儿子，要么有0个儿子。
满二叉树：对于每一层都有2^x个节点。
完全二叉树：除了最后一层以外都是满的，最后一排左对齐
树的存储方法：vector < int> childs[n]; int father[n];
或者使用邻接表。

day2

小考

（为什么只有十分钟啊生气！）
分光计

约定时间：10分钟
满分：20分

在这些题目中，我们只考虑通常的NOI Linux比赛环境：计算机的字长为32位，有符号整数类型采用补码（2's complement）方法表示。并且，我们暂且不考虑C++标准的要求，只考虑实际编译器的效果。

整数类型（5分）

对于下面的整数类型，指出其宽度（以二进制位计）、能表示的最小数、能表示的最大数（如果你记不住具体的数字，也可以用数学表达式描述这些数，形如 $2^{33}-666$ ）。

short
int
unsigned int
long long
unsigned long long

时间复杂度（11分）

如果是均摊，则必须注明这个复杂度是均摊复杂度，同时注明此时的最坏复杂度。

(1)

for(i = 1; i <= n; i *= 2)
    for(int j = 1; j <= n; j += i)
        ans++;

(2)

void f(int x) {
    if(x >= 2) {
        ans++;
        for(int i = 1; i < x; i++)
            f(i);
    }
}
f(n);

(3)

对长度为 $\sqrt n$ 的序列进行选择排序
对长度为 $n^2$ 的序列进行归并排序
对 $n$ 个不超过 $m$ 的正整数进行桶排序

(4)

对 $n$ 个元素的向量进行一次push_back
对 $n$ 个元素的向量进行一次pop_back
对 $n$ 个元素的链表进行一次insert
对 $n$ 个元素的链表进行一次erase
对 $n$ 个元素的（带有getmax功能的）队列进行一次push
对 $n$ 个元素的（带有getmax功能的）栈进行一次push

判断题（4分）

对于：

栈
队列

分别判断以下是否为真：

先进入的元素一定先出去，后进入的元素一定后出去
先进入的元素一定后出去，后进入的元素一定先出去

算法

DFS（深度优先搜索）

Traversal遍历

//图上DFS O(n+m)
dfs(u)
{
   vis[u]=1;
   for(each edge)
   {
        if(!vis[v]) dfs(v);
   }
}

dfs序列：
dfs时访问每个节点顺序的序列
节点顺序、边顺序（欧拉序）

BFS（宽度优先搜索）

顺序：一层一层
求出节点深度，儿子
O(n+m)
按照遍历序列逆推一边就能求子树大小了。

二叉树上dfs：得到一个dfs序列。

dfs(u)
{
    //print(u); 先序遍历
    dfs(lch[u]);
    //print(u); 中序遍历
    dfs(rch[u]);
    //print(u); 后序遍历
}

只要有中序+任意，就能还原二叉树
如果是前序+后序，则只能还原真二叉树

二分图

v1,v2：所有边从v1连到v2.
没有v1,v2内部的边
性质：不存在奇数条边构成的环。
每条边的两个端点都在不同的集合
判断二分图：染色
或者图上不存在奇环。

拓扑排序

定义：对于一张有向图，如果i->j存在边，则j依赖于i。若i可达k，则k间接依赖于i。
输出一个节点序列，使得排在前面的节点不依赖于后面的节点。

q= new queue();
for(int i=0;i<n;i++) if(in.deg[i]==0) q.push(i);
ans=new vector();
while(!q.empty())
{
    u=q.pop();
    ans.push_back(u);
    for(each edge(u,v)) if(--in.deg[v]==0) q.push(v);
    if(ans.size()==n) print ans;
    else printf("qwq");
}

DAG:有向无环图

字符串

noi linux: $man strstr 会返回

字符串匹配

定义：
1.单串匹配
一个模式串a，一个待匹配串p，找到a的字串与p相等
2.多串匹配
一堆串a,一个串p。

暴力算法：
取a每个位置比较就行啦，真的很暴力
设a长度n,b长度m。平均复杂度O(n);
best O(n) worst O(n*m);

哈希：
string->int
对应关系
n+m，有一定概率出错。减少错误率：

KMP：克努特——莫里斯——普拉特算法
a的第i个前缀等于最长的后缀的长度
next[1]=0;

//O(n)
for(int i=2;i<=m;i++)
{
    int t=next[i-1];
    while(t && a[t]!=a[i-1]) t=next[t];//自我匹配
    next[i]=t+(a[t]==a[i-1]);
}

for(int i = 1, j = 0; i <= n; i++){
    while(j && B[j+1] != A[i]) j = nxt[j];
    if(B[j+1] == A[i]) j++;
    if(j == m){
        printf("%d\n", i - j + 1);
        //这句是输出找到的【B字串在 A中位置】
        //如果要求的是出现次数，这里也有可能是ans++什么的
        j = nxt[j];//让循环进行下去
    }
}

多串匹配：AC自动机：Aho-Corasick

自动机：种类：有限状态自动机：1.字符集 2.状态集 3.转移集

首先，建立一个trie树。在树上预处理出fail（即kmp中的nxt）
BFS，将第二层的节点的fail全都连到root上。对于接下来的每个点，假设当前点为x,数值是C，我们往上找fail[x的父亲]，若fail[x的父亲]的一个儿子是C，那么我们就把fail[x]=fail[x的父亲]的为C的那个儿子。如果fail[x的父亲]没有为C的儿子，那么再找fail[fail[x的父亲]]]……直到为root。
然后像KMP那么跑就行啦。

建立O(n),跑O(m)【待匹配串】

数据结构（2）

堆 heap
定义：
一种数据结构
维护一个数的集合
功能：insert,getmin,delete,decreasekey（将堆中某个元素变小）;
二叉堆，二顶堆O(logn);
fib堆除了deletemin都是O(1);
二项堆merge O(logn);fib堆 merge O(1);

二叉堆：一个完全二叉树，满足堆的性质：每个节点的值不大于它的儿子的值
以小根堆为例，getmin O(1);
插入元素：O(logn);
decreasekey:O(logn)-----up
deletemin:O(logn);
down：O(n)；

线段树

维护一个序列
O(logn)
区间查询
区间最值
区间修改

树状数组

while(x<=n) T[x]+=val,x+=x & -x;//修改
while(x) ret+=T[x],x-=x&-x;//求值

跑得比线段树还快！

分块思想：在各种范围内都很好用。
举个栗子：要求区间和：线段树太难写，树状数组不会背，怎么办？
对询问分块.

图论（2）

所有节点编号都是1-n,边编号1-i；

tarjan
强连通分量：极大的强连通子图。
dfn[x]一个节点在Dfs时访问到的顺序
low[x]某种最小值。
tarjan主要基于dfs。

dfn[x]=low[x]=++index;
s.push(x);
instack[x]=true;
for each edge(x,y)
{
    if(!dfn[y])
    {
        dfs(y);
        low[y]=min(low[y],low[x]);
    }
    else if(instack[y])
    {
        low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        while(1)
        {
            t=s.pop();
            instack[t]=0;
            if(t==x) break;
        }
    }
}

割点：删掉该点后，图不连通
桥：一条边删掉后图不连通
无向图上tarjan:双连通分量
点双连通：任意两点间存在两条路径，且节点序列不相交。【缩点后成树】
边双连通：边序列不相交。

/*
dfs(u,fa)
{
    dfn[u]=low[u]=++index;
    int n_ch=0;
    dfs(v,u);
    low[u]=min(low[v],low[u]);
    if(low[v]==dfn[v]) bridges.push_back(u,v);
    if(low[v]==dfn[u]) is_ap[u]=1; ++n_ch;
    else if(a!=NULL && v!=f[a])
    {
        low[u]=min(low[u]////)
    }
}
*/

day3

最短路

简单最短路：不重复的边

无负权边：不可能出现重复的边

floyd:求多源最短路（最短路不存在或者两点之间不可达：无法求得）

f[k][x][y]:通过1~k的点从X到Y的最短路
然而在循环的时候，我们只用到了k和k-1，所以第三维的数组是可以省略的。在循环k=n~1时，覆盖之前的数据就可以了。
时间O(n^3) 空间O(n^2)

Bellman-ford
n*m（暴力搜索，可以处理负边）

SPFA