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

#京东信息集散地#