计算机专业考研复试上机算法学习

计算机专业考研复试上机算法学习

这篇博客是博主在准备可能到来的线下上机复试基于王道机试指南的学习，将各道习题链接和代码记录下来，这篇博客权且当个记录。

文章目录

• 计算机专业考研复试上机算法学习
• • 1.STL容器学习
  • • 1.1 vector动态数组
    • • 1.1.1 完数VS盈数
    • 1.2 stack栈
    • • 1.2.1 逆序输出
      • 1.2.2 后缀运算符
      • 1.2.3 堆栈的使用
    • 1.3 queue队列
    • • 1.3.1 实现循环队列来解决约瑟夫问题
    • 1.4 priority_queue优先队列
    • • 1.4.1 优先队列解决复数集合问题
      • 1.4.2 优先队列解决哈夫曼树问题
    • 1.5 双向链表 list
    • 1.6 set集合
    • 1.7 map映射容器
    • • 1.7.1 map的应用
      • 1.7.2 统计字符串出现次数//
      • 1.7.3 查询分数
      • 1.7.4 开门人 和关门人
      • 1.7.5 谁是你的潜在朋友
    • 1.8 sort排序函数
    • 1.9 next_permutation函数
  • 2.算法学习
  • • 2.1 递归实现求元素的全排列
    • 2.2 反序数
    • 2.3百鸡问题
    • 2.4 火鸡账单
    • 2.5 今年的第几天
    • 2.6打印日期
    • 2.7 日期累加
    • 2.8 [日期差值_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/ccb7383c76fc48d2bbc27a2a6319631c?tpId=40&tqId=21442&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)
    • 2.9 [Day of Week_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/a3417270d1c0421587a60b93cdacbca0?tpId=40&tqId=21439&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)
    • 2.10[剩下的树_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/f5787c69f5cf41499ba4706bc93700a2?tpId=60&tqId=29497&tPage=2&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking)
    • 2.11[xxx定律_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/75c189249d6145cfa33cd53edae6afc8?tpId=63&tqId=29579&tPage=1&ru=/kaoyan/retest/9001&qru=/ta/zju-kaoyan/question-ranking)
    • 2.12 排序题
    • 2.13带学号的成绩排序问题
    • 2.14 考虑输入次序的学生成绩排序
    • 2.15特殊排序
    • 2.16 整数奇偶排序（简单）
    • 2.17 小白鼠排序
    • 2.18 奥运排序问题
    • 2.19多次查找
    • 2.20找最小数
    • 2.21 找位置
  • 3.字符串习题
  • • ****字符串的一些用法***
    • 3.1 特殊乘法
    • 3.2字符转换
    • 3.3 密码转换
    • 3.4 计算字符出现次数
    • 3.5 统计大写字母出现次数
    • 3.6 SKEW数
    • 3.7 查找字符串
    • 3.8 将单词首字母转换成大写
    • 3.9 浮点数加法
    • 3.10 使用KMP求字符串完全匹配次数
  • 4.特殊的数学问题
  • • 4.1十进制转二进制
    • 4.2 使用大数除法的十进制转二进制
    • 4.3 二进制转十进制
    • 4.4 M进制转换成N进制
    • 4.5 十进制转八进制
    • 4.6 A+B 转m进制
    • 4.7 十六进制转十进制
    • 4.8 数制转换
    • 4.9 最大公约数
    • 4.10 最小公倍数
    • 4.11 判断最简真分数
    • 4.12 判断是否是素数
    • 4.13 输出个位数为1的素数
    • 4.14 质因数
    • 4.15 约数的个数
    • 4.16 整除问题///
    • 4.17 快速幂的应用
    • 4.18 矩阵乘法
    • 4.19 矩阵快速幂
    • 4.20 矩阵加法
  • 5.贪心算法
  • • 5.1匹配服务器
    • 5.2 区间贪心：看电视节目
    • 5.3 油价
    • 5.4 加油站问题（贪心算法）
  • 6.递归与分治
  • • 6.1 n的阶乘
    • 6.2 杨辉三角
    • 6.3 全排列(元素个数与之前一样)
    • 6.4 斐波那契数列
    • 6.5 求完全二叉树结点的子树
    • 6.6分解数字转二的次幂
  • 7.搜索算法
  • • 7.1 广度优先算法
    • 7.2 广度优先解决玛雅密码问题
    • 7.3 深度优先算法搜索状态问题
    • 7.4 神奇的口袋
    • 7.4 八皇后问题
  • 8.动态规划
  • • 8.1 上楼梯
    • 8.2 吃糖果
    • 8.3 最长子序列和
    • 8.4 最长递增子序列
    • 8.5 最大递增子序列2
    • 8.6 最长不递增子序列
    • 8.7 最大上升子序列和
    • 8.8 合唱队形
    • 8.9 0-1背包问题，同一件物品最多只能选择一件
    • 8.11 最小邮票数
    • 8.12 完全背包
    • 8.13 多重背包
    • 8.14 三角形
    • 8.15 暂时未解决的问题
    • 8.16 放苹果
    • 8.17 划分
  • 9.二叉树
  • • 9.1 根据前序和中序生成二叉树序列
    • 9.2 根据前序序列构成二叉树
    • 9.3 二叉排序树的生成
    • 9.4 记录插入结点的父节点
    • 9.5 判断两棵二叉树是否相同
    • 9.6 查找第k小数
  • 10.图论
  • • 10.1 并查集
    • • 10.1.2 连通工程
      • 10.1.3 判断是否是一棵树
      • 10.1.4 寻找直系亲属///
      • 10.1.5 统计图的联通分支
      • 10.1.6 寻找集合内权重最大的节点
    • 10.2 最小生成树
    • • 10.2.1 使用克鲁斯卡尔算法来解决最小生成树
      • 10.2.2 在二维平面上使用最小生成树
      • 10.3.3 Jungle Roads
    • 10.3 最短路径
    • • 10.3.1 迪杰斯特拉算法
      • 10.3.1.1
    • 10.4 拓扑排序
    • 10.5 关键路径
  • 11.补充刷题
  • • 11.1 二叉树找父节点
    • 11.2 后缀字串排序
    • 11.3 寻找大富翁
    • 11.4 **还是A+B**
    • 11.5 判断欧拉回路
    • 11.6 字符串排序
    • 11.7 畅通工程
    • 11.8 买房子
    • 11.9 ZOJ字符串
    • 11.10 bg
    • 11.11 完全二叉树查找
    • 11.12 守形数
    • 11.13 围圈报数
    • 11.14 反序数
    • 11.9 ZOJ字符串
    • 11.10 bg
    • 11.11 完全二叉树查找
    • 11.12 守形数
    • 11.13 围圈报数
    • 11.14 反序数

1.STL容器学习

1.1 vector动态数组

vector是C加加语言中的动态数组，内存空间是连续的，适用于插入删除操作少，随机访问频繁的场景。

#定义vector动态数组
vector<int> a;
vector<int> a;
a.push_back(500);//插入数据
a.insert(a.begin(),99);//在对应元素前面插入99
a.erase(a.begin()+1);//删除对应位置得到数据
cout<<a[1];//直接按照数组访问方式来访问
sort(a.begin(),a.end());
a.pop_back();//删除数组末尾元素
a.erase(a.begin()+1,a.begin()+2);//删除区间[i,j)之间的元素 
a.clear()//清空数组内部元素
reverse(a.bgin(),a.end())//反转数组元素

1.1.1 完数VS盈数

完数VS盈数_牛客题霸_牛客网 (nowcoder.com)

本题按照题意即可,主要是使用动态数组处理不定元素的数组较为方便

#include <iostream>
#include<vector>
using namespace std;

int main() {
    vector <int>e;
    vector<int> g;
    for(int nums=2;nums<=60;nums++){
        int res =0;
        for(int i=1;i<nums;i++){
            if(nums%i==0){
                res+=i;
            }
        }
        if(res == nums) e.push_back(nums);
        else{
            if(res>nums) g.push_back(nums);
        }
    }
    cout<<"E:";
    for(int i=0;i<e.size();i++){
       cout<<" "<<e[i];
    }
    cout<<endl;
    cout<<"G:";
    for(int i=0;i<g.size();i++){
       cout<<" "<<g[i];
    }
    cout<<endl;

}

1.2 stack栈

stack<int> st;
st.push(1);//插入元素到栈顶
    cout<<st.top();//访问元素的栈顶
    cout<<endl<<st.size();
    st.pop();//删除栈顶元素
    if(st.empty())
        cout<<"empty";

1.2.1 逆序输出

Zero-complexity Transposition_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<stack>
using namespace std;

int main() {
    int n;
    while(cin>>n){
        stack<int> s;
        int k;
        for(int i=0;i<n;i++){
            cin>>k;
            s.push(k);
        }
        while(!s.empty()){
            cout<<s.top()<<" ";
            s.pop();
        }
        cout<<endl;
    }
}

1.2.2 后缀运算符

简单计算器_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<stack>
#include<string>
#include <map>
using namespace std;
double calculate(double a, double b, char op) {
    double n1 = double(a);
    double n2 = double(b);
    switch (op) {
        case'+':
            return n1 + n2;
            break;
        case '-':
            return n1 - n2;
            break;
        case '*':
            return n1 * n2;
            break;
        case '/':
            return n1 / n2;
            break;
    }
    return 0;
}

double GetNumber(string str, int& index) {
    double number = 0;
    while (str[index] >= '0' && str[index] <= '9') {
        number = number * 10 + str[index] - '0';
        index++;
    }
    return number;
}

int main() {
    string str;
    map<char, int> m;
    m['+'] = 1;
    m['-'] = 1;
    m['*'] = 2;
    m['/'] = 2;

    while (getline(cin, str)) {
        if (str == "0") break;
        stack<double> s1;
        stack<char> op;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] >= '0' && str[i] <= '9') {
                s1.push(GetNumber(str, i));
            } else {
                if (str[i] == ' ')
                    continue;
                else {

                    if (op.empty() || m[op.top()] < m[str[i]]) {
                        op.push(str[i]);
                    } else {
                        while (m[op.top()] >= m[str[i]]) {
                            double b = s1.top();
                            char ch = op.top();
                            op.pop();

                            s1.pop();
                            double a = s1.top();
                            s1.pop();
                            s1.push(calculate(a, b, ch));
                            if (op.empty()) break;
                        }
                        op.push(str[i]);

                    }
                }
            }
        }
        while (!s1.empty()) {
            double b = s1.top();
            char ch = op.top();
            op.pop();
            s1.pop();
            double a = s1.top();
            s1.pop();
            s1.push(calculate(a, b, ch));
            if (s1.size() == 1) {
                printf("%0.2f\n", calculate(a, b, ch));
                break;
            }
        }
    }
}

计算表达式_牛客题霸_牛客网 (nowcoder.com)

另一个版本的后缀运算，代码大同小异

#include <iostream>
#include<stack>
#include<string>
#include <map>
using namespace std;
double calculate(double a, double b, char op) {
    double n1 = double(a);
    double n2 = double(b);
    switch (op) {
        case'+':
            return n1 + n2;
            break;
        case '-':
            return n1 - n2;
            break;
        case '*':
            return n1 * n2;
            break;
        case '/':
            return n1 / n2;
            break;
    }
    return 0;
}

double GetNumber(string str, int& index) {
    double number = 0;
    while (str[index] >= '0' && str[index] <= '9') {
        number = number * 10 + str[index] - '0';
        index++;
    }
    return number;
}

int main() {
    string str;
    map<char, int> m;
    m['+'] = 1;
    m['-'] = 1;
    m['*'] = 2;
    m['/'] = 2;

    while (getline(cin, str)) {
        if (str == "0") break;
        stack<double> s1;
        stack<char> op;
        for (int i = 0; i < str.size(); i++) {
            if (str[i] >= '0' && str[i] <= '9') {
                s1.push(GetNumber(str, i));
                i--;
            } else {
                if (str[i] == ' ')
                    continue;
                else {

                    if (op.empty() || m[op.top()] < m[str[i]]) {
                        op.push(str[i]);
                    } else {
                        while (m[op.top()] >= m[str[i]]) {
                            double b = s1.top();
                            char ch = op.top();
                            op.pop();

                            s1.pop();
                            double a = s1.top();
                            s1.pop();
                            s1.push(calculate(a, b, ch));
                            if (op.empty()) break;
                        }
                        op.push(str[i]);

                    }
                }
            }
        }
        while (!s1.empty()) {
            double b = s1.top();
            char ch = op.top();
            op.pop();
            s1.pop();
            double a = s1.top();
            s1.pop();
            s1.push(calculate(a, b, ch));
            if (s1.size() == 1) {
                printf("%d\n", int(calculate(a, b, ch)));
                break;
            }
        }
    }
}

1.2.3 堆栈的使用

堆栈的使用_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<stack>
using namespace std;

int main() {
    int n;
    int a,b,c;
    while (cin >> n) { // 注意 while 处理多个 case
         stack<int> s;
         char ch;
        for(int i=0;i<n;i++){
            cin>>ch;
            if(ch=='P') {
                cin>>a;
                s.push(a);
            }
            else if(ch=='A'){
                if(!s.empty()){
                    cout<<s.top()<<endl;
                }
                else{
                    cout<<'E'<<endl;
                }
            }

            else{
                if(!s.empty()) s.pop();
                else continue;

            }
        }
    }
}

1.3 queue队列

queue<int> s;//创造队列
 s.push(100);
 s.push(1000);
 s.pop();//删除队首元素
 //front访问对首位置，back访问队尾位置
 cout<<s.front()<<" "<<s.back();

1.3.1 实现循环队列来解决约瑟夫问题

约瑟夫问题I__牛客网 (nowcoder.com)

本题最重要的是怎么用队列实现正常的循环队列

#include <iostream>
#include<queue>
using namespace std;
class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        queue<int> p;
        for(int i=1;i<=n;i++){
            p.push(i);
        }
        while(!p.empty()){
            for(int i=1;i<m;i++){
                p.push(p.front());
                p.pop();
            }
            if(p.size()==1)
                return p.front();
            p.pop();
        }
    }
};

下面这个是书上的约瑟夫改版问题

#include <iostream>
#include<queue>
using namespace std;
int main() {
    int n,p,m;
    cin>>n>>p>>m;
    queue<int> children;
    for(int i=1;i<=n;i++){
        children.push(i);
    }
    for(int i=1;i<p;i++){
        children.push(children.front());
        children.pop();//出栈后再压入栈
    }
    while(!children.empty()){
        for(int i=1;i<m;i++){
            children.push(children.front());
            children.pop();

        }
        if(children.size()==1){
            cout<<children.front()<<endl;
        }
        else{
            cout<<children.front()<<" ";
        }
        children.pop();
    }

}

1.4 priority_queue优先队列

• 头文件：include

• priority_queue<Type, Container, Functional>，Type为元素类型；Container为容器类型，默认为vector，可选 项；Functional为比较方式，默认为降序排列。

• 按照一定方式排列的队列，由二叉堆实现（根据 优先级形成大根堆），每次插入删除的时间复杂度为O(log2n)

• 优先级最高的节点先出队

  //方式一
  priority_queue<int> pq;
  //方式二
  priority_queue<int,vector<int>,greater<int>> pq;//升序排列
  priority_queue<int,vector<int>,less<int>> pq;//降序排列
  pq.top();//队首元素
  pq.pop();//出队
  

  1.4.1 优先队列解决复数集合问题

  复数集合_牛客题霸_牛客网 (nowcoder.com)

  #include<iostream>
  #include<algorithm>
  #include<vector>
  #include<queue>
  #include<cstring>
  #include<string>
  
  using namespace std;
  struct Complex{
      int real;
      int imag;
      Complex(int a, int b): real(a),imag(b){}
      bool operator<(Complex c) const{
      if(real*real+imag*imag==c.real*c.real+c.imag*c.imag){
          return imag>c.imag;
      }
      else{
          return real*real+imag*imag<c.real*c.real+c.imag*c.imag;
  
      }
  
      }
  };
  
  int main() {
      int n;
      string str;
      while(cin>>n){
          priority_queue<Complex> pq;
          while(n--){
              cin>>str;
              if(str=="Pop"){
                  if(pq.empty()){
                      cout<<"empty"<<endl;
                  }
                  else{
                      Complex current  =pq.top();
                      pq.pop();
                      printf("%d+i%d\n",current.real,current.imag);
                      printf("SIZE = %d\n",pq.size());
                  }
              }
  
              else{
                  int a,b;
                  scanf("%d+i%d",&a,&b);
                  pq.push(Complex(a,b));
                  printf("SIZE = %d\n",pq.size());
              }
  
          }
      }
  }
  
  

1.4.2 优先队列解决哈夫曼树问题

搬水果_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<queue>
using namespace std;
int main() {
    int n;
    priority_queue<int, vector<int>, greater<int>>pq;
    while (cin >> n) { // 注意 while 处理多个 case
        if (n == 0) break;
        int a, b;
        while (n--) {
            cin >> a;
            pq.push(a);
        }
        int ans = 0;
        while (pq.size() > 1) {
            a = pq.top();
            pq.pop();
            b = pq.top();
            pq.pop();
            ans += a + b;
            pq.push(a + b);
        }
        cout << ans << endl;
    }
}

1.5 双向链表 list

双向链表的结点同时拥有指向后继和先驱指针的链表，内存空间可以是不连续的，插入和删除频繁，随机访问较少

list<int> mylist;
//要访问顺序容器和关联容器中的元素，需要通过“迭代器（iterator）”进行。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。\
//迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。
list<int>::iterator it;//
int i;
for(i= 0;i<=5;i++){
    mylist.push_back(i);
    if(i==6) printf("yes");
}
cout<<endl;
for(it = mylist.begin();it!=mylist.end();it++){
    cout<<*it<<" ";//it相当于指针
}

1.6 set集合

C++中的集合由二叉搜索树（二叉查找树）实现，集合中的每个元素都只会出现一次，访问元素的时间复杂度为O(log2n)

//lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

//upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
set<int> a;//定义
set<int>::iterator it;
a.insert(100);//插入元素100
a.insert(100);
a.insert(101);
cout<<a.size();
//a.erase(100);//删除元素100
//a.clear();//清空
a.empty();//判断是否为空
cout<<a.size()<<endl;
it = a.find(100);//返回一个迭代器指向键值100
it = a.lower_bound(80);//返回键值不小于80的第一个元素
cout<<*it<<endl;
it = a.upper_bound(200);
cout<<*it<<endl;

1.7 map映射容器

• 用红黑树实现，会对键值进行自动排序,在某些时候排序可以很方便解决某些问题(不排序的map称为unordered_map)

• 如果没有查找到对应字符串的话value为字符串返回空串(“”),为数值时返回0，为指针时返回nullptr(C++推荐使用nullptr指针)

#include <cstdio>
#include <iostream>
#include <map>

using namespace std;

map <string,int> myMap;//内部按照关键字进行排序，底层为红黑树

int main(){
    //插入，添加元素
    myMap["Emma"]=67;
    myMap.insert(pair<string,int>("Bob",72));

    //查
    cout<<myMap["Emma"]<<endl;
    cout<<myMap.at("Bob")<<endl;

    //删除
    myMap.erase("Emma");

    map<string,int>::iterator it;
    for(it=myMap.begin();it!=myMap.end();it++){
        cout << it->first <<" "<<it->second<<endl;
    }

    //查找
    it=myMap.find("Bob");//返回迭代器
    if(it!=myMap.end()){
        return 0;//未找到
    }

    cout<<myMap.size();

    myMap.clear();//晴空

}

1.7.1 map的应用

查找学生信息_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<map>
using namespace std;
struct student {
    string name;
    string sex;
    int age;
    student(string name, string sex, int age): name(name), sex(sex), age(age) {}
};
int main() {
    int a, b;
    map<string, student*> m;
    string name, key, sex;
    int age;
    while (cin >> a ) { // 注意 while 处理多个 case
        if (a == 0) break;
        m.clear();
        while (a--) {
            cin >> key >> name >> sex >> age;
            m[key] = new student(name, sex, age);
        }
        cin >> b;
        student* tmp = nullptr;
        while (b--) {
            cin >> key;
            tmp = m[key];
            if (tmp == nullptr) {
                cout << "No Answer!" << endl;
            } else {
                cout << key << " " << tmp->name << " " << tmp->sex << " " << tmp->age << endl;
            }
        }
    }
}

1.7.2 统计字符串出现次数//

子串计算_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<map>
using namespace std;

int main() {
    int a, b;
    map<string, int> m;
    string str;
    while (cin >> str) {
        m.clear();
        int n = str.size();
        //学会如何生成所有字串
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                string sub = str.substr(j, i - j);
                m[sub] += 1;
            }
        }
        map<string, int>::iterator it;
        for (it = m.begin(); it != m.end(); it++) {
//        if(it->first=="") continue;
            if (it->second > 1)
                cout << it->first << " " << it->second << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")

1.7.3 查询分数

统计同成绩学生人数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<map>
using namespace std;

int main() {
    int n;
    map<int,int>m;
    int score;
    while (cin >> n) { // 注意 while 处理多个 case
        if(n==0) break;
        m.clear();
        while(n--){
            cin>>score;
            m[score]+=1;
        }
        cin>>score;
        cout<<m[score]<<endl;
    }
}

1.7.4 开门人 和关门人

开门人和关门人_牛客题霸_牛客网 (nowcoder.com)

本题利用map会给键值自动排序的功能即可解决

#include <iostream>
#include<map>
using namespace std;

int main() {
    int n;
    string code, start, end;
    map<string, string> m1;
    map<string, string> m2;
    while (cin >> n) { // 注意 while 处理多个 case
        while (n--) {
            cin >> code >> start >> end;
            m1[start] = code;
            m2[end] = code;
        }
        map<string, string>::iterator it;
        it = m1.begin();
        cout << it->second << " ";
        it = m2.end();
        it--;
        cout << it->second << endl;
    }
}/
    

1.7.5 谁是你的潜在朋友

谁是你的潜在朋友_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<map>
#include<vector>
using namespace std;
int main() {
    int n, m;
    map<int, int> table;
    vector<int> vec;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        int num;
        while (n--) {
            cin >> num;
            vec.push_back(num);
            table[num] += 1;
        }
        for (int i = 0; i < vec.size(); i++) {
            int res = table[vec[i]] - 1;
            if (res == 0)cout << "BeiJu" << endl;
            else cout << res << endl;
        }
    }
}

1.8 sort排序函数

#include<algorithm>//需要引用<algorithm>头文件
bool compare(point p1, point p2){
    return p1.x>p2.x;//按x从大到小排序
}
list<point> l1;
sort(l1.begin(),l1.end(),compare);

1.9 next_permutation函数

STL提供的求再当前数组元素排列下求下一个排列组合的函数，每次使用next_permutation都会将元素按照排列重新放入对应位置，当按照字典序的大小没有下一个排列的时候返回false否则返回true

    int num[3] = {1,2,3};
    do{
        cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
    }while(next_permutation(num, num+3));
int num[3] = {3, 2, 1};
    do{
        cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
    }while(prev_permutation(num, num+3));//prev与他返回则完全相反

2.算法学习

2.1 递归实现求元素的全排列

int num[3] = {3, 2, 1};
int Perm(int begin, int end){
    int i;
    if(begin == end){
        cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
    }
    else{
        for(i=begin;i<=end;i++){
            swap(num[begin],num[i]);
            Perm(begin+1,end);
            swap(num[begin],num[i]);//交换回去开始下一波
        }
    }

}


int main()
{
    clock_t start,end;
    start = clock();
    Perm(0,2);
    end=clock();
    cout<<endl<<(double)(end - start)/CLOCKS_PER_SEC;
}

2.2 反序数

设N是一个四位数，它的9倍恰好是其反序数（例如：1234的反序数是4321）,求N的值

#include <iostream>
using namespace std;
int reverse(int n){
    int revx =0;
    while(n!=0){
        revx*=10;
        revx+=n%10;
        n/=10;
    }
    return revx;
}

int main() {
    for(int i=0;i<=256;i++){
        int k=(i*i);
        if(k==reverse(k))
        cout<<k<<endl;
    }

2.3百鸡问题

百鸡问题_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;

void solve(int n){
    int i,j,k;
    for(i=0;i<=100;i++){
        for(j=0;j<=100-i;j++){//不能变成负数记得加上100-i
            k=100-i-j;
            if((i*15+j*9+k)<=n*3)
            printf("x=%d,y=%d,z=%d\n",i,j,k);
            
        }
    }
}

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        solve(n);
    }
}

2.4 火鸡账单

Old Bill_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;
void solve(int n, int x, int y, int z){
    int maxSum =0;
    int maxi=0,maxj=0;
    for(int i=1;i<=9;i++){
        for(int j=0;j<9;j++){
            int sum=(i*10000+x*1000+y*100+z*10+j);
            if(sum%n==0){
                sum /=n;
                if(sum>maxSum){
                    maxSum = sum;
                    maxi=i;
                    maxj=j;
                }
            }
        }

    }
    if(maxSum == 0)
        cout<<0;
    else{
    printf("%d %d %d",maxi,maxj,maxSum);}
}
int main() {
    int n,x,y,z;
    while (cin >> n>>x>>y>>z) { // 注意 while 处理多个 case
        solve(n, x, y, z);
    }
}
// 64 位输出请用 printf("%lld")

2.5 今年的第几天

今年的第几天？_牛客题霸_牛客网 (nowcoder.com)

#include <cstdio>
#include <iostream>
using namespace std;

void solve(int year, int month, int day){
int data[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//闰年的判断思路是如果年份不能被100整除，却能被4整除或400整除
if((year%100!=0&&year%4==0)||year%400==0) data[2] = 29;
int res =0;
for(int i=0;i<month;i++){
    res+=data[i];
}
res+=day;
cout<<res<<endl;
}

int main() {
    int year,month,day;
    while(scanf("%d %d %d",&year, &month, &day)!=EOF){
        solve(year, month, day);
    }

}
// 64 位输出请用 printf("%lld")

2.6打印日期

打印日期_牛客题霸_牛客网 (nowcoder.com)

#include <cstdio>
#include <iostream>
using namespace std;

void solve(int year, int date){
int data[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
if((year%100!=0&&year%4==0)||year%400==0) data[2] = 29;
int res =0;
int i=0;
for(i=1;i<=12;i++){
    if(date-data[i]>0)
    date -=data[i];
    else break;
}
printf("%d-%02d-%02d\n", year,i,date);

}

int main() {
    int year,day;
    while(cin>>year>>day){
        solve(year,  day);
    }

}
// 64 位输出请用 printf("%lld")

2.7 日期累加

日期累加_牛客题霸_牛客网 (nowcoder.com)

#include <cstdio>
#include <iostream>
using namespace std;

void solve(int year, int month, int day, int addDay) {
    int data[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if ((year % 100 != 0 && year % 4 == 0) || year % 400 == 0) data[2] = 29;
    int res = 0;
    int i = 0;
    addDay+=day;
    do{

    for (i = month; i <= 12; i++) {
        if (addDay - data[i] > 0)
            addDay -= data[i];
        else break;
    }
    if(i>12) {
        month =1;
        year+=1;
        //在改变年份的时候记得修改2月的日期！！！！！
        if ((year % 100 != 0 && year % 4 == 0) || year % 400 == 0)          data[2] = 29;
        else data[2] =28;
        }
    
    }while(i>12);

    printf("%d-%02d-%02d\n", year, i, addDay);

}

int main() {
    int num;
    cin>>num;
    int year, month, day,addDay;
    for(int i=0;i<num;i++){
    cin >> year >>month>> day>> addDay;
    solve(year,  month, day, addDay);   
    }

}
// 64 位输出请用 printf("%lld")

2.8 日期差值_牛客题霸_牛客网 (nowcoder.com)

#include <cstdio>
#include <iostream>
using namespace std;

void solve(int year, int month, int day, int year2, int month2, int day2) {
    int data[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if ((year % 100 != 0 && year % 4 == 0) || year % 400 == 0) data[2] = 29;
    int res = 0;
    int i = 0;
    res -= day;
    while (year != year2) {
        for (i = month; i <= 12; i++) {
            res += data[i];
        }
        if (year != year2) {
            month = 1;
            year += 1;
            //在改变年份的时候记得修改2月的日期！！！！！
            if ((year % 100 != 0 && year % 4 == 0) ||
                    year % 400 == 0)          data[2] = 29;
            else data[2] = 28;
        }

    }
    if (year == year2) {

        while (month < month2) {
            res += data[month];
            month++;
        }
        res += (day2 + 1);

    }
    cout << res;


    // printf("%d-%02d-%02d\n", year, i, addDay);

}

int main() {
    int num1, num2;
    while (cin >> num1 >> num2) {
        int year1 = num1 / 10000;
        num1 %= 10000;
        int month1 = num1 / 100;
        int day1 = num1 % 100;
        int year2 = num2 / 10000;
        num2 %= 10000;
        int month2 = num2 / 100;
        int day2 = num2 % 100;
        
        solve(year1, month1, day1, year2, month2, day2);

    }


}
// 64 位输出请用 printf("%lld")

2.9 Day of Week_牛客题霸_牛客网 (nowcoder.com)

#include <cstdio>
#include <iostream>
#include<string>
#include<map>
using namespace std;

int solve(int year, int month, int day, int year2, int month2, int day2) {
    int data[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if ((year % 100 != 0 && year % 4 == 0) || year % 400 == 0) data[2] = 29;
    int res = 0;
    int i = 0;
    res -= day;
    while (year != year2) {
        for (i = month; i <= 12; i++) {
            res += data[i];
        }
        if (year != year2) {
            month = 1;
            year += 1;
            //在改变年份的时候记得修改2月的日期！！！！！
            if ((year % 100 != 0 && year % 4 == 0) ||
                    year % 400 == 0)          data[2] = 29;
            else data[2] = 28;
        }

    }
    if (year == year2) {

        while (month < month2) {
            res += data[month];
            month++;
        }
        res += (day2 + 1);

    }
    return res;


    // printf("%d-%02d-%02d\n", year, i, addDay);

}

int main() {
    int num1, num2;
    map<string, int> m;
    map<int, string> week;
//    一月 January，缩写Jan
//    二月 February，缩写Feb
//    三月 March，缩写Mar
//    四月 April，缩写Apr
//    五月 May，缩写May
//    六月 June，缩写Jun
//    七月 July，缩写Jul
//    八月 August，缩写Aug
//    九月 September，缩写Sep/Sept
//    十月 October，缩写Oct
//    十一月 November，缩写Nov
//    十二月 December，缩写Dec

    m["January"] = 1;
    m["February"] = 2;
    m["March"] = 3;
    m["April"] = 4;
    m["May"] = 5;
    m["June"] = 6;
    m["July"] = 7;
    m["August"] = 8;
    m["September"] = 9;
    m["October"] = 10;
    m["November"] = 11;
    m["December"] = 12;
    week[1] = "Monday";
    week[2] = "Tuesday";
    week[3] = "Wednesday";
    week[4] = "Thursday";
    week[5] = "Friday";
    week[6] = "Saturday";
    week[0] = "Sunday";
    int day, year;
    string month;
    while (cin >> day >> month >> year) {
        int m1 = m[month];
        //1969年12月29日是星期一
        int days = solve( 1969, 12, 29, year, m1, day);
        days %= 7;
        cout << week[days] << endl;

    }


}
// 64 位输出请用 printf("%lld")

2.10剩下的树_牛客题霸_牛客网 (nowcoder.com)

本题有一个很靠谱的思路，就是利用bool数组来处理可能重复处理的区间，暴力解法容易想到

#include <iostream>
using namespace std;
#define MAX 10001
int main() {
    bool tree[MAX];
    int i,j;
    int L,M;
    cin>>L>>M;
    int num =L+1;
    int left,right;
    for(i=0;i<=L;i++){
        tree[i]=true;
    }
    for(j=0;j<M;j++){
        cin>>left>>right;
        for(i=left;i<=right;i++){
            if(tree[i]){//如果以及被移除便不再处理
                tree[i] = false;
                num--;
            }
        }
    }
    cout<<num;
}
// 64 位输出请用 printf("%lld")

2.11xxx定律_牛客题霸_牛客网 (nowcoder.com)

本题按照题设做即可，不难

#include <iostream>
using namespace std;

void solve(int n){
    int num=0;
    while(n!=1){
        num++;
    if(n%2==0){
        n/=2;

    }
    else{
        n=n*3+1;
        n/=2;
    }

    }
    cout<<num<<endl;
}


int main() {
    int a;
    while (cin >> a ) { // 注意 while 处理多个 case
        solve(a);
    }
}
// 64 位输出请用 printf("%lld")

2.12 排序题

排序_牛客题霸_牛客网 (nowcoder.com)

//偷懒使用sort算法
#include <iostream>
#include<algorithm>
using namespace std;
#define MaxSize 101
int main() {
 int a[MaxSize]={0};
 int n;
 while(cin>>n){
 for(int i=0;i<n;i++){
     cin>>a[i];
 }
 sort(a,a+n);
 for(int i=0;i<n;i++){
     cout<<a[i]<<" ";
 }

 cout<<endl;
 }


}

2.13带学号的成绩排序问题

成绩排序_牛客题霸_牛客网 (nowcoder.com)

本题 尤其注意当成绩相同的时候应该要比较学号

#include <iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

typedef struct{
    int num;
    int score;
}students;

bool compare(students s1, students s2){
    if(s1.score==s2.score) 
        return s1.num<s2.num; 
    return s1.score<s2.score;

}

int main() {
    vector<students> vec;
    int num;
    while (cin >> num) { // 注意 while 处理多个 case
    for(int i=0;i<num;i++){
        students stu;
        cin>>stu.num>>stu.score;
        vec.push_back(stu);
    }
    sort(vec.begin(),vec.end(),compare);
    for(int i=0;i<vec.size();i++){
    cout<<vec[i].num<<" "<<vec[i].score<<endl;

    }
        
    }
}

2.14 考虑输入次序的学生成绩排序

成绩排序_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

typedef struct {
   string name;
    int score;
    int order;
} students;
//升序
bool compare1(students s1, students s2) {
    if(s1.score==s2.score)
        return s1.order<s2.order;//如果成绩相同按照次序先后排
    return s1.score < s2.score;

}
//降序
bool compare0(students s1, students s2) {
    if(s1.score==s2.score)
        return s1.order<s2.order;
    return s1.score > s2.score;


}

int main() {
    vector<students> vec;
    int num,method;
    while (cin >> num>>method) { // 注意 while 处理多个 case
        //cin>>method;
        vec.clear();//针对多次输入记得即使清空数据
        for (int i = 0; i < num; i++) {
            students stu;
            cin >> stu.name >> stu.score;
            stu.order=i;
            vec.push_back(stu);
        }
        if(method==0)
            sort(vec.begin(), vec.end(), compare0);
        else sort(vec.begin(), vec.end(), compare1);
        for (int i = 0; i < vec.size(); i++) {
            cout << vec[i].name << " " << vec[i].score << endl;
        }

    }
}

2.15特殊排序

特殊排序_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

typedef struct {
   string name;
    int score;
} students;
//升序
bool compare1(students s1, students s2) {
    return s1.score < s2.score;

}
//降序
bool compare0(students s1, students s2) {
    return s1.score > s2.score;

}

int main() {
    vector<students> vec;
    int num,method;
    while (cin >> num) { // 注意 while 处理多个 case
        cin>>method;
        for (int i = 0; i < num; i++) {
            students stu;
            cin >> stu.name >> stu.score;
            vec.push_back(stu);
        }
        if(method==0)
            sort(vec.begin(), vec.end(), compare0);
        else sort(vec.begin(), vec.end(), compare1);
        for (int i = 0; i < vec.size(); i++) {
            cout << vec[i].name << " " << vec[i].score << endl;
        }

    }
}

2.16 整数奇偶排序（简单）

整数奇偶排序_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compare(int a, int b){
    return a>b;
}

int main() {
    int b,i,j;
    int a[10]={0};
    vector<int> vec1;//存放奇数的数组
    vector<int> vec2;
    while (cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]>>a[7]>>a[8]>>a[9]) { // 注意 while 处理多个 case
    for(i=0;i<10;i++){
        if(a[i]%2!=0)
        vec1.push_back(a[i]);
        else{
            vec2.push_back(a[i]);
        }
    }
    sort(vec1.begin(), vec1.end(),compare);
    sort(vec2.begin(),vec2.end());
    for(i=0;i<vec1.size();i++)
        cout<<vec1[i]<<" ";
    for(i=0;i<vec2.size();i++)
        cout<<vec2[i]<<" ";
    cout<<endl;
        
    }
}
// 64 位输出请用 printf("%lld")

2.17 小白鼠排序

小白鼠排队_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

typedef struct {
    string color;
    int weight;
} mouse;

bool compare1(mouse s1, mouse s2) {
    return s1.weight > s2.weight;

}

int main() {
    vector<mouse> vec;
    int num;
    while (cin >> num ) { // 注意 while 处理多个 case
        vec.clear();//针对多次输入记得即使清空数据
        for (int i = 0; i < num; i++) {
            mouse m;
            cin >> m.weight >> m.color;
            vec.push_back(m);
        }
        sort(vec.begin(), vec.end(),compare1);

        for (int i = 0; i < vec.size(); i++) {
            cout << vec[i].color << endl;
        }

    }
}

2.18 奥运排序问题

奥运排序问题_牛客题霸_牛客网 (nowcoder.com)

本题有一个很重要的技巧，就是在可能出现名次并列的情况使用逐个比较，而不是直接排序

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
// 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例
struct country {
    float gold;
    float reward;
    float numOfPeoples;
    float goldScale;
    float rewardScale;
    int rank[4] = {0};
};
int main() {
    int N, M;
    int id;
    vector<country> vec;
    vector<country> resVec;
    while (cin >> N >> M) { // 注意 while 处理多个 case
        vec.clear();
        resVec.clear();
        for (int i = 0; i < N; i++) {
            country c;
            cin >> c.gold >> c.reward >> c.numOfPeoples;
			//使用下面这个才能过的原因应该是在检查点中由人数为0和奖牌数为0的输入数据
            //为了规避将除数为0的bug使用了下面这个方式
            c.goldScale = c.gold ? c.gold / c.numOfPeoples : 0 ;
            c.rewardScale =  c.reward ? c.reward / c.numOfPeoples : 0 ;
            vec.push_back(c);
        }
        for (int i = 0; i < M; i++) {
            cin >> id;
            resVec.push_back(vec[id]);
        }
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                if (resVec[i].gold < resVec[j].gold)
                    resVec[i].rank[0] += 1;
                if (resVec[i].reward < resVec[j].reward)
                    resVec[i].rank[1] += 1;
                if (resVec[i].goldScale < resVec[j].goldScale)
                    resVec[i].rank[2] += 1;
                if (resVec[i].rewardScale < resVec[j].rewardScale)
                    resVec[i].rank[3] += 1;
            }
        }

        for (int i = 0; i < M; i++) {
            int min = 0;
            for (int j = 0; j < 4; j++) {
                if (resVec[i].rank[j] < resVec[i].rank[min])
                    min = j;
            }
            //排名:排名方式
            printf("%d:%d\n", resVec[i].rank[min] + 1, min + 1);

        }
        cout << endl;

    }
}

2.19多次查找

为了在规定的时间内多次查找数据，本次使用二分查找(使用递归形式的时间太久，这里使用循环方式的)

查找_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXSIZE 101`
bool binarySearch(int a[], int left, int right, int  num) {
    while(left<=right){
        int mid= (left+right)/2;
        if(a[mid]<num) left = mid+1;
        else if(a[mid]>num){
            right = mid-1;
        }
        else{
            return true;
        }
    }
    return false;

}
int main() {
    int a[101] = {0};
    int b[101] = {0};
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        int num, i, k;
        for (i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a, a + n);
        cin >> num;
        for (i = 0; i < num; i++) {
            cin >> k;
            if (binarySearch(a, 0, n - 1, k)) {
                cout << "YES" << endl;
            } else cout << "NO" << endl;
        }

    }
}

2.20找最小数

找最小数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct  stu {
    int x, y;
};
bool compare(stu d1, stu d2) {
    if (d1.x == d2.x) {
        return d1.y < d2.y;
    }
    return d1.x < d2.x;
}

int main() {
    int n;
    vector<stu> vec;
    while (cin >> n) {
        vec.clear();
        for (int i = 0; i < n; i++) {
            stu d;
            cin >> d.x >> d.y;
            vec.push_back(d);
        }
        sort(vec.begin(), vec.end(), compare);
        cout << vec[0].x << " " << vec[0].y << endl;
    }
}

2.21 找位置

找位置_牛客题霸_牛客网 (nowcoder.com)

本题为寻找多个重复的元素出现的位置，下次再次遇到这种情况可以使用逐一比较的方法

#include <string>
#include <iostream>
using namespace std;
int main() {
    string str;
    while(cin>>str){
        for(int i=0;i<str.size();i++){
            if(str[i]=='*') continue;
            int tmp=i;
            for(int k=i+1;k<str.size();k++){
                if(str[i]==str[k]){
                    str[k]='*';//修改代表访问过
                    cout<<str[i]<<":"<<tmp<<",";
                    tmp=k;
                }
            }
            //重复
            if(tmp!=i){
                cout<<str[i]<<":"<<tmp<<endl;
            }
        }
    }
}

3.字符串习题

*字符串的一些用法

s

3.1 特殊乘法

本题中需要注意的一点是，怎么将字符9转换成整数9！！！！

特殊乘法_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>

using namespace std;

int main() {
    string a,b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        int num=0;
        for(int i=0;i<a.size();i++){

            for(int j=0;j<b.size();j++){

                num+=(a[i]-'0')*(b[j]-'0');
            }
        }
        cout<<num<<endl;
    }

}

3.2字符转换

密码翻译_牛客题霸_牛客网 (nowcoder.com)

本题重点：如何获取一整行的字符串输入，和判断字符是否是字母

#include <iostream>
#include<string>
using namespace std;

int main() {
    // int a, b;
    string a;
    while (getline(cin,a)) { // 注意 while 处理多个 case
        for(int i=0;i<a.size();i++){

            if((a[i]>='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z')){

                if(a[i]=='z')
                    a[i]='a';
                else if(a[i]=='Z')
                    a[i]='A';
                else{
                      a[i]+=1;
                               }
            }
        }
        cout<<a<<endl;
    }
}

3.3 密码转换

简单密码_牛客题霸_牛客网 (nowcoder.com)

本题主要是看穿规律，然后利用取余规律来进行转换

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str;
    while (getline(cin,str)) { // 注意 while 处理多个 case
        if(str=="ENDOFINPUT"){
            break;
        }
        getline(cin,str);//密文
        for(int i=0;i<str.size();i++){
            if(str[i]>='A'&&str[i]<='Z'){
            str[i] =((str[i]-'A'-5+26)%26) +'A';//将数字转换成字母表中循环向前移动五位
            }
        }
        cout<<str<<endl;
        getline(cin,str);
        
    }
}

3.4 计算字符出现次数

本题注意一个函数memset初始化数组的函数(头文件为#include)

统计字符_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<cstring>//memset的头文件
#include<cstdio>
using namespace std;
#define MAXIZE 1000
int main() {
    string a;
    string str;
    int nums[MAXIZE]={0};
    while (getline(cin,a)) { 
        // 注意 while 处理多个   
        if(a=="#") break;
        memset(nums,0,sizeof (nums));//初始化整个数组
        
        getline(cin,str);
        for(int j=0;j<str.size();j++){
            nums[str[j]]++;
        }
        for(int i=0;i<a.size();i++){

            cout<<a[i]<<" "<<nums[a[i]]<<endl;
        }
    }
}

3.5 统计大写字母出现次数

本题依然是利用字母对应数组序号的思想

字母统计_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<cstring>
using namespace std;

int main() {
    string a;
    int nums[26];
    while (getline(cin, a)) { // 注意 while 处理多个 case
        memset(nums, 0, sizeof (nums));
        for (int i = 0; i < a.size(); i++) {
            if (a[i] >= 'A' && a[i] <= 'Z') {
                nums[a[i] - 'A']++;
            }
        }
        char ch = 'A';
        for (int i = 0; i < 26; i++) {
           
            cout << ch << ":" << nums[i] << endl;
             ch ++;
        }

    }
}

3.6 SKEW数

本题为傻瓜题照着题目说的写即可。

skew数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<math.h>
using namespace std;

int main() {
    string str;
    int x, k;
    while (cin >> str) { // 注意 while 处理多个 case
        int res = 0;
        for (int i = 0; i < str.size(); i++) {
            x = str[i] - '0';
            k = str.size() - i;
            res += (str[i] - '0') * (pow(2, k) - 1);
        }
        cout << res << endl;
    }
}

3.7 查找字符串

单词替换_牛客题霸_牛客网 (nowcoder.com)

本题主要是使用了string的find,erase,insert各种操作

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s, a, b;
    getline(cin, s);
    getline(cin, a);
    getline(cin, b);
    s = " " + s + " ";
    a = " " + a + " ";
    b = " " + b + " ";
    int start;
    while (1) {
        start = s.find(a);
        if (start == string::npos)
            break;
        else {
            //本题主要是字符串的综合应用
            s.erase(start, a.length());
            s.insert(start, b);
        }
    }
    int n = s.size();
    cout << s.substr(1, n - 2);
    return 0;
}

3.8 将单词首字母转换成大写

本题按照题意来写即可，注意怎么小写转换成大写

首字母大写_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>

using namespace std;

int main() {
    string str;
    while(getline(cin,str)){
        char ch ='a';
        for(int i=0;i<str.size();i++){
            if(str[i]>='a'&&str[i]<='z')
          if(i==0||str[i-1]==' '||str[i-1]=='\t'||str[i-1]=='\r'||str[i-1]=='\n')
                str[i]=(str[i]-'a')+'A';
        }
        cout<<str<<endl;
    }
}

3.9 浮点数加法

浮点数加法_牛客题霸_牛客网 (nowcoder.com)

这里先将两个字符串补齐，再利用进位机制来处理即可。

//这里我先将两个字符串小数点前后补齐到相同的长度，再一一对位相加 (这里记得进位
#include <iostream>
#include<string>
using namespace std;

int main() {
    string a,b;
    string longer,shorter;
    while (getline(cin,a)) { // 注意 while 处理多个 case
        getline(cin,b);

        int find1=a.find('.');
        int find2 = b.find('.');//小数点位置
        if(find1<find2){
            longer = b;
            shorter =a;
        }
        else{
            longer =a;
            shorter = b;
        }//为了方便最高一位进位，在最高位前添加一位
        longer.insert(0,"0");
       do{
           //补全小数点前的0
            shorter.insert(0,"0");
            find1=longer.find('.');
            find2 = shorter.find('.');
        } while(find1!=find2);

        if(longer.size()<shorter.size()){
            swap(longer,shorter);
        }
        while(longer.size()!=shorter.size()){
            shorter.insert(shorter.size(),"0");
		  //补全小数点后的0
        }

        int flag=0;
        for(int i=longer.size()-1;i>=0;i--){
            if(longer[i]=='.') continue;
            int res =(longer[i]-'0')+(shorter[i]-'0')+flag;
            flag=res/10;
            res%=10;
            longer[i]=res+'0';
        }
        if(flag!=0){
            longer[0]=flag+'0';
            cout<<longer;

        }
        else{//没有进位的话直接输出
            cout<<longer.substr(1,longer.size());
        }
    }
}

3.10 使用KMP求字符串完全匹配次数

#include <iostream>
#include<string>
using namespace std;
const int MAXM =1000;
int nextTable[MAXM];
void GetNextTable(string pattern){
    int m = pattern.size();
    int j=0;
    nextTable[j]=-1;
    int i=nextTable[j];
    for(j=0;j<m;j++){
        if(i==-1||pattern[i]==pattern[j]){
            i++;
            j++;
            nextTable[j]=i;
        }
        else{
            i=nextTable[i];
        }

    }
    return;
}

int KMP(string text, string pattern){
   GetNextTable(pattern);
   int n = text.size();
   int m = pattern.size();
   int number =0;
   int i,j;
   i=j=0;
   while(i<n){
       if(j==-1||text[i]==pattern[j]){
           i++;
           j++;
       }
       else{
           j=nextTable[j];
       }
       if(j==m){
           number++;
           j=nextTable[j];
       }
   }
   return number;
}
int main() {
    string str1 ="hello world";
    string str2="l";
    cout<<KMP(str1, str2);

}

4.特殊的数学问题

4.1十进制转二进制

二进制数_牛客题霸_牛客网 (nowcoder.com)

本题的重点是如何将十进制数转换成二进制数，使用栈的特性便可以轻松解决。

#include <iostream>
#include<stack>
using namespace std;
int main() {
    int a;
    stack<int> s;
    while(cin>>a){
        while(a!=0){
            s.push(a%2);
            a/=2;
        }
        while(!s.empty()){
            cout<<s.top();
            s.pop();
        }
        cout<<endl;
    }
}

4.2 使用大数除法的十进制转二进制

本题的数字过长所以必须使用字符串来完成大数除法

进制转换_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<stack>
#include<string>
using namespace std;

string Divide(string str, int x) {
    int remainder = 0;
    for (int i = 0; i < str.size(); i++) {
        int current = remainder * 10 + str[i] - '0';
        str[i] = current / x + '0';
        remainder = current % x;
    }
    int pos = 0;
    while (str[pos] == '0')
        pos++;
    return str.substr(pos);
}

int main() {
    string str;
    stack<int> s;
    while (cin >> str) {
        while (str.size() != 0) {
            int last = str[str.size() - 1] + '0';
            s.push(last %= 2);
            str = Divide(str, 2);
        }
        while (!s.empty()) {
            cout << s.top();
            s.pop();
        }
        cout << endl;
    }
}

4.3 二进制转十进制

这里涉及到了大数的加法和乘法，这里我们需要用字符串来一一实现

进制转换_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<vector>
#include<string>
#include<math.h>
using namespace std;

string Divide(string str, int x) {
    int remainder = 0;
    for (int i = 0; i < str.size(); i++) {
        int current = remainder * 10 + str[i] - '0';
        str[i] = current / x + '0';
        remainder = current % x;
    }
    int pos = 0;
    while (str[pos] == '0')
        pos++;
    return str.substr(pos);
}
string Multiple(string str, int x){
    int carry = 0;
    for(int i=str.size()-1;i>=0;i--){
        int current = x*(str[i]-'0')+carry;
        str[i] = current%10+'0';
        carry = current/10;
    }
    if(carry!=0){
        str="1"+str;
    }
    return str;

}
string Add(string str, int x){
    int carry=x;
    for(int i=str.size()-1;i>=0;i--){
        int current =(str[i]-'0')+carry;
        str[i] = current%10+'0';
        carry = current/10;
    }
    if(carry!=0){
        str = "1"+str;
    }
    return str;
}
int main() {
    string str;
    vector<int> s;
    while (cin >> str) {
        long long res = 0;
        while (str.size() != 0) {
            int last = str[str.size() - 1] + '0';
            s.push_back(last % 2);
            str = Divide(str, 2);
        }
        int flag = 0;
        string answer="0";
        for(int i=0;i<s.size();i++) {

            answer = Multiple(answer,2);
            answer = Add(answer,s[i]);

        }
        cout << answer << endl;
    }
}

4.4 M进制转换成N进制

本题主要是 注意可能的进制用字母表示

#include <iostream>
#include <stack>
#include<string>
using namespace std;

int charToInt(char ch){
    if(ch>='0'&&ch<='9'){
        return ch-'0';
    }
    else{
        return ch-'A'+10;
    }
}
char intToChar(int n){
    if(n<=9) return n+'0';
    else return n-10+'a';
}
int main() {
    int a, b;
    string str;
    stack<char> s;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        cin>>str;
        long long ans =0;//这里记得使用long long数据类型
        for(int i=0;i<str.size();i++){
            //转换成 十进制
            ans = ans*a+charToInt(str[i]);
        }
        if(ans ==0) cout<<ans<<endl;
        while(ans!=0){
            int num = ans%b;
            s.push(intToChar(num));
            ans/=b;
        }
         while (!s.empty()) {
            cout << s.top();
            s.pop();
        }
        cout << endl;
    }
}

4.5 十进制转八进制

八进制_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<stack>
using namespace std;
int main() {
    int a;
    stack<int> s;
    while(cin>>a){
        while(a!=0){
            s.push(a%8);
            a/=8;
        }
        while(!s.empty()){
            cout<<s.top();
            s.pop();
        }
        cout<<endl;
    }
}

4.6 A+B 转m进制

又一版 A+B_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<stack>
using namespace std;
int main() {
    long long a,b,m;//使用长整型防止超过表示范围
    stack<int> s;
    while (cin >>m) {
        if(m==0) break;
        cin>> a>>b;
        a+=b;
        if(a==0)
        cout<<0;
        while (a != 0) {
            s.push(a % m);
            a /= m;
        }
        while (!s.empty()) {
            cout << s.top();
            s.pop();
        }
        cout << endl;
    }
}

4.7 十六进制转十进制

进制转换_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include <string>
using namespace std;
int charToInt(char ch){
    if(ch>='0'&&ch<='9')
     return ch-'0';
     else{
        return ch-'A'+10;
     }
}
int main() {
    string str;
    long long ans =0;
    while(cin>>str){
        ans=0;
        str.erase(str.begin(), str.begin()+2);//删除开头的字符
        for(int i=0;i<str.size();i++){
            ans=ans*16+charToInt(str[i]);

        }
        cout<<ans<<endl;
    }
}

4.8 数制转换

数制转换_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include <stack>
#include<string>
using namespace std;

int charToInt(char ch) {
    if (ch >= '0' && ch <= '9') {
        return ch - '0';
    } else {
        if(ch>='A'&&ch<='Z')
            return ch - 'A' + 10;
        else
            return ch-'a'+10;
    }
}
char intToChar(int n) {
    if (n <= 9) return n + '0';
    else return n - 10 + 'A';
}
int main() {
    int a, b;
    string str;
    stack<char> s;
    while (cin >> a >>str>> b) { // 注意 while 处理多个 case
        long long ans = 0; //这里记得使用long long数据类型
        for (int i = 0; i < str.size(); i++) {
            //转换成 十进制
            ans = ans * a + charToInt(str[i]);
        }
        if (ans == 0) cout << ans << endl;
        while (ans != 0) {
            int num = ans % b;
            s.push(intToChar(num));
            ans /= b;
        }
        while (!s.empty()) {
            cout << s.top();
            s.pop();
        }
        cout << endl;
    }
}

4.9 最大公约数

最大公约数_牛客题霸_牛客网 (nowcoder.com)

本题利用一个特殊的公式求最大公约数

#include <iostream>
using namespace std;
//求最大公约数
int gcd(int a, int b){
    if(b==0) return a;
    else{
        return gcd(b,a%b);
    }
}
int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        cout << gcd(a,b)<< endl;
    }
}

4.10 最小公倍数

a,b的最小公倍数是a和b的乘积除以最大公约数。

#include <iostream>
using namespace std;
//求最大公约数
int gcd(int a, int b){
    if(b==0) return a;
    else{
        return gcd(b,a%b);
    }
}
//求最小公倍数
int lcm(int a, int b){
    int n=gcd(a,b);
    return (a*b)/n;

}
int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        cout << lcm(a,b)<< endl;
    }
}

4.11 判断最简真分数

最简真分数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<vector>
using namespace std;
//求最大公约数
int gcd(int a, int b) {
    if (b == 0) return a;
    else {
        return gcd(b, a % b);
    }
}
//求最小公倍数
int lcm(int a, int b) {
    int n = gcd(a, b);
    return (a * b) / n;

}
int main() {
    int n;
    vector<int> vec;
    int num = 0;
    while (cin >> n) { // 注意 while 处理多个 case
        if (n == 0) break;
        vec.clear();
        num = 0;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            vec.push_back(a);
        }
        for (int i = 0; i < vec.size() - 1; i++) {
            for (int j = i + 1; j < vec.size(); j++) {
                if (gcd(vec[i], vec[j]) == 1)
                    num += 1;
            }
        }
        cout << num << endl;
    }
}

4.12 判断是否是素数

素数判定_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cmath>
using namespace std;

bool  judge(int n){
    //0,1，负数都是非素数
    if(n<=1) return false;
    int b = sqrt(n);
    for(int i=2;i<=b;i++){
        if(n%i==0) return false;
    }
    return true;
}

int main() {
    int a;
    while (cin >> a ) { // 注意 while 处理多个 case
        if(judge(a)){
            cout<<"yes"<<endl;
        }
        else cout<<"no"<<endl;
    }
}

4.13 输出个位数为1的素数

素数_牛客题霸_牛客网 (nowcoder.com)

本题有一个很重要的技巧，非素数一定存在一个素数作为他的因子

#include <iostream>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;
#define MAXN 1000000
bool isPrime[MAXN];
vector<int> prime;
bool  judge(int n){
    if(n==1) return true;
    int b = sqrt(n);
    for(int i=2;i<=b;i++){
        if(n%i==0) return false;
    }
    return true;
}
void init(){
    memset(isPrime,true,sizeof (isPrime));
    isPrime[0]=false;
    isPrime[1] = false;
    for(int i=2;i<MAXN;i++){
        if(!isPrime[i]){
            continue;
        }
        prime.push_back(i);
        for(int j=i*i;j<MAXN;j+=i){
            isPrime[j]=false;
        }
    }
    return;
}

int main() {
    int a;
    init();

    while (cin >> a ) { // 注意 while 处理多个 case
        int i=0;
        int flag=0;
        while(prime[i]<=a){
            if(prime[i]%10==1){
                if(flag) cout<<" ";
                cout<<prime[i];
                flag=1;

            }
            i++;
        }
    }
}

4.14 质因数

质因数的个数_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<cmath>
using namespace std;

int main(){
    int num;
    while(cin >> num){
        int cnt = 0;
        for(int i = 2; i <= sqrt(num); i ++){
            while(num % i == 0){
                cnt ++;
                num /= i;
            }
            if(num <= 1) break;
        }
        // 存在大于 sqrt(num) 的因子
        if(num > 1) cnt ++;
        cout << cnt;
    }
    return 0;
}

4.15 约数的个数

约数的个数_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;


int main() {
    int num;
    vector<long long>  vec;
    while (cin >> num) {
        for (int i = 0; i < num; i++) {
            long long a;
            cin >> a;
            vec.push_back(a);
        }
        int cnt = 0;
        for (int j = 0; j < num; j++) {
            if (vec[j] != 1) cnt = 2;
            else cnt = 1;
            int bound =  sqrt(vec[j]);
            for (int i = 2; i <= bound; i ++) {
                if (vec[j] % i == 0) {
                    if (vec[j] == (i * i)) cnt += 1;
                    else cnt += 2;
                }

            }

            cout << cnt << endl;

        }
    }
    return 0;
}

4.16 整除问题///

整除问题_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<vector>

using namespace std;
//统计 num 中的质因子数
void getPrime(vector<int>& factors, int num) {
    for (int i = 2; i * i <= num; i ++) {
        while (num % i == 0) {
            factors[i] ++;
            num /= i;
            if (num <= 1) return;
        }
    }
    if (num > 1) factors[num] ++;
}

int main() {
    int n, a;
    while (cin >> n >> a) {
        vector<int> factor_a(1000), factor_n(1000);
        getPrime(factor_a, a);
        for (int i = 2; i <= n; i ++)
            getPrime(factor_n, i);
        int k = 1000;
        for (int i = 2; i <= a; i ++) {
            if (factor_a[i]) k = min(k, factor_n[i] / factor_a[i]);
        }
        cout << k << endl;
    }
    return 0;
}

4.17 快速幂的应用

求root(N, k)_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<stack>
using namespace std;
long long fastMi(long long x, long long y, int k) {
    long long  answer = 1;
    while (y != 0) {
        if (y % 2 == 1) {
            answer =answer* x%(k-1);

        }
        y /= 2;
        x = x*x%(k-1);
    }
    return answer;
}


int main() {
    // int a, b;
    long long x, y, k;

    while (cin >> x >> y >> k) { // 注意 while 处理多个 case

        int res = fastMi(x, y,k);
        printf("%d",res?res:k-1);
    }
}

4.18 矩阵乘法

计算两个矩阵的乘积_牛客题霸_牛客网 (nowcoder.com)

本题需要注意矩阵乘法的步骤

#include <iostream>
#include<cstdio>
using namespace std;

struct Matrix {
    int matrix[3][3];
    int row, col;
    Matrix(int r, int c): row(r), col(c) {};
};

void printMatrix(Matrix m) {
    for (int i = 0; i < m.row; i++) {
        for (int j = 0; j < m.col; j++) {
            cout << m.matrix[i][j] << " ";
        }
        cout << endl;
    }
}

Matrix mulptileMatrix(Matrix a, Matrix b) {
    Matrix ans(a.row, b.col);
    for (int i = 0; i < ans.row; i++) {
        for (int j = 0; j < ans.col; j++) {
            ans.matrix[i][j] = 0;
            for (int k = 0; k < a.col; k++) {
                ans.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j];
            }
        }
    }
    return ans;
}
int main() {

    Matrix a(2, 3);
    Matrix b(3, 2);
    for (int i = 0; i < a.row; i++) {
        for (int j = 0; j < a.col; j++)
            cin >> a.matrix[i][j];

    }
    for (int i = 0; i < b.row; i++) {
        for (int j = 0; j < b.col; j++)
            cin >> b.matrix[i][j];

    }
    Matrix res = mulptileMatrix(a, b);
    printMatrix(res);

}

4.19 矩阵快速幂

矩阵幂_牛客题霸_牛客网 (nowcoder.com)

这里为了解决快速幂的问题，使用了一样的方法，记得掌握

#include <iostream>
#include<cstdio>
using namespace std;

struct Matrix {
    int matrix[10][10];
    int row, col;
    Matrix(int r, int c): row(r), col(c) {};
};

void printMatrix(Matrix m) {
    for (int i = 0; i < m.row; i++) {
        for (int j = 0; j < m.col; j++) {
            cout << m.matrix[i][j] << " ";
        }
        cout << endl;
    }
}

Matrix mulptileMatrix(Matrix a, Matrix b) {
    Matrix ans(a.row, b.col);
    
    for (int i = 0; i < ans.row; i++) {
        for (int j = 0; j < ans.col; j++) {
            ans.matrix[i][j] = 0;
            for (int k = 0; k < a.col; k++) {
                ans.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j];
            }
        }
    }
    return ans;
}

Matrix fastMatrixMi(Matrix x, int k) {
    Matrix answer(x.row, x.col);
    //构造单位矩阵
    for (int i = 0; i < answer.row; i++) {
        for (int j = 0; j < answer.col; j++) {
            if (i == j) {
                answer.matrix[i][j] = 1;
            } else {
                answer.matrix[i][j] = 0;
            }
        }
    }
    while (k != 0) {
        if (k % 2 == 1) {
            answer = mulptileMatrix(answer, x);
        }

        k /= 2;
        x = mulptileMatrix(x, x);
    }
    return answer;
}



int main() {

    int n, k;
    while (cin >> n >> k) {
        Matrix m(n, n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> m.matrix[i][j];
            }
        }
        m = fastMatrixMi(m, k);
        printMatrix(m);
    }
}

4.20 矩阵加法

A+B for Matrices_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstdio>
using namespace std;

struct Matrix {
    int matrix[10][10];
    int row, col;
    Matrix(int r, int c): row(r), col(c) {};
};

void printMatrix(Matrix m) {
    for (int i = 0; i < m.row; i++) {
        for (int j = 0; j < m.col; j++) {
            cout << m.matrix[i][j] << " ";
        }
        cout << endl;
    }
}

Matrix mulptileMatrix(Matrix a, Matrix b) {
    Matrix ans(a.row, b.col);
    for (int i = 0; i < ans.row; i++) {
        for (int j = 0; j < ans.col; j++) {
            ans.matrix[i][j] = 0;
            for (int k = 0; k < a.col; k++) {
                ans.matrix[i][j] += a.matrix[i][k] * b.matrix[k][j];
            }
        }
    }
    return ans;
}

Matrix addMatrix(Matrix a, Matrix b) {
    Matrix ans(a.row, a.col);
    for (int i = 0; i < ans.row; i++) {
        for (int j = 0; j < ans.col; j++) {
            ans.matrix[i][j] = a.matrix[i][j] + b.matrix[i][j];
        }
    }
    return ans;

}

int solve(Matrix ans) {
    int num = 0;
    bool flag1 = 0;
    for (int i = 0; i < ans.row; i++) {
        for (int j = 0; j < ans.col; j++) {
            if (ans.matrix[i][j] == 0) {
                flag1 = true;
            } else {
                flag1 = false;
                break;
            }
        }
        if (flag1) num += 1;
    }
    flag1 = 0;
    for (int i = 0; i < ans.col; i++) {
        for (int j = 0; j < ans.row; j++) {
            if (ans.matrix[j][i] == 0) {
                flag1 = true;
            } else {
                flag1 = false;
                break;
            }
        }
        if (flag1) num += 1;
    }
    return num;
}
int main() {

    int n, k;
    while (cin >> n) {
        if (n == 0) break;
        cin >> k;
        Matrix a(n, k);
        Matrix  b(n, k);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                cin >> a.matrix[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                cin >> b.matrix[i][j];
            }
        }
        a = addMatrix(a, b);
        cout << solve(a) << endl;
    }
}

5.贪心算法

5.1匹配服务器

代理服务器_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<vector>
#include<map>

using namespace std;

int getCnt(vector<string>& proxy, vector<string>& server, int m) {
    int  index=0;
    int count=0;
    while(index<m){
        int maxm=0;
        for(string ip:proxy){
            int j;
            for(j=index;j<m&&ip!=server[j];j++){}
            maxm=max(maxm, j-index);
        }
        if(maxm==0) return -1;
        index+=maxm;
        count++;
    }
    return count-1;
}
int main() {
    int n, m;
    while (cin >> n) {
        vector<string> proxy(n);
        for (int i = 0; i < n; i ++) {
            cin >> proxy[i];
        }
        cin >> m;
        vector<string> server(m);
        for (int i = 0; i < m; i ++)
            cin >> server[i];
        cout << getCnt(proxy, server, m);
    }
}

5.2 区间贪心：看电视节目

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

struct tv{
    int start;
    int end;
};

bool compare(tv a, tv b){
    return a.end<b.end;
}

int main() {
    int n;
    vector<tv> dianshi;
    while (cin >> n) {
        for(int i=0;i<n;i++){
            tv t;
            cin>>t.start>>t.end;
            dianshi.push_back(t);
        }
        sort(dianshi.begin(), dianshi.end(),compare);
        int timeNow=0;
        int num=0;
        for(int i=0;i<dianshi.size();i++){
            if(timeNow<=dianshi[i].start){
                timeNow=dianshi[i].end;
                num++;
            }
        }
        cout<<num<<endl;
    }
}

5.3 油价

To Fill or Not to Fill_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include <cstdio>
#include <algorithm>
/*
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
50 1300 12 2
7.10 0
7.00 600

749.17
The maximum travel distance = 1200.00
*/
using namespace std;
/*
输入 : 
对于每种情况，第一行包含4个正数：Cmax（<=100），即油箱的最大容量；D（<=30000），
即杭州到目的地城市的距离；Davg（<=20），即汽车每单位汽油可行驶的平均距离；N（<=500），
即加油站总数。接下来是N行，每行包含一对非负数：Pi，煤气单价，Di（<=D），这个站到杭州的距离，i=1，…N。一行中的所有数字用空格隔开。

输出 :
对于每个测试用例，一行打印最便宜的价格，精确到小数点后2位。
假设开始时油箱是空的。如果无法到达目的地，请打印“最大行驶距离=X”，
其中X是车辆可以行驶的最大可能距离，精确到小数点后2位。 
*/
struct GasStation {
    double price;
    int distance;
};

bool ComparePrice(GasStation x, GasStation y) {
    return x.price < y.price;
}

int main() {
    int cmax, d, davg, n; // cmax : 箱的最大容量, d : 州到目的地城市的距离, davg : 车每单位汽油可行驶的平均距离, n : 加油站总数;
    while (cin >> cmax >> d >> davg >> n) {
        double currentprice = 0; // 当前油费 

        bool tag[d + 1]; // 记录当前有哪段道路是从加油站出发能走的 
        GasStation gasStation[n];

        for (int i = 1; i <= d; ++i) tag[i] = false;
        for (int i = 0; i < n; ++i) cin >> gasStation[i].price >> gasStation[i].distance;

        sort(gasStation, gasStation + n, ComparePrice); // 对油价按升序排 

        for (int i = 0; i < n; ++i) {  // 对tag[]进行记录, 并同时计算出 currentprice
            int currentdistance = 0; // 记录从这个加油站出发要用其油的距离 
            for (int j = gasStation[i].distance + 1; j <= gasStation[i].distance + cmax * davg; ++j) {
                if (tag[j] == false) { // 如果 tag[j]为假则可走 
                    tag[j] = true;
                    currentdistance++;
                }
                if (j == d || j == gasStation[i].distance + cmax * davg) { // 走到了尽头 
                    currentprice += gasStation[i].price  * currentdistance / (davg * 1.0);
                    break;
                }
            }
        }

        int fill = 1; // tag[]是否全为真的标志位
        double journey = 0;
        for (int i = 1; i <= d; ++i) {
            if (tag[i] == true) journey++;
            else {
                fill = 0;
                break;
            }
        }

        if (fill) printf("%.2f\n",currentprice);
        else printf("The maximum travel distance = %.2f\n", journey);    
    }
    return 0;
}

5.4 加油站问题（贪心算法）

3659. 加油站 – AcWing题库

#include <iostream>
#include <cstring>
#include <iostream>
#include<climits>
const int maxn=5010;
using namespace std;

//7 7
//1 2 3 4 5 1 6 6

int solve(int dis[],int k, int maxDist){
    int ans=0;
    int n=maxDist;
    for(int i=0;i<=k;i++){
        if(dis[i]<=n){
            n-=dis[i];
        }
        else{


            ans+=1;
            n=maxDist-dis[i];
            if(n<0) return -1;
        }
    }
    return ans;
}



int  main(){
    int n,k;
    int dis[maxn];
    while(cin>>n>>k){
        memset(dis,0,sizeof (dis));
        int d=0;
        for(int i=0;i<=k;i++){
            cin>>dis[i];
        }
        int res=solve(dis,k,n);
        if(res==-1) cout<<"No Solution"<<endl;
        else{
            cout<<res<<endl;
        }
    }
}

6.递归与分治

6.1 n的阶乘

n的阶乘_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;

long long factor(long long n){
    if(n==1||n==0)  return 1;
    else return n*factor(n-1);
}
int main() {
    int a;
    while (cin >> a) { // 注意 while 处理多个 case
        cout << factor(a)<< endl;
    }
}
// 64 位输出请用 printf("%lld")

6.2 杨辉三角

杨辉三角_牛客笔试题_牛客网 (nowcoder.com)

#include<iostream>
using namespace std;
void solve(int n){
    int Matrix[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i)
                Matrix[i][j]=1;

            else{
                Matrix[i][j]= Matrix[i-1][j-1]+Matrix[i-1][j];
            }
            printf("%5d",Matrix[i][j]);
        }
        cout<<endl;
    }

}
int main(){
    int a;
    while(cin>>a){
     solve(a);
    }
}

6.3 全排列(元素个数与之前一样)

全排列_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
string a;


int main()
{
    vector<char> vec;
    char num[6];
    while(cin>>a){
        int n=a.size();
        for(int i=0;i<n;i++){
            num[i]=a[i];

        }
        //while(next_permutation(num,num+n));
        do{
            cout<<num<<endl;
        }while(next_permutation(num, num+n));
    }

}

6.4 斐波那契数列

Fibonacci_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;

int solve(int n){
    if(n==0) return 0;
    if(n==1||n==2) return 1;
    else return solve(n-1)+solve(n-2);
}

int main() {
    int a;
    while (cin >> a ) { // 注意 while 处理多个 case
        cout << solve(a)<< endl;
    }
}
// 64 位输出请用 printf("%lld")

6.5 求完全二叉树结点的子树

二叉树_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;
int a;
int solve(int m){
    if(m>a) return 0;

    //左子树和右子树
    else return solve(2*m)+solve(2*m+1)+1;
}

int main() {
    int  b;
    while (cin >> b>> a) { // 注意 while 处理多个 case
        if(a==0) break;
        cout<<solve(b)<<endl;
    }
}
// 64 位输出请用 printf("%lld")

6.6分解数字转二的次幂

2的幂次方_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<vector>
using namespace std;

void solve(int n) {
    if (n == 1) //这里的 1代表2的1次幂
        cout << "2";
    else if (n == 2) //2代表2的2次幂
        cout << "2(2)";
    else if (n == 0)
        cout << "2(0)";
    else {
        vector<int> vec;
        while (n != 0) {
            vec.push_back(n % 2);
            n /= 2;
        }
        vector<int> res;
        for (int i = vec.size() - 1; i >= 0; i--)
            if (vec[i] == 1) res.push_back(i);

        for (int i = 0; i < res.size(); i++) {
            if (res[i] > 2) {
                cout << "2(";
                solve(res[i]);
                cout << ")";
                if (i != res.size() - 1) {
                    cout << "+";
                }
            } else {
                solve(res[i]);
                if (i != res.size() - 1) {
                    cout << "+";
                }
            }
        }

    }
}

int main() {
    int a;
    while (cin >> a) {
        solve(a);
    }

}

7.搜索算法

7.1 广度优先算法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=10001;
struct status{
    int n,t;
    status(int n, int t):n(n),t(t){};
};

bool visit[MAXN];




int bfs(int n, int k){
    queue<status>myQueue;
   myQueue.push(status(n,0));//初始状态入队
    visit[n]=true;
    while(!myQueue.empty()){
        status current = myQueue.front();
        myQueue.pop();
        if(current.n==k){
            return current.t;
        }
        else{

            for(int i=0;i<3;i++){
                 status next(current.n, current.t+1);
                if(i==0)next.n+=1;
                else if(i==1)next.n-=1;
                else if(i=2)next.n*=2;
                if(next.n<0||next.n>=MAXN||visit[next.n]){
                    continue;
                }
                if(next.n<0||next.n>10001||visit[next.n])continue;//越界或者已被访问
                myQueue.push(next);
                visit[next.n]=true;

            }
        }
    }
}

int main(){
    int n,k;


        memset(visit,false,sizeof (visit));
        cout<<bfs(5,17)<<endl;
}

7.2 广度优先解决玛雅密码问题

玛雅人的密码_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int MAXN = 10001;

struct data1 {
    string str;
    int depth;
    data1(string str, int depth): str(str), depth(depth) {};
};

void solve(string str) {
    map<string, int> m;
    queue<data1> myQueue;
    myQueue.push(data1(str, 0));
    while (!myQueue.empty()) {
        data1 current = myQueue.front();
        myQueue.pop();
        if (current.str.find("2012") != string::npos) {
            cout << current.depth << endl;
            return;
        }
        for (int i = 1; i < str.size() - 1; i++) {
            for (int j = 0; j < 2; j++) {
                string str = current.str;

                if (j == 0) {
                    swap(str[i], str[i - 1]);

                } else {
                    swap(str[i], str[i + 1]);
                }
                //将已经访问过的字符串记录状态不在访问
                //节省内存
                if (m[str] == 1) continue;
                else m[str] = 1;
                myQueue.push(data1(str, current.depth + 1));
            }

        }
    }
}
int main() {
    int n;
    string str;
    while (cin >> n) {
        cin >> str;
        solve(str);
    }
}

7.3 深度优先算法搜索状态问题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
const int MAXN=25;
int side,m;
int sticks[MAXN];
int visit[MAXN];
bool DFS(int sum, int number, int position){
    if(number==3) return true;
    int sample=0;
    for(int i=position;i<m;i++){
        if(visit[i]||sum+sticks[i]>side||sticks[i]==sample){
            continue;
        }
        visit[i]=true;
        if(sum+sticks[i]==side){
            if(DFS(0,number+1,0)){
                return true;
            }
            else{
                sample=sticks[i];
            }

        }
        else{
            if(DFS(sum+sticks[i],number,i+1)){
                return true;
            }
            else{
                sample = sticks[i];
            }
        }
        visit[i]=false;
    }
    return false;
}

bool compare(int x, int y){
    return x>y;
}

int main(){
    cin>>m;
    memset(sticks,0,sizeof (sticks));
    int length=0;
    for(int i=0;i<m;i++){
        cin>>sticks[i];
        length+=sticks[i];
    }
    if(length%4!=0){
        cout<<"no"<<endl;
    }
    else{
        sort(sticks,sticks+m,compare);

        side = length/4;
        if(sticks[0]>side){
            cout<<"no";
        }
        else if(DFS(0,0,0)){
            cout<<"yes"<<endl;
        }
        else cout<<"no";
    }
}

7.4 神奇的口袋

神奇的口袋_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 21
int weight[maxn];
int n;

int visit[maxn];
int num=0;
void dfs(int sum, int k) {
  
    for (int i = k; i < n; i++) {
        int cal =sum+weight[i];
        if (cal> 40) {
            dfs(sum,i+1);
        }
        
        else if(cal<40){
           dfs(cal,i+1);
            }
        else{
            num++;
        }
    }
}

int main() {
    while (cin >> n) {
        memset(weight, 0, sizeof(weight));
        // 注意 while 处理多个 case
        for (int i = 0; i < n; i++) {
            cin >> weight[i];
        }
        sort(weight, weight + n);
        if (weight[0] > 40) {
            cout << 0 << endl;
        } else {
            dfs(0,0);
            cout<<num;
        }

    }
}

7.4 八皇后问题

这里注意不能处于同一斜行的条件

八皇后_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> vec;
int visit[9];
int arr[9];
bool judge(int k, int a){
    for(int i=1;i<k;i++){
        if(arr[i]==a||(i-arr[i]==k-a)||(i+arr[i]==a+k)){
            return false;
        }
    }
    return true;
}


void dfs(int k,int n){
    if(k==9){
        vec.push_back(n);
        return;

    }
    for(int i=1;i<9;i++){

        if(judge(k,i)){
            arr[k]=i;
           dfs(k+1, n*10+i);
        }
    }

}



int main() {
    dfs(1,0);
    sort(vec.begin(),vec.end());
    int n;
    while(cin>>n){
        cout<<vec[n-1]<<endl;
    }
}
// 64 位输出请用 printf("%lld")

8.动态规划

8.1 上楼梯

N阶楼梯上楼问题_牛客题霸_牛客网 (nowcoder.com)

#include <cstring>
#include <iostream>
using namespace std;
const int maxn=91;
int floor[maxn];
int fib(int n){
     int answer;
    if(n==0||n==1)
        answer=n;
     
    else if(floor[n]!=-1){
       answer= floor[n];
    }
    else{
        answer = fib(n-1)+fib(n-2);
        
    }
    floor[n]=answer;
    return answer;
}

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        memset(floor, -1, sizeof(floor));
        cout<<fib(n+1)<<endl;
    }
}
// 64 位输出请用 printf("%lld")

8.2 吃糖果

吃糖果_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;
const int maxn=21;
int solve(int n){
    int cho[maxn]={0};
    cho[0]=1;
    cho[1]=1;
    for(int  i=2;i<=n;i++){
        cho[i]=cho[i-1]+cho[i-2];
    }
    return cho[n];
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        cout<<solve(n)<<endl;
    }
}

8.3 最长子序列和

超时方案(递归效率太低了）：

最大序列和_牛客题霸_牛客网 (nowcoder.com)

#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 10;
//const int INF = INT_MAX; //int数据的最大值，即无穷大
long long arr[maxn];
long long  Fun1(int n) {
    long long answer;
    if (n == 0) answer = arr[n];
    else {
        answer = max(arr[n], Fun1(n - 1) + arr[n]);
    }
    return answer;

}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        long long res = Fun1(0); //
        for (int i = 1; i < n; i++) {
           res=max(res,Fun1(i));
        }
        cout << res << endl;
    }
}
// 64 位输出请用 printf("%lld")

不会超时的动态规划方法：

#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 10;
//const int INF = INT_MAX; //int数据的最大值，即无穷大
long long arr[maxn];
long long memo[maxn];
void Fun2(int n){
    long long answer;
    for(int i=0;i<n;i++){
   if (i == 0) answer = arr[i];
    else {
        answer = max(arr[i], memo[i-1]+ arr[i]);
    }
    memo[i]=answer;

    }
}
int main() {
    int n;   
    while (cin >> n) { // 注意 while 处理多个 case
         memset(memo, -1, sizeof(memo));
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
       Fun2(n);
       long long res = memo[0];
        for (int i = 1; i < n; i++) {
            res = max(res, memo[i]);
        }
        cout << res << endl;
    }
}

8.4 最长递增子序列

最大子矩阵__牛客网 (nowcoder.com)

#include <cstring>
#include <iostream>
#include<climits>
using namespace std;
const int maxn=100;
const int inf =INT_MAX;
int arr[maxn];
int memo[maxn];
int total[maxn][maxn];

int fib(int n){
    int maxm=-inf;
    for(int i=0;i<n;i++){
        if(i==0) memo[i]=arr[i];
        else{
            memo[i]=max(arr[i],arr[i]+memo[i-1]);
        }
        maxm = max(maxm,memo[i]);
    }
    return maxm;
}

int solve(int n){
    int maxmal=-inf;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            for(int k=0;k<n;k++){
                if(i==0){
                    arr[k]=total[j][k];
                }
                else{
                    arr[k]= total[j][k]-total[i-1][k];
                }
            }
            int current = fib(n);
        maxmal = max(current, maxmal);
        }
        
    }
    return maxmal;
}

int main() {
    int n;
    int matrix[maxn][maxn];
    while(cin>>n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>matrix[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==0){
                total[i][j]=matrix[i][j];
            }
            else{
                total[i][j]=total[i-1][j]+matrix[i][j];
            }

        }
    }
    cout<<solve(n)<<endl;
}

8.5 最大递增子序列2

最大连续子序列_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include <cstring>
#include <iostream>
#include<climits>
using namespace std;
const int maxn = 10001;
const int inf = INT_MAX;
int arr[maxn];
int memo[maxn];
int start[maxn];

void fib(int n) {
    int maxm = -inf;
    for (int i = 0; i < n; i++) {        
        if (i == 0) memo[i] = arr[i];
        else {
          //  memo[i] = max(arr[i], arr[i] + memo[i - 1]);
            if(arr[i]<arr[i]+memo[i-1]){
                start[i]=start[i-1];
                memo[i]=arr[i]+memo[i-1];
            }
            else{
                memo[i]=arr[i];
            }
        }

    }
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        if(n==0) break;
        int flag=0;
        memset(memo,0,sizeof(memo));
        for(int i=0;i<n;i++){
            cin>>arr[i];
            if(arr[i]>=0) flag=1;
            start[i]=arr[i];//起始是自己
        }
        if(flag==0)  cout<<0<<" "<<arr[0]<<" "<<arr[n-1]<<endl;
    else{
        fib(n);
        int maxIndex=0;
        int max=memo[0];
        for(int i=0;i<n;i++){
            if(max<memo[i]){
                max=memo[i];
                maxIndex=i;
            }
        }
    
        cout<<max<<" "<<start[maxIndex]<<" "<<arr[maxIndex]<<endl;
    }
    }
}

8.6 最长不递增子序列

拦截导弹_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;
const int maxn=26;
int dp[maxn];
int arr[maxn];

int fun(int n){
    int answer=1;
    for(int i=0;i<n;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(arr[j]>=arr[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        answer=max(answer,dp[i]);
    }
    return answer;
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        cout<<fun(n)<<endl;
    }
}

8.7 最大上升子序列和

最大上升子序列和_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;
const int maxn = 1001;
int dp[maxn];
int arr[maxn];

int fun(int n) {
    int answer = -maxn;
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + arr[i]);
            }
        }
        answer = max(answer, dp[i]);
    }
    return answer;
}
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        cout << fun(n) << endl;
    }
}

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin >>arr[i];
    }
    support[0]=-maxn;
    int length=0;
    for(int i=0;i<n;i++){
        if(support[length]<arr[i]){
            support[++length]=arr[i];
        }
        else{
            int pos  = lower_bound(support,support+length,arr[i])-support;
            support[pos]=arr[i];
        }
    }
    cout<<length;

}

8.8 合唱队形

合唱队形_牛客题霸_牛客网 (nowcoder.com)

两边小中间大的最大长度。

#include <iostream>
#include<algorithm>
using namespace std;
const int maxn = 101;
int dp[maxn];
int dp2[maxn];
int arr[maxn];

int fun(int n) {
    int answer = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        answer = max(dp[i], answer);
    }
    return answer;
}

int fun2(int n) {
    int answer = 1;
    for (int i = n-1; i >=0; i--) {
        dp2[i] = 1;
        for (int j=n-1; j > i; j--) {
            if (arr[j] < arr[i]) {
                dp2[i] = max(dp2[i], dp2[j] + 1);
            }
        }
        answer = max(dp2[i], answer);
    }
    return answer;
}

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int  ans=1;
        fun(n);
        fun2(n);
        for(int i=0;i<n;i++){
            if(dp[i]+dp2[i]>ans){
                ans =dp[i]+dp2[i];
            }
        }
        cout << (n - ans+1) << endl;
    }
}

8.9 0-1背包问题，同一件物品最多只能选择一件

点菜问题_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
using namespace std;
const int maxn=1001;
int weight[maxn];
int value[maxn];
int dp[maxn][maxn];
int main() {
    int c, n;
    while (cin >> c >> n) { // 注意 while 处理多个 case

        for(int i=1;i<=n;i++){
            cin>>weight[i]>>value[i];
        }
       for(int i=0;i<=n;i++){
        dp[i][0]=0;

       }
       for(int j=0;j<=c;j++){
           dp[0][j]=0;
       }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=c;j++)
            if(j<weight[i]){
                dp[i][j]=dp[i-1][j];
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                //cout<<dp[i][j]<<endl;
            }
        }
        cout<<dp[n][c]<<endl;

    }
}

空间优化版本：

#include <iostream>
#include<cstring>
using namespace std;
const int maxn = 1001;
int weight[maxn];
int value[maxn];
int dp[maxn];
int main() {
    int c, n;
    while (cin >> c >> n) { // 注意 while 处理多个 case

        for (int i = 1; i <= n; i++) {
            cin >> weight[i] >> value[i];
        }
        memset(dp, 0, sizeof (dp));
        for (int i = 1; i <= n; i++) {
            for (int j = c; j >= weight[i]; j--) //逆向更新
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            //cout<<dp[i][j]<<endl;

        }
        cout << dp[c] << endl;

    }
}
// 64 位输出请用 printf("%lld")

采药__牛客网 (nowcoder.com)

一个代码，换了种问法而已。

8.11 最小邮票数

最小邮票数_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int MAX = 100000;

int main() {
    int m, n;
    while (cin >> m >> n) {
        vector<int> stamps(n + 1, 0);
        vector<int> dp(m + 1, MAX);
        for (int i = 1; i <= n; i ++)
            cin >> stamps[i];
        dp[0] = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = m; j >= stamps[i]; j --) {
                dp[j] = min(dp[j], dp[j - stamps[i]] + 1);

            }
        }

        if (dp[m] == MAX)
            cout << 0 << endl;
        else
            cout << dp[m] << endl;
    }
    return 0;
}

使用dfs来解决：

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<climits>
#include<algorithm>
const int maxn = 1001;
using namespace std;
int res = INT_MAX;
void dfs(vector<int> vec, int index, int nums, int weight) {
    if (weight == 0) res = min(res, nums);
    for (int i = index; i < vec.size(); i++) {
        if (weight < vec[i]) return;
        else {
            dfs(vec, i + 1, nums + 1, weight - vec[i]);
        }
        dfs(vec, i + 1, nums, weight);

    }




}
int main() {
 int weight, value, m;
    while (cin >> weight) {
        vector<int> vec;
        cin >> m;
        while (m--) {
            cin >> value;
            vec.push_back(value);
        }
        sort(vec.begin(), vec.end());
        dfs(vec, 0, 0, weight);
        if(res==INT_MAX){
            cout<<0<<endl;
            continue;
        }
        cout << res << endl;



    }


}

8.12 完全背包

每件物品无穷个，与0/1背包区分

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN = 110;
const int MAXM=1e5+10;
int weight[MAXN];
int value[MAXN];
int dp[MAXN];
int main() {
    int m, n;
    while (cin >> n) {
        for(int i=1;i<=n;i++){
            cin>>value[i]>>weight[i];
        }
        cin>>m;
        memset(dp,0,sizeof (dp));
        for(int i=1;i<=n;i++){
            for(int j=weight[i];j<=m;j++){
                 dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);//拿了一件还可以拿

            }
        }
        cout<<dp[m]<<endl;
    return 0;
}}

8.13 多重背包

每个商品的数量都是有限的

多重背包__牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1e4+10;
int weight[maxn];
int amount[maxn];
int value[maxn];
int dp[maxn];
int newWeight[20*maxn];
int newValue[20*maxn];
数量、体积和价值
int main() {
    int m, n;
    while(cin>>m>>n){
    for(int i=0;i<n;i++){
       cin>>amount[i]>>weight[i]>>value[i];
    }
    int num=0;
    for(int i=0;i<n;i++){
        for(int k=1;k<=amount[i];k*=2){
            newWeight[num]=weight[i]*k;
            newValue[num]=value[i]*k;
            num++;
            amount[i]-=k;
        }
        if(amount[i]>0){
            newWeight[num]=weight[i]*amount[i];
            newValue[num]=value[i]*amount[i];
            num++;

        }
    }
    memset(dp,0,sizeof (dp));
    for(int i=0;i<num;i++){
        for(int j=m;j>=newWeight[i];j--){
            dp[j]=max(dp[j],dp[j-newWeight[i]]+newValue[i]);
        }
    }

    cout<<dp[m]<<endl;
    }
}

8.14 三角形

三角形__牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1001;
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int res[maxn][maxn];
       
        int n=triangle.size();
        for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            vector<int> vec=triangle[i];
            res[i][j] = vec[j];//初始值设定
        }
    }
    for (int i = n - 2; i >= 0; --i) {//倒推回去
        for (int j = 0; j <= i; ++j) {//第i行只有i个元素
            //
            res[i][j] += min(res[i + 1][j], res[i + 1][j + 1]);
        }
    }
        return res[0][0];
        
    }
};

8.15 暂时未解决的问题

题解 | #Monkey Banana Problem#_牛客网 (nowcoder.com)

8.16 放苹果

放苹果__牛客网 (nowcoder.com)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int M, N;
	while (cin >> M >> N) {
		if (M < 1 || M>10 || N < 1 || N>10) {
			cout << -1 << endl;
			continue;
		}
		vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
		for (int i = 1; i <= N; i++) dp[0][i] = 1;
		for (int i = 1; i <= M; i++)
			for (int j = 1; j <= N; j++)
				dp[i][j] = dp[i][j - 1] + (i < j ? 0 : dp[i - j][j]);
		cout << dp[M][N] << endl;
	}
}

8.17 划分

整数拆分_牛客题霸_牛客网 (nowcoder.com)

真的太难想了。。。

#include<iostream>
using namespace std;
int dp[1000001];
int main() {
    int n;
    dp[0] = 1;
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) {
                dp[i] = (dp[i - 1] + dp[i / 2]) % 1000000000;
            } else {
                dp[i] = dp[i - 1] % 1000000000;
            }
        }
        cout << dp[n] << endl;
    }
    return 0;
}

9.二叉树

9.1 根据前序和中序生成二叉树序列

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

struct treeNode {
    char data;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(char c): data(c), leftChild(nullptr), rightChild(nullptr) {};
};

treeNode* Build(string pre, string in) {
    if (pre.size() == 0) return nullptr;
    char c = pre[0];
    treeNode* root = new treeNode(c);
    int pos = in.find(c);
    root->leftChild = Build(pre.substr(1, pos), in.substr(0, pos));
    root->rightChild = Build(pre.substr(pos + 1), in.substr(pos + 1));
    return root;
}

void postOrder(treeNode* root) {
    if (root == nullptr) return;
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    cout << root->data;

}

int main() {
    string pre, in;
    while (cin >> pre >> in) {

        treeNode* res = Build(pre, in);
        postOrder(res);
        cout << endl;
    }
}

9.2 根据前序序列构成二叉树

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>

using namespace std;

struct treeNode {
    char data;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(char c): data(c), leftChild(nullptr), rightChild(nullptr) {};
};


void inOrder(treeNode* root) {
    if (root == nullptr) return;
    inOrder(root->leftChild);
    cout << root->data << ' ';
    inOrder(root->rightChild);

}

string arr;
int index1 = 0;
treeNode* createTree() {

    if (arr[index1] == '#') {
        index1++;
        return nullptr;
    }
    treeNode* root = new treeNode(arr[index1++]);
    root->leftChild = createTree();
    root->rightChild = createTree();
    return root;


}

int main() {
    while (cin >> arr) {
        index1=0;
        treeNode* res = createTree();
        inOrder(res);
        cout << endl;
    }


}

9.3 二叉排序树的生成

二叉排序树_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>

using namespace std;

struct treeNode {
    int data;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(int c): data(c), leftChild(nullptr), rightChild(nullptr) {};
};

treeNode* insert(treeNode* root, int x) {
    if (root == nullptr) {
        root = new treeNode(x);

    } else if (x < root->data) {
        root->leftChild = insert(root->leftChild, x);
    } else if (x > root->data) {
        root->rightChild = insert(root->rightChild, x);
    }

    return root;
}

void preOrder(treeNode* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preOrder(root->leftChild);
    preOrder(root->rightChild);
}

void inOrder(treeNode* root) {
    if (root == nullptr) return;

    inOrder(root->leftChild);
    cout << root->data << " ";
    inOrder(root->rightChild);
}
void postOrder(treeNode* root) {
    if (root == nullptr) return;
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    cout << root->data << " ";
}

int main() {
    int n;
    int a;
    while (cin >> n) {
        treeNode* root = nullptr;
        for (int i = 0; i < n; i++) {
            cin >> a;
            root = insert(root, a);
        }
        preOrder(root);
        cout << endl;
        inOrder(root);
        cout << endl;
        postOrder(root);

        cout << endl;
    }
}

9.4 记录插入结点的父节点

二叉排序树_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>

using namespace std;

struct treeNode {
    int data;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(int c): data(c), leftChild(nullptr), rightChild(nullptr) {};
};

treeNode* insert(treeNode* root, int x, int parent) {
    if (root == nullptr) {
        root = new treeNode(x);
        cout << parent << endl;

    } else if (x < root->data) {
        root->leftChild = insert(root->leftChild, x, root->data);
    } else if (x > root->data) {
        root->rightChild = insert(root->rightChild, x, root->data);
    }

    return root;
}
int main() {
    int n;
    int a;
    while (cin >> n) {
        treeNode* root = nullptr;
        for (int i = 0; i < n; i++) {
            cin >> a;
            root = insert(root, a, -1);
        }
    }
}

9.5 判断两棵二叉树是否相同

二叉搜索树_牛客题霸_牛客网 (nowcoder.com)

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>

using namespace std;

struct treeNode {
    int data;
    treeNode* leftChild;
    treeNode* rightChild;
    treeNode(int c): data(c), leftChild(nullptr), rightChild(nullptr) {};
};

treeNode* insert(treeNode* root, int data) {
    if (root == nullptr) {
        root = new treeNode(data);
    } else if (data < root->data) {
        root->leftChild = insert(root->leftChild, data);
    } else if (data > root->data) {
        root->rightChild = insert(root->rightChild, data);
    }
    return root;
}

bool judge(treeNode* t1, treeNode* t2) {
    if (t1 == nullptr && t2 == nullptr) return true;
    else {
        if (t1 == nullptr || t2 == nullptr) return false;
        else {
            if (t1->data == t2->data) {
                return judge(t1->leftChild, t2->leftChild) &&
                       judge(t1->rightChild, t2->rightChild);
            } else {
                return false;
            }
        }
    }
}
int main() {
    int n;
    int a;
    string arr;
    while (cin >> n) {
        if (n == 0) break;
        treeNode* root = nullptr;
        cin >> arr;
        for (int i = 0; i < arr.size(); i++) {
            root = insert(root, arr[i] - '0');
        }

        while (n--) {
            treeNode* tmp = nullptr;
            cin >> arr;
            for (int  i = 0; i < arr.size(); i++) {
                tmp = insert(tmp, arr[i] - '0');
            }

            if (judge(root, tmp)) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }


        }

    }
}

9.6 查找第k小数

本题重点在排除重复的数

查找第K小数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e4 + 10;
int main() {
    int n, c;
    int arr[maxn];
    while (cin >> n) { // 注意 while 处理多个 case
        memset(arr, 0, sizeof(arr));
        vector<int> vec;
        while (n--) {
            cin >> c;
            if (arr[c] == 1) continue;
            arr[c] = 1;
            vec.push_back(c);
        }
        sort(vec.begin(), vec.end());
        int k;
        cin >> k;
        cout << vec[k - 1] << endl;
    }
}

10.图论

10.1 并查集

并查集操作的基础代码(优化过的)：

#include <iostream>
using namespace std;
const int maxn=1000;
int  father[maxn];
int height[maxn];//每个节点的高度，用于高树合并矮树
void init(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
        height[i]=0;
    }
}
int find(int x){
    if(x!=father[x]){
        //return find(father[x]);//未优化状态
        father[x] = find(father[x]);//查找路径压缩
    }
    return father[x];
}
void Union(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
    if(height[x]<height[y]){
        father[x]=y;  
    }
    else if(height[x]>height[y]){
        father[y]=x;
    }
    else{
        father[y]=x;
        height[x]+=1;//并查集中唯一可以让高度增加的方法
    }   
    }
}

用并查集解决连通图问题

连通图_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
using namespace std;
const int maxn = 1000 + 10;
int  father[maxn];
int height[maxn];//每个节点的高度，用于高树合并矮树
void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        //return find(father[x]);//未优化状态
        father[x] = find(father[x]);//查找路径压缩
    }
    return father[x];
}

void Union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;

        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1; //并查集中唯一可以让高度增加的方法
        }

    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        memset(height, 0, sizeof (height));
        if (n == 0) {
            break;
        }
        int x, y;
        init(n + 1);
        while (m--) {

            cin >> x >> y;
            Union(x, y);
        }
        int component = 0;
        for (int i = 1; i <= n; i++) {
            if (i == find(i)) {
                component += 1;
            }
        }
        if (component != 1) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}

10.1.2 连通工程

畅通工程_牛客题霸_牛客网 (nowcoder.com)

n个联通分量只需要n-1条边即可联通，所以本题只需要求出有多少个联通分量

#include <iostream>
#include<cstring>
using namespace std;
const int maxn = 1000 + 10;
int  father[maxn];
int height[maxn];//每个节点的高度，用于高树合并矮树
void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        //return find(father[x]);//未优化状态
        father[x] = find(father[x]);//查找路径压缩
    }
    return father[x];
}

void Union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;

        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1; //并查集中唯一可以让高度增加的方法
        }

    }
}

int main() {
    int n, m;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        cin >> m;
        int x, y;
        init(n + 1);
        while (m--) {

            cin >> x >> y;
            Union(x, y);
        }
        int component = 0;
        for (int i = 1; i <= n; i++) {
            if (i == find(i)) {
                component += 1;
            }
        }
        cout << component - 1 << endl;
    }
}

10.1.3 判断是否是一棵树

Is It A Tree?_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<map>
#include<vector>
using namespace std;
const int maxn=1e4+10;
int father[maxn];
int height[maxn];
int indegree[maxn];
using namespace std;
void init(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
        height[i]=0;
        indegree[i]=0;
    }
}

int find(int x) {
    if (x != father[x]) {
        //return find(father[x]);//未优化状态
        father[x] = find(father[x]);//查找路径压缩
    }
    return father[x];
}

void Union(int x, int y) {
    x=find(x);
       y=find(y);
       if(x!=y){
           if(height[x]<height[y]){
               father[x]=y;
           }
           else if(height[x]>height[y]){
               father[y]=x;
           }
           else{
               father[y]=x;
               height[x]+=1;
           }
       }
}
int main() {
    int a, b;
    int k=0;

    while (1) { // 注意 while 处理多个 case

        k++;
      map<int,int>m;
     
      vector<pair<int,int>> data;
      
      int num=1;
      do{
          cin>>a>>b;
          if(a<0&&b<0){
              goto jieshu;
          }
          if(a==0&&b==0) break;
         data.push_back(make_pair(a,b));
          if(m[a]==0){
              m[a]=num++;
          }
          if(m[b]==0){
              m[b]=num++;
          }
      }while(a!=0&&b!=0);
      init(num);

      for(int i=0;i<data.size();i++){
          pair<int,int> d=data[i];
          int a=d.first;
          int b=d.second;
          a=m[a];
          b=m[b];
          indegree[b]+=1;
          Union(a,b);
      }
      int component=0;
      int flag1=0;
      for(int i=1;i<num;i++){
          if(i==find(i)){
              component+=1;
          }
          if(indegree[i]>1){
              flag1=1;
              break;
          }
      }
      if(flag1){
          printf("Case %d is not a tree.\n",k);
      }
      else{
          if(component>1){
              printf("Case %d is not a tree.\n",k);
          }
          else{
          printf("Case %d is a tree.\n",k);
          }
      }



    }
    jieshu:return 0;
}
// 64 位输出请用 printf("%lld")

10.1.4 寻找直系亲属///

这里用son数组j记录自己的子节点并且用高度来比会比较好一点

找出直系亲属_牛客题霸_牛客网 (nowcoder.com)

//大佬代码
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 50;

int son[MAXN];      //父节点是儿子，所以以son命名
int height[MAXN];    //表示结点高度，最小的儿子高度为0，越往下辈分越大

//并查集思想

void Initial() {               //初始化函数  父节点默认设为自己，高度默认为0
    for (int i = 0; i < MAXN; i++) {
        son[i] = i;
        height[i] = 0;
    }
}

int Find(int x, int y, int count) {
    if (son[x] == son[y] && x != y && son[x] != x &&
            son[y] != y) return -1; //若当前两个节点的父节点是同一个，即拥有同个儿子，则不是直系
    if (height[x] <
            height[y]) { //高度高的辈分大，则辈分高取自己的儿子，然后递归find，count作为记录取儿子的次数，取一次表面差一个辈分
        y = son[y];
        count++;
        return Find(x, y, count);
    } else if (height[x] > height[y]) { //同理
        x = son[x];
        count++;
        return Find(x, y, count);
    } else {
        return count;
    }
    return -1;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        Initial();
        for (int i = 0; i < n; i++) {
            string str;
            cin >> str;
            int a = str[0] -'A';    //由于是A-Z的字符，则用-'A'来变成数，方便记录son数组的值
            if (str[1] != '-') { //如果缺失则跳过
                int b = str[1] - 'A';
                son[b] = a;       //记录自己的儿子节点
                height[b] = 1 + height[a];  //b的高度是儿子的高度加1，以此类推，高度越高辈分越大
            }
            if (str[2] != '-') {
                int c = str[2] - 'A';
                son[c] = a;
                height[c] = 1 + height[a];
            }
        }
        for (int i = 0; i < m; i++) {
            string str;
            cin >> str;
            int a = str[0] - 'A';
            int b = str[1] - 'A';

            //两个判断有点冗余，可以封装成函数作为调用
            if (height[a] >=
                    height[b]) { //若a高度大于b，则a的辈分高，输出parent
                int ans = Find(a, b, 0);
                string str1 = "";
                if (ans == -1) {
                    str1 += "-";
                    cout << str1 << endl;
                } else if (ans == 1) {
                    str1 += "parent";
                    cout << str1 << endl;
                } else if (ans == 2) {
                    str1 += "grandparent";
                    cout << str1 << endl;
                } else if (ans > 2) {
                    str1 += "grandparent";
                    while (ans > 2) {
                        str1 = "great-" + str1;
                        ans--;
                    }
                    cout << str1 << endl;
                }
            } else if (height[a] <
                       height[b]) { //若a的高度低，则a的辈分低，输出child
                int ans = Find(a, b, 0);
                string str1 = "";
                if (ans == -1) {
                    str1 += "-";
                    cout << str1 << endl;
                } else if (ans == 1) {
                    str1 += "child";
                    cout << str1 << endl;
                } else if (ans == 2) {
                    str1 += "grandchild";
                    cout << str1 << endl;
                } else if (ans > 2) {
                    str1 += "grandchild";
                    while (ans > 2) {
                        str1 = "great-" + str1;
                        ans--;
                    }
                    cout << str1 << endl;
                }
            }
        }
    }
    return 0;
}

10.1.5 统计图的联通分支

本题主要是输入样例很大

第一题_牛客题霸_牛客网 (nowcoder.com)

//本题注意两件事，一是测试案例数据量很大，设置的数组大小记得扩大
//二是输入的节点编号不是连续的，为了方便出路将节点编号转变成连续的然后再用并查集的思想即可
#include <iostream>
#include<cstring>
#include<map>
using namespace std;
const int maxn = 1e6+ + 10;i9m,ik
int  father[maxn];
int height[maxn];//每个节点的高度，用于高树合并矮树
void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        //return find(father[x]);//未优化状态
        father[x] = find(father[x]);//查找路径压缩
    }
    return father[x];
}

void Union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;

        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1; //并查集中唯一可以让高度增加的方法
        }

    }
}

int main() {
    int x, y;
    init(maxn);
    map<int, int> m;
    int num = 0;
    while (scanf("%d %d", &x, &y) != EOF) {
        if (m[x] == 0) {
            m[x] = num++;
        }
        if (m[y] == 0) {
            m[y] = num++;
        }

        Union(m[x], m[y]);
    }
    int component = 0;
    for (int i = 0; i < num; i++) {
        if (i == find(i)) {
            component += 1;
        }
    }
    cout << component  << endl;
}

10.1.6 寻找集合内权重最大的节点

Head of a Gang_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<map>
const int maxn = 26;
using namespace std;
int father[maxn];
int height[maxn];
int phone[maxn];
void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
        phone[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x, int  y) {
    x = find(x);
    y = find(y);//记得别再写错了
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1;
        }
    }
}


int countFather(int x) {
    int count = 0;
    for (int i = 0; i < maxn; i++) {
        if (find(i) == find(x)) {
            count++;
        }
    }
    return count;
}


int main() {
    int num, weight;
    string a, b;
    int numa, numb, minute; //通话时长

    while (cin >> num >> weight) { // 注意 while 处理多个 case
        map<int, int> result;
        map<int, string> m;
        init(maxn);
        while (num--) {
            cin >> a >> b >> minute;
            numa = a[0] - 'A';
            numb = b[0] - 'A';
            m[numa] = a;
            m[numb] = b;
            phone[numa] += minute;
            phone[numb] += minute;
            Union(numa, numb);
        }
        for (int i = 0; i < maxn; i++) {
            if (i == find(i) && countFather(i) > 2) {
                int sumWeight, maxWeight, maxIndex;
                sumWeight = 0;
                maxWeight = 0;
                maxIndex = 0;
                for (int j = 0; j < maxn; j++) {
                    if (find(j) == i) {
                        sumWeight += phone[j];
                        if (phone[j] > maxWeight) {
                            maxWeight = phone[j];
                            maxIndex = j;
                        }
                    }
                }
                sumWeight /= 2;
                if (sumWeight > weight) {
                    result[maxIndex] = countFather(i);

                }
            }
        }
        cout << result.size() << endl;
        map<int, int>::iterator it;
        for (it = result.begin(); it != result.end(); it++) {
            cout << m[it->first] << " " << it->second << endl;
        }
    }
}

10.2 最小生成树

10.2.1 使用克鲁斯卡尔算法来解决最小生成树

还是畅通工程_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
const int maxn = 110;
using namespace std;
int father[maxn];
int height[maxn];

struct Edge {
    int from;
    int to;
    int length;
    bool operator<(const Edge& e) {
        return length < e.length;
    }
};

Edge edge[maxn * maxn];

void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x, int  y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1;
        }
    }
}

int kruskal(int n, int edgeNumber) {
    init(n);
    sort(edge, edge + edgeNumber);
    int sum = 0;
    for (int i = 0; i < edgeNumber; i++) {
        Edge current = edge[i];
        if (find(current.from) != find(
                    current.to)) { //将这条边联通不会产生回环

            Union(current.from, current.to);
            sum += current.length;
        }
    }
    return sum;

}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        int num = n * (n - 1) / 2;

        for (int i = 0; i < num; i++) {
            scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].length);


        }
        cout << kruskal(n, num) << endl;

    }
}

10.2.2 在二维平面上使用最小生成树

Freckles_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
const int maxn = 110;
using namespace std;
int father[maxn];
int height[maxn];

struct Edge {
    int from;
    int to;
    double length;
    bool operator<(const Edge& e) {
        return length < e.length;
    }
};

struct Point {
    double x, y;
    Point(double x, double y): x(x), y(y) {}
};

double distance1(Point* p1, Point* p2) {
    double dis = (p1->x - p2->x) * (p1->x - p2->x) + (p1->y - p2->y) *
                 (p1->y - p2->y);
    return sqrt(dis);
}

Edge edge[maxn * maxn];

void init(int n) {
    for (int i = 0; i <= n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x, int  y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1;
        }
    }
}

double kruskal(int n, int edgeNumber) {
    init(n);
    sort(edge, edge + edgeNumber);
    double sum = 0;
    for (int i = 0; i < edgeNumber; i++) {
        Edge current = edge[i];

        if (find(current.from) != find(
                    current.to)) { //将这条边联通不会产生回环

            Union(current.from, current.to);
            sum += current.length;
        }
    }
    return sum;

}

//3
//1.0 1.0
//2.0 2.0
//2.0 4.0

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        double x, y;
        vector<Point*> points;
        for (int i = 0; i < n; i++) {
            cin >> x >> y;
            points.push_back(new Point(x, y));
        }
        int num = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                edge[num].from = i;
                edge[num].to = j;
                edge[num].length = distance1(points[i], points[j]);
                num++;
            }
        }

        printf("%0.2f\n", kruskal(n, num));


    }
}

10.3.3 Jungle Roads

Jungle Roads_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
const int maxn = 110;
using namespace std;
int father[maxn];
int height[maxn];

struct Edge {
    int from;
    int to;
    int length;
    bool operator<(const Edge& e) {
        return length < e.length;
    }
};

Edge edge[maxn * maxn];

void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x, int  y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x] += 1;
        }
    }
}

int kruskal(int n, int edgeNumber) {
    init(n);
    sort(edge, edge + edgeNumber);
    int sum = 0;
    for (int i = 0; i < edgeNumber; i++) {
        Edge current = edge[i];
        if (find(current.from) != find(
                    current.to)) { //将这条边联通不会产生回环

            Union(current.from, current.to);
            sum += current.length;
        }
    }
    return sum;

}



int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        char from, to;
        int f, t, num, weight;
        int edgeNums = 0;
        for (int i = 1; i < n; i++) {
            cin >> from >> num;
            f = from - 'A';
            while (num--) {
                cin >> to >> weight;
                t = to - 'A';
                edge[edgeNums].from = f;
                edge[edgeNums].to = t;
                edge[edgeNums].length = weight;
                edgeNums++;
            }
        }
        cout << kruskal(n, edgeNums) << endl;
    }
}

10.3 最短路径

10.3.1 迪杰斯特拉算法

本题暂时找不到测试源：畅通工程续_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
const int maxn = 210;
using namespace std;

const int INF=INT_MAX;//无穷大

struct Edge{
    int to;
    int length;
    Edge(int t, int l):to(t),length(l){}
};
vector<Edge> graph[maxn];//一个二维数组

int dis[maxn];//顶点到其他所有点的长度
bool visit[maxn]; //判断顶点是否已被纳入集合内

void Dijkstra(int  start, int n){
    //memset能赋值0和-1其他不能，在头文件<cstring>里
    memset(visit,false, sizeof(visit));
    //fill算法可以赋任何值在头文件<algorithm>里
    fill(dis,dis+n,INF);
    dis[start]=0;
    for(int i=0;i<n;i++){
        int u=-1;
        for(int j=0;j<n;j++){
            if(visit[j]){
                continue;
            }
            if(u==-1||dis[j]<dis[u]){
                u=j;
            }
        }


      for(int j=0;j<graph[u].size();j++){
                   int v=graph[u][j].to;
                   int d=graph[u][j].length;
                   if(dis[u]+d<dis[v]){
                       dis[v]=dis[u]+d;
                       }
                   }

        visit[u]=true;
    }
    return;
}
//3 3
//0 1 1
//0 2 3
//1 2 1


int main(){
    int n,m;
    while(cin>>n>>m){
        memset(graph,0,sizeof (graph));
        while (m--) {
            int from,to,length;
            cin>>from>>to>>length;
            //索引当作from
            graph[from].push_back(Edge(to,length));
            graph[to].push_back(Edge(from,length));

        }
        int start;
        int terminal;
        cin>>start>>terminal;
        Dijkstra(start,n);
        if(dis[terminal]==INF){
            cout<<-1<<endl;
        }
        else{
            cout<<dis[terminal]<<endl;
        }
    }

}

使用优先队列优化后的算法：

#include <iostream>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<cmath>
#include<algorithm>
const int maxn = 210;
using namespace std;

const int INF=INT_MAX;//无穷大

struct Edge{
    int to;
    int length;
    Edge(int t, int l):to(t),length(l){}
};

struct Point{
    int number;
    int distance;
    Point(int n, int d):number(n),distance(d){}
    
    //运算符重载记得学会怎么写
    bool operator<(const Point& p) const{
        return distance<p.distance;
    }
};
vector<Edge> graph[maxn];//一个二维数组
int dis[maxn];//顶点到其他所有点的长度
bool visit[maxn]; //判断顶点是否已被纳入集合内
void Dijkstra(int  start, int n){
    //memset能赋值0和-1其他不能，在头文件<cstring>里
    memset(visit,false, sizeof(visit));
    //fill算法可以赋任何值在头文件<algorithm>里
    fill(dis,dis+n,INF);
    dis[start]=0;
    priority_queue<Point> pq;
    pq.push(Point(start,dis[start]));
    while(!pq.empty()){
        Point p=pq.top();
        int u=p.number;
        pq.pop();
     for(int j=0;j<graph[u].size();j++){
        int v=graph[u][j].to;
        int d=graph[u][j].length;
          if(dis[u]+d<dis[v]){
            dis[v]=dis[u]+d;
            pq.push(Point(v,dis[v]));
                }
                     }

          visit[u]=true;
    }

return;
}


int main(){
    int n,m;
    while(cin>>n>>m){
        memset(graph,0,sizeof (graph));
        while (m--) {
            int from,to,length;
            cin>>from>>to>>length;
            //索引当作from
            graph[from].push_back(Edge(to,length));
            graph[to].push_back(Edge(from,length));
        }
        int start;
        int terminal;
        cin>>start>>terminal;
        Dijkstra(start,n);
        if(dis[terminal]==INF){
            cout<<-1<<endl;
        }
        else{
            cout<<dis[terminal]<<endl;
        }
    }
}

最短路径问题_牛客题霸_牛客网 (nowcoder.com)

本题注意在选择的时候注意代价：

#include <iostream>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<cmath>
#include<algorithm>
#include<climits>
const int maxn = 1e5+10;
using namespace std;

const int INF = INT_MAX; //无穷大

struct Edge {
    int to;
    int length;
    int price;
    Edge(int t, int l, int p): to(t), length(l), price(p) {}
};

struct Point {
    int number;
    int distance;
    Point(int n, int d): number(n), distance(d) {}

    //运算符重载记得学会怎么写
    bool operator<(const Point& p) const {
        return distance < p.distance;
    }
};
vector<Edge> graph[maxn];//一个二维数组
int dis[maxn];//顶点到其他所有点的长度
int cost[maxn];
bool visit[maxn]; //判断顶点是否已被纳入集合内
void Dijkstra(int  start, int n) {
    //memset能赋值0和-1其他不能，在头文件<cstring>里
    memset(visit, false, sizeof(visit));
    //fill算法可以赋任何值在头文件<algorithm>里
    fill(dis, dis + n, INF);
    fill(cost, cost + n, INF);
    dis[start] = 0;
    cost[start] = 0;
    priority_queue<Point> pq;
    pq.push(Point(start, dis[start]));
    while (!pq.empty()) {
        Point p = pq.top();
        int u = p.number;
        pq.pop();
        for (int j = 0; j < graph[u].size(); j++) {
            int v = graph[u][j].to;
            int d = graph[u][j].length;
            int p = graph[u][j].price;
            if (dis[u] + d < dis[v] || (dis[u] + d == dis[v]) && cost[u] + p < cost[v]) {
                dis[v] = dis[u] + d;
                cost[v] = cost[u] + p;
                pq.push(Point(v, dis[v]));
            }
        }

        visit[u] = true;
    }

    return;
}


int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;
        memset(graph, 0, sizeof (graph));
        while (m--) {
            int from, to, length, w;
            cin >> from >> to >> length >> w;
            //索引当作from
            graph[from].push_back(Edge(to, length, w));
            graph[to].push_back(Edge(from, length, w));
        }
        int start;
        int terminal;
        cin >> start >> terminal;
        Dijkstra(start, n + 1);
        if (dis[terminal] == INF) {
            cout << -1 << endl;
        } else {
            cout << dis[terminal] << " " << cost[terminal] << endl;
        }
    }
}

10.3.1.1

最短路径_牛客题霸_牛客网 (nowcoder.com)

题乍一看是单元最短路径问题，这是一道披着最短路径外衣的最小生成树，因为路径长度是从20开始，其实举例到第3条路径就可以发现：22=4>20+21，也就是说，当一条边的两个端点不在同一集合时，这条边的长度就是这两点间的最短距离，可以直接取mod，这时只用更新一下两个集合里各点间的距离就行，而如果这条边的两个端点在同一集合，那么这条边就可以直接舍去了，因为这条边的长度将会比之前出现的所有边长度的总和还要长。
因此，只需要采用最小生成树的思想，对最小生成树的各条边进行Dijstra算法即可。

/*方法二，使用并查集，因为后面边的长度比前面所有边长之和还要长*/
/*所以后面加的边就不用再考虑，如果两个点不属于一个集合，*/
/*直接合并这两个点即可，此时长度一定是最短的*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

const int MAXN = 100 + 20;
const int MOD = 100000;
const int INF = INT_MAX;
int father[MAXN];
int height[MAXN];

void Initial() {
    for (int i = 0; i < MAXN; i++) {
        father[i] = i;
        height[i] = 1;
    }
    return;
}
int Find(int x) {
    if (father[x] != x) {
        father[x] = Find(father[x]);
    }
    return father[x];
}
void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) {
        return;
    }
    if (height[x] < height[y]) {
        father[x] = y;
    } else if (height[x] > height[x]) {
        father[y] = x;
    } else {
        father[x] = y;
        height[y]++;
    }
    return;
}
struct Point {
    int number = 0;
    int distance;
    Point(int n, int d): number(n), distance(d) {}
    bool operator<(const Point& p)const {
        return distance > p.distance;
    }
};
struct Edge {
    int to;
    int k;//第几条路
    Edge(int t, int kt): to(t), k(kt) {}
    Edge() {}
    bool operator < (Edge e) const {
        return k < e.k;
    }
};
vector<Edge> edges[MAXN];
int dis[MAXN];
void Dijstra(int start, int n) {
    fill(dis, dis + n + 1, INF);
    dis[start] = 0;
    priority_queue<Point> Q;
    Q.push(Point(start, 0));
    while (!Q.empty()) {
        Point p = Q.top();
        Q.pop();
        int from = p.number;
        for (int i = 0; i < edges[from].size(); i++) {
            int to = edges[from][i].to;
            int len = edges[from][i].k;
            if (dis[to] > dis[from] + len) {
                dis[to] = dis[from] + len;
                Q.push(Point(to, dis[to]));
            }
        }
    }
    return;
}
int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    int c1, c2;
    Initial();
    int len = 1;
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &c1, &c2);
        if (Find(c1) != Find(c2)) {
            Union(c1, c2);
            edges[c1].push_back(Edge(c2, len));
            edges[c2].push_back(Edge(c1, len));
        }
        len = (len * 2) % MOD;
    }
    Dijstra(0, N);
    for (int i = 1; i < N; i++) {
        printf("%d\n", (dis[i] == INF) ? -1 : dis[i] % MOD);
    }
    return 0;
}

10.4 拓扑排序

杭电oJ最近关闭了，只能找到关于这道题的博客：

【HDU – 1285】确定比赛名次 （拓扑排序）_牛客博客 (nowcoder.net)

#include <iostream>
#include <queue>
#include <cstdio>
#include <climits>
#include<cstring>

using namespace std;

const int maxn=510;

int inDegree[maxn];
vector<int> graph[maxn];
vector<int> topoSort(int n){
    vector<int> res;
    priority_queue<int, vector<int>,greater<int>> pq;//默认为大顶堆，所以要修改为小顶堆
    for(int i=1;i<=n;i++){//i的范围记得要看清
        if(inDegree[i]==0){
            pq.push(i);
        }
    }
    while(!pq.empty()){
        int u=pq.top();
        pq.pop();
        res.push_back(u);
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i];//连接的点
            inDegree[v]--;
            if(inDegree[v]==0){
                pq.push(v);
            }
        }

    }
    return res;

}

//4 3
//1 2
//2 3
//4 3
int main(){
    int n,m;
    while(cin>>n>>m){
        memset(graph,0,sizeof (graph));
        memset(inDegree,0,sizeof (inDegree));
        int from,to;
        while(m--){
            cin>>from>>to;
            graph[from].push_back(to);
            inDegree[to]++;
        }
        vector<int> res=topoSort(n);
        for(int i=0;i<n;i++){
            cout<<res[i]<<" ";
        }
        cout<<endl;
    }


    return 0;
}

除此之外拓扑排序还可以用来判断是否有环，当拓扑排序无法将所有序列纳入序列中，图中便存在环，判读有向图有环：

Legal or Not_牛客网 (nowcoder.com)

#include <iostream>
#include <queue>
#include <cstdio>
#include <climits>
#include<cstring>

using namespace std;

const int maxn=510;

int inDegree[maxn];
vector<int> graph[maxn];

vector<int> topoSort(int  n){
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0;i<n;i++){//要注意节点的排序
        if(inDegree[i]==0){
            pq.push(i);
        }
    }
    vector<int> res;
    while(!pq.empty()){
        int u=pq.top();
        pq.pop();
        res.push_back(u);
        for(int i=0;i<graph[u].size();i++){
            int v=graph[u][i];
            inDegree[v]--;
            if(inDegree[v]==0){
                pq.push(v);
            }
        }
    }
    return res;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0) break;
        memset(graph,0,sizeof (graph));
        memset(inDegree,0,sizeof (inDegree));
        int from,to;
        while(m--){
            cin>>from>>to;
            graph[from].push_back(to);
            inDegree[to]++;
        }
        vector<int> res=topoSort(n);
        if(res.size()==n){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

判断无向图有环,可以直接使用并查集（684. 冗余连接 – 力扣（Leetcode））

class Solution {
public:
	int father[1001];
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {		
		for(int i=0;i<1001;i++) father[i]=i;
		for(int i=0;i<edges.size();i++){
		vector<int> res=edges[i];
		int x=res[0]; int y=res[1];
		if(find(x)==find(y)) return res;
		else{
			Union(x,y);
		}

		}
		return edges[0];

    }
	int find(int x){
	if(x!=father[x]){
	father[x]=find(father[x]);
	}
	return father[x];
	
	}
	void Union(int x,int y){
		x=find(x);
		y=find(y);
		if(x!=y) father[x]=y;
		return;
		
	}
	
};

10.5 关键路径

• 完成工程最短需要多少时间

• 那些活动影响工程进度的关键

• 关键路径：源点到汇点的最长路径，但是直接求最长路径不好求，所以在代码上我们求最早开始 时间和最晚开始时间

  

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <climits>

using namespace std;

const int MAXN = 1000 + 10;
const int INF = INT_MAX;

struct Edge {
    int to;                                     //终点
    int length;                                 //长度
    Edge(int t, int l): to(t), length(l) {}
};

vector<Edge> graph[MAXN];
int earliest[MAXN];                             //最早完成时间
int latest[MAXN];                               //最晚完成时间
int inDegree[MAXN];                             //入度

int CriticalPath(int n) {
    vector<int> topology;                       //拓扑序列
    queue<int> node;
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) {
            node.push(i);
            earliest[i] = 1;                    //初始化为1
        }
    }
    int totalTime = 0;                          //总耗时
    while (!node.empty()) {
        int u = node.front();
        topology.push_back(u);
        node.pop();
        for (int i = 0; i < graph[u].size(); ++i) {
            int v = graph[u][i].to;
            int l = graph[u][i].length;
            earliest[v] = max(earliest[v], earliest[u] + l);
            inDegree[v]--;
            if (inDegree[v] == 0) {
                node.push(v);
                totalTime = max(totalTime, earliest[v]);
            }
        }
    }
    for (int i = topology.size() - 1; i >= 0; --i) {
        int u = topology[i];
        if (graph[u].size() == 0) {
            latest[u] = earliest[u];            //汇点的最晚完成时间初始化
        } else {
            latest[u] = INF;                    //非汇点的最晚完成时间初始化
        }
        for (int j = 0; j < graph[u].size(); ++j) {
            int v = graph[u][j].to;
            int l = graph[u][j].length;
            latest[u] = min(latest[u], latest[v] - l);
        }
    }
    return totalTime;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(graph, 0, sizeof(graph));
        memset(earliest, 0, sizeof(earliest));
        memset(latest, 0, sizeof(latest));
        memset(inDegree, 0, sizeof(inDegree));
        while (m--) {
            int from, to, length;
            scanf("%d%d%d", &from, &to, &length);
            graph[from].push_back(Edge(to, length));
            inDegree[to]++;
        }
        int answer = CriticalPath(n);
        printf("%d\n", answer);
    }
    return 0;
}

11.补充刷题

11.1 二叉树找父节点

二叉树_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
		while(a!=b){
		if(a>b) a/=2;
		else b/=2;
		}
		cout<<a<<endl;
    }
}
// 64 位输出请用 printf("%lld")

11.2 后缀字串排序

后缀子串排序_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    string str;
    while (cin >> str) {
        vector<string> vec;
        for (int i = str.size() - 1; i >= 0; i--) {
            vec.push_back(str.substr(i));
        }
        sort(vec.begin(), vec.end());
        for (int i = 0; i < vec.size(); i++) {
            cout << vec[i] << endl;
        }
    }
}

11.3 寻找大富翁

寻找大富翁_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

//3 1
//2 5 -1

int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        int data;
        priority_queue<int> pq;
        while (n--) {
            cin >> data;
            pq.push(data);
        }
        while (!pq.empty()) {
            int u = pq.top();
            pq.pop();
            cout << u << " ";
            m--;
            if (m == 0) break;
        }
        cout << endl;

    }}

11.4 还是A+B

还是A+B_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

//1 2 1
//A,B,K
int strToInt(string str){
	int res=0;
	for(int i=0;i<str.size();i++){
	res=res*10+(str[i]-'0');
	}
	return res;
}

int main(){
	string a,b;
	int k;
	while(cin>>a>>b>>k){
	if(a=="0"&&b=="0") break;
	bool flag=true;
	int i=a.size()-1;
	int j=b.size()-1;
	while(k--){
		if(i<0||j<0) break;
		if(a[i]!=b[j]){
		flag=false;
		break;
		
		}
		i--;
		j--;

	}
	if(flag) cout<<-1<<endl;
	else cout<<strToInt(a)+strToInt(b)<<endl;
		
	}
	}

11.5 判断欧拉回路

欧拉回路_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int maxn = 1001;
int father[maxn];

void init(int n) {
    for (int i = 1; i <= n; i++) father[i] = i;
}

int  find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        father[x] = y;
    }
}

//1 2 1
//A,B,K

int main() {
    int n, m;
    while (cin >> n >> m) {
        int x, y;
        bool flag = 1;
        init(n);
        int a, b;
        map<int, int> edge;
        while (m--) {
            if (m == 0) break;
            cin >> x >> y;
            edge[x] = 1;
            edge[y] = 1;
            if (x != y && find(x) == find(y)) {
                flag = 0;
            }
            Union(x, y);
        }
        cin >> x >> y;
        if (x == y) flag = 1;
        if (flag) {

            if (x == y) {
                Union(x, y);
                int res = 0;
                for (auto data : edge) {
                    if (data.first == find(data.first)) res++;
                }
                if (res == 1) cout << 1 << endl;
                else cout << 0 << endl;
            } else {
                if (father[x] == father[y]) cout << 1 << endl;
                else cout << 0 << endl;
            }
        } else cout << 0 << endl;

    }
}

11.6 字符串排序

字符串排序_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=21;

int main(){
	string str;
	map<int,char> dataMap;
	vector<int> vec;
	while(cin>>str){
		for(int i=0;i<str.size();i++){
		dataMap[int(str[i])]=str[i];
		vec.push_back(int(str[i]));
		
		}
		sort(vec.begin(),vec.end());
		for(int i=0;i<vec.size();i++){
		cout<<dataMap[vec[i]];
		
		}
		cout<<endl;
	
	}
}

11.7 畅通工程

畅通工程_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn = 21;
int father[maxn];

struct graph {
    int from, to, length;
    graph(int f, int t, int l): from(f), to(t), length(l) {}
    bool operator<(const graph& g ) const {
        return length > g.length;
    }

};


void init(int n) {
    for (int i = 1; i <= n; i++)
        father[i] = i;


}

int find(int x) {
    if (x != father[x]) {
        father[x] = find(father[x]);
    }
    return father[x];

}

void Union(int x, int y) {
    x = find(x);
    y = find(y);
    father[x] = y;


}

bool connectGraph(int n) {
    int component = 0;
    for (int i = 1; i <= n; i++) {
        if (i == father[i]) component++;
    }
    if (component == 1) return true;
    return false;

}

/*3 3
1 2 1
1 3 2
2 3 4*/
int main() {
    int n, m;
    while (cin >> m >> n) {
        if (m == 0) break;
        init(n);

        int from, to, length;
        priority_queue<graph> edges;
        while (m--) {
            cin >> from >> to >> length;
            edges.push(graph(from, to, length));
        }

        int res = 0;

        while (!edges.empty()) {
            graph minEdges = edges.top();
            edges.pop();
            int from = minEdges.from;
            int to = minEdges.to;
            if (find(from) != find(to)) {
                res += minEdges.length;
                Union(from, to);

            }

        }
        if (connectGraph(n)) {
            cout << res << endl;
        } else cout << "?" << endl;


    }


}

11.8 买房子

买房子_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=21;


int main(){
double n,k;
while(cin>>n>>k){
	int year=1;
	double tar=200;
	double caichan=n;
	while(caichan<tar&&year<=21){
		caichan+=n;
		tar=tar*(1+k*0.01);
		year++;
	}
	if(year>21) cout<<"impossible"<<endl;
	else cout<<year<<endl;
}
}

11.9 ZOJ字符串

ZOJ_牛客题霸_牛客网 (nowcoder.com)

本题最重要的是学会如何删除字符

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=21;

int main(){
	string str;
	char chaxun[]={'Z','O','J'};
	while(cin>>str){
	int index=0;
	string::iterator it;
	while(str.size()!=0){
		for(it=str.begin();it!=str.end();it++){
			if((*it)==chaxun[index]){
				cout<<*it;
				str.erase(it);
				break;		
			}
		
		}
		index=(index+1)%3;
		
		}
	}
	
	}

11.10 bg

毕业bg_牛客题霸_牛客网 (nowcoder.com)

本题用动态规划做不会超时，直接使用dfs会超时

dfs版本：

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=31;
int res=0;
bool visit[maxn];


struct bg{
    int happy,continuous,time;
    bg(int h, int l, int t):happy(h),continuous(l),time(t){}
    bool operator<(const bg& b) const {
        return time<b.time;
    }


};

vector<bg> vec;
void dfs(int now,int index, int n, int happy){

    for(int i=index;i<n;i++){
        if(now>vec[i].time) return;
        if(now+vec[i].continuous<=vec[i].time){
            dfs(now+vec[i].continuous,i+1,n,happy+vec[i].happy);
        }
        dfs(now,i+1,n,happy);

    }
    res=max(happy,res);
}




int main(){
    int n;
    while(cin>>n){
        if(n==-1) break;
        vec.clear();
        int h,l,t;
        for(int i=0;i<n;i++){
        cin>>h>>l>>t;
        vec.push_back(bg(h,l,t));

        }
        sort(vec.begin(),vec.end());

        dfs(0,0,n,0);
        cout<<res<<endl;
}
}

动态规划版本：

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=31;
int res=0;
bool visit[maxn];


struct bg{
    int happy,continuous,time;
    bg(int h, int l, int t):happy(h),continuous(l),time(t){}
    bool operator<(const bg& b) const {
        return time<b.time;
    }


};

vector<bg> vec;
void dfs(int now,int index, int n, int happy){

    for(int i=index;i<n;i++){
        if(now>vec[i].time) return;
        if(now+vec[i].continuous<=vec[i].time){
            dfs(now+vec[i].continuous,i+1,n,happy+vec[i].happy);
        }
        dfs(now,i+1,n,happy);

    }
    res=max(happy,res);
}




int main(){
    int n;
    while(cin>>n){
        if(n==-1) break;
        vec.clear();
        int h,l,t;
        for(int i=0;i<n;i++){
        cin>>h>>l>>t;
        vec.push_back(bg(h,l,t));

        }
        sort(vec.begin(),vec.end());

        dfs(0,0,n,0);
        cout<<res<<endl;



    }



}

11.11 完全二叉树查找

树查找_牛客题霸_牛客网 (nowcoder.com)

本题利用完全二叉树的性质

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=31;


int main(){
	vector<int> vec;
	int n,u,k;
	while(cin>>n){
		vec.clear();
		vec.push_back(0);
		for(int i=0;i<n;i++){
		cin>>u;
		vec.push_back(u);
		}
		cin>>k;
		int minNode=pow(2,k-1);
		int maxNode=min(int(pow(2,k)),n);
	if(minNode>n) cout<<"EMPTY";
	else{
	for(int i=minNode;i<maxNode;i++){
		cout<<vec[i]<<" ";
		}
	}
		cout<<endl;
	
	
	}
	
	
	}

11.12 守形数

守形数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<climits>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = INT_MAX;

int main() {
    int n, res;
    while (cin >> n) {
        res = n * n;
        string str = to_string(res);
        string n_str = to_string(n);
        string str2 = str.substr(str.size() - n_str.size());
        if (str2 == n_str) {
            cout << "Yes!" << endl;
        } else cout << "No!" << endl;

    }
}

11.13 围圈报数

围圈报数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<climits>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
const int maxn = INT_MAX;


int main() {
    int m;
    int n;
    while (cin >> n) {
        while (n--) {
            while (cin >> m) {
                queue<int> q;
                for (int i = 1; i <= m; i++) {
                    q.push(i);
                }
                while (!q.empty()) {
                    if (q.size() == 1) {
                        cout << q.front();
                        break;
                    }
                    int u;
                    for (int i = 0; i < 2; i++) {
                        u = q.front();
                        q.pop();
                        q.push(u);
                    }
                    u = q.front();
                    q.pop();
                    cout << u << " ";


                }
                cout << endl;


            }

        }
    }
}

11.14 反序数

反序相等_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;

int reversInt(int a){
int res=0;
while(a!=0){
	res=res*10+a%10;
	a/=10;
}
return res;
}

int main() {
	for(int i=1000;i<=1111;i++){
		if(reversInt(i)==i*9){
		cout<<i<<endl;
		}
	
	}
}
// 64 位输出请用 printf("%lld")

nnectGraph(n)) {
cout << res << endl;
} else cout << “?” << endl;

}

}

### 11.8 买房子 

[买房子_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/a4b46b53773e4a8db60b5f7629ce03e9?tpId=40&tags=&title=&difficulty=&judgeStatus=3&rp=1&sourceUrl=&gioEnter=menu)

```c++
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=21;


int main(){
double n,k;
while(cin>>n>>k){
	int year=1;
	double tar=200;
	double caichan=n;
	while(caichan<tar&&year<=21){
		caichan+=n;
		tar=tar*(1+k*0.01);
		year++;
	}
	if(year>21) cout<<"impossible"<<endl;
	else cout<<year<<endl;
}
}

11.9 ZOJ字符串

ZOJ_牛客题霸_牛客网 (nowcoder.com)

本题最重要的是学会如何删除字符

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=21;

int main(){
	string str;
	char chaxun[]={'Z','O','J'};
	while(cin>>str){
	int index=0;
	string::iterator it;
	while(str.size()!=0){
		for(it=str.begin();it!=str.end();it++){
			if((*it)==chaxun[index]){
				cout<<*it;
				str.erase(it);
				break;		
			}
		
		}
		index=(index+1)%3;
		
		}
	}
	
	}

11.10 bg

毕业bg_牛客题霸_牛客网 (nowcoder.com)

本题用动态规划做不会超时，直接使用dfs会超时

dfs版本：

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=31;
int res=0;
bool visit[maxn];


struct bg{
    int happy,continuous,time;
    bg(int h, int l, int t):happy(h),continuous(l),time(t){}
    bool operator<(const bg& b) const {
        return time<b.time;
    }


};

vector<bg> vec;
void dfs(int now,int index, int n, int happy){

    for(int i=index;i<n;i++){
        if(now>vec[i].time) return;
        if(now+vec[i].continuous<=vec[i].time){
            dfs(now+vec[i].continuous,i+1,n,happy+vec[i].happy);
        }
        dfs(now,i+1,n,happy);

    }
    res=max(happy,res);
}




int main(){
    int n;
    while(cin>>n){
        if(n==-1) break;
        vec.clear();
        int h,l,t;
        for(int i=0;i<n;i++){
        cin>>h>>l>>t;
        vec.push_back(bg(h,l,t));

        }
        sort(vec.begin(),vec.end());

        dfs(0,0,n,0);
        cout<<res<<endl;
}
}

动态规划版本：

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
using namespace std;
const int maxn=31;
int res=0;
bool visit[maxn];


struct bg{
    int happy,continuous,time;
    bg(int h, int l, int t):happy(h),continuous(l),time(t){}
    bool operator<(const bg& b) const {
        return time<b.time;
    }


};

vector<bg> vec;
void dfs(int now,int index, int n, int happy){

    for(int i=index;i<n;i++){
        if(now>vec[i].time) return;
        if(now+vec[i].continuous<=vec[i].time){
            dfs(now+vec[i].continuous,i+1,n,happy+vec[i].happy);
        }
        dfs(now,i+1,n,happy);

    }
    res=max(happy,res);
}




int main(){
    int n;
    while(cin>>n){
        if(n==-1) break;
        vec.clear();
        int h,l,t;
        for(int i=0;i<n;i++){
        cin>>h>>l>>t;
        vec.push_back(bg(h,l,t));

        }
        sort(vec.begin(),vec.end());

        dfs(0,0,n,0);
        cout<<res<<endl;



    }



}

11.11 完全二叉树查找

树查找_牛客题霸_牛客网 (nowcoder.com)

本题利用完全二叉树的性质

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=31;


int main(){
	vector<int> vec;
	int n,u,k;
	while(cin>>n){
		vec.clear();
		vec.push_back(0);
		for(int i=0;i<n;i++){
		cin>>u;
		vec.push_back(u);
		}
		cin>>k;
		int minNode=pow(2,k-1);
		int maxNode=min(int(pow(2,k)),n);
	if(minNode>n) cout<<"EMPTY";
	else{
	for(int i=minNode;i<maxNode;i++){
		cout<<vec[i]<<" ";
		}
	}
		cout<<endl;
	
	
	}
	
	
	}

11.12 守形数

守形数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<climits>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = INT_MAX;

int main() {
    int n, res;
    while (cin >> n) {
        res = n * n;
        string str = to_string(res);
        string n_str = to_string(n);
        string str2 = str.substr(str.size() - n_str.size());
        if (str2 == n_str) {
            cout << "Yes!" << endl;
        } else cout << "No!" << endl;

    }
}

11.13 围圈报数

围圈报数_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
#include<cstring>
#include<string>
#include<vector>
#include<climits>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
const int maxn = INT_MAX;


int main() {
    int m;
    int n;
    while (cin >> n) {
        while (n--) {
            while (cin >> m) {
                queue<int> q;
                for (int i = 1; i <= m; i++) {
                    q.push(i);
                }
                while (!q.empty()) {
                    if (q.size() == 1) {
                        cout << q.front();
                        break;
                    }
                    int u;
                    for (int i = 0; i < 2; i++) {
                        u = q.front();
                        q.pop();
                        q.push(u);
                    }
                    u = q.front();
                    q.pop();
                    cout << u << " ";


                }
                cout << endl;


            }

        }
    }
}

11.14 反序数

反序相等_牛客题霸_牛客网 (nowcoder.com)

#include <iostream>
using namespace std;

int reversInt(int a){
int res=0;
while(a!=0){
	res=res*10+a%10;
	a/=10;
}
return res;
}

int main() {
	for(int i=1000;i<=1111;i++){
		if(reversInt(i)==i*9){
		cout<<i<<endl;
		}
	
	}
}
// 64 位输出请用 printf("%lld")