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

#京东信息集散地#
全部评论
第三题用动态规划也可以
1 回复 分享
发布于 2023-08-19 13:22 广东
第三题不知道为什么超内存了,搁那里想了一小时,换成手动模拟队列又说我段错误
点赞 回复 分享
发布于 2023-08-19 12:04 广东
__builtin_popcount这个你平时都会背下来?
点赞 回复 分享
发布于 2023-08-19 12:31 湖北
为什么 o*o *o* o*o是平局呢
点赞 回复 分享
发布于 2023-08-19 12:36 浙江
大佬,如果用 visit[]数组记录入过队列的点,我认为作用相当于 dist[i][y] < dist[x][y] + 1,为什么还是 TLE? 大佬请问怎么得到的时间复杂度 O(n^3)?每个点入队一次,不是 O(n^2)吗?
点赞 回复 分享
发布于 2023-08-19 12:49 北京
伊泽,%%%
点赞 回复 分享
发布于 2023-08-19 13:42 安徽

相关推荐

努力成为C语言高手:质疑大祥老师,理解大祥老师,成为大祥老师
点赞 评论 收藏
分享
Java抽象带篮子:难蚌,点进图片上面就是我的大头😆
点赞 评论 收藏
分享
12 21 评论
分享
牛客网
牛客企业服务