2021vivo提前批软件类编程题目&代码 (c++）

第一题第二题ac 第三题来不及做了第二天继续写，给的案例通过了，其他的就不知道了。

很多人输入数出有遇到麻烦，这种形式的输入输出对于c++真的太不友好了，好麻烦。。不过acm模式经常这样，还是要多多联系做好准备啊。

第一题：幸运员工抽奖

从团队中选出整个工号中含有数字7或者工号是7的倍数的员工。

输入：一组空格分隔的员工工号列表。

输出：幸运员工总人数，未找到时输出0。

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

vector<int> split(string str, string pattern){
	string::size_type pos;
	vector<int> result;
	str += pattern;
	int size = str.size();
	for(int i = 0; i < size; i++){
		pos = str.find(pattern, i);
		if(pos < size){
			string s = str.substr(i, pos - i);
			result.push_back(stoi(s));
			i = pos + pattern.size() - 1;
		}
	}
	return result;
}

bool fun(int num){
	string str = to_string(num);
	for(int i = 0; i < str.size(); i++){
		if(str[i] == '7'){
			return true;
		}
	}
	return false;
}

int main(){
	string input = "";
	getline(cin, input);
	//input = "7 17 27 35 8 49 50";
	vector<int> vec = split(input, " ");
	int result = 0;
	for(auto it: vec){
		if(it % 7 == 0){
			result++;
		}
		else{
			if(fun(it)){
				result++;
			}
		}
	}
	//cout<<vec.size()<<endl;
	cout<<result<<"\n";
	return 0;
	
}

第二题：货运装箱问题

货轮最大重量C，有N个集装箱，每个集装箱重量W(i)，对应货物价值V(i)。求货轮不超过最大载重的前提下装载货物总价值最大。

输入：第一行最大重量C，第二行每个集装箱重量W(i)，第三行每个集装箱价值V(i)。

输出：货物总价值。

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

vector<int> split(string str, string pattern){
	string::size_type pos;
	vector<int> result;
	str += pattern;
	int size = str.size();
	for(int i = 0; i < size; i++){
		pos = str.find(pattern, i);
		if(pos < size){
			string s = str.substr(i, pos - i);
			result.push_back(stoi(s));
			i = pos + pattern.size() - 1;
		}
	}
	return result;
}


int main(){
	int bagweight = 0;
	string input1;
	string input2;
	cin>>bagweight;
	cin>>input1;
	cin>>input2;
	vector<int> weight = split(input1, ",");
	vector<int> value = split(input2, ",");
	vector<int> dp(bagweight + 1, 0);
	for(int i = 0; i < weight.size(); i++){
		for(int j = bagweight; j >= weight[i]; j--){
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
		}
	}
	cout<<dp[bagweight]<<endl;
	return 0;
}

第三题：最短路径

图像从传感器到输出JPEG格式图片经过很多node处理，这些node构成一个图像处理的pipeline，其中的有些节点依赖于其他节点输出。A->B表示B的执行依赖于A。

假设每个node执行时间为A(t)，即node A需要执行t秒，没有依赖的node可以并行执行。编写一个方法输入一个有向无环图pipeline，输出执行完需要的最短时间。

输入：第一行输入node的执行时间，第二行输入node的依赖关系。

输出：最短时间。

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

vector<int> split(string str, string pattern){
	string::size_type pos;
	vector<int> result;
	str += pattern;
	int size = str.size();
	for(int i = 0; i < size; i++){
		pos = str.find(pattern, i);
		if(pos < size){
			string s = str.substr(i, pos - i);
			result.push_back(stoi(s));
			i = pos + pattern.size() - 1;
		}
	}
	return result;
}

vector<string> split2(string str, string pattern){
	string::size_type pos;
	vector<string> result;
	str += pattern;
	int size = str.size();
	for(int i = 0; i < size; i++){
		pos = str.find(pattern, i);
		if(pos < size){
			string s = str.substr(i, pos - i);
			result.push_back(s);
			i = pos + pattern.size() - 1;
		}
	}
	return result;
}


int main(){
	string input1;
	string input2;
	//cin>>input1;
	//cin>>input2;
	input1 = "3,1,2,5,3,1";
	input2 = "2,3,4;5;5,6;0;6;0";
	vector<int> time = split(input1, ",");
	vector<string> str_relation = split2(input2, ";");
	vector<vector<int>> relation;
	for(auto it: str_relation){
		vector<int> temp;
		temp = split(it, ",");
		relation.push_back(temp);
	} 
	int num_node = time.size();
	vector<int> ceng(num_node + 1, 1);
	ceng[0] = 0;
	int count = 1;
	for(auto i: relation){
		for(auto j: i){
			if(j == 0){
				break;
			}
			ceng[j] = ceng[count] + 1;
			
		}
		count++;
	}
	vector<int> result_time(num_node + 1, 0);
	int max_ceng = *max_element(ceng.begin(), ceng.end());
	//cout<<max_ceng;
	for(int i = 1; i <= max_ceng; i++){  //从第一层到最大层 逐层遍历 
		for(int j = 1; j < ceng.size(); j++){  //遍历所有节点 
			if(ceng[j] == i){  //如果是第i层的节点 
				int last_time = INT_MIN;  //上层所有节点的最大执行时间 
				for(int m = 0; m < relation.size(); m++){
					vector<int> temp = relation[m];
					for(auto n: temp){
						if(n == j && result_time[m + 1] > last_time){  //说明j节点依赖于m 并且 被依赖的m节点执行时间更长 
							last_time = result_time[m + 1];
						}
					}
				}
				if(last_time == INT_MIN){
					result_time[j] = time[j - 1];
				}
				else{
					result_time[j] = last_time + time[j - 1];	
				}
				
			}
		}
	}
	int result = INT_MIN;
	for(int i = 1; i <= ceng.size(); i++){
		if(ceng[i] == max_ceng && result_time[i] > result){
			result = result_time[i];
		}
	}
	cout<<result<<"\n";
	return 0;
}

#面经##vivo##校招#