【Nowcoder Girl 2017】全通过的C++代码

首先祝大家双旦快乐！！！
【Nowcoder Girl 2017题目集合】题目链接：https://www.nowcoder.com/test/8527168/summary

本套6道题全PASS的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

查看了排行榜，第一个全PASS，先将所有的C++代码发布上来。
1.勇气获得机
【题解】用while实现一个递归。

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int n; cin >> n;
    string result = "";
    while (n != 0) {
        result = (n % 2 ? "N" : "G") + result;
        n = (n - 1) / 2;
    }
    cout << result;
    return 0;
}

2.排列
【题解】如果有一个pi=i或一对pi=i并且pi+1=i+1，则需要一次交换。

#include <iostream>
using namespace std;
int main()
{
    int n; cin >> n;
    int equal = 0, count = 0, data;
    while (count < n) {
        cin >> data;
        if (data == ++count) {
            if (count != n) cin >> data;
            count++; equal++;
        }
    }
    cout << equal;
    return 0;
}

3.打车
【题解】最多只有10个硬币，简单遍历一下就可以啦。

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n, s; cin >> n >> s;
    int data[10] = { 0 };
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    int result = 0;
    for (int i = 0; i < pow(2, n); i++) {
        int mincoin = 10000, sum = 0, sumcoin = 0;
        int temp = i;
        for (int j = 0; j < n; j++) {
            if (temp % 2) {
                sum += data[j];
                mincoin = mincoin < data[j] ? mincoin : data[j];
                sumcoin++;
            }
            temp >>= 1;
        }
        result = sum >= s && sum - mincoin < s ? result>sumcoin ? result : sumcoin : result;
    }
    cout << result;
    return 0;
}

4.勇敢的妞妞
【题解】没有想到好办法，m大于等于5时取各个属性的最大值，m小于等于3时遍历，m等于4时为防止超时，用一点小小的技巧即可通过。

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n, m; cin >> n >> m;
    int **r = new int*[n], result = 0;
    int maxr[5] = { 0 };
    for (int i = 0; i < n; i++) {
        r[i] = new int[5];
        for (int j = 0; j < 5; j++) {
            cin >> r[i][j];
            maxr[j] = max(maxr[j], r[i][j]);
        }
    }
    if (m == 1) {
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int k = 0; k < 5; k++) {
                temp += r[i][k];
            }
            result = max(result, temp);
        }
    }
    else if (m == 2) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = 0;
                for (int k = 0; k < 5; k++) {
                    temp += max(r[i][k], r[j][k]);
                }
                result = max(result, temp);
            }
        }
    }
    else if (m == 3) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = 0; p < n; p++) {
                    int temp = 0;
                    for (int k = 0; k < 5; k++) {
                        temp += max(max(r[i][k], r[j][k]), r[p][k]);
                    }
                    result = max(result, temp);
                }
            }
        }
    }
    else if (m == 4) {
        int maxtemp[5][5] = { 0 };
        for (int p = 0; p < 5; p++) {
            for (int q = p + 1; q < 5; q++) {
                int temp = 0;
                for (int i = 0; i < n; i++) {
                    temp = max(temp, r[i][p] + r[i][q]);
                }
                for (int k = 0; k < 5; k++) {
                    if (k != p && k != q) {
                        temp += maxr[k];
                    }
                }
                result = max(result, temp);
            }
        }
    }
    else {
        for (int k = 0; k < 5; k++) {
            result += maxr[k];
        }
    }
    cout << result;
    return 0;
}

5.平方数
【题解】简单处理：(int)sqrt(N)*(int)sqrt(N)。

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int n; cin >> n;
    cout << (int)sqrt(n)*(int)sqrt(n) << endl;
    return 0;
}

6.美丽的项链
首先为了方便，在输入的时候，将 [li,ri] 的区间缩小为 [0,ri-li] 。
使用动态规划，DP[i][j]为用前i+1种珠宝制作数量为j的项链的方案数量。
DP[i][j+k]=DP[i-1][j]，其中k属于 [0,ri-li]。

【Nowcoder Girl 2017】全通过的C++代码

全站热榜

创作者周榜