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

1、小红的夹吃棋

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

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

输入

第一行输入一个正整数\(t\),代表询问的次数。

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

输出

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

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入:
3
...
o*o
...
o**
ooo
..*
o*o
*o*
o*o

输出:
yukari
kou
draw

解答

枚举盘面上每个棋子'o',判断它的上方和下方或者是左边和右边是否同时有'*'即可,此时对应了其中一种情况\(c_0\)

对于另一种情况,将棋盘上的所有棋子全部“取反”,再沿用上面的判断方式,就可以得到另一种情况\(c_1\)

只需要综合考虑\(c_0\)\(c_1\)的值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 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\)行,每行输入一个正整数,代表当前小红服用药后,身体有多少症状。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
输入:
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\)比特数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 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\)列的棋盘,有一些格子是障碍物不能通过。小红控制一个皇后在从左上角出发,每次移动她可以控制皇后进行以下三种方式中的一种:

  1. 向右移动若干个格子。
  2. 向下移动若干个格子。
  3. 向右下移动若干个格子。

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

输入

第一行输入两个正整数\(n\)\(m\),代表行数和列数。

接下来的\(n\)行,每行输入一个长度\(m\)的字符串,用来表示棋盘。

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

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

  • \(1\leq n,m \leq 2000\)

输出

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

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

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入:
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\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 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);
}

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝