360公司2018春季招聘编程题 - 题解

个人题解，不一定全部通过，各位多指正，360的选做题都是动态规划。

第一题：画板

题目描述：

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

输入

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

输出

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

样例

in:
2
2
1 1 2 3
2 2 3 3
2
1 1 3 3
1 1 3 3

out:
10
18

解析

这题有了题中加粗的部分就很好解决了，只需要看下这个矩形中有多少个像素点就行了。

代码

#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)$(T<=100)$，表示数据组数。
对于每组数据，第一行3个整数r，g，b，分别表示三种颜色的气球个数(0<=r,g,b<=2∗109)$(0<=r,g,b<=2\ast {10}^9)$

输出

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

样例

in:
2
5 4 3
2 3 3

out:
4
2

解析

思维题，这是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<240$5<=n<=100,k<2^{40}$

输出

输出一行表示答案

样例

in:
5 4 10
0 1
0 2
1 3
1 4

out:
3

解析

这个题我一开始也不知道怎么做，后来请教了大神，才知道是图上Dp，图上Dp也是我第一次接触。

如果不用图上Dp的话很麻烦，首先，两个联通块有没有环你不知道，如果有环根本做不了，如果用图上Dp，这个点就不是问题了；

首先把0 - 1这条边砍掉，dp0[d][i]表示0号结点所在的联通块中，结点i到0结点距离为d有多少条路径，dp1[d][i]类似，由于只有0 - 1这条边把两个联通块联通，那么根据乘法原理，奇异长度为D的路径数就为∑Dd=0dp0[d][i]∗dp1[D−1−d][j]∗2$\sum _{d=0}^{D}dp0[d][i]\ast dp1[D-1-d][j]\ast 2$，路径是双向的，所以乘2，那么dp0[d][i]怎么求呢？设与i直接相连的结点为j，那么dp0[d][i]=∑dp0[d−1][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)$(b>0)$个硬币，交易后，每个人有ai$a_i$个硬币。由于硬币不方面携带，在交易过程中可能会丢失。现在沫璃想知道是否一定丢失硬币，或者在可能没有丢失硬币的情况下，交易前每个人的硬币数b。沫璃只是组织者，不参与交易。

输入

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

输出

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

样例

in:
2
2 5 4 0 4
4 5 9 2 1

out:
3
-1

解析

加起来看看是不是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)$(T<=100)$，表示数据组数。
对于每组数据，第一行一个整数n , (1<=n<=100)$(1<=n<=100)$
接下来一行，2*n个整数，第i个整数vi$v_i$表示第i匹马的速度, (1<=vi<=1000)$(1<=v_i<=1000)$

输出

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

样例

in:
2
2
1 2 3 4
1
1 1

out:
YES
NO

解析

注意题中加粗的字体，无论怎么安排，要全胜，而且如果两匹马速度一样，胜负还不一定，因此，贪心，先排序一下，用数组的后半段和前半段去比，如果第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 / 2 - 1] != arr[n / 2] ? "YES" : "NO") << endl;
    }
    return 0;
}

第六题：玫瑰花(选答)

题目描述：

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

输入

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

输出

输出一行表示答案

样例

in:
3 2

out:
6

解析

组合做不了，会出现重复的组合，因此用动态规划做。

定义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;
}