京东秋招 2023.08.19 编程题目与题解

发表于 2023-08-19 更新于 2023-10-14 分类于笔试阅读次数： 343 本文字数： 2.2k 阅读时长 ≈ 2 分钟

1、小红的夹吃棋

在一个 3*3 的棋盘上，小红和小紫正在玩 “夹吃棋”。所谓 “夹吃棋”，即如果存在一个白子，它的两侧（横向或者纵向）相邻都是黑子，则这个棋子将被 “夹吃”；对于黑棋亦然。如果一个棋盘的局面没有一方被夹吃，或者黑白双方都被对面夹吃，则认为是平局。如果只有一方夹吃了另一方，则认为夹吃方赢，被夹吃方输。

小红执黑棋，小紫执白棋，现在给定一个局面，请你判断当前棋局是谁获胜。

输入

第一行输入一个正整数 $t$ ，代表询问的次数。

接下来每组询问输入三行，每行是一个长度为 3 的字符串，字符串仅由'o'、'*'、'.' 组成。其中'o' 代表白棋，'*' 代表黑棋，'.' 代表未放置棋子。

输出

对于每个棋局，输出一行字符串表示答案，小红获胜输出 "kou"，小紫获胜输出 "yukari"，平局输出 "draw"。

样例

输入：
3
...
o*o
...
o**
ooo
..*
o*o
*o*
o*o

输出：
yukari
kou
draw

解答

枚举盘面上每个棋子'o'，判断它的上方和下方或者是左边和右边是否同时有'*' 即可，此时对应了其中一种情况 $c_{0}$ 。

对于另一种情况，将棋盘上的所有棋子全部 “取反”，再沿用上面的判断方式，就可以得到另一种情况 $c_{1}$ 。

只需要综合考虑 $c_{0}$ 和 $c_{1}$ 的值即可。

代码

# include <bits/stdc++.h>
using namespace std;

char s[6][6];
void trans(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++){
            if(s[i][j]=='o') s[i][j]='*';
            else if(s[i][j]=='*') s[i][j]='o';
        }
}
int check(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            if(s[i][j]=='o'&&
               (s[i][j-1]=='*'&&s[i][j+1]=='*'||
               s[i-1][j]=='*'&&s[i+1][j]=='*')) return 1;
    return 0;
}
void solve(){
    for(int i=1;i<=3;i++)
        scanf("%s",s[i]+1);
    int c0=check();
    trans();
    int c1=check();
    if(c0==0&&c1==1) puts("yukari");
    else if(c0==1&&c1==0) puts("kou");
    else puts("draw");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
}

2、小红吃药

小红准备买药治病。已知共有 n 种症状和 m 种药，第 i 种药可以治疗一些症状，但可能会导致一些副作用，添加一些新的症状。小红依次服用了一些药，请你告诉小红，当她每次服用一副药时，当前还有多少症状？

输入

第一行输入一个正整数 $n$ ，代表症状的数量。

第二行输入一个长度为 $n$ 的 01 串，第 $i$ 位是 '1' 代表小红目前有第 $i$ 个症状，第 $i$ 位是 '0' 代表没有该症状。

第三行输入一个正整数 $m$ ，代表药的数量。

接下来的 $2 * m$ 行，每 $2$ 行描述一副药：

第一行输入一个长度为 $n$ 的 01 串，代表该药能治疗的症状。'1' 代表可以治疗，'0' 代表不能治疗。

第二行输入一个长度为 $n$ 的 01 串，代表该药会产生的副作用。'1' 代表会产生该症状，'0' 代表不会产生。

接下来的一行，输入一个正整数 $q$ ，代表小红服用的药数量。

接下来的 $q$ 行，每行输入一个正整数 $u$ ，代表小红服用了第 $u$ 副药。

$1 \leq n \leq 20$
$1 \leq m, q \leq 10^{4}$
$1 \leq a_{i}, u \leq m$

保证每副药副作用产生的症状和该药治疗的症状是不会重复的，即不会存在同一个位置的两个 01 串都是 '1'。

输出

输出 $q$ 行，每行输入一个正整数，代表当前小红服用药后，身体有多少症状。

样例

输入：
4
0101
3
1100
0010
0101
1000
1001
0000
3
2
3
1

输出：
1
0
1

提示：
最开始小红有第二个、第四个症状。
开始小红服用了第二副药，治好了这两个症状，但新增了第一个症状。目前症状数量为1。
然后小红服用了第三副药，治好了第一个症状，并没有新增症状。目前症状数量为0。
最后小红服用了第一副药。由于小红没有症状，所以没有治疗，但又新增了第三个症状，目前症状数量为1。

解答

本题考查的是位运算。

将每种症状视为一个比特，那么每种药的治疗效果和副作用都可以处理成一个 $n$ 比特数，其中治疗效果是 $m_{1} [i]$ ，副作用是 $m_{2} [i]$ 。

对于当前的某个患病状态 $s t$ ，如果第 $i$ 种药能治疗第 $j$ 种疾病，那么就是将 $s t$ 的第 $j$ 位设置为 $0$ ，对应在位运算中，这种操作是 st &= ((1 << n) - 1) ^ m1[i]，即将 $m_{1} [i]$ 中的所有比特先取反，然后再求与。如果这种药的副作用添加了第 $j$ 个症状，那么就是将 $s t$ 的第 $j$ 位设置为 $1$ ，对应在位运算中，这种操作是 st |= m2[i]，即直接求或即可。

最终直接暴力求出 $s t$ 中有多少个 $1$ 比特即可，这里使用了__builtin_popcount 直接求出 $1$ 比特数。

代码

# include <bits/stdc++.h>
using namespace std;

const int N=10004;
int m1[N],m2[N],n,q,m;
int parse(string &s){
    int x=0;
    for(int i=0;i<n;i++)
        x|=int(s[i]-'0')<<i;
    return x;
}
int main(){
    string s,t;
    cin>>n>>s>>m;
    int st=parse(s);
    for(int i=1;i<=m;i++){
        cin>>s>>t;
        m1[i]=parse(s);
        m2[i]=parse(t);
    }
    cin>>q;
    int id;
    while(q--){
        cin>>id;
        st &= ((1<<n)-1)^m1[id];
        st |= m2[id];
        cout<<__builtin_popcount(st)<<"\n";
    }
}

3、小红的皇后

有一个 $n$ 行 $m$ 列的棋盘，有一些格子是障碍物不能通过。小红控制一个皇后在从左上角出发，每次移动她可以控制皇后进行以下三种方式中的一种：

向右移动若干个格子。
向下移动若干个格子。
向右下移动若干个格子。

用数学语言描述，当前的坐标在 $(x, y)$ 时，每次移动可以到 $(x + k, y)$ 或 $(x, y + k)$ 或 $(x + k, y + k)$ ，其中 $k$ 为任意正整数。移动的前提是，路径上没有障碍物。小红想知道，皇后从左上角移动到右下角，最少要移动多少步？

输入

第一行输入两个正整数 $n$ 和 $m$ ，代表行数和列数。

接下来的 $n$ 行，每行输入一个长度 $m$ 的字符串，用来表示棋盘。

其中 '.' 代表可以通过的位置，'*' 代表障碍物。

保证左上角和右下角都不是障碍物。

$1 \leq n, m \leq 2000$

输出

如果无法到达，请输出 - 1。

否则输出一个整数，代表最少的移动次数。

样例

输入：
3 3
...
.**
.*.

输出：
-1

输入：
3 4
....
**.*
....

输出：
2

解答

本质上，这是求出一条行走路径，其中方向的 “变化” 次数最少。

因此，比起普通的迷宫 BFS 问题，我们再添加一个维度 $d i r$ ，用于表示走到某个格子时皇后所面对的方向。

更具体的，用 $d (x, y, k)$ 来表示从起点开始，走到格子 $(x, y)$ ，面朝方向 $k$ 时，路径方向的最小 “变化” 次数。其中 $k \in {0, 1, 2}$ ，分别表示 $3$ 个方向。

如果走到下一个格子时，方向和原来的一致，那么走到新格子时不需要再添加代价，否则需要添加代价 $1$ 。

因此这转化成了一个 0-1BFS 问题。在实现时，边的权值仅仅是 $0$ 和 $1$ ，可以使用双端队列 deque 来存储每个节点，以保持队列中的节点的距离值是非递减的。

因此最终答案为 ${min}_{k = 0}^{2} {d (n, m, k)} + 1$ 。

需要注意的是，如果 $n = m = 1$ ，那么不需要步数，输出 $0$ 。

代码

# include <bits/stdc++.h>
using namespace std;

const int N=2004;
char s[N][N];
int d[N][N][3];
int n,m;
struct P{
    int x,y,dir,dis;
};
int dx[3]={1,1,0},dy[3]={1,0,1};
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    memset(d,0x3f,sizeof(d));
    int inf=0x3f3f3f3f;
    deque<P>q;
    for(int d=0;d<3;d++){
        q.push_back(P{1,1,d,0});
    }
    while(!q.empty()){
        P u=q.front();q.pop_front();
        if(d[u.x][u.y][u.dir]!=inf) continue;
        d[u.x][u.y][u.dir]=u.dis;
        for(int k=0;k<3;k++){
            int x=u.x+dx[k],y=u.y+dy[k];
            if(x>n||y>m||d[x][y][k]!=inf||s[x][y]=='*') continue;
            if(k==u.dir) q.push_front(P{x,y,k,u.dis});
            else q.push_back(P{x,y,k,u.dis+1});
        }
    }
    int ans=min(min(d[n][m][0],d[n][m][1]),d[n][m][2]);
    if(ans==inf) ans=-1;
    else ++ans;
    if(n==1&&m==1) ans=0;
    printf("%d\n",ans);
}