360公司2018春招编程题题解【附C/C++代码】

注：本篇博客代码均为博主手敲已经通过牛客网的编译，如果有问题可以留言。

题目1：画板

沫璃有一个画板，画板可以抽象成有100行每行100个像素点的正方形。沫璃在画板上画画，她一共画了n次，每次将一个矩形涂上颜色。沫璃想知道一共有多少个像素点被她涂过颜色。若一个像素点被涂了k次，那么认为有k个像素点被涂过颜色。
输入描述

第一行一个数T(T<=100)，表示数据组数。
对于每组数据，第一行一个整数n , (1<=n<=100)
接下来n行，每行4个整数x1, y1,x2, y2 (1 <= x1 <= x2 <= 100, 1 <= y1 <= y2 <= 100)，表示矩形的两个对角所对应的像素点的坐标。

输出描述

对于每组数据，输出一行，表示沫璃一共涂了多少个像素点。

输入例子1:

2
2
1 1 2 3
2 2 3 3
2
1 1 3 3
1 1 3 3

输出例子1:

10
18

代码（c++/c）

#include<iostream> 
using namespace std;
int main(){
	int n;
	cin >> n;  // 画的次数 
	
	while(n--){
		int T; // 这一次画 花了几个矩形区域
		int ans = 0 ; // 这一次画 画的像素格子个数（多个矩形区域格子个数之和） 
		cin >> T; 
		while(T--){
			int x1,y1,x2,y2; // 矩形区域的左上角(x1,y1)和右上角坐标 (x2,y2)
			cin >> x1 >> y1 >> x2 >> y2 ;
			ans += (x2 - x1 + 1) * (y2 - y1 + 1);
		} 
		cout<<ans<<endl; // 输出这一次画的区域像素个数之和 
	}
	
	return 0;
}

---

题目2：交易

沫璃发起了一场交易，她将她的5个朋友聚在一起准备进行一场交易。交易开始前，大家各有b(b>0)个硬币，交易后，每个人有ai个硬币。由于硬币不方面携带，在交易过程中可能会丢失。现在沫璃想知道是否一定丢失硬币，或者在可能没有丢失硬币的情况下，交易前每个人的硬币数b。沫璃只是组织者，不参与交易。

输入描述

第一行一个数T(T<=100)，表示数据组数。
对于每组数据，第一行5个整数，第i个整数ai表示交易后第i个朋友的硬币数(0<=ai<=100)

输出描述

对于每组数据，输出一行，若一定丢失硬币输出-1，若可能没有丢失硬币，输出b。

输入例子1:

2
2 5 4 0 4
4 5 9 2 1

输出例子1:

3
-1

代码（c++/c）

#include<iostream> 
using namespace std;
int main(){
	int T; // 数据组数
	cin >> T;
	int a[5] = {0};
	while(T--) {	
	
		int n = 5; // 朋友个数 
		int sum = 0; // 这一次硬币交易的总额 
		while(n--){ // 获取朋友的硬币数
			cin >> a[n]; // 交易后每个人的硬币个数
			sum += a[n];
		};
		if(sum % 5 == 0 && sum != 0){ // 如果这个总额能整除5而且最后的硬币之和不是0（因为原始每个人均分的硬币个数是大于0的）说明大家现有的硬币没有丢失，反之则丢失了 
			cout<<sum/5<<endl;	// 如果没有丢失，输出游戏开始大家均分的金币数额	
		}else{
			cout<<-1<<endl; // 丢失了就输出-1 
		};		
	};
	return 0;
}

---

题目3：派对

沫璃邀请她的朋友参加周末的派对。沫璃买了3种颜色的气球，现在她要有这些气球来装饰餐桌，每个餐桌只用恰好3个气球装饰，要求3个气球的颜色不能完全一样，可以是2种或者3种颜色。沫璃想知道这些气球最多能装饰多少张餐桌。

输入描述

第一行一个数T(T<=100)，表示数据组数。
对于每组数据，第一行3个整数r，g，b，分别表示三种颜色的气球个数(0<=r, g, b<=2*10^9)

输出描述

对于每组数据，输出一行，一个整数表示最多能装饰的餐桌数量。

输入例子1:

2
5 4 3
2 3 3

输出例子1:

4
2

代码（c++/c）

#include<iostream> 
using namespace std;
typedef long long LL;
// 注意：本题目 (0<=r, g, b<=2*10^9) 因此int类型范围会超出
// 因此使用long long类型 
LL findMin(LL r , LL g , LL b){
	LL min;
	if(r > g){
		min = g;
	}else{
		min = r;
	};
	if(g > b){
		min = b;
	}else{
		min = g;
	}
	
	return min;
};

LL findMax(LL r , LL g , LL b){
	LL max = -1;
	if (max < r){
		max = r;
	};
	if (max < g){
		max = g;
	};
	if (max < b){
		max = b;
	};
	
	return max;
};

LL findMid(LL r , LL g , LL b){
	return r+g+b-(findMax(r,g,b) + findMin(r,g,b) );
};
int main(){
	int T; // 数据组数
	cin >> T;
	LL r , g , b; // 每一种颜色气球的个数 
	LL n ; // 餐桌个数 
	while(T--) {	
		cin >> r >> g >> b ;
		LL max = findMax(r,g,b);
		LL min = findMin(r,g,b);
		LL mid = findMid(r,g,b);
		if (max > (min + mid) * 2){
			n = mid + min;
		}else{
			n = (mid + max + min) / 3;
		};
		cout << n << endl;
	};
	return 0;
};

---

题目4：赛马

茉莉有2n匹马，每匹马都有一个速度v，现在茉莉将马分为两个队伍，每个队伍各有n匹马，两个队之间进行n场比赛，每场比赛两队各派出一匹马参赛，每匹马都恰好出场一次。茉莉想知道是否存在一种分配队伍的方法使得无论怎么安排比赛，第一个队伍都一定能获的全胜，两匹马若速度不同，那么速度快的获胜，若速度一样，则都有可能获胜。

输入描述

对于每组数据，输出一行，若存在一种分配方法使得第一个队伍全胜输出YES，否则输出NO
第一行一个数T(T<=100)，表示数据组数。
对于每组数据，第一行一个整数n , (1<=n<=100)
接下来一行，2*n个整数，第i个整数vi表示第i匹马的速度, (1<= vi <= 1000)

输出描述

对于每组数据，输出一行，若存在一种分配方法使得第一个队伍全胜输出YES，否则输出NO

输入例子:

2
2
1 2 3 4
1
1 1

输出例子

YES
NO

代码（c++/c）

#include<iostream> 
using namespace std;
// 直接插入排序 
void sort(int *p , int size){
	for(int i = 1; i < size ; i++){
		int temp = p[i];
		int j = i;
		while(p[j - 1] > temp && j > 0){
			p[j] = p [j-1];
			j--;
		}
		p[j] = temp;
	} 
} 
int main(){
	int T; // 数据组数
	cin >> T;

	while(T--) {	
		int n; // 队伍进行的比赛场数
		cin >> n;
		int size = 2 * n; // 马匹的数目 
		// 动态生成马匹 i的速度vi数组
		int *v = new int[size];
		// 获取每匹马的速度
		 
		while(size--) {
			cin >> v[size] ;
		}
		size = 2 * n;
		// 对数组进行排序
		sort(v , size);		
		// 判断中间两个速度是不是相等 
		// 如果速度相等就有可能输 即无法确定全胜
		if (v[size / 2] > v[size / 2 - 1]){
			cout<<"YES"<<endl;
		}  else{
			cout<<"NO"<<endl;
		}
	};
	return 0;
};

---

题目5：玫瑰花

有K种不同的玫瑰花，现在要摆放在N个位置上，要求每种颜色的花至少出现过一次，请问有多少种不同的方案数呢？，因为答案可能很大，你只需要输出它对772235取余后的结果.

输入描述

输入只有1行，分别有两个整数N,K( 1 <= N <= 50000 , 1 <= K <= 30 )

输出描述

输出一行表示答案

输入例子:

3 2

输出例子:

6

思路分析
一看到对某个数取余就知道这个是大数计算了，不能用int类型。
自以为使用long long类型避开了大数的坑，结果还是运算错误，因为简单的用组合会重复（为什么会重复我也不知道），后来改用动态规划来写。
上一波只有**20%**通过率的错误代码。
错误代码！！！ERROR

#include<iostream> 
#include<math.h> //为了计算次幂 
using namespace std;
typedef long long LL;
double combine(int up , int down){
	LL a = 1 ,b = 1;
	while(up--){
		a *= down;
		b *= up + 1;
		down -- ;
	}
	return a/b;
} 

int main(){
	int K , N; // K种玫瑰花，N个位置
	cin >> N >> K;
	//cout<<combine(K,N) ;
	LL result = (LL(combine(K,N)) * LL(pow(K,N-K))) % 772235;
	cout << result << endl;
	return 0;
};

正确代码（c++/c）

暂时没写

---

题目6：奇异长度（选做）

给你一个图，0节点连接这一个联通块a，1节点连接着一个联通块b,ab仅由01这条边相连。现在我们定义奇异路径为恰好经过0-1这条边一次的路径。在这个图中有无数条奇异路径，问第k长的奇异路径长度是多少？

输入描述

输入若干行，第一行有三个正整数n,m,k,表示有n个节点，0~n-1,有m条边，问第k长，接下来有m行u,v,表示边，保证0-1边只出现一次,保证a,b联通块只通过0-1相连。
5<=n<=100,k<2^40

输出描述

输出一行表示答案

输入例子:

5 4 10
0 1
0 2
1 3
1 4

输出例子1:

4

代码（c++/c）

暂时没写

---

如果我的文章能帮你节约20秒，就请你为我的文章点个赞吧！