华为OD题库

1.最大化资源控制成本

查看代码测试

公司创新实验室正在研究如何最小化资源成本，最大化资源利用率，请你设计算法帮他们解决个任务混部问题: 有taskNum项任务，每个任务有开始时间 (startTime) ，结束时间(endTime)并行度(parallelism) 三个属性，并行度是指这个任务运行时将会占用的服务器数量，一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用，任务运行完成立即释放(结束时刻不占用)。任务混部问题是指给定一批任务，让这批任务由同一批服务器承载运行请你计算完成这批任务混部最少需要多少服务器，从而最大最大化控制资源成本。
输入描述:
第一行输入为taskNum，表示有taskNum项任务接下来taskNum行，每行三个整数，表示每个任务的开始时间(startTime ) ，结束时间 (endTime ) ，并行度 (parallelism)
输出描述:
个整数，表示最少需要的服务器数量
示例1 输入输出示例仅供调试，后台判断数据一般不包含示例输入
3
2 3 1
6 9 2
0 5 1
输出
2

说明共有三个任务，第一个任务在时间区间[2，3]运行，占用1个服务器，第二个任务在时间区间[6，9] 运行，占用2个服务器，第三个任务在时间区间[0，5]运行，占用1个服务器，需要最多服务器的时间区间为[2，3]和[6，9] ，需要2个服务器

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

//仿函数
struct cmp{
    bool operator()(vector<int> a, vector<int> b )
    {
        return a[0]>b[0];//小顶堆,结束时间最早的在堆顶
    }
};

int main()
{
    int n;
    cin>>n;
    vector<vector<int>> task(n,vector<int>(3,0));
    for(int i=0; i<n; i++)
    {
        cin>>task[i][0]>>task[i][1]>>task[i][2];
    }
    //priority_queue存放未完成的task
    //每次只需要比较堆顶的结束时间和当前任务的开始时间就可以得知当前任务是否可以加入
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;

    //任务按照开始时间升序
    sort(task.begin(),task.end(),[](auto a, auto b){
        return a[0]<b[0];
    });
    int max_res=0;
    int cur_res=0;//优先队列里面的任务对应并发度
    for(int i=0; i<task.size(); i++)
    {
        //将结束时间小于当前任务开始时间的任务清空
        while(pq.size()>0){
            if(pq.top()[0]<task[i][0]){
                cur_res-=pq.top()[1];
                pq.pop();
            }else{
                break;
            }
        }
        pq.push(vector<int>{task[i][1],task[i][2]});
        cur_res+=task[i][2];
        if(cur_res>max_res) max_res=cur_res;
    }
    cout<<max_res<<endl;
    return 0;
}

2.完美走位

查看代码测试

输入一个长度为4的倍数的字符串，字符串中仅包含WASD四个字母将这个字符串中的连续子串用同等长度的仅包含WASD的 字符串替换Q，如果替换后整个字符串中WASD四个字母出现的频数相同，那么我们称替换后的字符串是“完美走位”。求子串的最小长度。如果输入字符串已经平衡则输出0.
二、输入
一行字符表示给定的字符串s
数据范围:
1<=n<=10^5且n是4的倍数，字符串中仅包含WASD四个字母
三、输出
一个整数表示答案
四、样例输入输出
输入:
WASDAASD
输出:

1
说明:
将第二个A替换为W，即可得到完美走位

#include<iostream>
#include<map>
#include<unordered_map>
using namespace std;
/*
滑动区间内为可自由变更的区间，若滑动区间的长度可以>=最大值与各个字母的差
且二者的差值为4的整数倍，滑动区间满足
*/
int main()
{
    string str;
    cin>>str;
    map<char,int> char_count;
    //初始化不能省略
    char_count['W']=0;
    char_count['A']=0;
    char_count['S']=0;
    char_count['D']=0;

    for(auto x: str)
    {
        char_count[x]++;
    }
    if(char_count['W']==char_count['A']&&
    char_count['W']==char_count['S']&&
    char_count['W']==char_count['D']){
        cout<<0<<endl;
        return 0;
    }
    int left=0;
    int right=0;
    int length=0;
    int ans=str.size();
    //出现最多的字母
    int max_char_num=0;
    // 空闲的字母数
    int surplus_char_num=0;
    //初始时，滑动窗口的长度为1,滑动窗口外的相应字母--
    char_count[str[0]]--;
    while(right<str.size())
    {
        //每次都要重新赋值，不然会保留最开始的最大值
        max_char_num=0;
        for(auto x: char_count){
            max_char_num=max(max_char_num,x.second);
        }
        //cout<<"最大的字母数:"<<max_char_num<<endl;
        //滑动窗口的长度也是可自由分配字母的个数
        length=right-left+1;
        //需要改变的字母数
        int required=0;
        for(auto x: char_count)
        {
            required+=(max_char_num-x.second);
        }
        //cout<<"需要改变的字母数"<<required<<endl;
        //cout<<"区间长度"<<length<<","<<"区间范围"<<left<<","<<right<<endl;

        surplus_char_num=length-required;
        //区间满足，左指针左移
        if(surplus_char_num>=0&&surplus_char_num%4==0)
        {
            if(length<ans) ans=length;
            char_count[str[left]]++;
            left++;
        }else{
            //区间不满足，右指针右移
            //右指针需要先右移
            right++;
            char_count[str[right]]--;
        }        
    }
    cout<<ans<<endl;
    return 0;
}

3.羊、狼、农夫过河

查看代码测试

羊、狼、农夫都在岸边，当羊的数量小于狼的数量时，狼会攻击羊，农夫则会损失羊。农夫有一艘容量固定的船，能够承载固定数量的动物。要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。
备注: 农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊农夫自身不占用船的容量。
输入描述
第一行输入为M，N，x，分别代表羊的数量，狼的数量，小船的容量.
输出描述
输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。(若无法满足条件则输出0)

#include<iostream>
#include<limits.h>
using namespace std;
int minTimes=INT_MAX;
void transport(int m0, int n0, int x, int m1, int n1, int times)
{
    if(x>=m0+n0){
        if(times+1<minTimes) minTimes=times+1;
    }
    //外层保证羊的数量小于容量
    for(int i=0; i<=m0 && i<=x; i++)
    {
        //保证羊+狼不超重
        for(int j=0; j<=n0 && i+j<=x; j++)
        {
            if(i+j==0) continue;
            //保证两岸的羊数量>=狼(要么羊数量为0)
            if((m0-i==0||m0-i>n0-j)&&(m1+i==0||m1+i>n1+j)){
                transport(m0-i,n0-j,x,m1+i,n1+j,times+1);
            }
        }
    }
}
int main()
{
    int M,N,X;
    cin>>M>>N>>X;
    transport(M,N,X,0,0,0);
    if(minTimes==INT_MAX){
        cout<<0<<endl;
        return 0;
    }
    cout<<minTimes<<endl;

    return 0;
}

4.字符串重新排列

查看代码测试

给定一个字符串s，s包括以空格分隔的若干个单词，请对s进行如下处理后输出

1、单词内部调整: 对每个单词字母重新按字典序排序
2、单词间顺序调整:
1)统计每个单词出现的次数，并按次数 降序排列Q
2)次数相同，按单词长度Q 升序排列
3)次数和单词长度均相同，按字典升序排列
请输出处理后的字符串，每个单词以一个空格分隔
输入描述:
一行字符串，每个字符取值范围:[a-ZA-z0-9] 以及空格，字符串长度范围:[1，1000]
例1:
输入
This is an apple
输出
an is This aelpp
例2:
输入:
My sister is in the house not in the yard
输出:
in in eht eht My is not adry ehosu eirsst

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
bool cmp(pair<string,int> a, pair<string,int> b)
{
    if(a.second!=b.second) return a.second>b.second;
    else{
        if(a.first.size()!=b.first.size()) return a.first.size()<b.first.size();
        else return a.first<b.first;
    }

}
int main()
{
    string input_str;
    getline(cin,input_str);
    //空格分割
    vector<string> v;
    while(input_str.find(" ")!=-1){
        int pos = input_str.find(" ");
        v.push_back(input_str.substr(0,pos));
        input_str=input_str.substr(pos+1);
    }
    v.push_back(input_str);
    //第一步，单词内部调整
    for(int i=0; i<v.size(); i++){
        sort(v[i].begin(),v[i].end());
    }
    //第二步，单词间调整
    map<string,int> str_count;
    for(int i=0; i<v.size(); i++){
        if(str_count.count(v[i])){
            str_count[v[i]]+=1;
        }else{
            str_count[v[i]]=1;
        }
    }
    //排序
    vector<pair<string,int>> str_count_vec(str_count.begin(),str_count.end());
    sort(str_count_vec.begin(),str_count_vec.end(),cmp);
    for(auto item : str_count_vec){
        for(int i=0; i<item.second; i++) cout<<item.first<<" ";
    }

    return 0;
}

5.租车骑绿岛

查看代码测试

部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，做最大载重M。给出部门每个人的体重，请问最多需要租用多少双人自行车

输入描述:
第一行两个数字m、n，分别代表自行车限重，部门总人数。第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。0<me=200
0<n<=1000000
输出描述:
最小需要的双人自行车数量。
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例输入
34
3 2 2 1
输出

3

思路：这个问题可以通过贪心算法来解决。首先，将所有人的体重从小到大排序。然后，从最轻的人开始，每次选择最轻的人和最重的人搭配在一起。如果两个人的体重之和不超过自行车的限重，则他们可以共用一辆自行车；否则，最重的人需要单独使用一辆自行车。重复这个过程，直到所有人都被安排好。

#include <iostream>
#include <algorithm>
using namespace std;
int min_bikes(int m, int n, int weights[]) {
    sort(weights, weights + n);
    int left = 0;
    int right = n - 1;
    int bikes = 0;
    while (left <= right) {
        if (weights[left] + weights[right] <= m) {
            left++;
            right--;
            bikes++;
        }else{
            right--;
            bikes++;
        }

    }
    return bikes;
}
int main() {
    int m, n;
    cin >> m >> n;
    int weights[n];
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    cout << min_bikes(m, n, weights) << endl;
    return 0;
}

6.无向图染色

查看代码测试

给一个无向图Q 染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案?
输入描述:
第一行输入M(图中节点数) N(边数)
后续N行格式为: V1 V2表示一个V1到V2的边
数据范围: 1 <= M <= 15.0 <= N <= M3，不能保证所有节点都是连通的

输出描述:
输出一个数字表示染色方案的个数
示例1:
输入:
4 4
1 2
2 4
3 4
1 3
输出:

7
说明: 4个节点，4条边，1号节点和2号节点相连，2号节点和4号节点相连，3号节点和4号节点相连，1号节点和3号节点相连，若想必须保证相邻两个节点不能同时为红色，总共7种方案。

思路：遍历所有的染色方案，再逐一判断每条边的两边是否都是红色

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int m, n;
    cin>>m>>n;
    vector<pair<int,int>> edges;
    for(int i=0; i<n; i++)
    {
        int a,b;
        cin>>a>>b;
        //存入结点时，以0号结点开头
        edges.push_back({a-1,b-1});
    }
    int count=0;
    /*
    0101表示0号结点为黑，1号结点为红，2号结点为黑，3号结点为红
    从右边往左边分别是0,1,2,3
    为了取得相应结点的颜色，需要右移0,1,2,3位
    */
    for(int i=0; i<(1<<m); i++)
    {
        bool flag=1;
        //检测所有边的两端
        for(auto edge: edges){
            int node1=i>>edge.first;
            int node2=i>>edge.second;
            if((node1&1) && (node2&1))
            {
                flag=false;
                break;
            }
        }
        if(flag) count++;
    }
    cout<<count<<endl;
    return 0;

}

7.单向链表中间节点

查看代码测试

求单向链表Q 中间的节点值，如果奇数个节点取中间，偶数个取偏右边的那个值。

输入描述:
第一行 链表头节点地址path 后续输入的节点数n后续输入每行表示一个节点，格式:”节点地址 节点值 下一个节点地址(-1表示空指针“输入保证链表不会出现环，并且可能存在一些节点不属于链表输出描述:
链表中间节点值。
测试用例:
输入:
00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451
输出:
6

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

int main()
{
    map<string,int> node_value;
    map<string,string> node_node;
    string head;
    int n;
    cin>>head>>n;
    for(int i=0; i<n; i++)
    {
        string start,end;
        int val;
        cin>>start>>val>>end;
        node_value[start]=val;
        node_node[start]=end;
    }
    //遍历一遍求长度
    string tmp=head;
    int cnt=1;
    while(node_node[tmp]!="-1")
    {
        tmp=node_node[tmp];
        cnt++;
    }
    tmp=head;
    for(int i=0; i<cnt/2; i++)
    {
        tmp=node_node[tmp];
    }
    cout<<node_value[tmp]<<endl;
    return 0;
}

8.划分为k个相等的子集

查看代码测试

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

思路一：动态规划

class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0) return false;
    int target = sum / k;
    //dp压缩状态，dp[i]表示状态i下是否可以划分为x个target
    vector<int> dp(1 << nums.size(), -1);
    dp[0]=0;
    //枚举每一种状态，并由当前状态推导出后面的状态
    for(int i=0; i<(1<<nums.size()); i++)
    {
        if(dp[i]==-1) continue;
        for(int j=0; j<nums.size(); j++)
        {
            //第j位是否为1,即是否已经使用
            int flag=i&(1<<j);
            if(!flag&&dp[i]+nums[j]<=target){
                dp[i|(1<<j)]=(dp[i]+nums[j])%target;
            }
        }
    }
    return dp[(1<<nums.size())-1]==0;
}
};

思路二：回溯法

class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
    int sum=accumulate(nums.begin(),nums.end(),0);
    if(sum%k!=0) return false;
    int target=sum/k;
    sort(nums.begin(),nums.end(),[](int a, int b){
        return a>b;
    });
    vector<int> bucket(k,0);
    return backtrack(nums,0,bucket,k,target);
}
bool backtrack(vector<int>& nums,int index, vector<int>& bucket, int k, int target)
{
    if(index==nums.size()) return true;
    //每个球有k个选择
    for(int i=0; i<k; i++)
    {
        if(i>0&&bucket[i]==bucket[i-1]) continue;
        if(bucket[i]+nums[index]>target) continue;
        bucket[i]+=nums[index];
        if(backtrack(nums,index+1,bucket,k,target)) return true;
        bucket[i]-=nums[index];
    }
    return false;
}
};

9.最多颜色的车

查看代码测试

在一个狭小的路口，每秒只能通过一辆车，假好车辆的颜色只有 3 种，找出N 秒内经过的最多颜色的车辆数量。
三种颜色编号为0，1，2
输入描述
第一行输入的是通过的车辆颜色信息
[0,1,1,2]代表4 秒钟通过的车辆颜色分别是 0，1，1，2

第二行输入的是统计时间窗，整型，单位为秒输出描述
输出指定时间窗内经过的最多颜色的车辆数量
样例
样例一:
输入
0 1 2 1
3
输出
2
样例解释
在 3 秒时间窗内，每个颜色最多出现 2 次。例为: [1,2,1]
样例二:
输入
0 1 2 1
2
输出

1
样例解释
在 2 秒时间窗内，每个颜色最多出现1 次

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

int main()
{
    //处理输入
    string input_str;
    getline(cin,input_str);
    int window;
    cin>>window;
    vector<int> cars;
    while(input_str.find(" ")!=-1)
    {
        int found=input_str.find(" ");
        cars.push_back(stoi(input_str.substr(0,found)));
        input_str=input_str.substr(found+1);
    }
    cars.push_back(stoi(input_str));
    //初始化滑动窗口
    vector<int> car_count=vector<int>(3,0);
    for(int i=0;i<window; i++)
    {
        car_count[cars[i]]+=1;
    }
    //滑动窗口滑动
    int max_res=*max_element(car_count.begin(),car_count.end());
    for(int i=window; i<cars.size(); i++)
    {
        car_count[cars[i]]++;
        car_count[cars[i-window]]--;
        max_res=max(max_res,*max_element(car_count.begin(),car_count.end()));
    }
    cout<<max_res<<endl;
}

10.不含101的数

查看代码测试

小明在学习二进制时，发现了一类不含 101的数，也就是：将数字用二进制表示，不能出现 101 。现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个不含 101 的数？

输入描述

输入的唯一一行包含两个正整数 l， r（ 1 ≤ l ≤ r ≤ 10^9）。

输出描述

输出的唯一一行包含一个整数，表示在 [l,r] 区间内一共有几个不含 101 的数。

样例一：

输入

1 10

输出

8

样例解释：区间 [1,10] 内， 5 的二进制表示为 101 ，10的二进制表示为 1010 ，因此区间 [ 1 , 10 ] 内有 10−2=8个不含 101的数。

思路一：暴力法

#include<iostream>
#include<bitset>
using namespace std;
bool isValid(int num)
{
    bitset<64> bit(num);
    string bin=bit.to_string();
    cout<<bin<<endl;
    if(bin.find("101")==-1) return true;
    return false;
}
int main()
{
    int m,n;
    cin>>m>>n;
    int cnt=0;
    for(int i=m; i<=n; i++)
    {
        if(isValid(i)){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

思路二：数位dp

#include<bits/stdc++.h>
using namespace std;

int search(int p, bool flag, vector<vector<vector<int>>> binary_dp, vector<int> single_binary_nums, int pre, int prepre) {
    if (p == single_binary_nums.size()) {
        return 1;
    }

    if (!flag && binary_dp[p][pre][prepre] != 0) {
        return binary_dp[p][pre][prepre];
    } 

    int index = flag ? single_binary_nums[p] : 1;
    int count = 0;

    for (int i = 0; i < index+1; i++) {
        if (i == 1 && pre == 0 && prepre == 1) {
            continue;
        }
        count += search(p + 1, flag && i == index, binary_dp, single_binary_nums, i, pre);
    }

    if (!flag) {
        binary_dp[p][pre][prepre] = count;
    }

    return count;
}

 int dp(int num) {
    // 10 -> [1,0,1,0,0]
    bitset<20> number;
    number = num;
    string number_str=number.to_string(); 
    vector<int> single_binary_nums(number_str.size(), 0);
    for (int i=0;i<number_str.size();i++) {
        single_binary_nums[i] = (int)number_str[i]-48;
    }


    vector<vector<vector<int>>> binary_dp(single_binary_nums.size(), vector<vector<int>>(2, vector<int>(2, 0)));
    return search(0, true, binary_dp, single_binary_nums, 0, 0);
}

int main() {
    //处理输入
    int left, right;
    cin >> left >> right;


    cout << dp(right)-dp(left-1);

    return 0;
}

11.过滤组合字符串

查看代码测试

数字0、1、2、3、4、5、6、7、8、9分别关联 a~z 26个英文字母
0关联”a””b””c”
1关联”d”,”e”,”?
2关联”g”,”h”””
3 关联”,”k”,””
4 关联”m””n””o”
5关联”p”,”q”””
6关联”s”,”t”
7 关联”u””v”
8关联”w””x”
9关联”y”,”z”
例如7关联”u””v”，8关联”x””w”，输入一个字符串例如“78”和一个屏蔽字符串“ux”,那么“78”可以组成多个字符串例如:“ux”，“uw”“vx”，“ww”，过滤这些完全包含屏蔽字符串的每一个字符的字符串，然后输出剩下的字符串。
示例:
输入:
78
ux
输出:
uw vx vw
说明: ux完全包含屏蔽字符串ux，因此别除

#include<bits/stdc++.h>
using namespace std;
const string letterMap[10]={
    "abc", //0
    "def",//1
    "ghi",//2
    "jkl",//3
    "mno",//4
    "pqr",//5
    "st",//6
    "uv",//7
    "wx",//8
    "yz",//9
};
vector<string> result;
void dfs(int index, string& digits, string s)
{
    if(index==digits.size()){
        result.push_back(s);
        return ;
    }
    int digit = digits[index]-'0';
    string letters = letterMap[digit];//取数字对应字母集
    for(int i=0; i<letters.size(); i++)
    {
        dfs(index+1,digits,s+letters[i]);
    }        
}
//判断字符是否全部包含
bool check(string str1, string str2)
{
    set<char> set1;
    for(auto x:str1)
    {
        set1.insert(x);
    }
    set<char> set2;
    for(auto x:str2)
    {
        set2.insert(x);
    }
    for(auto x: set2)
    {
        if(set1.count(x)==0) return false;
    }
    return true;
}
int main()
{
    string digits;
    string filter;
    cin>>digits>>filter;
    dfs(0,digits,"");
    string result_str;
    for(auto x: result)
    {
        if(!check(filter,x)){
            result_str+=(x+" ");

        }
    }
    cout<<result_str<<endl;

    return 0;

}

12.真正的密码

查看代码测试

在一行中输入一个字符串数组Q，如果其中一个字符串的所有以索引0开头的子串在数组中都有，那么这个字符串就是潜在密码，在所有潜在密码中最长的是真正的密码，如果有多个长度相同的真正的密码，那么取字典序最大的为唯一的真正的密码，求唯一的真正的密码

示例1:
输入: h he hel hell hello o ok n ni nin ninj ninjaQ
输出: ninja说明:按要求，hello、ok、ninja都是潜在密码。检查长度，hello、ninja是真正的密码。检查字典序Q，ninja是唯一真正密码。
示例2:
输入:
a b c d f
输出:
说明: 按要求，a b c d f都是潜在密码。检查长度，a b c d f 是真正的密码。检查字典序，f是唯一真正密码

#include<bits/stdc++.h>
using namespace std;

int main() {
    string input_str;
    // 带空格的字符串输入
    getline(cin,input_str);

    //空格分割
    vector<string> v;
    while (input_str.find(" ") != string::npos) {
        int found = input_str.find(" ");
        v.push_back(input_str.substr(0, found));
        input_str = input_str.substr(found + 1);
    }    
    v.push_back(input_str);

    // 将所有字符串放入哈希集合
    set<string> word_set;
    for (auto s : v) {
        word_set.insert(s);
    }

    // 真正的密码
    string true_pass_word="";

    //按顺序检查每一个词
    for (auto s : v) {
        // 条件1：检查这个词所有以索引0开头的子串在数组中是否都有
        bool flag=true;
        for(int i=1;i<s.length();i++){
            // 以索引0开头的子串
            string sub_str=s.substr(0,i);
            if(!word_set.count(sub_str)){
                flag=false;
                break;
            }
        }

        if(flag){
            // 条件2：比较密码长度
            if(s.size()>true_pass_word.size())
                true_pass_word=s;
            // 条件3：比较密码字典排序
            if(s.size()==true_pass_word.size()&& s>true_pass_word){
                true_pass_word=s;
            }
        }
    }

    cout << true_pass_word;

    return 0;
}

13.最小调整顺序次数

查看代码测试

#include<bits/stdc++.h>
using namespace std;

vector<string> split(string input_str) {
    //空格分割
    vector<string> v;
    while (input_str.find(" ") != string::npos) {
        int found = input_str.find(" ");
        v.push_back(input_str.substr(0, found));
        input_str = input_str.substr(found + 1);
    }    
    v.push_back(input_str);
    return v;
}

int main() {
    string input_number;
    getline(cin,input_number);
    int number = stoi(input_number);

    vector<vector<string>> operations;
    for (int i =0;i<2*number;i++) {
        string input_str;
        // 带空格的字符串输入
        getline(cin,input_str);
        operations.push_back(split(input_str));
    }

    int queue_size = 0;
    //是否有序
    bool in_order = true;
    int result = 0;

    for (int i = 0; i < operations.size(); i++) {
        vector<string> operaion_str = operations[i];
        if (operaion_str[0]=="head") {
            if (queue_size > 0 && in_order) {
                in_order = false;
            }
            queue_size++;
        } else if (operaion_str[0]=="tail") {
            queue_size++;
        } else {
            if (queue_size == 0) {
                continue;
            }
            if (!in_order) {
                result++;
                in_order = true;
            }
            queue_size--;
        }
    }

    cout<<result;
    return 0;
}

14.星球移居计划-n

15.需要打开多少监视器-n

16.最佳种树距离-n

17.阿里巴巴寻宝盒-n

18.选修课-n

19.探索地块建立

查看代码测试

给一块nm的地块，相当于nm的二维数组，每个元素的值表示这个小地块的发电量;求在这块地上建立正方形的边长为c的发电站，发电量满足目标电量k的地块数量。输入描述:
第一行为四个按空格分隔的正整数，分别表示n,m,c k后面n行整数，表示每个地块的发电量输出描述:
输出满足条件的地块数量
示例:
输入:
2 5 2 6 // n m ck，下面每行是nm地块每格的发电量
1 3 4 5 8
2 3 6 7 1
输出:
4
说明:
满足条件的地块有以下几种
第一种:
1 3
2 3
第二种:
3 4
3 6
第三种:
4 5
6 7
第四种:
5 8
7 1

#include<bits/stdc++.h>
using namespace std;

vector<int> split(string input_str) {
    //空格分割
    vector<int> v;
    while (input_str.find(" ") != string::npos) {
        int found = input_str.find(" ");
        v.push_back(stoi(input_str.substr(0, found)));
        input_str = input_str.substr(found + 1);
    }    
    v.push_back(stoi(input_str));
    return v;
}
int getRect(vector<vector<int>> &P,int x1, int y1, int x2, int y2)
{
    return P[x2][y2]-P[x1-1][y2]-P[x2][y1-1]+P[x1-1][y1-1];
}
int get_area_count(vector<vector<int>>& mat, int threshold, int c) {
    int n = mat.size();
    int m = mat[0].size();
     vector<vector<int>> s(n + 1, vector<int>(m + 1));
    //1、生成前缀和子矩阵
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j) {
            //s[i][j]表示以[i,j]作为矩阵最右下角的最大矩阵的前缀和
            //解释：以点[i,j]作为作为最右下角的最大矩阵的前缀和需要加上点[i-1,j]和点[i,j-1]的前缀和，然而会重复多加一个点[i-1][j-1]的前缀和，所以要减一个
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
        }
    }
    int ans = 0;
    //2、遍历前缀和矩阵，获得边长等于c的矩阵
    for (int i = 1; i <= n-c+1; ++i) {
        for (int j = 1; j <= m-c+1; ++j) {
            if(getRect(s,i,j,i+c-1,j+c-1)>=threshold) ans++;
        }
    }
    return ans;
}


int main() {
    string input_params;
    getline(cin,input_params);
    vector<int> params = split(input_params);
    int n = params[0];
    int m = params[1];
    int c = params[2];
    int k = params[3];

    vector<vector<int>> matrix;
    for (int i =0;i<n;i++) {
        string input_str;
        // 带空格的字符串输入
        getline(cin,input_str);
        matrix.push_back(split(input_str));
    }


    cout << get_area_count(matrix, k, c);

    return 0;
}

20.模拟商场优惠打折

查看代码测试

模拟商场优惠打折，有三种 优惠券Q 可以用，满减券、打折券和无门槛券满减券: 满100减10，满200减20，满300减30，满400减40，以此类推不限制使用;打折券: 固定折扣92折，且打折之后向下取整Q，每次购物只能用1次:无门槛券: 一张券减5元，没有使用限制;
每个人结账使用优惠券时有以下限制: 每人每次只能用两种优惠券，并且同一种优惠券必须一次用完，不能跟别的穿插使用(比如用一张满减，再用一张打折，再用一张满减，这种顺序
不行)求不同使用顺序下每个人用完券之后得到的最低价格和对应使用优惠券的总数:如果两种顺序得到的价格一样低，就取使用优惠券数量较少的那个。输入描述:
第一行三个数字m,n,k，分别表示每个人可以使用的满减券、打折券和无门槛券的数量第二行一个数字x,表示有几个人购物
后面x行数字，依次表示是这几个人打折之前的商品总价输出描述:
输出每个人使用券之后的最低价格和对应使用优惠券的数量示例:
输入:
3 2 5
3
100
200
400
输出:
65 6
135 8
275 8

说明

第一个人使用 1 张满减券和5张无门槛券价格最低

第二个人使用 3 张满减券和5张无门槛券价格最低

第三个人使用 3 张满减券和5张无门槛券价格最低

#include<bits/stdc++.h>
using namespace std;

vector<int> split(string input_str) {
    //空格分割
    vector<int> v;
    while (input_str.find(" ") != string::npos) {
        int found = input_str.find(" ");
        v.push_back(stoi(input_str.substr(0, found)));
        input_str = input_str.substr(found + 1);
    }    
    v.push_back(stoi(input_str));
    return v;
}

//先满减后打折
pair<int, int> mode_a(int price, int m, int n) {
    int count = 0;
    while(m > 0) {
        if (price < 100) {
            break;
        }
        price -= (price/100 * 10);
        count += 1;
        m--;
    }
    if(n>0){
        price *= 0.92;
        count += 1;
    }
    return make_pair(price, count);
}

//先打折后满减
pair<int, int> mode_b(int price, int m, int n) {
    int count = 0;

    if(n>0){
        price *= 0.92;
        count += 1;
    }

    while(m > 0) {
        if (price <100) {
            break;
        }
        price -= (price/100 * 10);
        count += 1;
        m--;
    }

    return make_pair(price, count);

}

//先满减后无门槛
pair<int, int> mode_c(int price, int m, int k) {
    int count = 0;

    while(m > 0) {
        if (price <100) {
            break;
        }
        price -= (price/100 * 10);
        count += 1; 
        m--;
    }

    for (int i=0;i<k;i++) {
        price -= 5;
        count += 1;
        //无门槛用了为负数是直接置0
        if (price <= 0) {
            price=0;
            break;
        }
    }
    return make_pair(price, count);
}

//先打折后无门槛
pair<int, int> mode_d(int price, int n, int k) {
    int count = 0;

    if(n>0){
        price *= 0.92;
        count += 1;
    }

    for (int i=0;i<k;i++) {
        price -= 5;
        count += 1;
        //无门槛用了为负数是直接置0
        if (price <= 0) {
            price=0;
            break;
        }
    }
    return make_pair(price, count);
}

bool comp(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first){
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

int main() {
    // 处理输入
    string input_params;
    getline(cin,input_params);

    vector<int> params = split(input_params);
    int m = params[0];
    int n = params[1];
    int k = params[2];


    string input_params_x;
    getline(cin,input_params_x);
    int x = stoi(input_params_x);


    for (int i=0;i<x;i++) {
        string input_str;
        getline(cin,input_str);

        int price = stoi(input_str);

        vector<pair<int, int>> result;
        result.push_back(mode_a(price, m, n));
        result.push_back(mode_b(price, m, n));
        result.push_back(mode_c(price, m, k));
        result.push_back(mode_d(price, n, k));

        //按照价格降序，用券数降序排序
        sort(result.begin(), result.end(), comp);
        cout << result[0].first<<" "<< result[0].second<<endl;

    }
    return 0;
}

21.区间覆盖

查看代码测试

给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖住所有线段。
输入描述
第一行输入为所有线段的数量，不超过10000，后面每行表示一条线段，格式为”x,y”x和y 分别表示起点和终点，取值范围是[-10^5，10^5]。输出描述
最少线段数量，为正整数。
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例输入
1,4
2,5
3,6
输出

2

思路代码随想录

#include<bits/stdc++.h>
using namespace std;

bool comp(pair<int, int> x, pair<int, int> y)
{
    //按左端点从小到大排 ,左端点相同，右端点大的在前面
    if(x.first!=y.first)
    return x.first<y.first;       
    return x.second>y.second;
}

pair<int, int> split(string input_str) {
    pair<int, int> range;

    int found = input_str.find(",");
    range.first = stoi(input_str.substr(0, found));
    range.second = stoi(input_str.substr(found + 1));
    return range;
}

int main()
{
    // 输入处理
    int n;
    cin>>n;
    vector<pair<int, int>> ranges;
    int destiny=0;
    for(int i=0;i<n;i++) {
        string input_str;
        cin >> input_str;
        destiny=max(destiny,split(input_str).second);
        ranges.push_back(split(input_str));

    }
    sort(ranges.begin(), ranges.end(), comp); 
    int curDistance=ranges[0].second;//当前覆盖最远距离
    int ans=1;
    int nextDistance=ranges[0].second;//下一步覆盖最远距离
    for (int i = 1; i < ranges.size(); i++) {
       if(ranges[i].first<=curDistance){
           nextDistance=max(nextDistance,ranges[i].second);
       }else{
           i--;
           ans++;
           curDistance=nextDistance;
           if(nextDistance==destiny) break;
       }
    }
    if(curDistance!=destiny) ans++;
    cout<<ans<<endl;

    return 0;
}

22.二元组个数

查看代码测试

给定两个数组Qa，b，若l == ] 则称[,] 为一个二元组，求在给定的两个数组中，二元组的个数。输入描述:
第一行输入 m
第二行输入m个数，表示第一个数组
第三行输入 n
第四行输入n个数，表示第二个数组
输出描述:
二元组Q个数。
示例1:
输入:
d
1 2 34
输出:
说明: 二元组个数为 1个
示例2:
输入:
6
1 1 2 2 4 5
3
2 2 4
输出:
5
说明:二元组个数为 5 个

#include<bits/stdc++.h>
using namespace std;
int main() {
    //处理输入
    int m;
    cin >> m;
    vector<int> nums_a;
    map<int, int> nums_a_count;
    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        nums_a.push_back(a);
        nums_a_count[a] += 1;
    }

    int n;
    cin >> n;
    vector<int> nums_b;
    map<int, int> nums_b_count;
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b;
        nums_b.push_back(b);
        nums_b_count[b] += 1;
    }

    long result = 0;
    for (auto x : nums_a_count) {
        if (nums_b_count.count(x.first)) {
            result += x.second * nums_b_count[x.first];
        }
    }
    cout << result << endl;
    return 0;
}

23.连接器问题

查看代码测试

有一组区间[a0，b0]，[a1，b1]，… (a，b表示起点，终点) ，区间有可能重叠、相邻，重叠或相邻则可以合并为更大的区间;给定一组连接器[x1，x2，x3，…] (x表示连接器的最大可连接长度，即x>=gapQ)，可用于将分离的区间连接起来，但两个分离区间之间只能使用1个连接器请编程实现使用连接器后，最少的区间数结果。
区间数量<10000，ab均 <=10000
连接器梳理<10000; x <= 10000
输入描述
区间组: [1,10],[15,201,[18,30],[33,40]

连接器组: [5,4,3,2]
输出描述

1
说明:
合并后: [1,10],[15,30],[33,40]，使用5,3两个连接器连接后只剩下[1,40]。示例1 输入输出示例仅供调试，后台判题数据一般不包含示例入
[1,10],[15,20],[18,30],[33,40]
[5,4, 3, 2]
输出

1
说明
合并后: [1,10],[15,30],[33,40]，使用5,3两个连接器连接后只剩下[1,40]。

#include<bits/stdc++.h>
using namespace std;
vector<int> split(string input_str) {
    vector<int> v;
    while (input_str.find(",") != string::npos) {
        int found = input_str.find(",");
        v.push_back(stoi(input_str.substr(0, found)));
        input_str = input_str.substr(found + 1);
    }    
    v.push_back(stoi(input_str));
    return v;
}

bool comp(vector<int>& a, vector<int>& b) {
    if (a[0] > b[0]) {
        return false;
    } else if (a[0] == b[0]) {
        if (a[1] > b[1]) {
            return false;
        }
    }
    return true;
}

int main() {
    // 输入
    string range_str;
    cin >> range_str;
    range_str.erase(remove(range_str.begin(), range_str.end(), '['), range_str.end());
    range_str.erase(remove(range_str.begin(), range_str.end(), ']'), range_str.end());
    vector<int> temp_ranges = split(range_str);
    vector<vector<int>> ranges;
    for (int i=0;i<temp_ranges.size();i++) {
        if (i % 2 != 0) {
            vector<int> single_range;
            single_range.push_back(temp_ranges[i-1]);
            single_range.push_back(temp_ranges[i]);
            ranges.push_back(single_range);
        }
    }

    string conntetor_str;
    cin >> conntetor_str;
    conntetor_str.erase(remove(conntetor_str.begin(), conntetor_str.end(), '['), conntetor_str.end());
    conntetor_str.erase(remove(conntetor_str.begin(), conntetor_str.end(), ']'), conntetor_str.end());
    vector<int> connectors = split(conntetor_str);


    sort(ranges.begin(), ranges.end(), comp);

    // 合并区间
    vector<vector<int>> merge_ranges;
    merge_ranges.push_back(ranges[0]);
    vector<int> range_diffs;
    for (int i = 1; i < ranges.size(); i++) {
        vector<int> range1 = merge_ranges[merge_ranges.size()-1];

        vector<int> range2 = ranges[i];

        if (range2[0] <= range1[1]) {
            merge_ranges.pop_back();
            merge_ranges.push_back(vector<int>{range1[0], max(range1[1], range2[1])});
        } else {
            range_diffs.push_back(range2[0] - range1[1]);
            merge_ranges.push_back(range2);
        }
    }

    sort(range_diffs.begin(), range_diffs.end());
    sort(connectors.begin(), connectors.end());


    int result = merge_ranges.size();
    int idx = 0;
    for (int i = 0; i < connectors.size()&&idx<range_diffs.size(); i++) {
        if (connectors[i] >= range_diffs[idx]) {
            idx++;
            result--;
        }
    }

    cout<<result;
    return 0;
}

24.打印机队列

查看代码测试

有5台打印机打印文件，每台打印机有自己的待打印队列。因为打印的文件内容有轻重缓急之分，
所以队列中的文件有1~10不同的代先级，其中数宁越大优先级越高打印机会从自己的待打印队列中选择优先级最高的文件来打印。如果存在两个优先级一样的文件，则选择最早进入队列的那个文件现在请你来模拟这5台打印机的打印过程。
输入描述
每个输入包含1个测试用例，每个测试用例第一行给出发生事件的数量N (0 < N< 1000)。
接下来有 N 行，分别表示发生的事件。
共有如下两种事件:
1.“IN P NUM”，表示有一个拥有优先级 NUM 的文件放到了打印机 P 的待打印队列中。 (0< P<= 5, 0< NUM <= 10);
2.“OUT P”，表示打印机 P 进行了一次文件打印，同时该文件从待打印队列中取出。 (0< P<=57
输出描述
对于每个测试用例，每次”OUT P”事件，请在一行中输出文件的编号如果此时没有文件可以打印，请输出”NULL“。文件的编号定义为”IN P NUM”事件发生第 次，此处待打印文件的编号为x。编号从1开始.示例1 输入输出示例仅供调试，后台判断数据一般不包含示例
输入

7
IN 1 1
IN 1 2
IN 1 3
IN 2 1
OUT 1
OUT 2
OUT 2
输出

3

4

NULL

#include<bits/stdc++.h>
using namespace std;

vector<string> split(string input_str) {
    vector<string> v;
    while (input_str.find(" ") != string::npos) {
        int found = input_str.find(" ");
        v.push_back(input_str.substr(0, found));
        input_str = input_str.substr(found + 1);
    }    
    v.push_back(input_str);
    return v;
}

struct File {
    int order;
    int priority;
};

bool comp(File a, File b) {
    return b.priority-a.priority;
}

int main() {
    // 处理输入
    string input_count_str;
    getline(cin,input_count_str);
    int count = stoi(input_count_str);

    vector<vector<File>> printers(5, vector<File>());

    int flag = 0;
    for (int i = 0; i < count; i++) {
        string temp_str;
        getline(cin,temp_str);
        vector<string> operations = split(temp_str);
        string type = operations[0];

        if ("IN" == type) {
            int p = stoi(operations[1]);
            int num = stoi(operations[2]);
            flag++;
            File file;
            file.order = flag;
            file.priority = num;
            printers[p - 1].push_back(file);
        } else if ("OUT"==type) {
            int p = stoi(operations[1]);
            if (printers[p-1].size() > 0) {
                sort(printers[p-1].begin(), printers[p-1].end(), comp);
                File file = printers[p-1][0];
                cout<<file.order<<endl;
                printers[p-1].erase(printers[p-1].begin());
            } else {
                cout<<"NULL"<<endl;
            }
        }

    }    
    return 0;
}

25.处理器问题

26.日志首次上报最多积分

查看代码测试

日志采集是运维系统的的核心组件。日志是按行生成，每行记做一条，由采集系统分批上报。如果上报太频繁，会对服务端造成压力;如果上报太晚，会降低用户的体验,如果一次上报的条数太多，会导致超时失败。为此，项目组设计了如下的上报策略
1、每成功上报一条日志，奖励1分
2、每条日志每延迟上报1秒，扣1分3、积累日志达到100条，必须立即上报给出日志序列，根据该规则，计算首次上报能获得的最多积分数输入描述:
按时序产生的日志条数 T1,T2…Tn，其中 1<=n<=1000，0<=Ti<=100输出描述:
首次上报最多能获得的积分数
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
1 98 1
输出
98
说明:
T1 时刻上报得 1 分
T2 时刻上报得98分，最大
T3 时刻上报得 0分
示例2 输入输出示例仅供调试，后台判题数据一般不包含示例输入
3 7 40 10 60
输出

37
说明:
T1 时刻上报得 3 分
T2 时刻上报得 7 分
T3 时刻上报得 37 分，最大
T4 时刻上报得 -3 分
T5 时刻上报，因为已经超了100条的限制，所以只能上报100条，得 -23 分

#include<bits/stdc++.h>
using namespace std;

int main() {
    // 处理输入
    string input_str;
    getline(cin,input_str);
    vector<int> logs;
    while (input_str.find(" ") != string::npos) {
        int found = input_str.find(" ");
        logs.push_back(stoi(input_str.substr(0, found)));
        input_str = input_str.substr(found + 1);
    }    
    logs.push_back(stoi(input_str));

    //加分
    vector<int> plus_score(logs.size(), 0);
    plus_score[0] = logs[0];

    // 减分
    vector<int> minus_score(logs.size(), 0);

    vector<int> result(logs.size(), 0);
    result[0] = logs[0];

    for (int i = 1; i < logs.size(); i++) {
        plus_score[i] = min(100, plus_score[i - 1] + logs[i]);
        minus_score[i] = minus_score[i - 1] + plus_score[i - 1];
        result[i] = plus_score[i] - minus_score[i];

        if (plus_score[i] >= 100) {
            break;
        } 
    }

    int max_score = 0; // 最大值
    for (int item : result) {
        if (item > max_score) {
            max_score = item;
        }
    }
    cout<<max_score;

    return 0;
}

27.简单的曝光

查看代码测试

一个图像有n个像素点，存储在一个长度为n的数组img里，每个像素点的取值范围[0,255]的正整数。清你给图像每个像素点值加上一个整数k(可以是负数》，得到新图newImg，使得新图newImg的所有像素平均值最接近中位值128。请输出这个整数k。
输入描述
n个整数，中间用空格分开
例如
0 0 0 0
4个数值，中间用空格分开
输出描述
个整数k
补充说明
1<=n<= 100
·如有多个整数k都满足，输出小的那个k;新图的像素值会自动截取到[0,255]范围。当新像素值<0，其值会更改为0; 当新像素值>255其值会更改为255;
例如newlmg=”-1 -2 256”会自动更改为”0 0 255”
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例输入
0 0 0 0
输出
128

#include<bits/stdc++.h>
using namespace std;

vector<int> split(string input_str) {
    vector<int> v;
    while (input_str.find(" ") != string::npos) {
        int found = input_str.find(" ");
        v.push_back(stoi(input_str.substr(0, found)));
        input_str = input_str.substr(found + 1);
    }    
    v.push_back(stoi(input_str));
    return v;
}

vector<string> split_str(string params_str, string op) {
    vector<string> p;
    while (params_str.find(op) != string::npos) {
        int found = params_str.find(op);
        p.push_back(params_str.substr(0, found));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(params_str);
    return p;
}
int main() {
    // 输入处理
    string input_str;
    getline(cin, input_str);
    vector<int> nums = split(input_str);


    double min_diff = 256;
    int result = -256;

    for (int i = -127; i <= 128; i++) {
        double sum = 0;
        for (int j=0;j<nums.size();j++) {
            // 注意项3
            sum += max(0, min(nums[j] + i, 255));
        }

        //靠近中位数的程度
        double diff = abs(sum / nums.size() - 128);

        if (diff < min_diff) {
            min_diff = diff;
            result = i;
        } else if (diff == min_diff && result != -256) {
            //注意项2
            result = min(result, i);
        }
    }
    cout<<result;
    return 0;
}

27.最大版本号

查看代码测试

Maven 版本号定义，<主版本>.<次版本>.增量版本>-<里程碑版本举例3.1.4-beta 其中，主版本和次版本都是必须的，主版本，次版本，增量版本由多位数字组成，可能包含前导零，里程碑版本由字符串组成

<主版本>.<次版本>增量版本>: 基于数字比较

比较里程碑版本: 基于宁符串比较

采用字典典序比较版本号时，按从左到右的顺序依次比较。基于数字比较只需比较忽略任何前导零后的整数值

输入2个版本号

输出最大版本号
输入描述:
输入两个版本号，按行分割，每个版本号的长度小于50

输出描述:
输出较大的版本号
示例1:
输入:
2.5.1-0
1.4.2-D
输出:
2.5.1-0

28.二进制差异数

查看代码测试

对于任意两个正整数A和B，定义它们之间的差异值和相似值:差异值:A、B转换成二进制后，对于二进制的每一位，对应位置的bit值不相同则为1，否则为
0:
相似值: A、B转换成二进制后，对于二进制的每一位，对应位置的bit值都为1则为1，否则为0:
现在有n个正整数A0到A (n-1)，问有多少(i,j)0<=i<j<n) ，Ai和Aj的差异值大于相似值.假设A=5，B=3;则A的二进制表示101;B的二进制表示011;则A与B的差异值二进制为110;
相似值二进制为001;
A与B的差异值十进制等于6，相似值十进制等于1，满足条件。输入描述

输入个n

接下来n个正整数数据范围: 1<=n<=10^5，1<=A[i]<2^30输出描述
输出
满足差异值大于相似值的对数
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
4
4 3 5 2
输出
4
说明
样例1解释
满足条件的分别是(0,1)(0,3)(1,2)(2,3)，共4对

#include <iostream>
#include <vector>
int countPairsWithDifference(std::vector<int>& nums) {
    int count = 0;
    int n = nums.size();

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = nums[i] ^ nums[j];
            int sim = nums[i] & nums[j];

            if (diff > sim) {
                count++;
            }
        }
    }

    return count;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        std::cin >> nums[i];
    }

    int result = countPairsWithDifference(nums);
    std::cout << result << std::endl;

    return 0;
}

解法二思路：其实就是找规律，因为差异值大于相似值，其最高位的1必然不同，这样就会导致差异值的最高位为1，相似值的最高位为0。因此我们只要找到最高位的1的种类，然后相互组合即可。

#include<bits/stdc++.h>
using namespace std;

vector<int> split(string params_str) {
    vector<int> p;
    while (params_str.find(" ") != string::npos) {
        int found = params_str.find(" ");
        p.push_back(stoi(params_str.substr(0, found)));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(stoi(params_str));
    return p;
}


vector<string> split_str(string params_str, string op) {
    vector<string> p;
    while (params_str.find(op) != string::npos) {
        int found = params_str.find(op);
        p.push_back(params_str.substr(0, found));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(params_str);
    return p;
}

int main()
{
    string param_str;
    getline(cin, param_str);
    int n = stoi(param_str);

    string op_str;
    getline(cin, op_str);
    vector<int> nums = split(op_str);

    vector<int> bit_info(100, 0); 

    for (auto num : nums) {
      bitset<32> num_binary(num);
      string num_binary_str= num_binary.to_string();
      num_binary_str.erase(0,num_binary_str.find_first_not_of("0"));
      int len = num_binary_str.size(); 

      if ("" == num_binary_str) {
        bit_info[0]++;
      } else {
        bit_info[num_binary_str.size()]++;
      }
    }

    int res = 0;
    for (int i = 0; i < bit_info.size(); i++) {
      for (int j = i + 1; j < bit_info.size(); j++) {
        res += bit_info[i] * bit_info[j];
      }
    }
    cout<< res;
    return 0;
}

Excel单元格数值统计

相同数字的积木游戏

开放日活动

查看代码测试

其实题目很简单，就是设置一下 maxcapacity ，从大到小遍历即可，看每一轮消减小球个数后，能否满足条件。

二分法

投篮大赛

查看代码测试

你现在是一场采用特殊赛制投篮大赛的记录员。这场比赛由若干回合组成，过去几回合的得分口能会影响以后几回合的得分。
比赛开始时，记录是空白的。
你会得到一个记录操作的字符串列表 opsQ，其中ops是你需要记录的第i项操作，ops遵循下述规则:
。整数X-表示本回合新获得分数x
“+”- 表示本回合新获得的得分是前两次得分的总和
。“D”- 表示本回合新获得的得分是前一次得分的两倍
。“C”- 表示本回合没有分数，并且前一次得分无效，将其从记录中移除.
请你返回记录中所有得分的总和。
示例1:
输入: 52CD+
输出: 30
解释:
“5”-记录加5，记录现在是[5]
“2”-记录加2，记录现在是[5,2]
“C”-使前一次得分的记录无效并将其移除，记录现在是[5].
“D”-记录加2*5=10，记录现在是[5，10].
“+”-记录加5+10=15，记录现在是[5，10，15]所有得分的总和5+10+15=30

#include<bits/stdc++.h>
using namespace std;

vector<int> split(string params_str) {
    vector<int> p;
    while (params_str.find(" ") != string::npos) {
        int found = params_str.find(" ");
        p.push_back(stoi(params_str.substr(0, found)));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(stoi(params_str));
    return p;
}

vector<string> split_str(string params_str) {
    vector<string> p;
    while (params_str.find(" ") != string::npos) {
        int found = params_str.find(" ");
        p.push_back(params_str.substr(0, found));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(params_str);
    return p;
}


int main()
{
    string param_str;
    getline(cin, param_str);
    vector<string> params = split_str(param_str);

    //四个分支，但其实有隐患
    vector<int> scores;
    for (int i=0;i<params.size();i++) {
        if (params[i] == "+") {
            if (scores.size() < 2) {
                cout<<-1;
                return 0;
            }
            scores.push_back(scores[scores.size()-2] + scores[scores.size()-1]);
        } else if (params[i] == "D") {
            if (scores.size() < 1) {
                cout<<-1;
                return 0;
            }
            scores.push_back(2*scores[scores.size()-1]);
        } else if (params[i] == "C") {
            if (scores.size() < 1) {
                cout<<-1;
                return 0;
            }
            scores.pop_back();
        } else {
            scores.push_back(stoi(params[i]));
        }
    }


    cout<< accumulate(scores.begin(), scores.end(), 0);
    return 0;
}

开心消消乐

查看代码测试

通信误码

查看代码测试

信号传播过程中会出现一些误码，不同的数字表示不同的误码ID，取值范围为1~65535，用一个数组Q记录误码出现的情况，
每个误码出现的次数代表误码频度，请找出记录中包含频度最高误码的最小子 数组长度Q输入描述
误码总数目: 取值范围为0~255，取值为0表示没有误码的情况。误码出现频率数组: 误码ID范围为1~65535，数组长度为1~1000.输出描述
包含频率最高的误码最小子数组长度
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
5
1 2 2 4 1
输出
2
说明
频度最高的有1和2，他们的频度均为2
可能的记录数组为[2,2]和[1,2,2,4,1]
最短的长度为2.
示例2 输入输出示例仅供调试，后台判题数据一般不包含示例入

7
1 2 2 4 2 1 1
输出
4
说明
最短的为[2,2,4,2]

#include<bits/stdc++.h>
using namespace std;

vector<int> split(string params_str) {
    vector<int> p;
    while (params_str.find(" ") != string::npos) {
        int found = params_str.find(" ");
        p.push_back(stoi(params_str.substr(0, found)));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(stoi(params_str));
    return p;
}


vector<string> split_str(string params_str) {
    vector<string> p;
    while (params_str.find(" ") != string::npos) {
        int found = params_str.find(" ");
        p.push_back(params_str.substr(0, found));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(params_str);
    return p;
}

int main()
{
    string n_str;
    getline(cin, n_str);
    int n = stoi(n_str);

    string param_str;
    getline(cin, param_str);
    vector<int> nums = split(param_str);


    //计算频度最高的数字
    int max_count = 0;
    map<int, int> num_count;
    for (int i = 0; i < n; i++) {
        if (num_count.count(nums[i])) {
            num_count[nums[i]] = num_count[nums[i]] + 1;
        } else {
            num_count[nums[i]] = 1;
        }
        max_count = max(max_count, num_count[nums[i]]);
    }

    set<int> max_num;
    for (auto item : num_count) {
        if (item.second == max_count) {
            max_num.insert(item.first);
        }
    }


    //找到第一次和最后一次出现位置
    int result = n;
    for (auto i : max_num) {
        int left = 0, right = n - 1;
        while (nums[left] != i) {
            left++;
        }
        while (nums[right] != i) {
            right--;
        }
        if (left <= right) {
            result = min(result, rig
ht - left + 1);
        }
    }

    cout<< result;
    return 0;
}

最大报酬

查看代码测试

小明每周上班都会拿到自己的工作清单，工作清单内包含n项工作，每项工作都有对应的耗时时间（单位h）和报酬,

工作的总报酬为所有已完成工作的报酬之和，那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。

输入描述

输入的第一行为两个正整数T，n。

T代表工作时长（单位h，0<T<1000000），n代表工作数量（1<n≤3000）。

接下来是n行，每行包含两个整数t，w。

t代表该工作消耗的时长（单位h，t>0）,w代表该项工作的报酬。

输出描述

输出小明制定工作时长内工作可获得的最大报酬。

输入

40 3

20 10

20 20

20 5

输出

30

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int Cap, num;
    cin>>Cap>>num;
    int weight[100], value[100];
    for(int i=1; i<=num; i++)
    {
        cin>>weight[i]>>value[i];
    }
    int dp[100][100]={0};
    for(int i=1; i<=num; i++)
    {
        for(int j=weight[i]; j<=Cap; j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
        }
    }
    cout<<dp[num][Cap]<<endl;

    return 0;
}

机器人

新学校选址

寻找路径

查看代码测试

二叉树Q也可以用数组来存储，给定一个数组，树的根节点的值储存在下标1对于储存在下标n的节点，他的左子节点和右子节点分别储存在下标2n和2*n+1.并且我们用-1代表一个节点为空。
给定一个数组存储的二叉树，试求从根节点到最小的 叶子节点Q 的路径，路径由节点的值组
成。
输入描述
输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分割。注意第一个元素即为根节点的值，即数组的第n元素对应下标n。下标0在树的表示中没有使用所以我们省略了。输入的树最多为7层。
输出描述
输出从根节点到最小叶子节点的路径上各个节点的值由空格分割用例保证最小叶子节点只有一个示例一
输入
3 5 7 -1 -1 2 4
输出
3 7 2
示例二
输入
5 9 8-1 -1 7 -1 -1-1-1 -1 6
输出
5 8 7 6

#include<bits/stdc++.h>
using namespace std;

vector<int> split(string params_str) {
    vector<int> p;
    while (params_str.find(" ") != string::npos) {
        int found = params_str.find(" ");
        p.push_back(stoi(params_str.substr(0, found)));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(stoi(params_str));
    return p;
}


vector<string> split_str(string params_str) {
    vector<string> p;
    while (params_str.find(" ") != string::npos) {
        int found = params_str.find(" ");
        p.push_back(params_str.substr(0, found));
        params_str = params_str.substr(found + 1);
    }    
    p.push_back(params_str);
    return p;
}


int main()
{

    string operation_str;
    getline(cin, operation_str);
    vector<int> nodes = split(operation_str);

    int minValue = *max_element(nodes.begin(), nodes.end());
    int minPos = 0;


     //找最小叶子结点
    for (int i = nodes.size()-1; i >= 1; i--) {
        if (nodes[i] != -1) {
            if ((i * 2 + 1 <= nodes.size()-1 && nodes[i * 2 + 1] != -1) || (i * 2 + 2 <= nodes.size()-1 && nodes[i * 2 + 2] != -1)) {
                continue;
            }
            if (minValue > nodes[i]) {
                minValue = nodes[i];
                minPos = i;
            }
        }
    }

    //往上遍历
    vector<int> path;
    path.push_back(minValue);
    while (minPos >= 1) {
        path.push_back(nodes[(minPos-1)/2]);
        minPos = (minPos-1)/2;
    }


    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i];
        if (i != 0) {
            cout << " ";
        }
    }
    return 0;
}

任务调度

查看代码测试

现有一个CPU和一些任务需要处理，已提前获知每个任务的任务ID、优先级、所需执行时间和到达时间。CPU同时只能运行一个任务，请编写一个任务调度程序，采用“可抢占优先权调度”调度算法进行任务调度，规则如下：

1：如果一个任务到来时，CPU是空闲的，则CPU可以运行该任务直到任务执行完毕。但是如果运行中有一个更高优先级的任务到来，则CPU必须暂停当前任务去运行这个优先级更高的任务；

2：如果一个任务到来时，CPU正在运行一个比他优先级更高的任务时，信道大的任务必须等待；

3：当CPU空闲时，如果还有任务在等待，CPU会从这些任务中选择一个优先级最高的任务执行，相同优先级的任务选择到达时间最早的任务。

输入描述

输入有若干行，每一行有四个数字（均小于10^8）,分别为任务ID，任务优先级，执行时间和到达时间。每个任务的任务ID不同，优先级数字越大优先级越高，并且相同优先级的任务不会同时到达。

输入的任务已按照到达时间从小到大排序，并且保证在任何时间，处于等待的任务不超过10000个。

输出描述

按照任务执行结束的顺序，

示例一

输入

1 3 5 1

2 1 5 10

3 2 7 12

4 3 2 20

5 4 9 21

6 4 2 22

输出

1 6

3 19

5 30

6 32

4 33

2 35