传教士和野人问题

题目链接:codeforces上的一次比赛,tourist参加了

题目描述:

m个传教士和m个野人撑船过河,船上最多有n个人,最少有一个人(否则没人撑船了).

野人爱吃人,当他们人多势众时,就会把传教士给吃掉.也就是说,当野人的人数大于传教士的人数时,野人就把传教士全吃掉.

有三个吃人的地点:船上,左岸,右岸.

面对这滔滔河水,他们想尽快过河.给定m和n两个正整数,问能不能成功过河?如果能过河,最少需要撑几次船才能全部过去?

分析

这是一个经典的益智游戏.

关键在于状态描述,用三元组来描述(左岸羊的个数,左岸狼的个数,船在左岸还是右岸),符号表示(goat,wolf,boat).

那么右岸的状态就知道了(m-goat,m-wolf,!boat).

如何判断一个状态是否合法?

对于状态(goat,wolf,boat),满足左岸上goat>=wolf,右岸上m-goat>=m-wolf.

若要这两个不等式同时成立,必有goat=wolf.

或者是goat=0,羊的个数确实比狼少,狼想吃但没有.

或者是goat=m,这样跟上面那种情况对称,也是一种安全状态.

有三种合法状态:

(0)goat=0

(1)goat=wolf

(2)goat=m

于是,就有了改良了的状态描述方案:用三元组来表示(状态的类别编号,狼的个数,船的位置).空间复杂度骤减为O(m*3*2).

状态虽然有m*m*2个,但是合法的却只有6*m个.

状态转移:(g,w,b)的dg+dw<=n.于是有2种运输方案:

(0)把船所在的那个岸的羊全部运到对岸去,狼随便运,只要不超重.这样产生0,2两类状态.

(1)把dg个羊和dw个狼运到对岸去,还是保持平衡.这样保持1状态.

我的方法有点暴力,所以超时了.

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<math.h>
 6 #include<string.h>
 7 #include<stdlib.h>
 8 using namespace std;
 9 typedef long long ll;
10 typedef unsigned long long ull;
11 #define re(i,n) for(int i=0;i<n;i++)    
12 const int maxn = 1e5 + 7;
13 int n, m;
14 struct Node{
15     int wolf, kind, boat;
16     int fa;//记录是从那个节点到来的,用于回溯怎么到达这个节点
17 };
18 bool vis[maxn][3][2];//有没有访问过这个状态
19 int f[maxn][3][2];//到达此状态所需的步数
20 struct Q{
21     Node a[maxn * 6];
22     int h, r;
23     void init(){
24         memset(vis, 0, sizeof(vis));
25         h = r = 0;
26     }
27     void enq(int wolf, int kind, int boat, int step){
28         if (vis[wolf][kind][boat])return;
29         vis[wolf][kind][boat] = true;
30         f[wolf][kind][boat] = step;
31         a[r].wolf = wolf, a[r].boat = boat, a[r].kind = kind;
32         a[r].fa = h - 1;
33         r++;
34     }
35     Node deq(){
36         return a[h++];
37     }
38 }q;
39 int go(){
40     q.init();
41     q.enq(m, 2, 0, 0);
42     while (q.h != q.r){
43         Node now = q.deq();
44         if (now.kind == 2 && now.boat == 1 && now.wolf == m)
45             return f[now.wolf][now.kind][now.boat];
46         int w = now.wolf, g;
47         int step = f[now.wolf][now.kind][now.boat] + 1;
48         if (now.kind == 0)g = 0;
49         else if (now.kind == 1)g = w;
50         else if (now.kind == 2)g = m;
51         /*只有两种决策方案:把羊全部运过去
52         运相同数量的狼和羊
53         */
54         //羊的个数不为0且小于n,把羊全部运过去.生成2状态.
55         if (g <= n){
56             int sp = n - g;
57             //把狼运过去,至少运一只
58             for (int i = 1; i <= w&&i <= sp; i++){
59                 q.enq(m - w + i, 2, 1 - now.boat, step);
60             }
61             //狼1只也不运,只运羊就行了
62             if (g)q.enq(m - w, 2, 1 - now.boat, step);
63         }
64         //如果全是羊,但一只羊也不运过去,那就至少运去一只狼.生成0状态
65         if (g == m){
66             for (int i = 1; i <= w&&i <= n; i++){
67                 q.enq(m - w + i, 0, 1 - now.boat, step);
68             }
69         }
70         //运相等数量的狼羊,并且羊不能全部运过去,且至少运过去一只,只有1状态可以生成1状态
71         if (now.kind == 1){
72             int by = min(g - 1, w);
73             by = min(by, n >> 1);
74             for (int i = 1; i <= by; i++){
75                 q.enq(m - w + i, 1, 1 - now.boat, step);
76             }
77         }
78         //我这边羊满着,运一部分过去,使得两岸相等.由2状态可以到1状态,
79         if (g == m&&w < m&&n >= m - w){//w<g必为2状态
80             //需要运过去m-w只羊,因为河对岸有m-w只狼在等着
81             q.enq(m - w, 1, 1 - now.boat, step);
82         }
83     }
84     return -1;
85 }
86 int main(){
87     freopen("in.txt", "r", stdin);
88     for (m = 1; m < 100; m++){
89         for (n = 1; n <= m*2; n++){
90             int ans = go();
91             printf("%3d", ans);
92         }
93         puts("");
94     }
95     return 0;
96 }

我还不会,先贴上那次比赛中的几份神代码.第一份是正确的,后两份是错误的.

  1 import java.io.PrintWriter;
  2 import java.util.Arrays;
  3 import java.util.BitSet;
  4 import java.util.HashSet;
  5 import java.util.Scanner;
  6 
  7 public class F5 {
  8     Scanner in;
  9     PrintWriter out;
 10 //    String INPUT = "100000 10";
 11     String INPUT = "";
 12     
 13     int[] dec(int n, int m)
 14     {
 15         if(n <= m){
 16             return new int[]{n, 0};
 17         }else if(n <= 2 * m){
 18             return new int[]{n - m, n - m};
 19         }else{
 20             return new int[]{n - 2 * m - 1, m};
 21         }
 22     }
 23     
 24     int enc(int x, int y, int m)
 25     {
 26         if(y == 0){
 27             return x;
 28         }else if(x == y){
 29             return x + m;
 30         }else{
 31             return x + 2 * m + 1;
 32         }
 33     }
 34     
 35     void solve()
 36     {
 37         int m = ni();
 38         int n = ni();
 39         if(n <= Math.sqrt(Math.sqrt(m))){
 40             solveH(m, n);
 41         }else{
 42             solveB(m, n);
 43         }
 44     }
 45     
 46     void solveB(int m, int n){
 47             // (a, 0), (a, a), (a, m)
 48             BitSet visitedo = new BitSet();
 49             BitSet visitedh = new BitSet();
 50             BitSet q = new BitSet();
 51             q.set(0);
 52             boolean iso = true;
 53             int step = 0;
 54             
 55             outer:
 56             while(!q.isEmpty()){
 57 //                tr(step, q);
 58                 BitSet nq = new BitSet();
 59                 if(iso){
 60                     visitedh.or(q);
 61                 }else{
 62                     visitedo.or(q);
 63                 }
 64                 for(int cur = q.nextSetBit(0);cur != -1;cur = q.nextSetBit(cur+1)){
 65                     if(!iso && cur == 2 * m)break outer;
 66                     int[] co = dec(cur, m);
 67                     if(iso){
 68                         {
 69                             if(co[1] == 0){
 70                                 int inf = co[0] + 1;
 71                                 int sup = Math.min(m, co[0] + n);
 72                                 if(inf <= sup){
 73                                     nq.set(enc(inf, 0, m), enc(sup, 0, m) + 1);
 74                                 }
 75                             }
 76                         }
 77                         {
 78                             int inf = Math.max(co[0], co[1]);
 79                             if(co[0] == co[1])inf++;
 80                             int sup = Math.min(m, (n + co[0] + co[1]) / 2);
 81                             
 82                             if(inf <= sup){
 83                                 nq.set(enc(inf, inf, m), enc(sup, sup, m) + 1);
 84                             }
 85                         }
 86                         {
 87                             int inf = co[0];
 88                             if(co[1] == m)inf++;
 89                             int sup = Math.min(m - 1, co[0] + n - m + co[1]);
 90                             if(inf <= sup){
 91                                 nq.set(enc(inf, m, m), enc(sup, m, m) + 1);
 92                             }
 93                         }
 94                     }else{
 95                         {
 96                             if(co[1] == m){
 97                                 int inf = co[0] - 1;
 98                                 int sup = Math.max(0, co[0] - n);
 99                                 if(sup <= inf){
100                                     nq.set(enc(sup, m, m), enc(inf, m, m) + 1);
101                                 }
102                             }
103                         }
104                         {
105                             int inf = Math.min(co[0], co[1]);
106                             if(co[0] == co[1])inf--;
107                             int sup = Math.max(0, (-n + co[0] + co[1]) / 2);
108                             
109                             if(sup == 0)sup++;
110                             if(sup <= inf){
111                                 nq.set(enc(sup, sup, m), enc(inf, inf, m) + 1);
112                             }
113                         }
114                         {
115                             int inf = co[0];
116                             if(co[1] == 0)inf--;
117                             int sup = Math.max(0, co[0] - n + co[1]);
118                             if(sup <= inf){
119                                 nq.set(enc(sup, 0, m), enc(inf, 0, m) + 1);
120                             }
121                         }
122                     }
123                 }
124                 if(iso){
125                     nq.andNot(visitedo);
126                 }else{
127                     nq.andNot(visitedh);
128                 }
129                 q = nq;
130                 step++;
131                 iso = !iso;
132             }
133             if(q.isEmpty()){
134                 out.println(-1);
135             }else{
136                 out.println(step);
137             }
138     }
139     
140     void solveH(int m, int n){
141         
142         // (a, 0), (a, a), (a, m)
143         HashSet<Integer> visitedo = new HashSet<Integer>();
144         HashSet<Integer> visitedh = new HashSet<Integer>();
145         HashSet<Integer> q = new HashSet<Integer>();
146         q.add(0);
147         boolean iso = true;
148         int step = 0;
149         
150         outer:
151         while(!q.isEmpty()){
152 //            tr(step, q);
153             HashSet<Integer> nq = new HashSet<Integer>();
154             if(iso){
155                 visitedh.addAll(q);
156             }else{
157                 visitedo.addAll(q);
158             }
159             for(int cur : q){
160                 if(!iso && cur == 2 * m)break outer;
161                 int[] co = dec(cur, m);
162                 if(iso){
163                     {
164                         if(co[1] == 0){
165                             int inf = co[0] + 1;
166                             int sup = Math.min(m, co[0] + n);
167                             if(inf <= sup){
168                                 for(int i = enc(inf, 0, m);i <= enc(sup, 0, m);i++){
169                                     nq.add(i);
170                                 }
171                             }
172                         }
173                     }
174                     {
175                         int inf = Math.max(co[0], co[1]);
176                         if(co[0] == co[1])inf++;
177                         int sup = Math.min(m, (n + co[0] + co[1]) / 2);
178                         
179                         if(inf <= sup){
180                             for(int i = enc(inf, inf, m);i <= enc(sup, sup, m);i++){
181                                 nq.add(i);
182                             }
183                         }
184                     }
185                     {
186                         int inf = co[0];
187                         if(co[1] == m)inf++;
188                         int sup = Math.min(m - 1, co[0] + n - m + co[1]);
189                         if(inf <= sup){
190                             for(int i = enc(inf, m, m);i <= enc(sup, m, m);i++){
191                                 nq.add(i);
192                             }
193                         }
194                     }
195                 }else{
196                     {
197                         if(co[1] == m){
198                             int inf = co[0] - 1;
199                             int sup = Math.max(0, co[0] - n);
200                             if(sup <= inf){
201                                 for(int i = enc(sup, m, m);i <= enc(inf, m, m);i++){
202                                     nq.add(i);
203                                 }
204                             }
205                         }
206                     }
207                     {
208                         int inf = Math.min(co[0], co[1]);
209                         if(co[0] == co[1])inf--;
210                         int sup = Math.max(0, (-n + co[0] + co[1]) / 2);
211                         
212                         if(sup == 0)sup++;
213                         if(sup <= inf){
214                             for(int i = enc(sup, sup, m);i <= enc(inf, inf, m);i++){
215                                 nq.add(i);
216                             }
217                         }
218                     }
219                     {
220                         int inf = co[0];
221                         if(co[1] == 0)inf--;
222                         int sup = Math.max(0, co[0] - n + co[1]);
223                         if(sup <= inf){
224                             for(int i = enc(sup, 0, m);i <= enc(inf, 0, m);i++){
225                                 nq.add(i);
226                             }
227                         }
228                     }
229                 }
230             }
231             if(iso){
232                 nq.removeAll(visitedo);
233             }else{
234                 nq.removeAll(visitedh);
235             }
236             q = nq;
237             step++;
238             iso = !iso;
239         }
240         if(q.isEmpty()){
241             out.println(-1);
242         }else{
243             out.println(step);
244         }
245     }
246     
247     void run() throws Exception
248     {
249         in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
250         out = new PrintWriter(System.out);
251 
252 //        long s = System.currentTimeMillis();
253         solve();
254         out.flush();
255 //        long g = System.currentTimeMillis();
256 //        System.out.println(g - s + "ms");
257     }
258     
259     
260     public static void main(String[] args) throws Exception
261     {
262         new F5().run();
263     }
264     
265     int ni() { return Integer.parseInt(in.next()); }
266     void tr(Object... o) { if(INPUT.length() != 0)System.out.println(o.length > 1 || o[0].getClass().isArray() ? Arrays.deepToString(o) : o[0]); }
267 }

tourist的代码第十个样例,第十四个样例……是错误的,在比赛开始3小时之前答案是错的,所以tourist过了这道题.之后改了答案,tourist的代码就错了,然而系统没有进行重判,导致tourist一发就过.所以下面的代码是错的.于是乎,全场只有一份代码过了这道题:上面的java代码.

 1 var
 2   yy,zz,n,m,i,e: longint;
 3   lg,rg: array [0..2,0..1,0..110] of longint;
 4   kg: array [0..2,0..1] of longint;
 5   was: array [0..100010,0..2,0..1] of boolean;
 6   x,y,z,km: array [0..666666] of longint;
 7 
 8 procedure put(x1,x2,yy,zz:longint);
 9 var
10   u1,u2,v,j,xx: longint;
11 begin
12   if x2 < 0 then exit;
13   if x1 > n then exit;
14   zz:=1-zz;
15   yy:=2-yy;
16   if x1 < 0 then x1:=0;
17   if x2 > n then x2:=n;
18   xx:=x1; x1:=n-x2; x2:=n-xx;
19   u1:=x1; u2:=x2;
20   for v:=1 to kg[yy,zz] do
21   begin
22     if x1 < lg[yy,zz,v] then x1:=lg[yy,zz,v];
23     if x2 > rg[yy,zz,v] then x2:=rg[yy,zz,v];
24     for j:=x1 to x2 do
25       if not was[j,yy,zz] then
26       begin
27         inc(e);
28         x[e]:=j;
29         y[e]:=yy;
30         z[e]:=zz;
31         km[e]:=km[i]+1;
32         was[j,yy,zz]:=True;
33       end;
34     if x1 <= x2 then
35       if (x1 > lg[yy,zz,v]) and (x2 < rg[yy,zz,v]) then
36       begin
37         inc(kg[yy,zz]);
38         lg[yy,zz,kg[yy,zz]]:=x2+1;
39         rg[yy,zz,kg[yy,zz]]:=rg[yy,zz,v];
40         rg[yy,zz,v]:=x1-1;
41       end else
42       if x2 < rg[yy,zz,v] then lg[yy,zz,v]:=x2+1
43       else rg[yy,zz,v]:=x1-1;
44     x1:=u1; x2:=u2;
45   end;
46 end;
47 
48 begin
49 //  assign(input,'in'); reset(input);
50 //  assign(output,'out'); rewrite(output);
51   read(n,m);
52   for yy:=0 to 2 do
53     for zz:=0 to 1 do
54     begin
55       kg[yy,zz]:=1;
56       lg[yy,zz,1]:=0;
57       rg[yy,zz,1]:=n;
58     end;
59   fillchar(was,sizeof(was),False);
60   i:=1; e:=1;
61   x[1]:=n; y[1]:=2; z[1]:=0;
62   km[1]:=0;
63   was[n,2,0]:=True;
64   while i <= e do
65   begin
66     if (x[i] = n) and (y[i] > 0) and (z[i] = 1) then
67     begin
68       writeln(km[i]);
69       halt;
70     end;
71     if y[i] = 0 then
72     begin
73       put(x[i]-m,x[i]-1,0,z[i]);
74     end else
75     if y[i] = 1 then
76     begin
77       put(x[i]-(m shr 1),x[i]-1,1,z[i]);
78       if (x[i] > 0) and (x[i] <= m) then put(x[i]-(m-x[i]),x[i],0,z[i]);
79     end else
80     begin
81       put(x[i]-m,x[i]-1,2,z[i]);
82       if (n-x[i]) <= m then
83         if x[i] < n then put(x[i]-((m-(n-x[i])) shr 1),x[i],1,z[i])
84         else put(x[i]-(m shr 1),x[i]-1,1,z[i]);
85     end;
86     inc(i);
87   end;
88   writeln(-1);
89   close(input);
90   close(output);
91 end.

第二名的代码跟tourist有点像,他的代码是错的.

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <string>
  5 #include <sstream>
  6 #include <algorithm>
  7 #include <iostream>
  8 #include <iomanip>
  9 #include <map>
 10 #include <set>
 11 #include <list>
 12 #include <queue>
 13 #include <stack>
 14 #include <vector>
 15 #include <cassert>
 16 
 17 using namespace std;
 18 
 19 #define pb push_back
 20 #define mp make_pair
 21 #define REP(i, n) for (int i = 0; i < (int)(n); ++i)
 22 typedef long long LL;
 23 typedef pair<int, int> PII;
 24 
 25 struct S {
 26     int a, b, c;
 27     S(int a, int b, int c) : a(a), b(b), c(c) {}
 28     S() {}
 29 };
 30 
 31 int m, n, cur;
 32 int d[2][3][35];
 33 queue<S> q;
 34 
 35 bool aCunningPlan() {
 36     return m - cur + 1 <= n;
 37 }
 38 
 39 int updVal;
 40 void upd(int a, int b, int c) {
 41     if (d[a][b][c] == -1) {
 42         d[a][b][c] = updVal;
 43         if (a != 1 || b != 0 || c != m) {
 44             q.push(S(a, b, c));
 45         }
 46     }
 47 }
 48 
 49 int main() {
 50     scanf("%d%d", &m, &n);
 51     if (n < 4 && m > 33) {
 52         printf("-1\n");
 53         return 0;
 54     }
 55     if (m > 33) {
 56         if (n >= 2 * m) {
 57             printf("1\n");
 58             return 0;
 59         }
 60         int ans = 0;
 61         cur = 0;
 62         while (true) {
 63             int ncur = min(m, cur + n / 2 - 1);
 64             if (ncur == m) {
 65                 ++ans;
 66                 break;
 67             }
 68             if (aCunningPlan()) {
 69                 ans += 3;
 70                 printf("%d\n", ans);
 71                 return 0;
 72             }
 73             cur = ncur;
 74             ans += 2;
 75         }
 76         printf("%d\n", ans);
 77         return 0;
 78     }
 79     REP(i, 2) REP(j, 3) REP(k, m + 1) d[i][j][k] = -1;
 80     d[0][0][0] = 0;
 81     q.push(S(0, 0, 0));
 82     while (!q.empty()) {
 83         S s = q.front();
 84         q.pop();
 85         updVal = d[s.a][s.b][s.c] + 1;
 86         if (s.a == 0) {
 87             if (s.b == 0) {
 88                 for (int nc = s.c + 1; nc <= min(s.c + n / 2, m); ++nc) upd(1, 0, nc);
 89                 if (m - s.c <= n) upd(1, 1, s.c);
 90                 if (s.c == 0) for (int nc = s.c + 1; nc <= min(s.c + n, m); ++nc) upd(1, 2, nc);
 91             } else if (s.b == 1) {
 92                 for (int nc = s.c + 1; nc <= min(s.c + n, m - 1); ++nc) upd(1, 1, nc);
 93                 if (s.c + n >= m) upd(1, 0, m);
 94             } else {
 95                 for (int nc = s.c + 1; nc <= min(s.c + n, m); ++nc) upd(1, 2, nc);
 96                 if (m - s.c + m <= n) upd(1, 0, m);
 97                 if (s.c <= n) upd(1, 0, s.c);
 98             }
 99         } else {
100             if (s.b == 0) {
101                 for (int nc = s.c - 1; nc >= max(0, s.c - n / 2); --nc) upd(0, 0, nc);
102                 if (s.c <= n) upd(0, 2, s.c);
103             } else if (s.b == 1) {
104                 for (int nc = s.c - 1; nc >= max(0, s.c - n); --nc) upd(0, 1, nc);
105                 if (m - s.c <= n) upd(0, 0, s.c);
106             } else {
107                 for (int nc = s.c - 1; nc >= max(1, s.c - n); --nc) upd(0, 2, nc);
108             }
109         }
110     }
111     printf("%d\n", d[1][0][m]);
112     return 0;
113 }