8.12网易互娱 Ac代码 + 题目描述

网易互娱游戏研发工程师笔试题

第二次发帖，也是网易第二次笔试，依然是4道做出来3道。哎，其实不是自己实力涨了，是网易笔试考察的主要是编程基本功，这次笔试就感觉没有深入考察算法，就是给一个游戏场景，写一个小任务。

再接再厉，秋招不易，算法得练！

第4题的大神，可以分享下题目和代码，谢谢啦！

七星不靠

147 | 258 | 369

万 | 饼 | 条

上述9张数字牌，配合（万 | 饼 | 条），从中随便丢掉2张，剩下的牌，是可以胡牌的。

现在，输入N个7张牌，判断能不能胡牌。

#include <bits/stdc++.h>
using namespace std;
bool check(int i, unordered_map<int, char> &num2tp)
{
    char tt = 'A';
    for (int i = 1; i < 10; i += 3)
    {
        if (num2tp.find(i) != num2tp.end())
        {
            if (tt == 'A')
                tt = num2tp[i];
            else
            {
                if (tt != num2tp[i])
                {
                    printf("NO\n");
                    return false;
                }
            }
        }
    }
    return true;
}
int main(int argc, char const *argv[])
{
    int t;
    cin >> t;
    int num;
    char tp;
    while (t--)
    {
        unordered_map<int, char> num2tp;
        unordered_set<char> allTypeOk;
        bool ok = true;
        for (int i = 0; i < 7; ++i)
        {
            scanf("%d%c", &num, &tp);
            allTypeOk.insert(tp);
            if (num2tp.find(num) != num2tp.end())
                ok = false;
            else
                num2tp[num] = tp;
        }
        if (!ok || allTypeOk.size() != 3)
            printf("NO\n");
        else
        {
            bool ok = check(1, num2tp);
            if (!ok)
                continue;
            ok = check(2, num2tp);
            if (!ok)
                continue;
            ok = check(3, num2tp);
            if (!ok)
                continue;
            printf("YES\n");
        }
    }
    return 0;
}

2. 行列最大和删除

给你一个N*N的矩阵，每次删除（行列和）最大的一行、一列，直到删完。求，每一步删除的行i和列j。请注意，行列交点处的数字，求和只算一次。

#include <bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>> &nums, vector<int> &colSum, vector<int> &rowSum)
{
    if (nums.size() == 0)
        return;
    if (nums.size() == 1)
    {
        printf("1 1\n");
        return;
    }
    int maxI = 0, maxJ = 0, maxSum = -1;
    for (int i = 0; i < rowSum.size(); ++i)
    {
        for (int j = 0; j < colSum.size(); ++j)
        {
            if (rowSum[i] + colSum[j] - nums[i][j] > maxSum)
            {
                maxSum = rowSum[i] + colSum[j] - nums[i][j];
                maxI = i, maxJ = j;
            }
        }
    }
    printf("%d %d\n", maxI + 1, maxJ + 1);
    // delete row
    for (int j = 0; j < colSum.size(); ++j)
    {
        colSum[j] -= nums[maxI][j];
    }
    nums.erase(nums.begin() + maxI);
    rowSum.erase(rowSum.begin() + maxI);
    // delete col
    for (int i = 0; i < rowSum.size(); ++i)
    {
        rowSum[i] -= nums[i][maxJ];
    }
    colSum.erase(colSum.begin() + maxJ);
    for (int i = 0; i < nums.size(); ++i)
    {
        nums[i].erase(nums[i].begin() + maxJ);
    }
    dfs(nums, colSum, rowSum);
}
int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    vector<vector<int>> nums(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            scanf("%d", &nums[i][j]);
    }
    vector<int> colSum(n, 0);
    vector<int> rowSum(n, 0);
    for (int j = 0; j < n; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            colSum[j] += nums[i][j];
            rowSum[i] += nums[i][j];
        }
    }
    dfs(nums, colSum, rowSum);
    return 0;
}

3. 明日之后找出自身耗费时间最长的活动

明日之后里面，天天要造东西，需要花费时间，现在给你一系列活动的开始时刻、id和结束时刻，子活动在数据中保证比父活动先结束，数据肯定合法。

比如，想要造一个柜子，需要3块木板，木板有需要伐木，和找树枝，大概这个样子，理解下父与子。

说白了，用括号表示就是，((())) 和 ((()()())())，所以要用栈啊。

#include <bits/stdc++.h>
using namespace std;
stack<pair<long long, long long>> st;
int main(int argc, char const *argv[])
{
    long long T;
    cin >> T;
    while (T--)
    {
        long long n;
        cin >> n;
        long long t, e, s;
        long long id = -1, maxTime = -1;
        bool preIsEnd = false;
        for (long long i = 0; i < n; ++i)
        {
            scanf("%lld %lld %lld", &t, &e, &s);
            if (!s)
            {
                st.push(make_pair(t, 0));
                preIsEnd = false;
            }
            else
            {
                pair<long long, long long> &item = st.top();
                long long allTime = t - item.first;
                long long selfTime = allTime - item.second;
                if (selfTime > maxTime || selfTime == maxTime && id > e)
                {
                    id = e;
                    maxTime = selfTime;
                }
                st.pop();
                if (!st.empty())
                {
                    if (preIsEnd)
                        st.top().second += allTime;
                    else
                        st.top().second += selfTime;
                }
                preIsEnd = true;
            }
        }
        printf("%lld\n", id);
        while (!st.empty())
            st.pop();
    }
    return 0;
}

#笔试题目##网易互娱#