title: 蓝桥赛题ALGO 1 -50date: 2021-2-10 19：06:30
tags: C++
categories: 蓝桥赛练习

ALGO-1. 区间k大数查询

问题描述

给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  6. int cmp(int a,int b){
  7.     return a > b;
  8. }
  9. int main() {
  10.     int n;
  11.     cin>>n;
  12.     vector<int> a(n);
  13.     for(int i = 0;i < n;i++){
  14.         cin>>a[i];
  15.     }
  17.     int m,l,r,K;
  18.     vector<int> result(n);
  19.     vector<int> temp(n);
  20.     cin>>m;
  21.     for(int i = 0;i < m;i++){
  22.         cin>>l>>r>>K;
  23.         temp = a;  //每次sort会打乱原先的存储顺序，这里用深拷贝 
  24.         int *p = &temp[0];
  25.         sort(p + l - 1,p + r,cmp);  //注意sort函数的执行范围 
  26.         result[i] = temp[l - 1 + K - 1];
  27.     }
  29.     for(int i = 0;i < m;i++){
  30.         cout<<result[i]<<endl;
  31.     }
  32.     return 0;
  33. }
  1. 另一种深拷贝sort的方法
  2. int *temp = new int [n];
  3. for(int j = 0;j < n;j++){
  4.     temp[j] = a[j];
  5. } 
  6. sort(temp + l - 1,temp + r,cmp);
  7. result[i] = temp[l - 1 + K - 1];
  8. delete []temp;

笔记：sort函数的处理范围是第一个参数到第二个参数的前一个地址，对照平常用的sort(arrayName,arrayName + arrayLength,cmp)可以记忆，另外，vector的名称与数组名称不同，不能作为sort的参数，得另设指针

ALGO-4. 结点选择

问题描述

有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  5. int printFlag = 1;
  6. int dp[100010][2];
  7. vector<vector<int> > v;
  8. void dfs(int node,int pre){ 
  9.     for(int i = 0;i < v[node].size();i++){
  10.         int temp = v[node][i];
  11.         if(temp != pre){
  12.             dfs(temp,node);
  13.             dp[node][0] = max(dp[temp][0],dp[temp][1]);
  14.             dp[node][1] += dp[temp][0];
  16.             if(printFlag) {cout<<"累积步骤："<<endl;printFlag = 0;}  //测试--累积步骤 
  17.             cout<<"["<<node<<"]"<<"[0] = "<<dp[node][0]<<endl;
  18.             cout<<"["<<node<<"]"<<"[1] = "<<dp[node][1]<<endl;
  19.         }
  20.     }
  21. }
  22. int main() {
  23.     int n;
  24.     cin>>n;
  25.     for(int i = 1;i <= n;i++){  //给点赋权 
  26.         cin>>dp[i][1];
  27.     }
  28.     v.resize(n + 1);  //点的序号范围：1-n
  29.     int a,b;
  30.     for(int i = 0;i < n - 1;i++){  //描述边，建立邻接表 
  31.         cin>>a>>b;
  32.         v[a].push_back(b);
  33.         v[b].push_back(a);
  34.     } 
  35.     cout<<"打印邻接表 "<<endl;
  36.     for(int i = 1;i <= n;i++){  //测试--打印邻接表 
  37.         cout<<"["<<i<<"] ";
  38.         for(int j = 0;j < v[i].size();j++){
  39.             cout<<v[i][j]<<' ';
  40.         }
  41.         cout<<endl;
  42.     }
  43.     dfs(1,0);  //深度优先搜索 
  44.     cout<<max(dp[1][0],dp[1][1]); 
  45.     return 0;
  46. }

柳大的分析：

蓝桥赛题ALGO 1-50 - 图1

笔记：最大的收获是用vector建立动态规划建立邻接表

.pushback() ×

.push_back() √

resize()函数的用法

ALGO-5. 最短路

  1. #include <iostream>
  2. //#include <bits/stdc++.h>
  3. using namespace std;
  4. const int INF = 0x3f3f3f3f;
  5. const int maxn = 200001;
  6. int dis[20001] = { 0 };
  7. int u[maxn];
  8. int v[maxn];
  9. int w[maxn];
  10. int main() {
  11.     //ios::sync_with_stdio(false);  非常高大上的技巧， 
  12.     //cin.tie(0),cout.tie(0);       用于提升c++ 中cin cout的效率。 
  13.     int n, m;
  14.     cin >> n >> m;  //n个点 m条边 
  15.     fill(dis + 2,dis + 20001,INF);
  17.     for (int i = 1; i <= m; i++) {
  18.         cin >> u[i] >> v[i] >> w[i];
  19.     }
  20.     for (int i = 1; i <= n - 1; i++) {
  21.         int check = 0;
  22.         for (int j = 1; j <= m; j++) {
  23.             if (dis[v[j]] > dis[u[j]] + w[j]) {
  24.                 dis[v[j]] = dis[u[j]] + w[j];
  25.                 check = 1;  //说明本次有进行松弛 
  26.             }
  27.         }
  28.         if (check == 0) break;  //若是没有点可以松弛了早早退出循环免得超时 
  29.     }
  30.     for (int i = 2; i <= n; i++) {
  31.         cout << dis[i] << endl; 
  32.     }
  33.     return 0;
  34. }

笔记：

  1. 0x3f3f3f3f 0x开头的 是十六进制常数， 等于 十进制 1061109567 等于 二进制： 00111111 00111111 00111111 00111111
  2. 高大上的技巧
  3. 数组太大导致堆空间炸了，但是把数组定义成全局变量是可以编译的
  4. 算法松弛（他人的博客链接）

ALGO-8. 操作格子（线段树）

  1. #include <iostream>
  2. using namespace std;
  3. struct node{
  4.     int l;
  5.     int r;
  6.     int maxValue;
  7.     int sum;
  8. }a[1000000];
  10. //init
  11. void initTree(int left,int right,int i){
  12.     a[i].l = left;
  13.     a[i].r = right;
  14.     a[i].maxValue = 0;
  15.     a[i].sum = 0;
  17.     if(left != right){
  18.         int mid = (left + right) / 2;
  19.         initTree(left,mid,i * 2);
  20.         initTree(mid + 1,right,i * 2 + 1);
  21.     }
  22.     return;
  23. }
  24. //insert
  25. void insert(int i,int num,int value){
  26.     //cout<<"开始："<<"i = "<<i<<endl;
  27.     if(a[i].l == a[i].r){
  28.         a[i].maxValue = value;
  29.         a[i].sum = value;
  30.         return;  //在蓝桥练习题中第二次遇到这个性质的return，在此标记 
  31.     }else{
  32.         int mid = (a[i].l + a[i].r) / 2;
  33.         if(num <= mid){
  34.             insert(i * 2,num,value);
  35.         } else{
  36.             insert(i * 2 + 1,num,value);
  37.         }
  38.     }
  39.     //cout<<"i = "<<i<<endl;
  40.     a[i].maxValue = max(a[i * 2].maxValue,a[i * 2 + 1].maxValue);
  41.     a[i].sum = a[i * 2].sum + a[i * 2 + 1].sum;
  42.     return;
  43. }
  44. //find_sum
  45. int find_sum(int i,int x,int y){
  46.     if(a[i].l == x && a[i].r == y) return a[i].sum;
  47.     int mid = (x + y) / 2;
  48.     if(y <= a[i].l)
  49.         return find_sum(i * 2,x,y);
  50.     else if(x >= a[i].r)
  51.         return find_sum(i * 2 + 1,x,y);
  52.     else
  53.         return find_sum(i * 2,x,mid) + find_sum(i * 2 + 1,mid + 1,y);
  54. }
  55. //find_max
  56. int find_max(int i,int x,int y){
  57.     if(a[i].l == x && a[i].r == y) return a[i].maxValue;
  58.     int mid = (x + y) / 2;
  59.     if(y <= a[i].l)
  60.         return find_max(i * 2,x,y);
  61.     else if(x >= a[i].r)
  62.         return find_max(i * 2 + 1,x,y);
  63.     else
  64.         return max(find_max(i * 2,x,mid),find_max(i * 2 + 1,mid + 1,y));
  65. }
  67. int main() {
  68.     int n,m;
  69.     cin>>n>>m;
  70.     initTree(1, n, 1);
  71.     int value;
  72.     for(int k = 1;k <= n;k++){
  73.         cin>>value;
  74.         insert(1,k,value);
  75.     }
  76.     int p,x,y;
  77.     for(int i = 0;i < m;i++){
  78.         cin>>p>>x>>y;
  79.         if(p == 1)
  80.             insert(1, x, y);
  81.         if(p == 2)
  82.             cout<<find_sum(1, x, y)<<endl;
  83.         if(p == 3)
  84.             cout<<find_max(1, x, y)<<endl;
  85.     }
  86.     //cout<<"Done!"<<endl;
  87.     return 0;
  88. }

笔记:

  1. 线段树也就是二叉树，解题时个1~4的线段树就好理解。
  2. 关于初始化线段树：二叉树的左右孩子序号为i_2 与 i_2+1。其实与正序建立二叉树差不多，关键在于判断叶子节点条件为l == r
  3. 关于insert函数：从根节点开始递归找到叶子节点，处理叶子节点，再“原路返回”，返回过程中处理经过节点。“小段推出大段”，过程是由下至上的。
  4. 多练几遍，加深理解
  5. 大佬的线段树讲解

ALGO-10. 集合运算（map和迭代器的应用）

  1. #include <iostream>
  2. #include <map>
  3. using namespace std;
  5. int main() {
  6.     int n,m;
  7.     map<int, int> M;
  8.     int a[1001],b[1001];
  9.     cin>>n;
  10.     for(int i = 0;i < n;i++){
  11.         cin>>a[i];
  12.         M[a[i]] += 1;
  13.     }
  14.     cin>>m;
  15.     for(int i = 0;i < m;i++){
  16.         cin>>b[i];
  17.         M[b[i]] += 2;
  18.     }
  19.     map<int, int>::iterator i;
  20.     for(i = M.begin();i != M.end();i++){
  21.         if(i->second == 3) cout<<i->first<<' ';  //ab的交集 
  22.     }
  23.     cout<<endl;
  24.     for(i = M.begin();i != M.end();i++){
  25.         cout<<i->first<<' ';  //ab的并集 
  26.     }   
  27.     cout<<endl;
  28.     for(i = M.begin();i != M.end();i++){
  29.         if(i->second == 1) cout<<i->first<<' ';  //a - b 
  30.     } 
  31.     cout<<endl;
  32.     return 0;
  33. }

笔记：

  1. map 适合处理重复的元素，而且map自带的排序也很便利
  2. map 有键值和数值（映射值），map的迭代器对应用iteratorName->first/second调用键值和数值。
  3. 关于迭代器：来自C语言中文网
  4. 其他的map使用例题：数对 字符串哈希

ALGO-11. 瓷砖铺放（递归/动态规划）

问题描述：

有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度2，数目不
限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？

  1. #include <iostream>
  2. using namespace std;
  3. typedef long long LL;
  5. LL dfs(int x){
  6.     if(x == 1)
  7.         return 1;
  8.     if(x == 2)
  9.         return 2;
  10.     return dfs(x - 1) + dfs(x - 2);
  11. } 
  12. int main() {
  13.     int n;
  14.     cin>>n;
  15.     cout<<dfs(n);
  16.     return 0;
  17. }

笔记：

  1. 这个解法思路和之前做的背包问题（用二维表解法）思路是互通的。只是这题我用的是递归。我感觉都是动态规划的思想:问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

ALGO-12. 幂方分解

问题描述：

任何一个正整数都可以⽤2的幂次⽅表示。例如：
137=27+23+20
同时约定方次用括号来表示，即ab 可表示为a（b）。
由此可知，137可表示为：
2（7）+2（3）+2（0）
进一步：7= 22+2+20 （21用2表示）
3=2+20
所以最后137可表示为：
2（2（2）+2+2（0））+2（2+2（0））+2（0）

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  5. string dfs(int n) {
  6.     if(n == 0) return "0";
  7.     if(n == 1) return "1";
  9.     vector<int> position;
  10.     string ans;
  11.     int cnt = 0; 
  13.     while(n){
  14.         int temp = n % 2;
  15.         if(temp == 1) position.push_back(cnt);
  16.         n /= 2;
  17.         cnt++;
  18.     }
  19.     for(int i = position.size() - 1; i >= 0; i--){
  20.         ans += "2(" + dfs(position[i]) + ")";
  21.         if(i != 0) ans += "+";
  22.     }
  23.     return ans;
  24. }
  25. int main(){
  26.     string ans = dfs(137);
  27.     cout<<ans<<endl;  //通过过滤把2(1) 输出为 2 
  28.     for(int i = 0;i <= ans.size();i++){
  29.         if(ans[i + 1] == '1') i += 3;
  30.         if(i <= ans.size()) cout<<ans[i];  //防止超界 
  31.     }
  33.     return 0;
  34. }

笔记：

这道题纠结了我好久，虽然我知道用递归，也很容易分解出方次到数组中，但是输出格式老是不对

  1. 我总想着if(n == 2)的情况，但是换成最后筛选的思路就迎刃而解了
  2. “+”的添加也纠结了好久，说明递归还是不熟，容易钻牛角尖，此题也要重复

ALGO-14. 回文数

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6. int k;
  8. vector<int> cal(vector<int> v){
  9.     vector<int> v1(v),v2(v),ans(v.size(),0);
  10.     reverse(v1.begin(),v1.end());
  11.     int temp = 0;
  13.     for(int i = v.size() - 1;i >= 0;i--){  //注意是从小权值位加起 
  14.         ans[i] = (v1[i] + v2[i] + temp) % k;
  15.         temp = (v1[i] + v2[i] + temp) / k;
  16.     }
  17.     if(temp) ans.insert(ans.begin(),temp);
  19.     return ans;
  20. }
  21. bool is(vector<int> v){
  22.     for(int i = 0;i < v.size();i++){
  23.         if(v[i] != v[v.size() - 1 - i])
  24.             return false;
  25.     }
  26.     return true;
  27. }
  28. int main(){
  29.     int N; 
  30.     string M;
  31.     cin>>N;
  32.     cin.get();
  33.     cin>>M;
  34.     int cnt = 0;
  35.     k = N;
  36.     vector<int> v;
  38.     for(int i = 0;i < M.size();i++){
  39.         if('0' <= M[i] && M[i] <= '9') v.push_back(M[i] - '0');
  40.         else if('A' <= M[i] && M[i] <= 'F') v.push_back(M[i] - 'A' + 10);
  41.     }
  42.     while(!is(v)){
  43.         v = cal(v);
  44.         cnt++;
  45.         if(cnt >= 30){
  46.             cout<<"Impossible"<<endl;
  47.             return 0;
  48.         }
  49.     }
  50.     cout<<"STEP="<<cnt<<endl;
  51.     return 0;
  52. }

笔记：

  1. 关于vector的初始化：vector cde(10, 1); // 初始化了10个值为1的元素
  2. 关于函数v.push_back() //是成员函数 在v的内存后边建立新空间
    例：vector(int) v(4,0); v.push_back(1); 那么输出容器内值为00001而不是1
  3. 关于函数v.insert() //是成员函数 在给定位置前插入，后续自动调整
  4. 关于函数reverse() //不是成员函数 头文件< algorithm >
  5. vector v1(v);v = v1;在< vector >中有重载，但是v += 3;这样的想都别想

ALGO-21. 装箱问题（动态规划，01背包）

  1. #include <iostream>
  2. #include <iomanip> 
  3. using namespace std;
  4. int dp[31][2001];
  6. int main(){
  7.     int v,n;
  8.     cin>>v>>n;
  9.     for(int i = 1;i <= n;i++){
  10.         int t;
  11.         cin>>t;
  12.         for(int j = 1;j <= v;j++){
  13.             if(t > j) dp[i][j] = dp[i - 1][j];
  14.             else{
  15.                 dp[i][j] = max(dp[i - 1][j - t] + t,dp[i - 1][j]);
  16.             }
  17.         }
  18.     } 
  19.     for(int i = 0;i <= n;i++){  //测试相关 
  20.         for(int j = 0;j <= v;j++){
  21.             cout<<left<<setw();
  22.             cout<<dp[i][j]<<' ';
  23.         }
  24.         cout<<endl;
  25.     }
  26.     cout<<v - dp[n][v];
  27.     return 0;
  28. }

笔记：

  1. 把dp数组设置成全局变量，每个元素的初始值就是0，不用特地去设置边dp边界

ALGO-22. 数的划分

问题描述

将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
　　例如：n=7，k=3，下面三种分法被认为是相同的。
　　1，1，5; 1，5，1; 5，1，1;
　　问有多少种不同的分法。

  1. #include <iostream>
  2. using namespace std;
  3. int cnt = 0;
  4. void dfs(int front, int n, int step) {
  5.     if (step == 1) {
  6.         cnt++;
  7.         return;
  8.     }
  9.     for (int i = front; i <= n / step; i++) {
  10.         dfs(i, n - i, step - 1);
  11.     }
  12. }
  13. int main() {
  14.     int n, k;
  15.     cin >> n >> k;
  16.     dfs(1, n, k);
  17.     cout << cnt;
  18.     return 0;
  19. }

笔记：

当然用递归是比较正常的思路，但是要求不要重复的判断我怎么都写不出来，看了柳大的判断条件也不理解。我联想到的是“24小时时钟分割，有向线段转无向线段”。但是还是觉得不通，先欠着

ALGO-23. 一元三次方程求解

问题描述

有形如：ax3+bx2+cx+d=0 这样的一元三次方程。给出该⽅程中各项的系数(a，b，c，d 均为实
数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求
三个实根。

  1. #include <iostream>
  2. #include <iomanip>
  3. using namespace std;
  4. double a,b,c,d;
  6. double f(double x){
  7.     return a*x*x*x + b*x*x + c*x + d; 
  8. }
  9. double find (double x,double y){
  10.     if(y - x < 0.0001) return x;
  11.     else{
  12.         double mid = (x + y) / 2;
  13.         if(f(x) * f(mid) < 0) return find(x,mid);
  14.         else return find (mid,y);
  15.     }
  16. }
  17. int main(){
  18.     cin>>a>>b>>c>>d;
  19.     for(double i = -100;i <= 100;i++){
  20.         if(f(i) == 0) cout<<fixed<<setprecision(2)<<i<<' ';
  21.         else if(f(i) * f(i + 1) < 0) cout<<fixed<<setprecision(2)<<find(i,i + 1)<<' ';
  22.     }
  23.     return 0;
  24. }

笔记：

第一次接触二分逼近的思想，要求精确到0.01，那么y - x到0.001位都应是相等的，所以条件是差值 < 0.0001，也就是加了2个0,等等……是这样吗？

ALGO-25. Car的旅行路线

问题描述：

又到暑假了，住在城市 A 的 Car 想和朋友一起去城市 B 旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第 i 个城市中高速铁路的单位里程价格为 Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为 t。

那么 Car 应如何安排到城市 B 的路线才能尽可能的节省花费呢？她发现这并不是一个简单的问题，于是她来向你请教。

找出一条从城市 A 到 B 的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

输入格式

第一行有四个正整数 s，t，A，B。

S 表示城市的个数，t 表示飞机单位里程的价格，A，B 分别为城市 A，B 的序号，(1 <= A，B <= S)。

接下来有 S 行，其中第 i 行均有 7 个正整数 xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的 (xi1，yi1)，(xi2，yi2)，(xi3，yi3) 分别是第 i 个城市中任意三个机场的坐标，Ti 为第 i 个城市高速铁路单位里程的价格。

输出格式

一个正整数，表示最小花费，保留一位小数。

来自大佬https://www.cnblogs.com/jinkun113/p/13792527.html

样例输入

3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3

样例输出

47.5

  1. //#include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <iomanip>
  4. using namespace std;
  6. #define MAXN  405
  7. #define INF 0x7f7f7f7f
  9. double P;  //航班里程价 
  10. double xt[5], yt[5], x[MAXN], y[MAXN], p[101];
  11. double pri[MAXN][MAXN];
  12. double ans = INF;
  14. double cal(int a, int b, int c) {
  15.     if (xt[a] == xt[b] && yt[c] == yt[b] || xt[c] == xt[b] && yt[a] == yt[b]) return -1;
  16.     else return (yt[a] - yt[b]) / (xt[a] - xt[b]) * (yt[c] - yt[b]) / (xt[c] - xt[b]);
  17. }
  19. double getp(int r, int c) {  //同城地坐铁 否则坐飞机 
  20.     return sqrt((x[r] - x[c]) * (x[r] - x[c]) + (y[r] - y[c]) * (y[r] - y[c])) * (r / 4 == c / 4 ? p[r / 4 + 1] : P);
  21. }
  23. int main() {
  24.     int s, A, B;
  25.     cin >> s >> P >> A >> B;
  26.     for (int i = 1; i <= s; i++) {  //输入及处理 
  27.         for (int j = 1; j <= 3; j++) {
  28.             cin >> xt[j] >> yt[j];
  29.         }
  30.         if (cal(1, 2, 3) == -1) {  //直角点是 2
  31.             xt[4] = xt[1] + xt[3] - xt[2];
  32.             yt[4] = yt[1] + yt[3] - yt[2];
  33.         }
  34.         else if (cal(2, 1, 3) == -1) {  //直角点是 1
  35.             xt[4] = xt[2] + xt[3] - xt[1];
  36.             yt[4] = yt[2] + yt[3] - yt[1];
  37.         }
  38.         else {  //直角点是 3
  39.             xt[4] = xt[1] + xt[2] - xt[3];
  40.             yt[4] = yt[1] + yt[2] - yt[3];
  41.         }
  42.         for (int k = 1; k <= 4; k++) {
  43.             x[(i - 1) * 4 + k - 1] = xt[k];
  44.             y[(i - 1) * 4 + k - 1] = yt[k];
  45.         }
  46.         cin >> p[i];
  47.     }
  48.     memset(pri, INF, sizeof(pri));  //建立带权邻接表
  49.     for (int i = 0; i < s * 4; i++) {  //Price表描述带权无向图 
  50.         for (int j = 0; j < s * 4; j++) {
  51.             pri[i][j] = pri[j][i] = getp(i, j);
  52.         }
  53.     }
  54.     for (int i = 0; i < s * 4; i++) {  //Floyd算法 
  55.         for (int j = 0; j < s * 4; j++) {
  56.             if (i == j) continue;  //不考虑原地tp 
  57.             for (int k = 0; k < s * 4; k++) {
  58.                 if (k == i || k == j) continue;  //由a到b  k不为a或b 
  59.                 pri[i][j] = pri[j][i] = min(pri[i][j], pri[i][k] + pri[j][k]);
  60.             }
  61.         }
  62.     }
  63.     for (int i = 0; i < 4; i++) {
  64.         for (int j = 0; j < 4; j++) {
  65.             ans = min(ans, pri[(A - 1) * 4 + i][(B - 1) * 4 + j]);
  66.         }
  67.     }
  68.     cout << fixed << setprecision(1) << ans;
  69.     return 0;
  70. }

笔记：

小心题目样例！这道题给的样例本身不对，输入格式都不对！wdnmd
本身是求最短路径问题：

  1. 先求每个城市的第四个机场坐标：第四个点一定正对着已知直角点 用斜率相乘=-1判断直角，此外，对于平行/垂直坐标系的直线要特殊处理
  2. 用Floyd算法,先把图用邻接表描述出来
  3. ans = 从A城市到B城市16种出发/到达情况中最小权值和的情况

做的时候错误多多，一直调试(心碎)：

  1. getp函数返回精度太小了 同样此函数两点距离公式的应用也…也搞错了
  2. 求ans最小值也出错了：
    ans = min(ans,pri[ (A - 1)4 + j][(B - 1)_4 + j ]); ×
    ans = min(ans, pri[(A - 1)     4 + i][(B - 1) _ 4 + j ]); √

函数：memset()函数在C中是在string.h头文件里定义的，在C++中是在cstring头文件里定义的。

ALGO-26. 麦森数

  1. #include <iostream>
  2. #include <string> 
  3. #include <vector> 
  4. #include <algorithm>
  5. #include <cmath>
  6. using namespace std;
  7. typedef long long LL;
  9. string mul(string s1,string s2){
  10.     if(s1.length() >= 505) s1 = s1.substr(s1.length() - 505);  //避免超时，剪去头，留尾505位 
  11.     if(s2.length() >= 505) s2 = s2.substr(s2.length() - 505); 
  12.     string ans;
  13.     reverse(s1.begin(),s1.end());
  14.     reverse(s2.begin(),s2.end());
  15.     vector<int> v(s1.length() + s2.length(),0);
  17.     int t;
  18.     for(int i = 0;i < s1.length();i++){
  19.         for(int j = 0;j < s2.length();j++){
  20.             t = (s1[i] - '0') * (s2[j] - '0') + v[i + j];
  21.             v[i + j] = t % 10;
  22.             v[i + j + 1] += t / 10;  //注意逻辑，该运算写成=浪费我2小时(心碎)
  23.         }
  24.     }
  25.     int i;
  26.     for(i = v.size() - 1;v[i] == 0;i--);
  27.     for(int j = i;j >=0;j--) ans += v[j] + '0';
  29.      return ans;
  30. }
  32. string f(int n){  //快速幂二分求2^p 
  33.     if(n == 0) return "1";
  34.     if(n == 1) return "2";
  35.     if(n % 2 == 1) return mul(f(n - 1), "2");  
  36.     string s = f(n / 2);  //避免超时，如果为偶数幂，平方处理 
  37.     return mul(s,s);   
  38. }
  40. string sub(string s,int index){
  41.     if(s[index] != '0'){
  42.         s[index] -= 1;
  43.         if(s[0] == '0') s = s.substr(1);  //最大位为1且被借走时特殊处理 
  44.         return s;
  45.     }else{
  46.         s[index] = '9';
  47.         return sub(s,index - 1);
  48.     }
  49. }
  51. int main() {
  52.     LL P;
  53.     cin>>P;
  54.     cout<<(int) (P*log10(2)) + 1<<endl;  //求位数 注意括号取整型精度
  55.     string s = f(P);  //2的P次方  
  56.     s = sub(s,s.length() - 1);  //减一
  57.     string add(500,'0');
  58.     string ans = add + s;  //要求不足500的位数补0 
  59.     if(ans.length() > 500) ans = ans.substr(ans.length() - 500);  //是正序所以避免不了再剪
  60.     for(int i = 0;i < 500;i++){
  61.         cout<<ans[i];
  62.         if((i + 1) % 50 == 0) cout<<endl;
  63.     }
  65.     return 0;
  66. }

笔记：这道题注意点教多，笔记二三刷的时候再补充，一定要再刷！

ALGO-28. 星际交流

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  5. int main(){
  6.     int M,N;
  7.     cin>>M>>N;
  8.     int a[M];
  10.     for(int i = 0;i < M;i++){
  11.         cin>>a[i];
  12.     }
  13.     while(N--) next_permutation(a,a+M);  //进行N次全排列 
  14.     for(int i = 0;i < M;i++){
  15.         cout<<a[i]<<' ';
  16.     }
  17.     return 0;    
  18. }

笔记：

为next_permutation();函数量身打造的题目
如果范围内的数列有下一个（递增）的排列，那么函数返回1，并改变数组至该排列；如果没有，返回0
详解

ALGO-30. 入学考试（01背包，动态规划）

问题描述：

第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
　　包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
数据规模和约定
　　对于30%的数据，M <= 10；
　　对于全部的数据，M <= 100。

  1. #include <iostream>
  2. using namespace std;
  3. int dp[1001][101];
  5. int main(){
  6.     int t,m;
  7.     cin>>t>>m;
  8.     for(int i = 1;i <= m;i++){
  9.         int a,b;
  10.         cin>>a>>b;
  11.         for(int j = 1;j <= t;j++){
  12.             if(j >= a){
  13.                 dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - a] + b);
  14.             }else{
  15.                 dp[i][j] = dp[i - 1][j];
  16.             }
  17.         }
  18.     }
  19.     cout<<dp[m][t];
  20.     return 0;    
  21. }
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  6. int main() {
  7.     int t, m;
  8.     cin >> t >> m;
  9.     vector<vector<int> > dp(m + 1, vector<int>(t + 1, 0));
  10.     map<int, int> stuff;  //first:time   second:value
  11.     int temp = m;
  12.     while (temp--) {
  13.         int a, b;
  14.         cin >> a >> b;
  15.         stuff[a] = b;
  16.     }
  17.     map<int, int>::iterator p;
  18.     int i = 1;
  19.     for (p = stuff.begin(); p != stuff.end(); p++) {
  20.         for (int j = 1; j <= t; j++) {
  21.             if (j >= p->first) {
  22.                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p->first] + p->second);
  23.             }
  24.             else {
  25.                 dp[i][j] = dp[i - 1][j];
  26.             }
  27.         }
  28.         i++;
  29.     }
  30.     cout << dp[m][t];
  31.     return 0;
  32. }
  33. /*
  34. 70 3
  35. 71 100
  36. 69 1
  37. 1 2
  38. */                    想用上vector二维数组和map的画蛇添足版本

笔记：

背包问题典中典，对每一个物品把背包的空间全部拆分，然后考虑使用背包不同空间的情况：1. 空间不够大，不放入物品 2. 空间够大，放入物品或不放入物品取最优

ALGO-31. 开心的金明（01背包，动态规划）

  1. #include <iostream>
  2. using namespace std;
  3. int dp[25][30000];
  5. int main() {
  6.     int N,m;
  7.     cin>>N>>m;
  8.     int v,p;
  9.     for(int i = 1;i <= m;i++){
  10.         cin>>v>>p;
  11.         for(int j = 1;j <= N;j++){
  12.             if(j >= v){
  13.                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v] + v * p);
  14.             }else{
  15.                 dp[i][j] = dp[i - 1][j];
  16.             }
  17.         }
  18.     }
  19.     cout<<dp[m][N];
  20.     return 0;
  21. }

笔记：

没什么好说的，做的时候试了与题目无关的cmath库函数，干脆在这里随便记几个：
三角函数
sin(M_PI/6) = 0.5
开方
sqrt(9) = 3
指数
pow(2,10) = 1024
exp2(10) = 1024
对数
log2(2147483648) = 31
有意思的发现
int a;
a = exp2(31); //overflow in implicit constant conversion
a = pow(2,31); //OK with that

ALGO-34. 纪念品分组（贪心算法+排序）

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  5. int main() {
  6.     int m,n;
  7.     cin>>m>>n;
  8.     int a[n];
  9.     for(int i = 0;i < n;i++){
  10.         cin>>a[i];
  11.     }
  12.     sort(a,a+n);  //sort默认是从小到大排列 
  13.     int cnt = 0;
  14.     int i = 0, j = n -1;
  15.     while(i < j){
  16.         if(a[i] + a[j] <= m){
  17.             i++;
  18.             j--;
  19.             cnt++;
  20.         }else{
  21.             j--; 
  22.             cnt++;
  23.         }
  24.     }
  25.     if(i == j) cnt++;
  26.     cout<<cnt;
  27.     return 0;
  28. }

笔记：

贪心算法的经典题目之一，建议重刷

ALGO-37. Hankson的趣味题

问题描述：

已知正整数a0,a1,b0,b1，设某未知正
整 数x 满足： 1． x 和a0 的最大公约数是a1； 2． x 和b0 的最小公倍数是b1
输入格式
输入第一行为一个正整数n，表示有n 组输入数据。
接下来的n 每行输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔
开。输入数据保证a0 能被a1 整除，b1 能被b0 整除。
输出格式
输出共n行。每组输⼊数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的 x，请输出0； 若存在这样的 x，请输出满足条件的x 的个数；
样例输入
2
41 1 96 288
95 1 37 1776
样例输出
62

  1. #include <iostream>
  2. using namespace std;
  4. int gcd(int a, int b){
  5.     if(b == 0) return a;
  6.     else return gcd(b, a % b);
  7. }
  9. int main() {
  10.     int a0,a1,b0,b1;
  11.     int k;
  12.     cin>>k;
  13.     while(k--){
  14.         int ans = 0;
  15.         cin>>a0>>a1>>b0>>b1;
  16.         for(int i = 1;i <= b1;i++){
  17.             if(b1 % i == 0){  //剪枝，减少运算时间 
  18.                 if(gcd(a0,i) == a1 && i*b0 == gcd(i,b0)*b1) ans++;
  19.             }
  20.         }
  21.         cout<<ans<<endl;
  22.     }
  23.     return 0;
  24. }

笔记：

暴力枚举

ALGO-38 算法训练 接水问题（优先队列）

问题描述
学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的 供水量相等，均为1。 现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打 开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m， 则只有n’个龙头供水，其它m−n’个龙头关闭。 现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
输入格式
第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同 学的接水量。
输出格式
输出只有一行，1 个整数，表示接水所需的总时间。
样例输入
5 3
4 4 1 2 1
样例输出
4
样例输入
8 4
23 71 87 32 70 93 80 76
样例输出
163

  1. #include <iostream>
  2. #include <vector> 
  3. #include <queue>
  4. using namespace std;
  6. int main() {
  7.     priority_queue<int, vector<int>, greater<int> > q;  //升序序列 小顶堆 
  8.     int n,m;
  9.     cin>>n>>m;  
  10.     int t;
  11.     int ans = 0;
  12.     for(int i = 1;i <= n;i++){
  13.         cin>>t;
  14.         if(i <= m) q.push(t);
  15.         else{
  16.              t = q.top() + t;  //需要时间最少的一队 
  17.              q.pop();
  18.              q.push(t);  //再入队 由优先队列自动排序 
  19.         }
  20.     }
  21.     while(!q.empty()){
  22.         ans = q.top();
  23.         q.pop();
  24.     }
  25.     cout<<ans;
  26.     return 0;
  27. }

笔记：

升序队列，小顶堆
priority_queue q;
降序队列，大顶堆
priority_queue q;
仿函数*
greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

定义：priority_queue< Type, Container, Functional >
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。
笔记来自

ALGO-47. 蜜蜂飞舞

  1. #include <iostream>
  2. #include <cmath>
  3. #include <iomanip>
  4. using namespace std;
  6. int main(){
  7.     int x1 = 0,y1 = 0,z1 = 0,x2 = 0,y2 = 0,z2 = 0,n;
  8.     cin>>n;
  9.     int tx1 = 0,ty1 = 0,tz1 = 0,tx2 = 0,ty2 = 0,tz2 = 0;
  10.     int t = 0;
  11.     for(int i = 0;i <= n;i++){
  12.         cin>>tx1>>ty1>>tz1>>tx2>>ty2>>tz2;
  13.         if(i == n) t = 1;
  14.         else cin>>t;
  15.         x1 += t*tx1;
  16.         y1 += t*ty1;
  17.         z1 += t*tz1;
  18.         x2 += t*tx2;
  19.         y2 += t*ty2;
  20.         z2 += t*tz2;
  21.     }
  22.     double ans = sqrt( (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) + (z1 - z2)*(z1 - z2) );
  23.     cout<<fixed<<setprecision(2)<<ans;
  24.     return 0;
  25. }

ALGO-48. 关联矩阵

问题描述
有一个n个结点m条边的有向图，请输出他的关联矩阵。
输入格式
第一行两个整数n、m，表示图中结点和边的数目。n<=100,m<=1000。
接下来m行，每行两个整数a、b，表示图中有(a,b)边。
注意图中可能含有重边，但不会有自环。
输出格式
输出该图的关联矩阵，注意请勿改变边和结点的顺序。
样例输入
5 9
1 2
3 1
1 5
2 5
2 3
2 3
3 2
4 3
5 4
样例输出
1 -1 1 0 0 0 0 0 0
-1 0 0 1 1 1 -1 0 0
0 1 0 0 -1 -1 1 -1 0
0 0 0 0 0 0 0 1 -1
0 0 -1 -1 0 0 0 0 1

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  5. int main(){
  6.     int n,m;
  7.     cin>>n>>m;
  8.     vector<vector<int> > l(n, vector<int>(m,0));
  9.     for(int i = 0;i < m;i++){
  10.         int a,b;
  11.         cin>>a>>b;
  12.         l[a - 1][i] = 1;  //一条边关联两个结点 
  13.         l[b - 1][i] = -1;
  14.     }
  15.     for(int i = 0;i < n;i++){
  16.         for(int j = 0;j < m;j++){
  17.             cout<<l[i][j]<<' ';
  18.         }
  19.         cout<<endl;
  20.     }
  21.     return 0;
  22. }

笔记

  • 虽然是概念题，但是还是记下来，因为我做的时候把几个矩阵的概念搞混了

矩阵定义记录在此

ALGO-50. 数组查找及替换

问题描述
给定某整数数组和某一整数b。要求删除数组中可以被b整除的所有元素，同时将该数组各元素按从小到大排序。如果数组元素数值在A到Z的ASCII之间，替换为对应字母。元素个数不超过100，b在1至100之间。
输入格式
第一行为数组元素个数和整数b
第二行为数组各个元素
输出格式
按照要求输出
样例输入
7 2
77 11 66 22 44 33 55
样例输出
11 33 55 M 

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  6. int main(){
  7.     int m,n,t;
  8.     cin>>m>>n;
  9.     vector<int> v;
  10.     while(m--){
  11.         cin>>t;
  12.         if(t % n){
  13.             v.push_back(t);
  14.         }
  15.     }
  16.     sort(v.begin(), v.end());
  17.     for(int i = 0;i < v.size();i++){
  18.         if('A'<= v[i] && v[i] <= 'Z'){
  19.             cout<<(char)v[i]<<' ';
  20.         }else{
  21.             cout<<v[i]<<' ';
  22.         }
  23.     }
  24.     return 0;
  25. }