360公司2018春招编程题题解
原文CSDN链接：360公司2018春季招聘编程题 - 题解
GitHub代码：360公司2018春季招聘编程题
个人题解，不一定全部通过，各位多指正，360的选做题都是动态规划。
第一题：画板
题目描述：
沫璃有一个画板，画板可以抽象成有100行每行100个像素点的正方形。沫璃在画板上画画，她一共画了n次，每次将一个矩形涂上颜色。沫璃想知道一共有多少个像素点被她涂过颜色。若一个像素点被涂了k次，那么认为有k个像素点被涂过颜色。
输入
第一行一个数T$(T<=100)$，表示数据组数。
对于每组数据，第一行一个整数n, $(1<=n<=100)$
接下来n行，每行4个整数$x_1, y_1, x_2, y_2 (1 <= x_1 <= x_2 <= 100, 1 <= y_1 <= y_2 <= 100)$，表示矩形的两个对角所对应的像素点的坐标。
输出
对于每组数据，输出一行，表示沫璃一共涂了多少个像素点。
样例
<pre>
<b>in:</b>
2
2
1 1 2 3
2 2 3 3
2
1 1 3 3
1 1 3 3
<b>out:</b>
10
18
</pre>
解析
这题有了题中加粗的部分就很好解决了，只需要看下这个矩形中有多少个像素点就行了。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
for (int n, x1, y1, x2, y2; T--; ) {
cin >> n;
int ans = 0;
for (int i = 0; i < n; i++)
cin >> x1 >> y1 >> x2 >> y2,
ans += (x2 - x1 + 1) * (y2 - y1 + 1);
cout << ans << endl;
}
return 0;
} 第二题：派对
题目描述：
沫璃邀请她的朋友参加周末的派对。沫璃买了3种颜色的气球，现在她要有这些气球来装饰餐桌，每个餐桌只用恰好3个气球装饰，要求3个气球的颜色不能完全一样，可以是2种或者3种颜色。沫璃想知道这些气球最多能装饰多少张餐桌。
输入
第一行一个数T$(T<=100)$，表示数据组数。
对于每组数据，第一行3个整数r，g，b，分别表示三种颜色的气球个数$ (0<=r, g, b<=2*10^9)$
输出
对于每组数据，输出一行，一个整数表示最多能装饰的餐桌数量。
样例
<pre>
<b>in:</b>
2
5 4 3
2 3 3
<b>out:</b>
4
2
</pre>
解析
思维题，这是Codeforces的一个原题，首先，要明确一点，只能使用1 2和1 1 1这两种组合，而且能使用1 1 1的一般都可以使用1 2来替代，而且1 2这种组合还比1 1 1还少用一种颜色，因此，先把三种颜色按数量排序，颜色数量最多的那个用2个，其余的用一个，这样试一下看看行不行，如果行就最好，不行的话，用1 1 1这种组合和2 1这种组合来中和，这样去凑。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int T;
cin >> T;
for (LL r, g, b; T--; ) {
cin >> r >> g >> b;
LL R = min(min(r, g), b), B = max(max(r, g), b), G = r + g + b - R - B;
LL ans = (R + G) * 2 <= B ? R + G : (R + G + B) / 3;
cout << ans << endl;
}
return 0;
} 第三题：奇异长度(选做)
题目描述：
给你一个图，0节点连接这一个联通块a，1节点连接着一个联通块b,ab仅由01这条边相连。
现在我们定义奇异路径为恰好经过0-1这条边一次的路径，其他边可以经过任意次，且路径不带方向，1-2-3与3-2-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}$
输出
输出一行表示答案
样例
<pre>
<b>in:</b>
5 4 10
0 1
0 2
1 3
1 4
<b>out:</b>
3
</pre>
解析
这个题我一开始也不知道怎么做，后来请教了大神，才知道是图上Dp，图上Dp也是我第一次接触。
如果不用图上Dp的话很麻烦，首先，两个联通块有没有环你不知道，如果有环根本做不了，如果用图上Dp，这个点就不是问题了；
首先把0 - 1这条边砍掉，dp0[d][i]表示0号结点所在的联通块中，结点i到0结点距离为d有多少条路径，dp1[d][i]类似，由于只有0 - 1这条边把两个联通块联通，那么根据乘法原理，奇异长度为D的路径数就为$\sum_{d = 0}^{D}dp0[d][i] dp1[D - 1 - d][j] 2$，路径是双向的，所以乘2，那么dp0[d][i]怎么求呢？设与i直接相连的结点为j，那么$dp0[d][i] = \sum dp0[d - 1][j]$；
这里图可能有重边，因此我选择了领接表建图，用邻接矩阵也可以，各有各的好处吧；
注意这里dp0[d][i]，d这一维不知道该开多大，因此我用的是vector，需要多少创建多少空间，你也可以开一个比较大的空间，因为，答案增长地很快，d这一维不可能很大。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int find(vector<int> &p, int x)
{
return p[x] == -1 ? x : (p[x] = find(p, p[x]));
}
int main()
{
for (LL n, m, k; cin >> n >> m >> k; ) {
vector<int> mp[n];
vector<int> p(n, -1);
for (int i = 0, x, y; i < m; i++) {
cin >> x >> y;
if (x + y == 1)
continue;
mp[x].push_back(y), mp[y].push_back(x);
int fx = find(p, x), fy = find(p, y);
if (fx == fy)
continue;
if (fx == 0 || fx == 1)
p[fy] = fx;
else
p[fx] = fy;
}
vector<vector<LL> > dp0(1, vector<LL>(n, 0)), dp1(dp0);
dp0[0][0] = dp1[0][1] = 1;
LL pos = 1, d = 1;
for (; pos < k; ++d) {
dp0.push_back(vector<LL>(n, 0));
dp1.push_back(vector<LL>(n, 0));
for (int i = 2; i < n; i++) {
if (find(p, i) == 0) {
for (auto it = mp[i].begin(); it != mp[i].end(); ++it)
dp0[d][i] += dp0[d - 1][*it];
} else {
for (auto it = mp[i].begin(); it != mp[i].end(); ++it)
dp1[d][i] += dp1[d - 1][*it];
}
}
for (int dd = 0; dd <= d; dd++) {
for (int i = 0; i < n; i++) {
if (find(p, i) == 1)
continue;
for (int j = 0; j < n; j++) {
if (find(p, j) == 0)
continue;
pos += dp0[dd][i] * dp1[d - dd][j] * 2;
}
}
}
}
cout << d << endl;
}
return 0;
} 第四题：交易
题目描述：
沫璃发起了一场交易，她将她的5个朋友聚在一起准备进行一场交易。交易开始前，大家各有b$(b>0)$个硬币，交易后，每个人有$a_i$个硬币。由于硬币不方面携带，在交易过程中可能会丢失。现在沫璃想知道是否一定丢失硬币，或者在可能没有丢失硬币的情况下，交易前每个人的硬币数b。沫璃只是组织者，不参与交易。
输入
第一行一个数T$(T<=100)$，表示数据组数。
对于每组数据，第一行5个整数，第i个整数$a_i$表示交易后第i个朋友的硬币数 $(0<=a_i<=100)$
输出
对于每组数据，输出一行，若一定丢失硬币输出-1，若可能没有丢失硬币，输出b
样例
<pre>
<b>in:</b>
2
2 5 4 0 4
4 5 9 2 1
<b>out:</b>
3
-1
</pre>
解析
加起来看看是不是5的倍数就行了，注意5个输入全是0的情况就行了。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
for (int a[5]; T--; ) {
int sum = 0;
for (int i = 0; i < 5; cin >> a[i++]) {}
for (int i = 0; i < 5; sum += a[i++]) {}
cout << (sum && sum % 5 == 0 ? sum / 5 : -1) << endl;
}
return 0;
} 第五题：赛马
题目描述：
沫璃有2*n匹马，每匹马都有一个速度v。现在沫璃将马分成两个队伍，每个队伍各有n匹马，两个队之间进行n场比赛，每场比赛两队各派出一匹马参赛，每匹马都恰好出场一次。沫璃想知道是否存在一种分配队伍的方法使得无论怎么安排比赛，第一个队伍都一定能获得全胜。两匹马若速度不一样，那么速度快的获胜，若速度一样，则都有可能获胜。
输入
第一行一个数T$(T<=100)$，表示数据组数。
对于每组数据，第一行一个整数n, $(1<=n<=100)$
接下来一行，2*n个整数，第i个整数$v_i$表示第i匹马的速度, $(1 <= v_i <= 1000)$
输出
对于每组数据，输出一行，若存在一种分配方法使得第一个队伍全胜输出YES，否则输出NO
样例
<pre>
<b>in:</b>
2
2
1 2 3 4
1
1 1
<b>out:</b>
YES
NO
</pre>
解析
注意题中加粗的字体，无论怎么安排，要全胜，而且如果两匹马速度一样，胜负还不一定，因此，贪心，先排序一下，用数组的后半段和前半段去比，如果第n / 2 - 1和n / 2处的元素不一样，那么肯定可以。
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
for (int n; T--; ) {
cin >> n;
vector<int> arr;
for (int i = 0, x; i < n << 1; cin >> x, arr.push_back(x), ++i) {}
sort(arr.begin(), arr.end());
cout << (arr[n - 1] != arr[n] ? "YES" : "NO") << endl;
}
return 0;
} 第六题：玫瑰花(选答)
题目描述：
有K种不同的玫瑰花，现在要摆放在N个位置上，要求每种颜色的花至少出现过一次，请问有多少种不同的方案数呢？，因为答案可能很大，你只需要输出它对772235取余后的结果.
输入
输入只有1行，分别有两个整数N,K$( 1 <= N <= 50000 , 1 <= K <= 30 )$
输出
输出一行表示答案
样例
<pre>
<b>in:</b>
3 2
<b>out:</b>
6
</pre>
解析
组合做不了，会出现重复的组合，因此用动态规划做。
定义dp[i][j]为前i个位置用了j种颜色，那么状态转移方程为dp[i][j] = j * dp[i - 1][j] + (k - j + 1) * dp[i - 1][j - 1]，初始化dp[0][0] = 1。
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 772235;
int main()
{
for (int n, k; cin >> n >> k; ) {
vector<vector<int> > dp(n + 1, vector<int>(k + 1, 0));
dp[0][0] = 1;
for (int i = 1; i < n + 1; i++)
for (int j = 1; j < k + 1; j++)
dp[i][j] = (j * dp[i - 1][j] % mod + (k - j + 1) * dp[i - 1][j - 1] % mod) % mod;
cout << dp[n][k] << endl;
}
return 0;
}#春招##360公司##C/C++#
