版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1435858
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
题目意思很简单,如果先手有必胜策略,求能够达到必胜策略的操作个数。
这里简单介绍下Nim游戏下的必胜策略,综合来看,它们都属于回合制游戏,先后手,且游戏结果至于当前局面相关,所需要操作的集合先后手共享。
嗯哼,之前做过类似的Nim游戏,策略很简单,后手模仿先手操作,这样后手始终保持游戏状态为【对称】态,就能保证后手必赢。
而作为先手,只能在开局的第一回合中,看能否把它变成对称态,则保证先手必赢。
那显然,这类题目的目标就是保证在第一回合时,让当前局面进入对称态。
还可以参考《挑战》P311的游戏策略:
P312给了一个思路,对每个堆的石子数量进行异或,如果异或值非等于零,则先手必胜,否则后手必胜。
为什么可以利用异或?起码需要证明它的正确性,书中有证。
这里谈谈我对异或的看法,比如给定堆:
{1, 3, 2}
经过异或会发现 它的异或值为0,所以后手必胜
其实该集合还可以这么看,因为在后手的视角里为:
{1, {1, 2}, {2}}
所以不管先手怎么取,后手都有办法把它变成一种理想的对称。那么由于对称原理,后手必赢。
异或实际上是把一个大整数进行拆分,拆分成堆中堆,这样一来,视角将变得非常清晰。
再回到此题,实际上还是先异或,那么现在就考虑从每个堆中拿多少个石子,能否拿,让状态对称。
于是有了公式:
(xi - m) 异或 (XOR 异或 xi) = 0
当选择一个石堆,拿去m个石头后,重新异或,当然异或前还要排除这个元素的影响咯,如果为0,则进入必胜态。
所以 xi -m = xor ^ xi;
m = xi - xi ^ xor;
满足 m >= 1
即 xi > xi ^ xor
代码如下:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P2975.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
void solve() {
while (true) {
int n = ni();
if (n == 0) break;
int[] piles = new int[n];
for (int i = 0; i < n; ++i) piles[i] = ni();
int x = 0;
for (int i = 0; i < n; ++i) {
x ^= piles[i];
}
if (x == 0) out.println("0");
else {
int ans = 0;
for (int i = 0; i < n; ++i) {
if (piles[i] > (x ^ piles[i])) ans++;
}
out.println(ans);
}
}
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}
对grundy数理解的还不够透彻,有一篇比较好的博文把SG函数写的很形象。
博文链接:
https://software.intel.com/zh-cn/blogs/2014/03/06/nim-sg
脑洞大了一点,他把每个游戏抽象成有向图可达路径,而在所有可达路径中,对各个状态进行编号,编号的策略可以参考《挑战》P316
就拿此题来说,在任意一个点可以打上叉叉,那么该游戏就变成了两个子游戏,哪两个?
比如:
1 2 3 4 5 6 7 8
x
在 4 的位置上打上了叉叉,那么对于后一位选手来说,只会打1或者7,8
4 的周围是绝对不能打的,因为这样先手就必胜了,于是划分为两个子问题:
{1}, {7,8}
grundy数告诉我们,集合{1}和{7,8}如果【本质】上是一样的话,就可以采取对称策略,那么后手必输。
因为后手打破平衡,先手必然有办法保持平衡,直到后手再也不能划分为止,那么先手必赢。
所以只要grundy{1} ^ grundy{7,8} = 0,则先手必胜
那么对于当前grundy{1,2,3,4,5,6,7,8}必然非零
不过grundy的思想不仅如此。。。总感觉它忽略了一些细节,对问题进行了约简,才能如此高效,但自己暂未参透,对它的【编号】规则也是懵懵懂懂。
代码如下:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P3537.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX = 2000 + 16;
int[] mem;
void solve() {
mem = new int[MAX];
Arrays.fill(mem, -1);
while (more()) {
int n = ni();
out.println(grundy(n) != 0 ? "1" : "2");
}
}
int grundy(int n) {
if (n < 0) return 0;
if (mem[n] != -1) return mem[n];
int[] count = new int[MAX];
for (int i = 1; i <= n; ++i) {
count[grundy(i - 3) ^ grundy(n - i - 2)] = 1;
}
int res = 0;
while (count[res] != 0) res ++;
return mem[n] = res;
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}
好吧,还是找SG函数,参考博文:
此处把nm的棋牌分成了黑白两块,互不干扰,接着把棋盘顺时针45度旋转。
第一次接触旋转算法,于是写了一个测试代码,看了看具体的输出。
代码如下:
public class Diagonal {
public static void main(String[] args) {
int n = 8;
int w = 10;
String[][] board = new String[n][w];
int cnt = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < w; ++j) {
board[i][j] = cnt <= 9 ? "0" + cnt : cnt + "";
cnt ++;
}
}
String[][] trans = new String[n + w][n + w];
for (int i = 0; i < n + w; ++i) {
for (int j = 0; j < n + w; ++j) {
trans[i][j] = " ";
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < w; ++j) {
if (((i + j) & 1) == 0) {
int ni = i + j;
int nj = j - i + n;
trans[ni][nj] = board[i][j];
}
}
}
pp(board);
pp(trans);
}
public static void pp(String[][] board) {
StringBuilder sb = new StringBuilder();
int n = board.length;
int m = board[0].length;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
sb.append(board[i][j] + ((j + 1 == m) ? "\n" : " "));
}
}
System.out.println(sb.toString());
}
}
输出如下:
01 02 03 04 05 06 07 08 09 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 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
01
21 12 03
41 32 23 14 05
61 52 43 34 25 16 07
72 63 54 45 36 27 18 09
74 65 56 47 38 29 20
76 67 58 49 40
78 69 60
80
接着就可以继续写我们的分割算法了,一旦定位某个具体的位置,那么根据L和R还是X,就能对棋盘划分成多个子游戏,直到找不到这样的划分为止。
代码如下:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/C138D.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
int n, m;
char[][] board;
void solve() {
n = ni();
m = ni();
board = new char[n][m];
for (int i = 0; i < n; ++i) {
board[i] = ns().toCharArray();
}
out.println((calc(0) ^ calc(1)) != 0 ? "WIN" : "LOSE");
}
int[][][][] dp;
private int calc(int mod) {
int N = n + m;
dp = new int[N + 2][N + 2][N + 2][N + 2];
ArrayUtils.fill(dp, -1);
return grundy(0, 0, N, N, mod);
}
int grundy(int row_min, int col_min, int row_max, int col_max, int mod) {
if (dp[row_min][col_min][row_max][col_max] != -1) return dp[row_min][col_min][row_max][col_max];
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (((i + j) & 1) == mod) {
int ni = i + j;
int nj = j - i + n;
if (inside(ni, nj, row_min, col_min, row_max, col_max)) {
if (board[i][j] == 'L') {
int g1 = grundy(row_min, col_min, ni, col_max, mod);
int g2 = grundy(ni + 1, col_min, row_max, col_max, mod);
set.add(g1 ^ g2);
}
if (board[i][j] == 'R') {
int g1 = grundy(row_min, col_min, row_max, nj, mod);
int g2 = grundy(row_min, nj + 1, row_max, col_max, mod);
set.add(g1 ^ g2);
}
if (board[i][j] == 'X') {
int g1 = grundy(row_min, col_min, ni, nj, mod);
int g2 = grundy(row_min, nj + 1, ni, col_max, mod);
int g3 = grundy(ni + 1, col_min, row_max, nj, mod);
int g4 = grundy(ni + 1, nj + 1, row_max, col_max, mod);
set.add(g1 ^ g2 ^ g3 ^ g4);
}
}
}
}
}
int res = 0;
while (set.contains(res)) res ++;
return dp[row_min][col_min][row_max][col_max] = res;
}
boolean inside(int x, int y, int row_min, int col_min, int row_max, int col_max) {
return x >= row_min && x < row_max && y >= col_min && y < col_max;
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}
不去吐槽这英语了,且这题目的意思也没讲清楚,醉了。
题意:
国足:两名球员轮流从N个球中挑出不多于M个射门,每个球半径都是R,离球门S。由于国脚技术高超,每次只能踢出L以内的距离。进最后一个球者胜,求谁有必胜策略?
他实际是一个nim的强化版,思路和hankcs的差不多,参考链接如下:
http://www.hankcs.com/program/algorithm/poj-2315-football-game.html
思路:
如果思维活跃的话,会发现这题其实是一个强化的Nim游戏。如何看破呢?每个球到球门的距离除以周长得到一个数字k,向上取整,代表要踢多少圈才能进球。于是转换思维,将每个足球看做Nim游戏中一堆数目为k的石头堆。每次踢出距离不超过L,将L除以周长,向下取整,得到每次至多能拿的石头个数K。将每个k % (K+1),可以简化每个石头堆上的石头数,因为你拿走x个,我可以拿走K+1-x个,抵消你的操作,使得游戏状态不变。每次可选不多于M个足球,即每次可选M座石头堆。 经典算法中,XOR=k0^k1^…^kn-1,若为0,则先手必败,否则必胜。 XOR又称半加运算,即只执行加法而不执行进位。在原始Nim游戏中,只允许选取1堆,所以最终XOR的结果是以2为进制执行半加运算。在此处,每次可选M座石头堆,进制则为M+1。在实现的时候可以先不管进位,只做加法,最终对M+1求模,将carries去掉。
需要补充的:
首先一开始并没有理解M+1为什么就是M+1进制,后来发现这跟M+1进制没有关系。XOR是半加运算没错,但并不是因为它是半加的原因才适用于nim游戏,而在于mod 2的作用,好吧,还是半加。
我在纠结既然是M+1进制,那怎么不把每个k值转成M+1进制,再异或,这和题目本身有何联系?我想了很久都没找到。看了代码才发现问题,因为在做XOR累加时,实际上还是针对二进制下去做的,还在操作每一位。那这肯定不是M+1进制,只能说明hankcs大神理解有误啊。。。
真正的含义其实对于每一位累加,是想看看这些堆的组合能否自我对称。。。比如堆:
{1},{2},{3} m = 2
0001
0010
0011
---------
0022
对于每一位的累加实际是想统计能够在有1的情况下,有多少堆能够进行操作,显然如果超过(M + 1)的个数,能够被(M+1)整除的那些可以忽略不考虑。
所以有对每一位mod M + 1,而单独考虑每一位可动的次数,而我们知道,如果我从第一个减一,那么对手就可以从第三个堆里也减一,保证了对称。
所以对于先手来说,可以操作m % (M + 1)次,来率先完成对称。
所以才有了m % (M + 1) != 0 的情况下,先手必赢的结论。
比如:
{1},{1},{1}, m = 2
0001
0001
0001
--------
0000
很遗憾,先手的每一位都为0,因为为零的条件为% M+1为零,而先手只能操作0,1,...,M次,而这显然是无法完成的操作。。。惨呐
综上:和M+1进制没有关系。。。
代码如下:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P2315.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_N = 30;
static final int MAX_S = 27;
static final double PI = 3.14159265358979323846264338327950288;
int N, M, L, R;
int[] S;
int[] XOR;
void solve() {
while (more()) {
N = ni();
M = ni();
L = ni();
R = ni();
S = new int[MAX_N];
XOR = new int[MAX_S];
for (int i = 0; i < N; ++i) {
S[i] = ni();
}
out.println(nim() ? "Alice" : "Bob");
}
}
boolean nim() {
int K = distance(L); // 可以选取 K - 1 个石头
for (int i = 0; i < N; ++i) {
int g = distance(S[i]) % K;
for (int j = 0; g != 0; ++j, g >>= 1) {
XOR[j] += g & 1;
}
}
for (int i = 0; i < MAX_S; ++i) {
if (XOR[i] % (M + 1) != 0) return true;
}
return false;
}
int distance(int x) {
return (int) (x / (2 * PI * R)) + 1;
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
static class ArrayUtils {
public static void fill(int[][] f, int value) {
for (int i = 0; i < f.length; ++i) {
Arrays.fill(f[i], value);
}
}
public static void fill(int[][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
public static void fill(int[][][][] f, int value) {
for (int i = 0; i < f.length; ++i) {
fill(f[i], value);
}
}
}
}
最后一题,重返第一。