传教士和野人问题
题目链接: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 "); 53 return 0; 54 } 55 if (m > 33) { 56 if (n >= 2 * m) { 57 printf("1 "); 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 ", ans); 71 return 0; 72 } 73 cur = ncur; 74 ans += 2; 75 } 76 printf("%d ", 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 ", d[1][0][m]); 112 return 0; 113 }