蓝桥杯C++相关

文章目录

• 蓝桥杯算法
• • 有用链接
  • 小技巧
  • • 用变量大小初始的二维数组
    • 求gcd最大公约数
    • 对map for_each的遍历
    • 二进制输出
    • 初始化递增的数组或者容器
    • c++分割,按照指定字符分割
    • 求最大最小值
    • C++ vector与set互转
    • 输出到文件
    • 小数的二进制
    • 位运算
  • 注意事项
  • • 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;elsereturn 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;
}

C++ vector与set互转

set<int> st(v.begin(), v.end());//在构造函数中可以直接实现vector转set
v.assign(st.begin(), st.end());//用assign实现set转vector

版权声明：本文为CSDN博主「weixin_44744335」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/weixin_44744335/article/details/113882950

输出到文件

#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 
/**/
using namespace std;
array<int, 15> arr;void HeBing(int l, int r, int mid)
{int left = l, right = mid + 1, current = l;array<int, 15> tmpArr(arr);while (left <= mid && right <= r){if (arr[left] <= arr[right]){tmpArr[current++] = arr[left++];}else{tmpArr[current++] = arr[right++];}}while (left <= mid){tmpArr[current++] = arr[left++];}arr = tmpArr;for_each(tmpArr.begin(), tmpArr.end(), [](const auto &tmp) { cout << tmp << " "; });cout << endl;
}
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()
{iota(arr.begin(), arr.end(), 0);random_shuffle(begin(arr), end(arr));for_each(arr.begin(), arr.end(), [](const auto &tmp) { cout << tmp << " "; });cout << endl;GuiBing(0, arr.size()-1);for_each(arr.begin(), arr.end(), [](const auto &tmp) { cout << tmp << " "; });cout << endl;return 0;
}

#include 
/*1
归并排序
先分再合并，重要在合并上面
*/
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!$个情况， 那么在一种情况中， 随便选两个数有 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()); //这里的长度是lengthfor_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;
array<int, 15> arr;bool BinFind(const int &value, int l, int r)
{if (l <= r){int mid = (l + r) / 2;if (arr[mid] == value)return true;else if (arr[mid] > value)return BinFind(value, l, mid - 1);elsereturn BinFind(value, mid + 1, r);}return false;
}
int main()
{iota(arr.begin(), arr.end(), 0);cout << BinFind(10, 0, arr.size() - 1) << 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;elsecout << 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)); //二进制清空全为0memset(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资源约定：峰值内存消耗 < 256MCPU消耗 < 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;
array<int, 15> arr;void QuickSort(int l, int r)
{if (l < r){int pivit = arr[r];int i = l, j = l;for (j = l; j < r; j++){if (arr[j] < pivit){int tmp = arr[j];arr[j] = arr[i];arr[i] = tmp;i++;}}arr[j] = arr[i];arr[i] = pivit;QuickSort(l, i - 1);QuickSort(i + 1, r);}
}
int main()
{iota(arr.begin(), arr.end(), 0);random_shuffle(arr.begin(), arr.end());for_each(arr.begin(), arr.end(), [](const auto &tmp) { cout << tmp << " "; });cout << endl;QuickSort(0, arr.size() - 1);for_each(arr.begin(), arr.end(), [](const auto &tmp) { cout << tmp << " "; });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;
}

数组名真的不是指针

[数组名不是指针(https://blog.csdn.net/syzdev/article/details/78346352)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！