【算法基础】蓝桥杯入门算法

一、STL库

1.动态数组

vector<int> a
.push_back（）
.pop.back（）
.size（）
.clear（）

　　     可能存在空间爆炸问题，用  vector () .swap(v)来解决。
2.集合

set<int> v
.insert（）
.erase（）
.cout()

比较方式：

Bool operator<(const people &rhs) const
{

      Return h<rhs.h;

}

迭代器：

set：：iterator it =v.begin（） 
it!=v.end（）
it++
it－>x
*it

从小到大访问

3.映射

map m

#include

从小到大访问

也要用迭代器

It->first

It->second

在printf和scanf时可以用c_str().

printf(“%s  %d\n”  ,( it->first).c_str() , it->second);

4.字符串

Char a[15]

Scanf(“%s”,a);

PS:注意当时间超时时，可以试着把cout和cin改成printf和scanf。

二、stack

Stack s
.push()
.pop()
.size()
.top()
.empty()

PS:在可能超出int范围时，（2^6-1）可以采用long long 来表示。

       可以采用访问标志 vis【x】

       注意判断溢出等情况

       Include 可以用min（）函数

三、深度优先搜索DFS

例如迷宫问题：

Mes[i][j]----迷宫结构

Visit[i][j]----是否被访问过

Dir【4】【2】={{1，0}，{-1，0}，{0，1}，{0，-1}}-----前进方向

Dfs算法：

If( in(x,y) && !visit[x][y]  && mes[x][y]！=”T”)

{

       X=x+dir[i][0];

       Y=y+dir[i][1];

       Dfs[x,y];

       Return true;

}

四、抽象深度优先搜索问题

例如：N皇后问题

//r行i列

Int ans=0;

Bool col[10];x1[20],x2[20];

Void check(int r ,int i )

{

       Return !col[i] && !x1[r+1] && !x2[r-i+8];

}

Void dfs(int r )

{

       If(r==8)

       {

              Ans++;

              Return;

}

       For(int i=0;i<8;i++)

       {

              If(check(r,i))

{

                     Col[i] = x1[r+i]=x2[r-i+8]=true;

                     Dfs[r+1];

                     Col[i]=x1[r+i]=x2[r-i+8]=false;

 

}

}

}

Int main()

{

       Dfs(0);

       Cout<endl;

       Return 0;

}

五、深度搜索的剪枝策略

去除掉一些不可能发生的事件的搜索。以达到节省时间的目的。

 最优性剪枝：在求解迷宫问题时，如果当前步数已经超过了最优解的步数，则不需要继续搜索，这样可以省去大量冗余的步骤计算。

       　　　　在搜索是否有可行性问题时，一旦找到了一组解，后面的所有搜索就不必继续执行了。

例如：

• 重复性剪枝
• 可行性剪枝

六、广度优先搜索 BFS

队列

#include<queue;

Queue q;

q.push()入队

q.front()获取队首元素

q.pop()出队

q.empty()判断队列是否位空

注意！没有clear方法要自己手动pop清空队列

 广度优先搜索bfs 使用队列queue来实现

1、 把起始点放到队列中，标记起点访问

2、 如果队列不为空，出队列x，否则算法结束

3、 访问所有与x线=相连接的元素v，如果v没有被访问，v入队，并标记以访问

4、 重复步骤2

例如迷宫问题中，使用bfs可以直接求出其最短路径

七、Pair的用法

1，pair的应用

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。

其标准库类型--pair类型定义在#include 头文件中，定义如下：

类模板：template struct pair

参数：T1是第一个值的数据类型，T2是第二个值的数据类型。

功能：pair将一对值(T1和T2)组合成一个值，

        这一对值可以具有不同的数据类型（T1和T2），

        两个值可以分别用pair的两个公有函数first和second访问。

定义(构造函数)：

1. pair p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
2. pair p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
3. make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
4. p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
5. p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
6. p1.first;                   // 返回对象p1中名为first的公有数据成员
7. p1.second;                 // 返回对象p1中名为second的公有数据成员

2，pair的创建和初始化

pair包含两个数值，与容器一样，pair也是一种模板类型。但是又与之前介绍的容器不同；

在创建pair对象时，必须提供两个类型名，两个对应的类型名的类型不必相同

pair<string, string> anon;        // 创建一个空对象anon，两个元素类型都是string
pair<string, int> word_count;     // 创建一个空对象 word_count, 两个元素类型分别是string和int类型
pair<string, vector<int> > line;  // 创建一个空对象line，两个元素类型分别是string和vector类型

当然也可以在定义时进行成员初始化：

pair<string, string> author("James","Joy");    // 创建一个author对象，两个元素类型分别为string类型，并默认初始值为James和Joy。
pair<string, int> name_age("Tom", 18);
pair<string, int> name_age2(name_age);    // 拷贝构造初始化

pair类型的使用相当的繁琐，如果定义多个相同的pair类型对象，可以使用typedef简化声明：

 typedef pair<string,string> Author;
 Author proust("March","Proust");
 Author Joy("James","Joy");

变量间赋值：

pair<int, double> p1(1, 1.2);
pair<int, double> p2 = p1;     // copy construction to initialize object
pair<int, double> p3；
p3 = p1;    // operator =

3，pair对象的操作

访问两个元素操作可以通过first和sencond访问：

pair<int ,double> p1;
p1.first = 1;
p1.second = 2.5;
cout<' '<//输出结果：1 2.5
string firstBook;
if(author.first=="James" && author.second=="Joy")
firstBook="Stephen Hero";

4，生成新的pair对象

还可以利用make_pair创建新的pair对象：

pair<int, double> p1;
p1 = make_pair(1, 1.2);
cout << p1.first << p1.second << endl;  　　//output: 1 1.2
int a = 8;
string m = "James";
pair<int, string> newone;
newone = make_pair(a, m);
cout << newone.first << newone.second << endl;　　//output: 8 James

5，通过tie获取pair元素值

在某些清况函数会以pair对象作为返回值时，可以直接通过std::tie进行接收。比如：

std::pairstring, int> getPreson() {
　　return std::make_pair("Sven", 25);
}  
int main(int argc, char **argv) {
　　std::string name;
　　int ages;
　　std::tie(name, ages) = getPreson();
　　std::cout << "name: " << name << ", ages: " << ages << std::endl;
　　return 0;
}

 八、动态规划

动态规划是求解最优解问题的一种方法。

递推公式：

　　采用填表的形式，把所有计算结果填入表中。

• 最优化原理：一个最优策略的子策略，也是最优的。
• 无后效性：这个阶段以后过程的发展不受这个状态以前各个状态的影响。

状态转移方程（核心！）：

　　第i阶段的状态f（i）和决策u（i）来确定第i+1的状态，即为F(i+1)=T(f（i），u（i）)

        PS: 注意边界处理！

九、常见动态规划模型

• 最大子段和：
  • 当sum<0时，令sum=0，如果sum>ans，则更新ans；
• 最短编辑距离：
  • 当i==j，dp[i][j]=dp[i-1][j-1];
  • 否则,dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;

十、背包问题

• V[i]是第i的体积 ；    
• w[i]是第i的价值；

递推公式：

　　当第i步可以放入时:

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])

　　或者第二种方法:

for(int i=1;i<=n;i++)

       for(int j=v;j>=c[i];j--)

              dp[j]=max( dp[j-c[i]] + w[i] , dp[j] );