2023.8.19 京东第二场笔试题解
今天的题目比较简单,半个小时多点就成功AK了~下面讲下大概思路:
第一题:
第一题是个名副其实的模拟题,直接模拟即可,注意别被输入输出卡了。
第二题:
抽象一下题目模型就是给定一个用户初始状态(长度为20的字符串),有m种药可以对用户提供buff和debuff,给定一个用户嗑药的次序,输出每次嗑药之后的用户状态。观察一下数据范围,n只有20,并且又和01串有关,很容易想到考察点是位运算。这样一来,问题就变成了用一个int类型数字表示用户状态,每次嗑药的操作等价于位运算操作,最后输出1的个数即可。细节:用户施加buff等价于a|b,用户移除debuff等价于a^(a&b) 。这两种转换可以体会一下~ 下面给出代码:
const int N = 10010; int n,m,q; string s; string t; int state; PII nums[N]; void solve() { cin >> n; cin >> s; state = stoi(s,nullptr,2); cin >> m; for(int i=1;i<=m;++i){ string s1,s2; cin >> s1; cin >> s2; nums[i].first = stoi(s1,nullptr,2); nums[i].second = stoi(s2,nullptr,2); } cin >> q; for(int i=1;i<=q;++i){ int x; cin >> x; // 把对应的症状消除 同时加上新的症状 // 先与上 对应上1的位置就是兼容的位置 然后拿原内容异或一下1 // | nums[i].second int cur = state & nums[x].first; state = state ^ cur; state = state | nums[x].second; int ans = __builtin_popcount(state); cout << ans << endl; } }
第三题:
第三题乍一看就是个裸的最短路嘛~确实,然后兴冲冲写一个bfs一交,tle了!分析一下思路的瓶颈,由于每次转移都需要枚举右侧或者下侧或者右下的位置时,最坏的复杂度是$O(n^3)$.那么如何优化一下呢?这里其实就是在bfs过程中,枚举下一个移动位置时,如果出现dist[nx][ny]<dist[x][y]+1的情况,我们就提前结束搜寻下一个节点的遍历,这就相当于我们不会再做无意义的延申操作,总是把可能作为最短路径上的点加入队列并且扩展。下面给出代码:
#include <bits/stdc++.h> #include <numeric> #define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define PII pair<int, int> #define ll long long #define x first #define y second #define mod 998244353 using namespace std; const int N = 2010; char g[N][N]; int dist[N][N]; int n,m; void solve() { cin >> n >> m; for(int i=1;i<=n;++i){ cin >> g[i] + 1; } memset(dist,0x3f,sizeof dist); queue<PII> q; dist[1][1] = 0; q.push({1,1}); while(q.size()){ auto u = q.front(); q.pop(); int x = u.first,y = u.second; if(x == n && y == m){ cout << dist[x][y] << endl; return; } for(int j=y+1;j<=m;++j){ if(g[x][j] == '*' || dist[x][j] < dist[x][y] + 1){ break; } if(dist[x][j] > dist[x][y] + 1){ dist[x][j] = dist[x][y] + 1; q.push({x,j}); } } for(int i=x+1;i<=n;++i){ if(g[i][y] == '*' || dist[i][y] < dist[x][y] + 1){ break; } if(dist[i][y] > dist[x][y] + 1){ dist[i][y] = dist[x][y] + 1; q.push({i,y}); } } for(int d=1;x+d<=n&&y+d<=m;++d){ int nx = x + d,ny = y + d; if(g[nx][ny] == '*' || dist[nx][ny] < dist[x][y] + 1){ break; } if(dist[nx][ny] > dist[x][y] + 1){ dist[nx][ny] = dist[x][y] + 1; q.push({nx,ny}); } } } cout << -1 << endl; } int main() { IOS; int _ = 1; while (_--) { solve(); } return 0; }#京东信息集散地#