首页 > 代码库 > 786A(博弈&bfs)

786A(博弈&bfs)

2024-10-22 23:17:02   209人阅读

题目链接: http://codeforces.com/problemset/problem/786/A

 

题意: 一个环形路径编号为1-n，1号点为黑洞，玩家轮流让怪物前进若干步（从自己的操作集合里随便选），若该轮怪物走到黑洞，则该轮的玩家胜利。简单来说，当怪物在x点时，轮到玩家 a 操作，他有个操作为前进 y 步，若前进 y 步之后刚好到达 1 号点，则怪物死亡，玩家 a 胜利。题目要求我们求出所以怪物初始位置和玩家 a, b 各自先手的游戏结果。

 

思路: 若已知一种状态为 P 状态, 那么与其邻接的状态都为 N 状态, 若一个状态的邻接状态全为 N 状态, 则该状态为 P 状态.

用 (id, x) 记状态 id 从 x 开始, 用 vis[id][x] 记录状态 (id, x) 的结果. -1 表示未处理, 0 表示为 P 状态, 1 表示为 N 状态.

除了死循环的状态外, 终态必定为 (0, 0), (1, 0), 那么用 bfs 从这两个状态逆推前面的状态即可.

 

代码:

技术分享 
 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 using namespace std;
 6 
 7 const int MAXN = 7e3 + 10;
 8 int gel[2][MAXN], vis[2][MAXN], num[2][MAXN], k[2];
 9 int n;
10 
11 void bfs(void){
12     queue<pair<int, int> > q;
13     q.push({0, 0});
14     q.push({1, 0});
15     vis[0][0] = 0;
16     vis[1][0] = 0;
17     while(!q.empty()){
18         pair<int, int> cnt = q.front();
19         int id = cnt.first, x = cnt.second;
20         q.pop();
21         if(vis[id][x] == 0){
22             for(int i = 0; i < k[!id]; i++){
23                 int tmp = (x - gel[!id][i] + n) % n;
24                 if(vis[!id][tmp] == -1){
25                     vis[!id][tmp] = 1;
26                     q.push({!id, tmp});
27                 }
28             }
29         }else if(vis[id][x] == 1){
30             for(int i = 0; i < k[!id]; i++){
31                 int tmp = (x - gel[!id][i] + n) % n;
32                 if(vis[!id][tmp] == -1){
33                     if(++num[!id][tmp] == k[!id]){//累计邻接(!id, tmp)状态的必胜态
34                         vis[!id][tmp] = 0;
35                         q.push({!id, tmp});
36                     }
37                 }
38             }
39         }
40     }
41 }
42 
43 int main(void){
44     scanf("%d", &n);
45     for(int i = 0; i < 2; i++){
46         scanf("%d", &k[i]);
47         for(int j = 0; j < k[i]; j++){
48             scanf("%d", &gel[i][j]);
49         }
50     }
51     memset(vis, -1, sizeof(vis));
52     bfs();
53     for(int i = 0; i < 2; i++){
54         for(int j = 1; j < n; j++){
55             if(vis[i][j] == -1) printf("Loop ");
56             else if(vis[i][j]) printf("Win ");
57             else printf("Lose ");
58         }
59         puts("");
60     }
61     return 0;
62 }
View Code

 

786A(博弈&bfs)


联系
我们