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++#