Niuke - Huawei question bank (61~70)

---

61. Put apples

#include <bits/stdc++.h>

using namespace std;

int process(int m, int n){
    
    if(m < 0 || n < 0){
    
        return 0;
    }
    else if(m == 1 || n == 1){
    
        return 1;
    }
    else {
    
        //  In other cases , We have to calculate one less plate , And taking an apple from all the plates 
        return process(m, n - 1) + process(m - n, n); //
    }
    
}

int main(){
    
    int m = 0, n = 0;
    
    while(cin >> m >> n){
    
        int res = process(m, n);
        
        cout << res << endl;
    }
    
    return 0;
}

62. Find input integers in binary 1 The number of

#include<bits/stdc++.h>

using namespace std;

void process(int num, int& res){
    
    while(num != 0){
    
        res++;
        num = num & (num - 1);
    }
}

int main(){
    
    int num = 0;
    while(cin>>num){
    
        int res = 0;
        process(num, res);
        cout<<res<<endl;
    }
        
    return 0;
}

63.DNA Sequence

#include <bits/stdc++.h>

using namespace std;

void process(string str, int num, string& res){
    
    vector<string> vec; // Save all possible strings 
    
    for(int i = 0; i < str.size() - num + 1; i++){
    
        string tmp = str.substr(i, num);
        //cout << tmp << endl;
        vec.push_back(tmp);
    }
    
    int maxLen = INT_MIN;
    for(string s : vec){
    
        int t = 0;
        for(char ch : s){
    
            if(ch == 'C' || ch == 'G'){
    
                t++; // In the current string C and G The number of 
            }
        }
        
        if(t > maxLen){
    
            res = s;
            maxLen = t;
        }
    }
}

int main(){
    
    string str = "";
    cin >> str;
    int n = 0;
    cin >> n;
    
    string res = "";
    process(str, n, res);
    
    cout << res << endl;
    
    return 0;
}

64.MP3 Cursor position

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    // Input 
    int musicNum = 0;
    string command = "";
    cin >> musicNum;
    cin >> command;
    
    // Processing command 
    if(musicNum <= 4){
    
        int curMusicPos = 1; // A position of the current cursor 
        for(char ch : command){
    
            if(ch == 'U') curMusicPos--;
            else curMusicPos++;
        }
        
        // Output 
        for(int i = 1; i <= musicNum; i++){
    
            cout << i << " ";
        }
        cout << endl;
        //  One thing to note here is that the final position may exceed musicNum, Take a mold , Change to this range 
        if(curMusicPos >= 0){
    
            cout << (curMusicPos) % musicNum << endl; //
        }
        else{
    
            cout << (musicNum + curMusicPos + 1) % musicNum << endl;
        }
    }
    
    else{
     //musicNum > 4
        int curMusicPos = 1; // A position of the current cursor 
        int head = 1, end = 4; //head Which song is at the head of the current list , end Which song is at the end of the current list 
        
        for(char ch : command){
    
            if(ch == 'U') {
    
                curMusicPos--;
                // If the cursor is smaller than the first song 
                if(curMusicPos < 1){
     // Jump to the last page 
                    curMusicPos = musicNum; // Update cursor position 
                    head = musicNum - 4 + 1; // Update list header 
                    end = musicNum; // Update the end of the list 
                }
                else{
     // If the cursor is not less than 1
                    if(curMusicPos < head){
     // If the current position is smaller than the current list header , Description to update the list 
                        head = curMusicPos; // Update list header 
                        end--; // Update the end of the list 
                    }
                }
            }
            // ch == 'D'
            else{
     
                curMusicPos++;
                // If the cursor is larger than the position of the last song 
                if(curMusicPos > musicNum){
     // Jump to the position on the first page 
                    curMusicPos = 1; // Update cursor position 
                    head = 1; // Update list header 
                    end = 4; // Update the end of the list 
                }
                else{
     // If the cursor is not greater than musicNum
                    if(curMusicPos > end){
     // If the current position is larger than the current end of the list , Description to update the list 
                        end = curMusicPos; // Update the end of the list 
                        head++; // Update list header 
                    }
                }
            }
           
        }
         
        // Output 
        for(int i = head; i <= end; i++){
    
            cout << i << " ";
        }
        cout << endl;
        cout << curMusicPos << endl;
    }
      
    return 0;
}

65. Find two strings a,b The longest common substring in

#include <bits/stdc++.h>

using namespace std;

//dp
//dp[i][j] Express   To s1 The first i individual , To s2 The first j Up to   The length of the common substring  ( among s1 Shorter )
void longestCommonSubsequence(string s1, string s2, string& res) {
    
    vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
    int maxLength = INT_MIN, end = 0; //end Represents the last position of the string  ( No more than s1 The length of )
    
    for(int i = 1; i <= s1.size(); i++){
    
        for(int j = 1; j <= s2.size(); j++){
    
            if(s1[i - 1] == s2[j - 1]){
    
                dp[i][j] = dp[i - 1][j - 1] + 1; // Then increase the length 
            }
            else{
    
                dp[i][j] = 0; // // The position is 0
            }
            
            if(dp[i][j] > maxLength){
     // Update maximum length 
                maxLength = dp[i][j];
                end = i - 1; //
            }
        }
    }

    res = s1.substr(end - maxLength + 1, maxLength);
}

int main(){
    
    string s1 = "";
	string s2 = "";

	getline(cin, s1);
	getline(cin, s2);
    
    if(s1.length() > s2.length()){
    
        swap(s1, s2); // Make the smaller string first 
    } 
            
	string res = "";
	longestCommonSubsequence(s1, s2, res);
	cout << res << endl;
    
    return 0;
}

66. Configuration file recovery

#include <bits/stdc++.h>

using namespace std;

vector<pair<string, string>> youXiaoCommand = {
    
    {
    "reset", ""},
    {
    "reset", "board"},
    {
    "board", "add"},
    {
    "board", "delete"},
    {
    "reboot", "backplane"},
    {
    "backplane", "abort"}
};

vector<string> commandRes = {
    
    "reset what",
    "board fault",
    "where to add",
    "no board at all",
    "impossible",
    "install first"
};

int main(){
    
    string str = "";
    while(getline(cin, str)){
    
        stringstream iss(str);
        string key1 = "", key2 = "";
        getline(iss, key1, ' '); // First keyword 
        getline(iss, key2, ' '); // Second keyword 
        
        string res = "";
        int piPeiCount = 0; // Record the number of matching keywords  ( be equal to 1 Time is the only match to   That is, the match is successful )
        for(auto iter = youXiaoCommand.begin(); iter != youXiaoCommand.end(); iter++){
    
            int key1Pos = iter->first.find(key1); //key1 The subscript that first appears in the first half of the command  ( by 0 The match is successful )
            int key2Pos; //key2 The subscript that first appears in the first half of the command  ( by 0 The match is successful )
            
            if(key2 != ""){
     // Yes key2
                key2Pos = iter->second.find(key2); //key2 The subscript that first appears in the first half of the command 
            }
            else if(key2 == "" && iter->second.empty()){
     // Special cases match the command  {"reset", ""},
                key2Pos = 0;
            }
            else{
     // It didn't match 
                key2Pos = -1;
            }
            
            if(key1Pos == 0 && key2Pos == 0){
     // The match is successful 
                piPeiCount++; // The number of successful matches 
                res = commandRes[iter - youXiaoCommand.begin()]; // Index position ：iter - youXiaoCommand.begin()
            }
        }
        
        if(piPeiCount == 1){
     // The match is successful and unique 
            cout << res << endl;
        }
        else{
    // Otherwise, there is no match , Output "unknown command"
            cout<<"unknown command"<<endl;   
        }
    }
    
    return 0;
}

67.24 Point game algorithm

#include <bits/stdc++.h>

using namespace std;

double num = 1e-6;
int ANS = 24;
int ADD = 0, SUB = 1, MUL = 2, DIV = 3;

bool process(vector<double>& l){
    
    if(l.size() == 0) return false;
    if(l.size() == 1) return abs(24 - l[0]) < num; // There is only one number left 
    
    int size = l.size(); //
    for(int i = 0; i < size; i++){
    
        for(int j = 0; j < size; j++){
    
            if(i != j){
     // Two indexes cannot be equal 
                vector<double> l2;
                for(int k = 0; k < size; k++){
    
                    if(k != i && k != j){
    
                        l2.push_back(l[k]);// First put in the numbers that will not be processed in this round 
                    }
                }   
                
                //" Two - "
                for(int m = 0; m < 4; m++){
     // Four treatments ： Add, subtract, multiply and divide 
                    if(m == ADD){
    
                        l2.push_back(l[i] + l[j]);
                    }
                    else if(m == SUB){
    
                        l2.push_back(l[i] - l[j]);
                    }
                    else if(m == MUL){
    
                        l2.push_back(l[i] * l[j]);
                    }
                    else{
    
                        if(abs(l[j]) < num) continue; // When dividing, the denominator cannot be 0
                        l2.push_back(l[i] / l[j]);
                    }
                    
                    if(process(l2)){
    
                        return true; //
                    }
                    
                    l2.pop_back(); //
                }                                
            }
        }
    }
    return false;
}

int main(){
    
    int a = 0, b = 0, c = 0, d = 0;
    while(cin >> a >> b >> c >> d){
    
        // Two -  + dfs
        vector<double> l1;
        l1.push_back((double)a);
        l1.push_back((double)b);
        l1.push_back((double)c);
        l1.push_back((double)d);
        
        bool res = process(l1);
        
        if(res)
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    
    return 0;
}

68. Grade ranking

#include <bits/stdc++.h>

using namespace std;

struct cmpJiangXu{
    
  bool operator()(const pair<string, int>& a, const pair<string, int>& b){
    
      return a.second > b.second;
  }  
};

struct cmpShengXu{
    
  bool operator()(const pair<string, int>& a, const pair<string, int>& b){
    
      return a.second < b.second;
  }  
};

int main(){
    
    int n = 0;
    // Law 1 
    /*while(cin >> n){ int sortWay = 0; // sort order  cin >> sortWay; // Enter your name and grade  vector<pair<string, int>> info; for(int i = 0; i < n; i++){ string name = ""; int score = 0; cin >> name >> score; info.push_back(make_pair(name, score)); } // Sort  //stable The function ensures that the original relative order of equal elements remains unchanged after sorting  if(sortWay == 0){ // From high to low   Descending  stable_sort(info.begin(), info.end(), cmpJiangXu()); } else if(sortWay == 1){ // From low to high   Ascending  stable_sort(info.begin(), info.end(), cmpShengXu()); } // Output  for(auto iter = info.begin(); iter != info.end(); iter++){ cout << iter->first << " " << iter->second << endl; } }*/
    
    // Law two 
    while(cin >> n){
    
        int sortWay = 0; // sort order 
        cin >> sortWay;
        // Enter your name and grade 
        map<int, vector<string>> info;
        for(int i = 0; i < n; i++){
     // Establish the mapping between grades and names 
            string name = "";
            int score = 0;
            cin >> name >> score;
            info[score].push_back(name);
        }
        
        // Sort 
        if(sortWay == 0){
    
            // From high to low   Descending 
            // Traversal in reverse order  // rbegin rend
            // Output 
            for(auto iter = info.rbegin(); iter != info.rend(); iter++){
     //iter++
                for(int i = 0; i < iter->second.size(); i++){
     // The same results , Output in input order 
                    cout << iter->second[i] << " " << iter->first << endl;
                }                
            }
        }
        
        else if(sortWay == 1){
    
            // From low to high   Ascending 
            // Sequential traversal 
            for(auto iter = info.begin(); iter != info.end(); iter++){
     //iter++
                for(int i = 0; i < iter->second.size(); i++){
    
                    cout << iter->second[i] << " " << iter->first << endl;
                }  
            }
        } 
        
    }
    
    return 0;
}

69. Matrix multiplication

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    // Input 
    int firstRows = 0;
    int firstCols = 0;
    int secondRows = 0;
    int secondCols = 0;
    cin >> firstRows;
    cin >> firstCols;
    secondRows = firstCols;
    cin >> secondCols;
    
    int num = 0;// Matrix elements 
    // Enter the first matrix 
    vector<vector<int>> firstMatrix(firstRows, vector<int>(firstCols, 0));    
    for(int i = 0; i < firstRows; i++){
    
        for(int j = 0; j < firstCols; j++){
    
            cin >> num;
            firstMatrix[i][j] = num;
        }
    }
    // Enter the second matrix 
    vector<vector<int>> secondMatrix(secondRows, vector<int>(secondCols, 0));
    for(int i = 0; i < secondRows; i++){
    
        for(int j = 0; j < secondCols; j++){
    
            cin >> num;
            secondMatrix[i][j] = num;
        }
    }
    
    // Calculate the multiplication result matrix 
    vector<vector<int>> mulRes(firstRows, vector<int>(secondCols, 0));
    for(int i = 0; i < firstRows; i++){
    
        for(int j = 0; j < secondCols; j++){
    
            
            for(int k = 0; k < firstCols; k++){
    
                mulRes[i][j] += firstMatrix[i][k] * secondMatrix[k][j]; // Multiply and add 
            }
           
        }
    }
    
    // Output 
    for(int i = 0; i < firstRows; i++){
    
        for(int j = 0; j < secondCols; j++){
    
            cout << mulRes[i][j] << " ";
        }
        cout << endl; // Line break , Output the elements of the next row of the matrix 
    }
    
    return 0;
}

70. Matrix multiplication calculation amount estimation

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    int n = 0;
    while(cin >> n){
    
        vector<pair<int, int>> matrixs(n); // Number of rows and columns 
        for(int i = 0; i < n; i++){
    
            cin >> matrixs[i].first;
            cin >> matrixs[i].second;
        }
        string s = "";
        cin >> s;
        
        // Matrix multiplication   The first row and the first column are multiplied and added 
        //A It's a 50×10 Matrix ,B yes 10×20 Matrix   Then the number is ：50×10×20
        int res = 0;
        stack<pair<int, int>> st; // The stack stores the number of rows and columns of the matrix 
        for(int i = 0; i < s.size(); i++){
     // Traversal string 
            if(s[i] == ')'){
     // If it's right bracket , Then two elements pop up on the stack , And accumulate the times of multiplication 
                auto y = st.top(); // The following matrix 
                st.pop();
                auto x = st.top(); // The previous matrix 
                st.pop();
                
                if(x.second == y.first){
    
                    res += x.first * x.second * y.second;
                    st.push({
    x.first, y.second}); // // Put the number of rows and columns of the new matrix on the stack 
                }
                //
                /*else if(y.second == x.first){ res += y.first * y.second * x.second; st.push({y.first, x.second}); // Put the number of rows and columns of the new matrix on the stack  }*/
            }
            else if(s[i] != '('){
      If it's a character , Then push directly 
            //else if(isalpha(s[i])){ 
                // A Is the first matrix   Its row number and column number correspond matrix[0]
                int t = s[i] - 'A';
                st.push(make_pair(matrixs[t].first, matrixs[t].second));
            }
        }
        
        // Output 
        cout << res << endl;
    }
    
    return 0;
}