笔试真题

刺骨的言语ヽ痛彻心扉 2021-09-20 10:46 422阅读 0赞

**网易实习生**

![1074344-20180329115033123-838466640.png][]

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

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;
        }
    }

**网易游戏**

![1074344-20180401212514689-2116069753.png][]

![1074344-20180401212521308-1290539182.png][]

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

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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**

**![1074344-20180403204750518-295868992.png][]**

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

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;
        }
    }

转载于:https://www.cnblogs.com/hqxue/p/8668943.html

[1074344-20180329115033123-838466640.png]: /images/20210726/ab1208ba5b284aa6882ea4c682438590.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210726/808775fa956a4cfaa662b8b29a3016fe.png
[1074344-20180401212514689-2116069753.png]: /images/20210726/a581c8ebd0f840f188304ea4cf9fb56b.png
[1074344-20180401212521308-1290539182.png]: /images/20210726/7b4b5f5d880c421db8a7fd8da1e7faf0.png
[1074344-20180403204750518-295868992.png]: /images/20210726/1d4e1014165e444f994e8cb50ecdc7e7.png