笔试真题-蒲公英云

笔试真题

网易实习生

题解：超大容量背包问题。因为背包容量过大，不能用背包解法。而物品个数最多只有三十个，但是所有状态也高达2^30，所以将所有物品折半dfs

代码：

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
void dfs(vector<int>& v, int r, int id, long long tmp, vector<long long>& num, int& w) {
    if (tmp > w) return;
    if (id > r) {
        num.push_back(tmp);
        return;
    }
    dfs(v, r, id+1, tmp, num, w);
    dfs(v, r, id+1, tmp+v[id], num, w);
}
int main() {
    int n, w;
    while (cin>>n>>w) {
        vector<int> v(n);
        for (int i = 0; i < n; i++) cin>>v[i];
        vector<long long> num1, num2;
        dfs(v, n/2, 0, 0, num1, w);
        dfs(v, n-1, n/2+1, 0, num2, w);
        sort(num1.begin(), num1.end());
        sort(num2.begin(), num2.end());
        long long ans = 0, j = num2.size()-1;
        for (int i = 0; i < num1.size(); i++)
            while (j >= 0) {
                if (num1[i]+num2[j] <= w) {
                    ans += j+1;
                    break;
                }
                j--;
            }
        cout<<ans<<endl;
    }
}

网易游戏

题解：bfs，但是需要四维，分别记录人的位置和箱子的位置

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<string>
#include<iostream>
#include<queue>
#include<cstdlib>
using namespace std;
const int dir[4][2] = {
     {-1, 0}, {
     1, 0}, {
     0, -1}, {
     0, 1}};
int main() {
    int n, m, x, y, aimx, aimy, bx, by;
    int v[10][10][10][10];
    while (cin>>n>>m) {
        vector<vector<char> > mapp(n, vector<char>(m));
        memset(v, -1, sizeof(v));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                cin>>mapp[i][j];
                if (mapp[i][j] == 'X') x = i, y = j;
                if (mapp[i][j] == '*') bx = i, by = j;
                if (mapp[i][j] == '@') aimx = i, aimy = j;
            }
        queue<vector<int> > q;
        q.push({x, y, bx, by});
        v[x][y][bx][by] = 0;
        bool flag = 1;
        while (!q.empty() && flag) {
            vector<int> tmp = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int xx = tmp[0]+dir[i][0], yy = tmp[1]+dir[i][1];
                int xxx = xx+dir[i][0], yyy = yy+dir[i][1];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && mapp[xx][yy] != '#' && (xx != tmp[2] || yy != tmp[3]) && v[xx][yy][tmp[2]][tmp[3]] == -1) {
                    v[xx][yy][tmp[2]][tmp[3]] = v[tmp[0]][tmp[1]][tmp[2]][tmp[3]]+1;
                    q.push({xx, yy, tmp[2], tmp[3]});
                } else if (xx == tmp[2] && yy == tmp[3] && xxx >= 0 && xxx < n && yyy >= 0 && yyy < m && mapp[xxx][yyy] != '#' && v[xx][yy][xxx][yyy] == -1) {
                    v[xx][yy][xxx][yyy] = v[tmp[0]][tmp[1]][tmp[2]][tmp[3]]+1;
                    if (xxx == aimx && yyy == aimy) {
                        cout<<v[xx][yy][xxx][yyy]<<endl;
                        flag = 0;
                        break;
                    }
                    q.push({xx, yy, xxx, yyy});
                }
            }
        }
        if (flag) cout<<"-1"<<endl;
    }
}

360

题解：容斥原理，C(k, 0)*k^n-C(k, 1)*(k-1)^n+C(k, 2)*(k-2)^n-……

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<string>
#include<iostream>
#include<queue>
#include<cstdlib>
using namespace std;
const long long mod = 772235;
long long quick_mod(long long a,long long b,long long m)
{
    long long ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a)%m;
            b--;
        }
        b=b>>1;
        a=a*a%m;
    }
    return ans;
}
long long C(int k, int i) {
    long long ans = 1;
    for (int j = 0; j < i; j++) {
        ans = ans*(k-j)/(j+1);
    }
    return ans;
}
int main() {
    long long n, k;
    while (cin>>n>>k) {
        if (n < k) {
            cout<<"0"<<endl;
            continue;
        }
        long long ans = 0;//quick_mod(k, n, mod);
        long long flag = 1;
        for (int i = 0; i <= k; i++) {
            ans = (ans+flag*C(k, i)*quick_mod(k-i, n, mod))%mod;
            flag *= -1;
        }
        if (ans < 0) ans += mod;
        cout<<ans<<endl;
    }
}