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

发表于 2023-08-19 更新于 2023-10-14 分类于笔试阅读次数：本文字数： 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]\)。

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

最终直接暴力求出\(st\)中有多少个\(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问题，我们再添加一个维度\(dir\)，用于表示走到某个格子时皇后所面对的方向。

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

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

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

因此最终答案为\(\displaystyle{\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);
}