网易C++后台开发笔试编程题

第一题

给你n个数，m次询问。每次询问x出现了多少次。数据范围好像是1e5；

思路：

可以之间用unordered_map来存一下，当然你也可以自己写哈希；

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define MAX_N 100010

int main() {
    #ifdef DEBUG
    freopen("data.txt", "r", stdin);
    #endif // DEBUG
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    unordered_map<int, int> F;
    for(int i = 0, tmp; i < n; i++)
    {
        cin >> tmp;
        F[tmp]++;
    }
    while(m--)
    {
        int tmp;
        cin >> tmp;
        cout << F[tmp] << endl;
    }

    return 0;
}

第二题

说一个人，有个无限容量的包（初始有m个积木），有n堆积木，第i堆有a[i]个，每次可以进行拿走一个放上去一个或者啥都不干操作；

问能不能使得最后严格单调递增。数据范围好像是1e5

思路：

考虑最蠢的办法，直接保证第一堆积木有0个，第二堆有1个，以此类推

然后求一下所有积木 + m 是否 >= (0 + n - 1) * n / 2，如果这都凑不够那铁定凉凉；

如果可以够，还要考虑如果后面的积木特别多，前面背包里的积木不够补的情况；

在线维护一下就行了

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define MAX_N 100010

int a[MAX_N];

int main() {
    #ifdef DEBUG
    freopen("data.txt", "r", stdin);
    #endif // DEBUG
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while(t--)
    {
        ll sum = 0, n, m;
        cin >> n >> m;
        for(ll i = 0; i < n; i++)
        {
            cin >> a[i];
            sum += a[i];
        }
        sum += m;
        if(sum < (n - 1) * n / 2)
        {
            cout << "NO" << endl;
            continue;
        }
        int flag = 1;
        for(int i = 0; i < n; i++)
        {
            if(i == 0)
            {
                m += a[i];
            }
            else
            {
                if(a[i] > i)
                {
                    m += a[i] - i;
                }
                else
                {
                    if(m < i - a[i])
                    {
                        flag = 0;
                        break;
                    }
                    else
                    {
                        m -= i - a[i];
                    }
                }
            }
        }
        if(flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

第三题

给你一个数组，要满足第i项大于等于前i-1项的和。问你满足这样的最长连续子序列的长度

考虑可以先用前缀和预处理一下，然后在线维护一下即可；

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define MAX_N 100010

ll a[MAX_N], sum[MAX_N];

int main() {
    #ifdef DEBUG
    freopen("data.txt", "r", stdin);
    #endif // DEBUG
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while(t--)
    {
        memset(sum, 0, sizeof(sum));
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
            sum[i] += sum[i - 1] + a[i];
        }
        ll Max = 0, tmp_Max = 0, pre = 0;
        for(int i = 1; i <= n; i++)
        {
            if(a[i] >= sum[i - 1] - pre)
                tmp_Max++;
            else
            {
                Max = max(Max, tmp_Max);
                tmp_Max = 1;
                pre = sum[i - 1];
            }
        }
        cout << Max << endl;
    }

    return 0;
}

第四题

给你一个数组和一个目标值。可以对数组中的元素进行加或者减操作，代价就是差值。现在要求操作后所有的数组元素乘机为目标值

问最小代价 n <= 1000

这道题我不会，考虑了唯一分解，但还是有很多情况，求大佬说一下正解，不过暴力骗分骗到了90%，还有10%的应该是初始情况所有的乘积 < 目标值

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define MAX_N 100010

int a[MAX_N];

int main() {
    #ifdef DEBUG
    freopen("data.txt", "r", stdin);
    #endif // DEBUG
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, key;
    cin >> n >> key;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n, [](int tmp_a, int tmp_b) {return tmp_a > tmp_b;});
    int tmp_val = 1, flag = 0;
    for(int i = 0; i < n; i++)
    {
        tmp_val *= a[i];
        if(tmp_val > key)
        {
            flag = 1;
            break;
        }
    }
    if(flag)
    {
        int p = 1;
        vector<int> val;
        for(int i = 0; i < n; i++)
        {
            if(key % a[i] == 0)
            {
                key /= a[i];
                p *= a[i];
            }
            else
            {
                val.push_back(a[i]);
            }
        }
        if(key == 1)
        {
            int sum = 0;
            for(int i = 0; i < val.size(); i++)
                sum += val[i] - 1;
            cout << sum << endl;
        }
        else
        {
            sort(val.begin(), val.end());
            int pos = lower_bound(val.begin(), val.end(), key) - val.begin();
            if(pos == 0)
            {
                int sum = abs(key - a[0]);
                for(int i = 1; i < val.size(); i++)
                    sum += val[i] - 1;
                cout << sum << endl;
            }
            else
            {
                if(abs(key - val[pos]) < abs(val[pos - 1]))
                {
                    int sum = abs(key - val[pos]);
                    for(int i = 0; i < val.size(); i++)
                    {
                        if(i != pos)
                            sum += val[i] - 1;
                    }
                    cout << sum << endl;
                }
                else
                {
                    int sum = abs(key - val[pos - 1]);
                    for(int i = 0; i < val.size(); i++)
                    {
                        if(i != pos - 1)
                            sum += val[i] - 1;
                    }
                    cout << sum << endl;
                }
            }
        }
    }
    else
    {
        cout << rand() % 100 + 1 << endl;
    }

    return 0;
}

#笔试题目##校招##网易##C/C++#