蓝桥杯C++相关

文章目录

• 蓝桥杯算法
• • 有用链接
  • 小技巧
  • • 用变量大小初始的二维数组
    • 求gcd最大公约数
    • 对map for_each的遍历
    • 二进制输出
    • 初始化递增的数组或者容器
    • c++分割,按照指定字符分割
    • 求最大最小值
    • 输出到文件
    • 小数的二进制
    • 位运算
  • 注意事项
  • • scanf和char
    • devc++中添加c++11标准
  • 归并算法
  • • 全排列逆序对的和
    • 归并算法解决逆序对次数
  • 子集问题
  • 全排序问题
  • 二分查找
  • DFS算法
  • • 加法分解
    • 7段码
    • 水洼数目
    • N皇后问题
    • 2n皇后问题
  • BFS
  • • 迷宫问题
  • DP
  • • 过河马
    • 最长递增子序列
    • • B君的希望
      • 密码脱落
      • 小明爬山
  • 背包问题
  • • 硬币表示
  • 并查集
  • 最小表示算法
  • 最小表示法
  • 其它经典题目
  • • 汉诺塔
    • 印章
    • 异或数列
    • 双向排序
    • 旋转数最大最小数字
    • 希尔排序
    • 快排
    • 找空字符串
    • 插入排序
    • 斐波那契串
    • 串

蓝桥杯算法 有用链接

十大经典排序算法

使用Dev-C++查看数组中的变量值而不是数组地址

小技巧 用变量大小初始的二维数组

#include 
using namespace std;

int m, n;
void Function(void *_map)
{
    int(*map)[n] = (int(*)[n])_map; //强制转换
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    // 请在此输入您的代码
    cin >> m >> n;
    int(*map)[n] = (int(*)[n])malloc(sizeof(int) * m * n); // m*n的二维数组
    //初始化全部为0,注意是按照字节赋值的，因此这里只有赋值0和-1才有用
    memset(map, 0, sizeof(int) * m * n);
    Function(map);
    return 0;
}

求gcd最大公约数

#include 
#include 
/*
最大公约数
 */
using namespace std;
int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return gcd(b, a % b);
}
int main()
{
    // 请在此输入您的代码
    cout << gcd(3, 4) << endl;
    cout << __gcd(3, 4) << endl;
    return 0;
}

对map for_each的遍历

void myPrint(map<int, vector<int> >::reference tmpVal)
{
 vector<int>::iterator it;
 cout<<tmpVal.first<<endl;
 for(it=tmpVal.second.begin(); it!=tmpVal.second.end(); it++)
 {
  cout<<*it<<"-";
 }  
 cout<<endl;
}

二进制输出

#include 
/*
任意进制转换 
 */
using namespace std;
int main()
{
    char radix_arr[1000];
    //转二进制
    int tmp_int = 15;
    //需要转换的数， 目标装载容器， 多少进制
    itoa(tmp_int, radix_arr, 2);
    cout << radix_arr << endl;
}

初始化递增的数组或者容器

#include 
/*
初始化递增的数组或者容器
*/
using namespace std;
void MyPrint(int tmp_val)
{
    cout << tmp_val << " ";
}
int main()
{
    // 请在此输入您的代码
    vector<int> v_tmp(26, 0); //容器
    int *tmp = (int *)malloc(sizeof(int) * 26); //数组
    //起始，结束，增量
    iota(v_tmp.begin(), v_tmp.end(), 0);
    iota(tmp, tmp + 26, 0);

    for_each(v_tmp.begin(), v_tmp.end(), MyPrint);
    cout << endl;
    for_each(tmp, tmp + 26, MyPrint);
    cout << endl;
    return 0;
}

c++分割,按照指定字符分割

int start = 目标字符串.find('目标字符', 0);
int 分割符的数量 = stoi(目标字符串.substr(0, start));
vector<int> realys;
while (分割符的数量--)
{
    int end = 目标字符串 .find('目标字符', start + 1);
    realys.push_back(stoi(目标字符串 .substr(start + 1, end)));
    start = end;
}

求最大最小值

#include 
/*
求容器或者数组中最大最小值
*/
using namespace std;
int arr[] = {1, 2, 6, 5, 3, 9, 7, 4, 5, 6, 4, 5, 6};
vector<int> v = {1, 2, 6, 5, 3, 9, 7, 4, 5, 6, 4, 5, 6};
int main()
{
    //!最大值
    //容器 
    vector<int>::iterator max_it =  max_element(v.begin(), v.end());
    cout << *max_it << endl;
    //数组
    int *max_p = max_element(arr, arr + (sizeof(arr) / sizeof(int)));
    cout << *max_p << endl;
    //!最小值
    //容器 
    vector<int>::iterator min_it =  min_element(v.begin(), v.end());
    cout << *min_it << endl;
    //数组
    int *min_p = min_element(arr, arr + (sizeof(arr) / sizeof(int)));
    cout << *min_p << endl;
    return 0;
}

输出到文件

#include 
#include 
using namespace std;

int main()
{
 ofstream cout("d1.txt");
 cout<<"good example"<<endl;
 return 0;
}

小数的二进制

#include 
/*
小数的二级制
*/
using namespace std;
int main()
{
    string result = "0."; //存储结果
    float point, intpart;
    cin >> point;
    float fracpart = modf(point, &intpart); //分离小数和整数部分
    while (fracpart)                        //小数部分不为0就一直进行下去
    {
        if (fracpart * 2 >= 1) 
        {
            result += "1";
            fracpart = fracpart * 2 - 1; //减去1
        }
        else
        {
            result += "0";
            fracpart = fracpart * 2;
        }
        if (fracpart == 0)
        {
            cout << result << endl;
            return 0;
        }
        if (result.length() > 32)
        {
            cout << result << endl;
            return 0;
        }
    }
    return 0;
}

位运算

• 判断奇偶
  奇数末尾为1， 偶数末尾为0
  待判断数 & 0x01

• 交换两个整数变量的值(不推荐)

• 异或
  相同为0， 不同为1， 可以找不同， 任意数^1都会翻转

• 算有多少个1

  #include 
  /*
  计算有多少个1
  */
  using namespace std;
  int main()
  {
      // 请在此输入您的代码
      int x = 31;
      int cnt = 0;
      char bin[1000] = {0};
      itoa(x, bin, 2);
      cout << bin << endl;
      while (x)
      {
          cnt++;
          x = (x - 1) & x;
      }
      cout << cnt << endl;
      return 0;
  } 
  

• 奇偶交换

  #include 
  /*
  奇偶交换
  */
  using namespace std;
  int main()
  {
      // 请在此输入您的代码
      int a, b, c;
      a = 0b1010;
      // 1010 1010  保留偶数位
      // 0101 0101  保留奇数位
      b = a & 0b10101010;
      c = a & 0b01010101;
      cout << bitset<8>((c << 1) | (b >> 1)) << endl;
      return 0;
  }
  

• 二个相同二进制做不进位加法为0；10个相同10进制做不进位加法为0(k个相同的k进制做不进位加法结果为0

注意事项 scanf和char

使用getchar()吸收回车非常重要

  scanf("%d", &N);
  char *my_char = (char *)malloc(sizeof(char)*N);
  for(int j = 0; j < N; j++)
  {
   getchar(); //吸收回车 
   scanf("%c", &my_char[j]);
  }

devc++中添加c++11标准

归并算法

归并排序算法完全依照了分治模式

• 分解: 将n个元素分成各含n/2个元素的子序列
• 解决：对两个子序列递归地排序；
• 合并：合并两个已排序的子序列以得到结果
  和快排不同:
• 归并的分解较为随意
• 重点是合并

#include 
/*
归并排序
先分再合并，重要在合并上面
*/
int arr[] = {1, 2, 6, 5, 3, 9, 7, 4, 5, 6, 4, 5, 6};

using namespace std;
int length;
void HeBing(int l, int r, int mid)
{
    //复制一个辅助数组
    int *help = (int *)malloc(sizeof(int) * (r-l+1));
    memcpy(help, arr, (r-l+1) * sizeof(int));
    int left = l;
    int right = mid + 1;
    int current = l;
    while (left <= mid && right <= r) //!界限
    {
        if (arr[left] > arr[right])
        {
            help[current] = arr[left];
            left++;
            current++;
        }
        else
        {
            help[current] = arr[right];
            right++;
            current++;
        }
    }
    //左边的没有走完，就要复制过去
    while (left <= mid)
    {
        help[current] = arr[left];
        left++;
        current++;
    }
    //赋值回去
    memcpy(arr, help, (r-l+1) * sizeof(int));
}

void GuiBing(int l, int r)
{
    int mid = l + ((r - l) >> 1);
    if (l < r) //界限
    {
        GuiBing(l, mid); //左边
        GuiBing(mid + 1, r);
        //分完了就合并
        HeBing(l, r, mid);
    }
}

int main()
{
    // 请在此输入您的代码
    length = (int)sizeof(arr) / (int)sizeof(int);
    GuiBing(0, length - 1);
    return 0;
}

全排列逆序对的和

由1,2,3…n共生成n!个排列的逆序数之和为: 1 2 × n ! × C n 2 \frac{1}{2}\times{n!}\times{C_n^2} 21​×n!×Cn2​
全排列有 n ! n! n!个情况， 那么在一种情况中， 随便选两个数有 C n 2 \mathrm{C}_n^2 Cn2​中情况， 那么是逆序的概率为 1 2 \frac 1 2 21​

归并算法解决逆序对次数

重点是当左边大于右边的时候, cnt += mid - left + 1

#include 
using namespace std;
vector<int> my_vector;
int cnt = 0;

void MyMerge(vector<int> &v, int l, int r, int mid)
{
    //复制
    vector<int> help = v;
    int left = l, right = mid + 1, current = l;
    while (left <= mid && right <= r)
    {
        if (help[left] <= help[right])
        {
            v[current++] = help[left++];
        }
        else
        {
            cnt += mid - left + 1;
            v[current++] = help[right++];
        }
    }
    while (left <= mid)
    {
        v[current++] = help[left++];
    }
}
void MergeSort(vector<int> &_v, int l, int r)
{
    if (l < r)
    {
        int mid = l + ((r - l) >> 1);
        MergeSort(_v, l, mid);
        MergeSort(_v, mid + 1, r);
        MyMerge(_v, l, r, mid);
    }
}

int main()
{
    // 请在此输入您的代码
    int n;
    cin >> n;
    for (int i = n; i >=0; i--)
    {
        my_vector.push_back(i);
    }
    MergeSort(my_vector, 0, my_vector.size() - 1);
    cout << cnt << endl;
    return 0;
}

子集问题

• 迭代方法
• 递推方法
• 二进制方法

#include 
/*
子集
*/
using namespace std;
string s = "ABCD";
//!注意迭代法和递推法如果在集合有重复元素下，用set去重
//迭代法,在排序后，是字典序的
vector<string> SubSet_Iteration(int n)
{
    vector<string> tmp_string;
    if (n == 0) //最开始的就是什么都不加
    {
        string ss = "";
        tmp_string.push_back(ss);
        return tmp_string;
    }
    //获取上一个的所有结果，然后在结果种，选择插入当前值，或者不插入值
    vector<string> subset = SubSet_Iteration(n - 1);
    for (auto it = subset.begin(); it != subset.end(); it++)
    {
        tmp_string.push_back(*it);            //不加
        tmp_string.push_back(*it + s[n - 1]); //加
    }
    return tmp_string;
}
//递推法
vector<string> SubSet_Recursion(int n)
{
    vector<string> v_tmp_string; //否则
    string tmp_string = "";
    v_tmp_string.push_back(tmp_string);
    while (n)
    {
        vector<string> v1_tmp_string;
        for (auto it = v_tmp_string.begin(); it != v_tmp_string.end(); it++)
        {
            v1_tmp_string.push_back(*it);            //不加
            v1_tmp_string.push_back(*it + s[n - 1]); //加
        }
        v_tmp_string = v1_tmp_string; //赋值回去
        n--;
    }
    return v_tmp_string;
}
//二进制法
vector<string> SubSet_Bin(int n)
{
    vector<string> v_tmp_string;
    int total_cnt = 1 << n;
    for (int i = 0; i < total_cnt; i++)
    {
        int cnt = n;//最多n位
        string tmp_string;
        while (cnt)
        {
            cnt--;
            if(((i>>cnt) & (0x1)) == 1) //这一位为一的话记录
            {
                tmp_string.push_back(s[cnt]); //记录这一位
            }
        }
        v_tmp_string.push_back(tmp_string);
    }
    return v_tmp_string;
}
void MyPrint(string s1)
{
    cout << s1 << " ";
}
int main()
{
    // 请在此输入您的代码
    //使用迭代的方式
    vector<string> result = SubSet_Bin(s.length()); //这里的长度是length
    for_each(result.begin(), result.end(), MyPrint);
    cout << endl;
    return 0;
}

全排序问题

C++ STL中 next_permutation函数的用法

//带去重的
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> vv;
        dfs(nums, 0, vv);
        return vv;
    }
    void dfs(vector<int>& nums, int i, vector<vector<int>>& vv)
    {
        int length = (int)nums.size();
        if(i == length)
        {
            vv.push_back(nums);
            return;
        }
        for(int j = i; j < length; j++)
        {
            sort(nums.begin()+i, nums.end());
            if((j != i) && nums[j] == nums[j-1]) continue;
            swap(nums[i], nums[j]);
            dfs(nums, i+1, vv);
            swap(nums[i], nums[j]);
        }
    }
};

有字典序

class Solution {
    static constexpr array factorial {1,1,2,6,24,120,720,5040,40320};
public:
    string getPermutation(int n, int k) {
        vector nums(n, 0);
        iota(begin(nums), end(nums), 1); //递增序列
        string ret;
        --k; //因为我们下标是从0开始的，而求的是1开始的
        for (int i = n - 1; i != -1; --i) {
            auto it = begin(nums) + k / factorial[i];
            ret += ('0' + *it);
            nums.erase(it);
            k %= factorial[i];
        }
        return ret;
    }
};

#include 
/*
全排列问题
*/
using namespace std;
string aggregation = "ABC";
//迭代方法
void Permutation_Iterator(int cnt, int n)
{
    if (cnt == n)
    {
        cout << aggregation << endl;
    }
    for (int i = cnt; i < n; i++)
    {
        swap(aggregation[i], aggregation[cnt]); //交换
        Permutation_Iterator(cnt + 1, n);
        swap(aggregation[i], aggregation[cnt]); //交换回来
    }
}
//前缀法
void Permutation_Prefix(string prefix, int n)
{
    if (prefix.length() == n)
    {
        cout << prefix << endl;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        //如果当前字符还没有被选完
        if (count(prefix.begin(), prefix.end(), aggregation[i]) <
            count(aggregation.begin(), aggregation.end(), aggregation[i]))
        {
            prefix.push_back(aggregation[i]); //加入进入
            Permutation_Prefix(prefix, n);
            prefix.pop_back(); //去掉刚才加入的
        }
    }
}
//插空法
// A
// AB BA
// CAB ACB ABC   CBA BCA BAC //插空 */
int main()
{
    // 请在此输入您的代码
    // Permutation_Iterator(0, aggregation.length());
    string prefix;
    Permutation_Prefix(prefix, aggregation.length());
    return 0;
}

二分查找

#include 
/*
二分查找, 需要保证有序!
*/
using namespace std;
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

int BinarySearch(int l, int r, int target)
{
    int mid = l + ((r - l) >> 1);
    if (l > r)
    {
        return 9999;
    }
    if (arr[mid] == target)
    {
        return mid;
    }
    if (arr[mid] >= target)
    {
        return BinarySearch(l, mid - 1, target); //选择左边一半
    }
    else
    {
        return BinarySearch(mid + 1, r, target); //选择右边一半 
    }
}

int main()
{
    cout << BinarySearch(0, 9, 0) << endl;
    return 0;
}

DFS算法 加法分解

加法分解方案

#include 
/*
问题描述
　　给一个正整数n，输出它所有的正整数加法的分解方法。

其中交换加数的位置视为不同的分解方案。

按字典序输出。

特别地，不分解也视为一种分解方案。


输入格式
　　输入共一行一个正整数n。


输出格式
　　输出若干行，为n的所有正整数加法分解方法。

每种方案输出一行。

对于一种方案，先输出n，再输出一个“=”。

然后输出分解的各数，不同的数之间用“+”连接。


样例输入
5
样例输出
5=1+1+1+1+1
5=1+1+1+2
5=1+1+2+1
5=1+1+3
5=1+2+1+1
5=1+2+2
5=1+3+1
5=1+4
5=2+1+1+1
5=2+1+2
5=2+2+1
5=2+3
5=3+1+1
5=3+2
5=4+1
5=5
数据规模及限制
　　对于100的数据，n为正整数且n≤15。


*/
using namespace std;
int sum;
void dfs1(int n, int count, int *p)
{

    if (n == 0)
    { //递归基，到叶子结点时输出结果
        cout << sum << "=";
        for (int i = 0; i < count; i++)
            if (i == count - 1)
                cout << p[i] << endl;
            else
                cout << p[i] << "+";
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        // cout << count << "         " << i << endl;
        p[count] = i;
        dfs1(n - i, count + 1, p);
    }
    return;
}

int main()
{
    // 请在此输入您的代码
    int n;
    cin >> n;
    sum = n;
    int *p = new int[n];
    dfs1(n, 0, p);
    return 0;
}

7段码

#include 
using namespace std;
//邻接矩阵 
int route[][7] = 
{
 0, 1, 0, 0, 0, 1, 0,
 1, 0, 1, 0, 0, 0, 1,
 0, 1, 0, 1, 0, 0, 1, 
 0, 0, 1, 0, 1, 0, 0, 
 0, 0, 0, 1, 0, 1, 1, 
 1, 0, 0, 0, 1, 0, 1, 
 0, 1, 1, 0, 1, 1, 0
};
int binary[8];
int visited[8];
void dfs(int i) //从某个顶点开始 
{
 for(int j = 0; j < 8; j++)
 {
  //选择一个可以走的路(我有这个数码管，并且该路可以走) 
  //并且没有被访问过的点(数码管)走
  if(binary[j] == 1 && route[i][j] == 1 && visited[j] == 0)
  {
   //选中这个路，那么这个路就被访问了 
   visited[j] = 1; 
   //然后开始继续往下
   dfs(j); 
  }
 }
 return; 
}
bool check(void)
{
 for(int i = 0; i < 8; i++)
 {
  //如果出现一个我含有的数码管，但是这个数码管没有走到，那就错了 
  if(binary[i] && (visited[i] == 0))
   return false;
 } 
 return true;
}
int main()
{
 //首先是有2^7种可能
 //开始的
 int ans = 127; 
 for(int i = 1; i < 128; i++)
 {
  //先转化为二进制  
  memset(binary, 0, sizeof(binary)); //二进制清空全为0
  memset(visited, 0, sizeof(visited)); //访问过的点清零 
  int k = 0;
  int tmpVal = i;
  while(tmpVal)
  {
   binary[k++] = tmpVal%2;
   tmpVal /= 2;
  }
  //然后从一个顶点开始走
  k = 0; 
  while(binary[k++] == 0); //找到一个不为0的顶点,下一句中k-1就是选中的顶点
  //然后开始深搜，每结束一次 
  dfs(k-1); 
  //搜索完了，那么如果二进制所有为1的，全部都在访问的点中，则就算一个成功
  bool ok = check();
  if(ok == 0)
   ans--;
  /* 
  for(int m = 0; m < 8; m++)
  {
   cout<
 } 
 //需要加上7个单独的 
 cout<<ans+7<<endl;
 return 0;
}

水洼数目

#include 
/*
M = 7 , N = 12
7x12
............
W.W...WWWWWW
.WW..WWWWWWW
WWW..W......
W...W.......
.......WWW..
WWWWWW......
*/

using namespace std;
int M, N;
void dfs(char *suitang, int i, int j)
{
    //把当前水塘清空
    suitang[i * N + j] = '.'; //清理水塘
    //对八个方向进行深搜
    for (int k = -1; k <= 1; k++)
    {
        for (int l = -1; l <= 1; l++)
        {
            if (k == 0 && l == 0) //略过自己那个点
                continue;
            //八个地方拓展
            else if (i + k >= 0 && i + k <= M - 1 && j + l >= 0 && j + l <= N - 1)
            {
                if (suitang[(i + k) * N + (j + l)] == 'W')
                    dfs(suitang, i + k, j + l);
            }
        }
    }
}
int main()
{
    // 请在此输入您的代码
    cin >> M >> N;
    char *suitang = (char *)malloc(M * N * sizeof(char));
    for (int i = 0; i < M; i++)
    {
        string tmpval;
        cin >> tmpval;
        memcpy(suitang + (i * N), tmpval.c_str(), N);
    }
    //进行扫描
    int cnt = 0;
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (suitang[i * N + j] == 'W') //如果找到一个水塘
            {
                dfs(suitang, i, j);
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

N皇后问题

#include 
using namespace std;
int N;
int cnt = 0;
void DFS(int row, int *v)
{
 if(row == N)
 {
  cnt++;
  return;
 }
 //新的一行来了 
 for(int col = 0; col < N; col++)//选择一列 
 {
  bool ok = true;
  for(int j = 0; j < row; j++)//遍历之前所有行的情况 
  {
   //不能在可攻击范围内 
   if(v[j] == col || v[j]-j == col-row || v[j]+j == col+row)
   {
    ok = false;
    break;  
   }
  }
  if(ok == true)//如果可以放下 
  {
   v[row] = col; //标记此行的占用情况 
   DFS(row+1, v);
   //不用回溯 
  }
  
 }
}
int  main()
{
 cin >> N;
 int *v = (int *)malloc(sizeof(int)*N);
 memset(v, 0, sizeof(int)*N);
 DFS(0, v);
 cout<<cnt<<endl;  
 return 0;
}

2n皇后问题

#include 
/*
问题描述
　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。

现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。

问总共有多少种放法？n小于等于8。


输入格式
　　输入的第一行为一个整数n，表示棋盘的大小。


　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。


输出格式
　　输出一个整数，表示总共有多少种放法。


样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0
*/
using namespace std;
int N, cnt = 0;
void dfs1(void *_map, void *_v1, void *_v2, int row)
{
    int(*map)[N] = (int(*)[N])_map;
    int *v1 = (int *)_v1;
    int *v2 = (int *)_v2;
    if (row == N)
    {
        cnt++;
        return;
    }
    for (int col = 0; col < N; col++) //对每一个可行的列进行遍历
    {
        bool ok = true;
        if (map[row][col] == 1 && v1[row] != col) //如果可以放，并且没有黑皇后
        {
            for (int i = 0; i < row; i++) //遍历是否能够放下
            {
                if (v2[i] == col || i + v2[i] == row + col || i - v2[i] == row - col) //判断是否满足条件黑
                {
                    ok = false;
                    break;
                }
            }
            if (ok == true) //如果满足可以
            {
                v2[row] = col;
                dfs1(map, v1, v2, row + 1);
            }
        }
    }
}
void dfs(void *_map, void *_v1, void *_v2, int row)
{
    int(*map)[N] = (int(*)[N])_map;
    int *v1 = (int *)_v1;
    int *v2 = (int *)_v2;
    if (row == N)
    {
        //开始白皇后的放置
        dfs1(map, v1, v2, 0);
        return;
    }
    for (int col = 0; col < N; col++) //对每一个可行的列进行遍历
    {
        if (map[row][col] == 1) //如果可以放的话, 不用考虑白皇后
        {
            bool ok = true;
            for (int i = 0; i < row; i++) //遍历是否能够放下
            {
                if (v1[i] == col || i + v1[i] == row + col || i - v1[i] == row - col) //判断是否满足条件黑
                {
                    ok = false;
                    break;
                }
            }
            if (ok == true) //如果满足可以
            {
                v1[row] = col;
                dfs(map, v1, v2, row + 1);
            }
        }
    }
}
int main()
{
    // 请在此输入您的代码
    cin >> N;
    int(*map)[N] = (int(*)[N])malloc(N * N * sizeof(int));
    int *v1 = (int *)malloc(N * sizeof(int));
    int *v2 = (int *)malloc(N * sizeof(int));
    memset(v1, 0, sizeof(int) * N); //访问一
    memset(v2, 0, sizeof(int) * N); //访问二
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    dfs(map, v1, v2, 0);
    cout << cnt << endl;
    return 0;
}

BFS 迷宫问题

#include 
/*
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可以通行的地方。


010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。



对于上面的迷宫，从入口开始，可以按 DRRURRDDDR 的顺序通过迷宫， 一共 1010 步。

其中 D、U、L、RD、U、L、R
分别表示向下、向上、向左、向右走。

 对于下面这个更复杂的迷宫（3030 行 5050
列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。



请注意在字典序中 D
using namespace std;
int M, N;

int dir[][2] = {1, 0, 0, -1, 0, 1, -1, 0};
char ch[4] = {'D', 'L', 'R', 'U'};
struct point
{
    int x, y;
    string road;
    point(int a, int b)
    {
        x = a;
        y = b;
    }
};

void Bfs(void *_m, void *_v)
{
    char(*m)[N] = (char(*)[N])_m;
    int(*v)[N] = (int(*)[N])_v;
    //初始化
    queue<point> q;
    point p(0, 0);
    p.road = "";
    q.push(p);
    v[0][0] = 1;
    while (!q.empty()) //如果还有路要走
    {
        point t = q.front(); //拿出一个点‘
        q.pop();
        if (t.x == M - 1 && t.y == N - 1) //如果走到了终点
        {
            cout << t.road << endl; //最先到达的一定是最短的
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            int dx = t.x + dir[i][0];
            int dy = t.y + dir[i][1];
            if (dx >= 0 && dx < M && dy >= 0 && dy < N) //!边界又错了
            {
                if (m[dx][dy] == '0' && !v[dx][dy]) //如果可以走，并且没有被访问过
                {
                    point tt(dx, dy);
                    tt.road = t.road + ch[i]; //记录路径
                    q.push(tt);
                    v[dx][dy] = 1;
                }
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    cin >> M >> N;
    char(*p)[N] = (char(*)[N])malloc(sizeof(char) * M * N);
    int(*v)[N] = (int(*)[N])malloc(sizeof(int) * M * N);
    for (int i = 0; i < M; i++)
    {
        string tmpval;
        cin >> tmpval;
        memcpy(p[i], tmpval.c_str(), N);
    }
    memset(v, 0, sizeof(int) * M * N);
    Bfs(p, v);
    return 0;
}

DP 过河马

#include 
/*
在那个过河卒逃过了马的控制以超级超级多的走法走到了终点之后，这匹马表示它不开心了....于是，终于有一天，它也过河了!
由于过河马积累了许多的怨念，所以这次它过了河之后，再也没有什么东西可以限制它，它可以自由自在的在棋盘上驰骋。

一开始，它是在一个n行
m列棋盘的左下角
(1.1)的位置，它想要走到终点右上角(n,
m)的位置。

而众所周知，马是要走日子格的。

可是这匹马在积累了这么多怨念之后，它再也不想走回头路——也就是说，它只会朝向上的方向跳，不会朝向下的方向跳。


那么，这匹马它也想知道，它想从起点跳到终点，一共有多少种走法呢?
输入格式
第一行两个数n，m，表示一个n行m列的棋盘，马最初是在左下角(1,1)的位置，终点在右上角 (n，m)的位置。


输出格式
输出有一行，一个数表示走法数。

由于答案可能很大，所以输出答案除以1000000007所得的余数即可。



样例输入
44
样例输出
2
数据规模和约定
n<=100,m<=100

*/
int M, N;
using namespace std;
long long dp[102][102] = {0};
int GuoHe(int m, int n)
{
    if (m == 1 && n == 1)
        return 1;
    if (m <= 0 || n <= 0 || m > M || n > N)
        return 0;
    return GuoHe(m - 2, n - 1) % 1000000007 + GuoHe(m - 1, n - 2) % 1000000007 + GuoHe(m - 2, n + 1) % 1000000007 +
           GuoHe(m - 1, n + 2) % 1000000007;
}

int Dp(int m, int n)
{
    for (int i = 0; i <= m; i++)
    {
        for (int h = 0; h <= n; h++)
        {
            if (i - 2 >= 1 && h - 1 >= 1)
            {
                dp[i][h] += dp[i - 2][h - 1];
            }
            if (i - 2 >= 1 && h - 2 >= 1)
            {
                dp[i][h] += dp[i - 1][h - 2];
            }
            if (i - 2 >= 1 && h + 1 >= 1)
            {
                dp[i][h] += dp[i - 2][h + 1];
            }
            if (i - 1 >= 1 && h + 2 >= 1)
            {
                dp[i][h] += dp[i - 1][h + 2];
            }
            dp[i][h] %= 1000000007;
        }
    }
    return dp[m][n];
}

int main()
{
    int m, n;
    cin >> m >> n;
    M = m;
    N = n;
    // cout << GuoHe(m, n) << endl;
    //初始化dp数组
    dp[1][1] = 0;
    dp[2][3] = 1;
    dp[3][2] = 1;
    cout << Dp(m, n) << endl;
    return 0;
}

最长递增子序列

最长递增子序列

B君的希望

#include 
/*
问题描述
　　你有个同学叫B君，他早听闻祖国河山秀丽，列了一张所有可能爬的山的高度表，因“人往高处走”的说法，所以他希望要爬的山按照表上的顺序，并且爬的每一座山都要比前一座高，爬的山数最多，请贵系的你帮他解决这个问题。

(cin,cout很坑)
输入格式
　　输入第一行为num(1~1000)和maxHeight(1~8848)，代表山的个数和最大高度
　　输入第二行有num个整数，代表表上每座山的高度height(1~maxHeight)
输出格式
　　输出只有一个数，为符合要求的最大爬山数
样例输入
10 10
8 6 8 5 9 5 2 7 3 6 3 4
样例输出
3
样例输入
10 20
8 19 9 10 3 3 15 3 10 6
样例输出
4
数据规模和约定
　　num(1~1000)，maxHeight(1~8848)，height(1~maxHeight)，都是正整数
*/
using namespace std;
int num, max_height;
vector<int> v, v1;
set<int> set1;
int LCS(vector<int> v, vector<int> v1, void *_visit, void *_dp)
{
    int(*visit)[num + 1] = (int(*)[num + 1]) _visit;
    int(*dp)[num + 1] = (int(*)[num + 1]) _dp; //!这里传参传成_visit了
    for (int i = 1; i <= v.size(); i++)
    {
        for (int j = 1; j <= v.size(); j++)
        {
            int vi = i - 1;
            int vj = j - 1;
            if (v[vi] == v1[vj]) //如果相等
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                visit[i][j] = 0;
            }
            else if (dp[i - 1][j] >= dp[i][j - 1])
            {
                dp[i][j] = dp[i - 1][j]; //这种写法，就是正着来
                visit[i][j] = 1;
            }
            else
            {
                dp[i][j] = dp[i][j - 1];
                visit[i][j] = -1;
            }
        }
    }
    return dp[num][num];
}
void PrintLCS(vector<int> v, vector<int> v1, void *_visit, void *_dp, int x, int y)
{
    int(*visit)[num + 1] = (int(*)[num + 1]) _visit;
    int(*dp)[num + 1] = (int(*)[num + 1]) _dp;
    if (x == 0 || y == 0)
        return;
    if (visit[x][y] == 0)
    {
        PrintLCS(v, v1, visit, dp, x - 1, y - 1);
        // cout << v[x - 1] << " ";
        set1.insert(v[x - 1]); //因为这里标号从0开始
    }
    else if (visit[x][y] == 1)
    {
        PrintLCS(v, v1, visit, dp, x - 1, y);
    }
    else
    {
        PrintLCS(v, v1, visit, dp, x, y - 1);
    }
}
int main()
{
    // 请在此输入您的代码
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        int tmpval;
        cin >> tmpval;
        v.push_back(tmpval);
    }
    v1 = v;
    sort(v1.begin(), v1.end()); //默认升序
    int init_num = num + 1;
    int(*visit)[init_num] = (int(*)[init_num])malloc(sizeof(int) * init_num * init_num);
    int(*dp)[init_num] = (int(*)[init_num])malloc(sizeof(int) * init_num * init_num);
    memset(visit, 0, sizeof(int) * init_num * init_num);
    memset(dp, 0, sizeof(int) * init_num * init_num);
    // cout << LCS(v, v1, visit, dp) << endl;
    LCS(v, v1, visit, dp);
    PrintLCS(v, v1, visit, dp, num, num);
    cout << set1.size() << endl;
    // cout << "---------" << endl;
    // PrintLCS(v, v1, visit, dp, num, num);
    // // cout << endl;
    // for (int i = 0; i < init_num; i++)
    // {
    //     for (int j = 0; j < init_num; j++)
    //     {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    return 0;
}

密码脱落

#include 
/*
　你的任务是：
　　给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。


　　输入一行，表示现在看到的密码串（长度不大于1000）
　　要求输出一个正整数，表示至少脱落了多少个种子。


　　例如，输入：
　　ABCBA
　　则程序应该输出：
　　0
　　再例如，输入：
　　ABECDCBABC
　　则程序应该输出：
　　3
　　资源约定：
　　峰值内存消耗 < 256M
　　CPU消耗 < 1000ms
*/
using namespace std;
//只记录长度算法
// int LCS(string rev_s, string s, void *v)
// {
//     int length = s.length();
//     int(*dp)[length + 1] = (int(*)[length + 1]) v; //!这里忘了+1导致错误
//     for (int i = 0; i < length; i++) //行
//     {
//         for (int j = 0; j < length; j++)//列
//         {
//             if (s[j] == rev_s[i])
//             {
//                 dp[i + 1][j + 1] = dp[i][j] + 1;
//             }
//             else
//                 dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
//             // cout << dp[i + 1][j + 1];
//         }
//         // cout << endl;
//     }
//     return dp[length][length];
// }
int LCS(string rev_s, string s, void *v, void *record)
{
    int length = s.length();
    int(*dp)[length + 1] = (int(*)[length + 1]) v;     //!这里忘了+1导致错误
    int(*b)[length + 1] = (int(*)[length + 1]) record; //!这里忘了+1导致错误
    for (int i = 0; i < length; i++)                   //行
    {
        for (int j = 0; j < length; j++) //列
        {
            if (s[i] == rev_s[j]) //谁是行,谁是列,注意,影响后面输出
            {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                b[i + 1][j + 1] = 0;
            }
            else if (dp[i + 1][j] >= dp[i][j + 1])
            {
                dp[i + 1][j + 1] = dp[i + 1][j];
                b[i + 1][j + 1] = 1;
            }
            else
            {
                dp[i + 1][j + 1] = dp[i][j + 1];
                b[i + 1][j + 1] = -1;
            }
        }
    }
}
void PrintLCS(string rev_s, string s, void *v, void *record, int i, int j)
{
    int length = s.length();
    int(*b)[length + 1] = (int(*)[length + 1]) record; //!这里忘了+1导致错误
    if (i == 0 || j == 0)
    {
        return;
    }
    if (b[i][j] == 0)
    {
        PrintLCS(rev_s, s, v, b, i - 1, j - 1);
        cout << s[i - 1]; //!输出的值肯定是i-1，因为是从0开始, 注意这里必须是行是行的，列是列的
        //!或者 // cout << rev_s[j - 1];
    }
    else if (b[i][j] == 1)
    {
        PrintLCS(rev_s, s, v, b, i, j - 1); //这里反着来，之前是i+1使之为1，那么这里就j-1
    }
    else
    {
        PrintLCS(rev_s, s, v, b, i - 1, j);
    }
}

int main()
{
    // 请在此输入您的代码
    string tmp_string, rev_string;
    cin >> tmp_string;
    rev_string = tmp_string;
    // reverse(rev_string.begin(), rev_string.end());
    sort(rev_string.begin(), rev_string.end());
    // int *v = (int(*))malloc(tmp_string.length() * sizeof(int));
    // memset(v, 0, sizeof(int) * tmp_string.length());
    int length = (int)tmp_string.length();
    int(*v)[length + 1] =
        (int(*)[length + 1]) malloc((length + 1) * (length + 1) * sizeof(int)); //!这里忘了*sizeof(int)导致不能正常退出
    int(*record)[length + 1] = (int(*)[length + 1]) malloc((length + 1) * (length + 1) * sizeof(int));
    memset(v, 0, sizeof(int) * (length + 1) * (length + 1));
    memset(record, 0, sizeof(int) * (length + 1) * (length + 1));
    // cout << LCS(rev_string, tmp_string, v) << endl;
    int lcs_length = LCS(rev_string, tmp_string, v, record);
    // cout << length - lcs_length << endl;
    // cout << "            " << endl;
    for (int i = 0; i < length + 1; i++)
    {
        for (int j = 0; j < length + 1; j++)
        {
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 0; i < length + 1; i++)
    {
        for (int j = 0; j < length + 1; j++)
        {
            cout << record[i][j] << "\t";
        }
        cout << endl;
    }
    PrintLCS(rev_string, tmp_string, v, record, length, length);
    return 0;
}

小明爬山

#include 
/*
问题描述
　　你有个同学叫小明，他早听闻祖国河山秀丽，于是有一个爬山的计划，并列了一张所有山的高度表，而又因“人往高处走”的说法，所以他希望爬的每一座山都比前一座要高，并且不能改变山的高度表上的顺序，爬的山数还要最多，请贵系的你帮他解决这个问题。


输入格式
　　输入第一行为num，代表山的个数
　　输入第二行有num个整数，代表每座山的高度
输出格式
　　输出只有一个数，为符合要求的最大爬山数
样例输入
10
1 3 5 7 9 2 4 6 8 10
样例输出
6
样例输入
10
1 3 2 7 5 4 5 6 10 11
样例输出
7
数据规模和约定
　　对于100%的数据，num <= 100000，高度<=10000。


*/
using namespace std;
int N;
int main()
{
    // 请在此输入您的代码
    cin >> N;
    int *map = (int *)malloc(sizeof(int) * N);
    memset(map, 0, sizeof(int) * N);
    int *dp = (int *)malloc(sizeof(int) * N);
    memset(dp, 0, sizeof(int) * N);
    int sum_max = 0;
    dp[0] = 1;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &map[i]);
    }
    for (int i = 1; i < N; i++)
    {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (map[i] > map[j]) //如果大于
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        if (dp[i] >= sum_max)
        {
            sum_max = dp[i];
        }
    }
    cout << sum_max << endl;
    return 0;
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int length = nums.size();
        int *dp = (int*)malloc(sizeof(int)*length*length);
        memset(dp, 0, sizeof(int)*length*length);
        for(int i = 0; i < length; i++)
        {
            dp[i] = 1;
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    dp[i] = max(dp[i], dp[j]+1);
                    if(sum_max <= dp[i])
                        sum_max = dp[i];
                }
            }
        }
        return sum_max;
    }
};

背包问题 硬币表示

#include 
/*
有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少组合可以组成n分钱
//也可以用二维矩阵
 0 1 2 3 4 5 6 7 8 9 10 ....
1 
5
10
25
*/
int coins[] = {1, 5, 10, 25};
//递推
int countWaysCore(int n, int cur) //n表示目标值， cur表示当前面值
{
    if(cur == 0) return 1; //只剩下最小面值， 那么只有1种方式
    int res = 0;
    for (int i = 0; i * coins[cur] <= n; i++) //通过最大面值选择有几种情况, 限制了n不会小于0
    {
        int shengyu = n - i * coins[cur];
        res += countWaysCore(shengyu, cur-1); 
    }
    return res;
}
using namespace std;
int main()
{
    // 请在此输入您的代码
    cout << countWaysCore(24, 3) << endl;
    return 0;
} 

并查集

// 题目描述
// 给定一个长度为 N 的数组 A = [A1, A2, · · · AN ]，数组中有可能有重复出现 的整数。


// 现在小明要按以下方法将其修改为没有重复整数的数组。

小明会依次修改 A2,A3,··· ,AN。


// 当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。

如果出现过，则 小明会给 Ai 加上 1 ;如果新的 Ai
// 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。


// 当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。

 现在给定初始的 A 数组，请你计算出最终的 A 数组
// 输入
// 第一行包含一个整数 N。

 第二行包含N个整数A1,A2,··· ,AN
// 对于 80% 的评测用例，1 ≤ N ≤ 10000。


// 对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ Ai ≤ 1000000。


// 输出
// 输出N个整数，依次是最终的A1,A2,··· ,AN。


// 样例输入
// 5
// 2 1 1 3 4
// 样例输出
// 2 1 3 4 5
// visited[x]= k记录访问x的次数，那么它后面的k个数也一定被访问过了，所以直接对x+k，将x调到x+k的位置在进行判断是否被访问了
//参考https://blog.csdn.net/weixin_44566432/article/details/115611171

#define __STDC_LIMIT_MACROS
#include 
#include 
#include 
#include 
using namespace std;

int visited[100055] = {0};
vector<int> v;
void myPrint(int tmpVal)
{
    cout << tmpVal << " ";
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int tmpVal;
        cin >> tmpVal;
        //判断这个数曾经是否访问过
        while (visited[tmpVal] != 0) //如果被访问过
        {
            int mid = tmpVal;          //记录现在的位置
            tmpVal += visited[tmpVal]; //位置跳到被访问次数后
            visited[mid]++;            //之前记录的位置被访问所以+1
        }
        visited[tmpVal]++; //到这里都是没有被访问的地方了,首次到这里就算访问一次了
        v.push_back(tmpVal);
    }
    for_each(v.begin(), v.end(), myPrint);
    cout << endl;
    return 0;
}

最小表示算法 最小表示法

最小表示法

其它经典题目 汉诺塔

#include 
using namespace std;
void hlt(int N, string from, string to, string help) 
{
    if(N == 1)
    {
        cout<<"move " << N << " from "<< from << " to " << to<<endl;
    }
    else
    {
        hlt(N-1, from, help, to);
        cout<<"move " << N << " from "<< from << " to " << to<<endl;
        hlt(N-1, help, to, from);
    }
}
int main()
{
    string a = "a", b = "b", c = "c";
    hlt(6,a, b, c);
    return 0;
}

印章

#include 
/*
问题描述
共有n种图案的印章，每种图案的出现概率相同。

小A买了m张印章，求小A集齐n种印章的概率。


输入格式
一行两个正整数n和m
输出格式
—个实数P表示答案,保留4位小数。


样例输入
2 3
样例输出
0.7500
*/
using namespace std; 
double dp[30][30];
int main(void)
{
 int n,m;
 cin>>n>>m;
 double p=1.0/n;
 memset(dp,0,sizeof(dp)); 
 for(int i=1;i<=m;i++)//i张印章 
 {
  for(int j=1;j<=n;j++)//j种图案 
  {
   if(i<j)//不可能凑齐 
   {
    dp[i][j]=0;
   }
   if(j==1)//j只要所有图案中的一种就可以了，所以我们(1/n)^i还要再乘n，就是p^i-1 
   {
    dp[i][j]=pow(p,i-1);
   }
   else//买了i张凑齐j种，第i张 要么和之前凑齐的一样，要么不一样 
   {
    dp[i][j]=dp[i-1][j]*(j*p)+dp[i-1][j-1]*(n-j+1)*p;  
                //凑齐了j种的，那么就是重复前面的j种， p为概率
                //没有凑齐j种，只是凑齐了j-1种 那么就是需要(n-(j-1))*p
   }
   } 
   
 } 
 printf("%.4lf\n",dp[m][n]);
 return 0;
} 

异或数列

#include 
/*
Alice和 Bob正在玩一个异或数列的游戏。

初始时，Alice和
Bob分别有一个整数α和b，初始值均为0。

有一个给定的长度为n的公共数列X,X2,… . ,Xn。

 Alice和
Bob轮流 *** 作，Alice先手，每步可以在以下两种选项中选一种:选项1:从数列中选一个X;给Alice 的数异或上，或者说令α变为a
eX;。

(其中e表示按位异或) 选项2:从数列中选一个X;给 Bob 的数异或上，或者说令b变为b
的X;。

每个数X;都只能用一次，当所有X;均被使用后（n轮后〉游戏结束。

游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。


现在双方都足够聪明，都采用最优策略，请问谁能获胜?

*/
using namespace std;
int N;
#define M 23
int num[M];
void MyPrint(int tmp_val)
{
    cout << tmp_val;
}
void pre(long long a)
{
    int cnt = 0;
    while (a)
    {
        if ((a & 1) == 1)
        {
            num[cnt]++;
        }
        cnt++;
        a >>= 1;
    }
}
int main()
{
    // 请在此输入您的代码
    cin >> N; // N组数据
    for (int j = 0; j < N; j++)
    {
        int tmp_cnt, sum = 0;
        cin >> tmp_cnt;
        memset(num, 0, sizeof(int) * M);
        for (int i = 0; i < tmp_cnt; i++) //读取所有数据
        {
            int tmp_value;
            cin >> tmp_value;
            pre(tmp_value);
            sum ^= tmp_value;
        }
        if (sum == 0)
        {
            cout << 0 << endl;
        }
        else
        {
            for (int i = 20; i >= 0; i--)
            {
                if (num[i] == 1)
                {
                    cout << 1 << endl;
                    break;
                }
                else if ((num[i] & 1) == 1) //如果1是是奇数
                {
                    if ((tmp_cnt & 1) == 1) //如果0的个数是偶数,则先手赢
                    {
                        cout << 1 << endl;
                        break;
                    }
                    else
                    {
                        cout << -1 << endl; //如果0的个数是奇数， 后手赢
                        break;
                    }
                }
            }
        }
    }

    return 0;
}

双向排序

蓝桥杯2021A组——双向排序

#include 
/*
0降序, a1-aq降序
1升序  aq-an升序
 */
using namespace std;
vector<int> v;
typedef struct info
{
    int a;
    int b;
} t_info;
typedef struct nn
{
    int first;
    int second;
}
t_new;
vector<t_info> infos;
vector<t_new> stk;
void MyPrint(int i)
{
    cout << i << " ";
}
int main()
{
    int m, n;
    cin >> n >> m; // n序列长度, m *** 作次数
    for (int i = 1; i < n + 1; i++)
    {
        v.push_back(i);
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        t_info tmpVal;
        tmpVal.a = a;
        tmpVal.b = b;
        infos.push_back(tmpVal);
    }
    for (vector<t_info>::iterator i = infos.begin(); i < infos.end(); i++)
    {
        if (i->a == 0) //降序
        {
            //第一次压缩, 连续的0，取范围大的
            if (stk.size() > 0 && stk.back().first == 0)
            {
                i->b = max(i->b, stk.back().second);
                stk.pop_back();
            }
            while (stk.size() >= 2 && (stk.end() - 2)->second <= i->b)
            {
                stk.pop_back();
                stk.pop_back();
            }
            t_new t;
            t.first = i->a;
            t.second = i->b;
            stk.push_back(t);
        }
        else if (stk.size()) //第一次为升序没有用， 因为本身就是升序
        {
            //第一次压缩, 连续的1,选范围大的
            if (stk.size() > 0 && stk.back().first == 1)
            {
                i->b = min(i->b, stk.back().second);
                stk.pop_back();
            }
            while (stk.size() >= 2 && (stk.end() - 2)->second >= i->b)
            {
                stk.pop_back();
                stk.pop_back();
            }
            t_new t;
            t.first = i->a;
            t.second = i->b;
            stk.push_back(t);
        }
    }
    for (vector<t_new>::iterator it = stk.begin(); it != stk.end(); it++)
    {
        if(it->first == 0)
        {
            stable_sort(v.begin(), v.begin()+it->second, greater<int>());
        }
        else
        {
            stable_sort(v.begin() + it->second - 1, v.end());
        }
    }
    for_each(v.begin(), v.end(), MyPrint);
    cout << endl;
    return 0;
}

旋转数最大最小数字

/* 
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1.
*/
#include 

using namespace std;

int FindMin(int* arr, int length)
{
    int begin = 0; int end = length - 1;
    //考虑没有特殊的旋转()
    if(arr[begin] < arr[end]) return arr[begin];
    //begin和end指向相邻元素，退出
    while(begin+1 < end)
    {
        int mid = begin + ((end-begin) >> 1);
        //要么左侧有序，要么右侧有序
        if(arr[mid] >= arr[begin])//左侧有序
        {
            begin = mid;
        }
        else
        {
            end = mid;
        }
    }
    return arr[end];
}
int main()
{
    int a[] = {5, 1, 2, 3, 4};
    int b[] = {1, 0, 1, 1, 1};
    cout<<FindMin(a, sizeof(a)/sizeof(int))<<endl;
    cout<<FindMin(b, sizeof(b)/sizeof(int))<<endl;//这是有问题的，如果这种测判断左头和有右头相等，则用扫描
    return 0;
}

希尔排序

#include 
using namespace std;
int attr[] = {3, 2, 9, 4, 5, 6, 2};
void ShellSort(int *_attr, int length)
{
    /*外层决定增量，内层插排*/
    for (int interval = length / 2; interval > 0; interval /= 2)
    {
        for (int i = interval; i < length; i++)
        {
            int target = _attr[i];//先把目标保存下来
            int j = i - interval;//把距离它interval前面的元素下标找到
            while (j > -1 && target < _attr[j]) //如果这个元素是比它大并且下标没有为负数
            {
                _attr[j + interval] = _attr[j];//把该元素给目标位置
                j -= interval;//并且继续往前面走interval个距离再找一个元素
            }
            _attr[j + interval] = target;
        }
    }
}

int main()
{
    ShellSort(attr, sizeof(attr) / sizeof(int));
    for (int i = 0; i < (int)(sizeof(attr) / sizeof(int)); i++)
    {
        cout << attr[i] << " ";
    }
    cout << endl;
    return 0;
}

快排

#include 
using namespace std;

void swap(int *A, int x, int y)
{
    int tmpVal = A[x];
    A[x] = A[y];
    A[y] = tmpVal;
}
int arr[] = {1, 2, 6, 5, 3, 9, 7, 4, 5, 6, 4, 5, 6};
int Partition(int *A, int left, int right)
{
    int pivot = A[left];
    int sp = left + 1;
    int bigger = right;
    while (sp <= bigger)
    {
        if (A[sp] <= pivot)
            sp++;
        else
        {
            swap(A, sp, bigger);
            bigger--;
        }
    }
    swap(A, left, bigger);//到这里只需要管，把元素换过去即可
    return bigger;
}
void QuickSort(int *A, int left, int right)
{
    if (left < right)
    {
        int choice = Partition(A, left, right);
        QuickSort(A, left, choice - 1);
        QuickSort(A, choice + 1, right);
    }
}

int main(int argc, char const *argv[])
{
    QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
    return 0;
}

找空字符串

/*
有个排序后的字符串数组，其中散布着一些空字符串，编写一个方法，找出给定字符串（肯定不是空字符串)的索引。


arr[] = {"a", "",  "ac", "", "ad", "b", "", "ba"};
*/
#include 

using namespace std;
//找重复，找变化，找出口
string arr[] = {"a", "", "ac", "", "ad", "b", "", "ba"};
void StringFind(string *s1, int left, int right, string target)
{
    int mid = left+((right+left)>>1);
    if(left >= right )
        cout<<"no"<<endl;
    while(s1[++mid] == "");//如果它是空串，则一直+1,一直到它不是空串
    //!如果超过了right表示其实没有找到
    if(mid > right)
    {
        cout<<"no"<<endl;
        return;
    }
    if(s1[mid] == target)
        cout<<"yes"<<endl;
    else if(s1[mid].compare(target) > 0)
    {
        right = mid - 1;
        StringFind(s1, left, right, target);
    }
    else
    {
        left = mid + 1;
        StringFind(s1, left, right, target);
    }
}
int main()
{
    // StringFind(arr, 0, (int)(sizeof(arr)/sizeof(string)) -1, "ac");
    StringFind(arr, 0, (int)(sizeof(arr)/sizeof(string)), "abc");
    return 0;
}

插入排序

/*
插入排序的递归表达
*/
#include 

using namespace std;
int length;
int arr1[] = {2, 3, 4, 1, 2, 3, 4, 5, 4, 3, 2, 7, 5, 6, 8, 9, 4, 3, 2, 3, 1, 2, 3, 6, 7, 8, 9};
void InsertSort(int left, int right, int *arr)
{
    if (left == length)
    {
        return;
    }
    int target = arr[right];
    int xiabiao = right;
    while(arr[left] > arr[right])//如果它小于左边的数，那么就一直往左边看,但是不能超过最低位
    {
        if(left == 0)
        {
            arr[right] = arr[left];
            arr[left] = target;
            break;
        }
        else
        {
            arr[right] = arr[left];
            arr[left] =  target;
            left--;right--;
        }
    }
    xiabiao++;
    //如果大于左边的了那么就放在left的右边,left右边的这个给右边 
    InsertSort(xiabiao-1, xiabiao, arr);
}
int main()
{
    length = sizeof(arr1)/sizeof(int) - 1;
    InsertSort(0, 1, arr1);
    return 0;
}

斐波那契串

#include 
/*
斐波那契串由下列规则生成:F[0]="0";
F[1]="1";
F[n] =F[n-1] +F[n-2] (n≥2，+表示连接)
给出─个由0和1构成的串S和一个数n，求出F[n]中S出现的次数。


输入格式
第—行—个数n。

第二行—个01串S。


输出格式
答案。


样例输入
96
10110101101101
样例输出
7548113804746346428
*/
using namespace std;
#define LL unsigned long long
int F_start = 1;
int F_end = 1;
int Fibonaqie(int n)
{
    if (n == 0)
        return F_start;
    if (n == 1)
        return F_end;
    return Fibonaqie(n - 1) + Fibonaqie(n - 2);
}
long long FF1(int n)
{
    if (n == 0)
    {
        return F_start;
    }
    if (n == 1)
    {
        return F_end;
    }
    long long s1 = F_start;
    long long s2 = F_end;
    long long s3;
    for (int i = 3; i < n + 1; i++)
    {
        s3 = s1 + s2;
        s1 = s2;
        s2 = s3;
    }
    return s3;
}
int SubCnt(string s1, string s2)
{
    long long sum = 0;
    if (s1.length() < s2.length())
    {
        return 0;
    }
    for (size_t i = 0; i < s1.length() - s2.length() + 1; i++)
    {
        if (s2 == s1.substr(i, s2.length()))
            sum++;
    }
    return sum;
}
long long FF(int n, string cmpStr)
{
    string s;
    if (n == 0)
    {
        if (cmpStr == "0") //如果比较的0字符串
            return 1;      //返回一次
        return 0;
    }
    if (n == 1)
    {
        if (cmpStr == "1")
            return 1;
        return 0;
    }
    string s1 = "0";
    string s2 = "1";
    string s3;
    int index = 0;
    for (int i = 3; i < n + 1; i++)
    {
        s3 = s2 + s1;
        s1 = s2;
        s2 = s3;
        // cout << s3 << endl;
        if (SubCnt(s3, cmpStr) != 0 && index == 0)
        {
            index = 1;
            F_start = SubCnt(s3, cmpStr);
        }
        else if (index == 1)
        {
            F_end = SubCnt(s3, cmpStr);
            index = i;
            break;
        }
    }
    // cout << index << endl;
    return FF1(n - index + 4);
}
int main()
{
    unsigned long long start = 0;
    long long n;
    string inString;
    cin >> n >> inString;
    start = FF(n, inString);
    cout << start-1 << endl;
    return 0;
}

串

#include 
/*
问题描述
　　给你一个串s[0~n-1],要求你选择两个数i,j，满足0<=i<=j<=n，然后将s[0~i-1]、s[i~j-1]、s[j~n-1]翻转，要求翻转后的串字典序最小。


输入格式
　　本题有多组数据，第一行一个数T，表示数据组数。


　　每组数据占一行，为一个串。


输出格式
　　对于每组数据输出两个数i、j，即变化后字典序最小的方案，多种方案任意输出一组方案即可。


样例输入
2
bacbadcba
abc
样例输出
2 5
1 2
数据规模和约定
　　串由小写字母构成；
　　令S为所有串长度之和；
　　对于10%的数据，S<=300；
　　对于30%的数据，S<=2000；
　　对于60%的数据，S<=200000；
　　对于100%的数据，S<=10000000；
　　请使用gets或者scanf或者更快的方法读入；
　　数据有梯度。


*/
using namespace std;
int N;
vector<string> in_strings;
int Split(int start, string s)
{
    for (int i = start; i < s.length() - 1; i++) //进行遍历
    {
        if (s.at(i + 1) > s.at(start)) //如果后一个比前一个大，退出
        {
            return i + 1;
        }
    }
    return s.length() - 1;
}
int main()
{
    // 请在此输入您的代码
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        string tmpstr;
        cin >> tmpstr;
        in_strings.push_back(tmpstr);
    }
    for (int i = 0; i < N; i++)
    {
        int start = 0;
        start = Split(start, in_strings.at(i));
        cout << start << " ";
        start = Split(start, in_strings.at(i));
        cout << start << endl;
    }
    return 0;
}