#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;
int flag;
int main ()
{
    string a , b ;
    int la , lb ;
    char temp ;
    int place;
    vector< char > w ;
    getline ( cin , a) ;
    la = a.length() ;
    b = a ;
    sort( b.begin() , b.end() ) ;
    temp = b[ 0 ] ;
    for ( int i = 0 ; i <= la - 1 ; i++ )
    {
        w.insert( w.end() , a[ i ] ) ;
    }
    while ( w[ w.size() - 1 ] == '0' &&  isdigit(w[ w.size() - 2] ) )
    {
        w.erase( w.end() - 1 ) ; //w.end()需要-1才能到动态数组中最后一个有效的数字 
    }
    if ( !isdigit(temp) )
    {
        place =  a. find( temp )  ; //返回下标 
        //cout << place ;
        reverse( w.begin( ) , w.begin() + place ) ;
        reverse( w.begin( ) + place + 1 , w.end() ) ;
        int i = 0 ,j = place + 1 ;
        while (  i < place  )
        {
            //cout << " w[i]=="<<w[ 0 ] <<endl ;
            if( w[ 0 ] == '0' && i + 1 != place  )  w.erase( w. begin( ) ) ;
            i++ ;
        }
        while (  j < la - 1  )  // la -1 为原来数组的最大下标 ，此时用来做最大执行次数 
        {
            if( w[ w.size() - 1] == '0' && j != la - 1) w.erase( w.end() - 1) ;
            j++ ;
        }
        for ( int i =0 ; i < w.size() ; i++ )
            cout << w[i] ;
    }
    else 
    {
        reverse( w.begin() , w.end() ) ;
        for ( int i =0 ; i < w.size() ; i++ )
            cout << w[i] ;
    }
    return 0;
}

二，字符反转

１.sort( ) ;

（1）是c++时(string a)

sort( a . bedin () , a . end() ) ;

reverse ( a . bedin () , a . end() ) ;

find ( x ) ; //x为字符型，返回的则是它的位置

（2）是c时( char a[ ] )

sort( a , a + num ) ; // num为整型数字

reverse ( a , a + num ) ;

P1553 数字反转（升级版）链接

三，模拟

步骤

1.最优化解题，滤清大概思路解题，写出解题框架。

2.可考虑多开数组，用来巧妙避免小出错。

3.发生周期性变化时，可用“%”使得周期性能够简易表达。

4.为防止数组越界问题，下标得开大一点。

5.下标从（1 . 1 ）开始比从（0.0）开始要容易避免数组越界的问题，并且在第一行，第一列可当作数组的边界，以防数组越界问题的出现。

P1002 [NOIP2002 普及组] 过河卒链接

当遇到矩阵旋转时，核心是抓住n*n阶旋转矩阵的中间点，然后其他与其相邻的点都可以用它来表示（用两个循环框架），令一个关键就是第一行到中心点的距离 r ，r= n（阶）/ 2 取整； r 直接影响 i 和 j ；

P4924 [1007]魔法少女小Scarlet

四，递归题框架

步骤

1.首先滤清题意，着重弄清要要解决什么问题

2.判断要回溯或不用，若解题要回溯的话，也是根据函数返回的东西来判断，回溯的话函数就是空类型，方便回溯，一般语句为 return ;

3.条件的考虑：

（1）结束条件是什么，有几个，在函数题的前端，回溯或递归是先行运作。

（2）要回溯时，回溯的条件是什么，

（3）递归条件，有几个，什么时候需要递归，

4，大局观，分析题目的大局，小问题后解决，框架先写出，时间顺序，先列大局，后小递归。

P1028 [NOIP2001 普及组] 数的计算

P1010 [NOIP1998 普及组] 幂次方P

5.递归用到的小技巧，记忆化搜索，作用：加快递归效率，减少运作时间，避免重复递归

。记忆化搜索

1.设置数组来标记，递归时判断，递归第一次时则标记为已递归的标志

2.设置数组直接存储递归的值，借它的下标组作为访问它的标志，下此运转时，直接输出数组里面的值，

该步骤比第一步更为简便和实用，根据具体题目来分析

P144 链接Function

#include<iostream>
#include<string>
#include<climits>
using namespace std;
long long  p[22][22][22];
long long he(long long a, long long b, long long c)
{
    if (a <= 0 || b <= 0 || c <= 0) { return 1; }
    else if (p[a][b][c] != 0) return p[a][b][c];//搜索的关键
    else if (a > 20 || b > 20 || c > 20)
    {
        return  he(20, 20, 20);
    }
    else if (a < b && b < c)
    {
        p[a][b][c]= he(a, b, c - 1) + he(a, b - 1, c - 1) - he(a, b - 1, c);
        return p[a][b][c];
    }
    else
    {
        p[a][b][c] = he(a - 1, b, c) + he(a - 1, b - 1, c) + he(a - 1, b, c - 1) - he(a - 1, b - 1, c - 1);
        return p[a][b][c];
    }
}
int main()
{
    long long  a, b, c;
    while (cin >> a >> b >> c)
    {
        if (a != -1 || b != -1 || c != -1)
        {
            printf("w(%lld, %lld, %lld) = ", a, b, c);
            if (a > 20)a = 21;
            if (b > 20)b = 21;
            if (c > 20)c = 21;
           cout<<he(a, b, c)<<endl;
        }
        else exit(0);
    }
    return 0; 
}

五,迷宫问题

步骤：

1.dfs（）函数一般是 void 空类型，回溯！

2.确定递归条件；

3确定回溯条件；

4.确定结束条件，越界，或者不合法情况；

5.小技巧：数组问题，迷宫问题时，可以开设方向数组/小数组；

void dfs (  ) 
{
    if (到达终点状态) //结束条件
    {
        return ；//回溯的标志
    }
    if (越界或者不合法情况) return; //回溯
    for ( 扩展方式 )
    {
        if(扩展方式 合法时)
        {
            进行修改操作；// 根据题意添加标记，如标记已访问
                dfs();
            (还原标记,回溯后需要执行的条件); // 是否需要根据题意 ，加上还原条件就是回溯法
        }
    } 
}
代码优化后
开设方向数组 dx 和 dy
{dx[ 4 ] = { 0, 1 , 0 , - 1 }
{dx[ 3 ] = { 1 , 0 , - 1 , 0 }
#include<iostream>
using namespace std ;
int m,n ,p,q,min = 99999999;//技巧：给最小值设置一个很大的值
int a[100][100],v[100][100];//前者是地图，后者是访问数组
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//技巧：开设方向数组
void dfs(int x , int y ,int step ) 
{
    if( x == p && y == q )
    {
        if( step < min ) min = step ; // 巧妙的将最短路径的步数一个一个比较并且存入min其中
        return ; //比min 大则回溯推出 
    }
    for ( int k = 0 ; k <= 3 ; k++ ) // k为四个可以走的方向 ：上下左右
    {
        int tx , ty ;
        tx = x + dx[k] ; 
        ty = y + dy[k] ;  //直接利用方向数组，将往哪个方向走巧妙的表达出来
        if( a[ tx ][ ty ] == 1 && v[ tx ][ ty ] == 0 ) //表示此时是空地且未访问 
        {
        v[ tx ][ ty ] == 1 ;//将该点访问
          dfs ( tx , ty , step + 1 ) ; // 继续搜索
            v[ tx ][ ty ] == 0 ; //当有一步到达终点后，它需要回退也就是回溯 ，重新找不同
                                //的路径，因为不排除其他三个方向都可以走的情况，也就是新路线
                               //所以之前走过的地方需要重新标记为未访问 
        }
        return ;
    }
}
int main ()
{
    int startx = 1  ,starty = 1; //定义起点的位置
    cin >> m >> n ;//地图大小
    cin >> p >> q ;//终点坐标
    for (int i = 1 ; i <= m ; i++ ) //画地图标明空地和障碍 空地为1，障碍为2
    {
        for (int j = 0 ; j <= n ; j++ )
             cin  >> a[i][j] ;
    }
    v[startx][starty] = 1 ; //已访问标记
    dfs ( startx , starty , 0 ) ; //dfs 进行最短路径探索 , 0 是步数
    cout << min ;
return 0 ;
}

未优化的递归回溯：

编辑

六，stl的map<char,int>

#include<iostream>
#include<map>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
map<char,int>m;
int main(){
    int maxx=-999999,minn=999999;
    char a[101];
    cin>>a;
    int l=strlen(a);
    for(int i=0;i<l;i++){
        m[a[i]]++;
        maxx=max(maxx,m[a[i]]);
        //minn=min(minn,m[a[i]]);
    }
    for(int i=0;i<l;i++){
        minn=min(minn,m[a[i]]);
    }
    //cout<<maxx<<' '<<minn<<endl;
    maxx-=minn;
   // cout<<maxx<<endl;
    if(maxx==0||maxx==1){
        cout<<"No Answer"<<endl;
            cout<<0;
            return 0;
    }
    for(int i=2;i<=sqrt(maxx);i++){
        if(maxx%i==0){
            cout<<"No Answer"<<endl;
            cout<<0;
            return 0;
        }
    }
    cout<<"Lucky Word"<<endl;
    cout<<maxx;
    return 0;
}

七，Vector容器/动态数组( vector < int > a )

1，算法

排序：sort ( a. begin( ) , a. end( ) );

反转：reverse( a. begin( ) , a. end( ) );

查询：find ( a. begin( ) , a. end( ) , number ) ; 自推仅限整型

2，函数

返回第一个元素：a . front( ) ;

判断容器空否：a . empty( ) ;

删除： a . erase ( a . begin ( ) ) ;

a . erase( a. end( ) - 1 ) ;

插入： a . insert ( a.bigin( ) , x ) ;

3，实例