笔试真题 刺骨的言语ヽ痛彻心扉 2021-09-20 10:46 354阅读 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
还没有评论,来说两句吧...