POJ-2975, ZOJ-3067 : Nim
問題概要
山の数N(<1000)個のNimが与えられる。勝ちになるような手の選び方が何通りあるか求める問題。
解法
よく知られているし、問題文にも書いてあるがNimはA[i]のxorが0なら負け、そうでなければ勝ちである。つまり自分の手番ではxorが0になるように取らなければならない。X=A[0]^A[1]^..^A[N-1]とする。このとき、A[i]からm個の石をとってxorが0になるようにするには、(A[i]-m)^(X^A[i]) = 0、すなわちA[i]-m = X^A[i] 、m = A[i] - X^A[i]個とればよい。後は1<=m<=A[i]となるようにとれるかどうか、すなわち、A[i]>X^A[i]であればよい。
acceptされたコード
計算量O(N)。
#include <cstdio> using namespace std; const int MAX_N = 1000; int N; int as[MAX_N]; bool init(){ scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%d", as+i); } return N > 0; } int solve(){ int x = 0; for(int i=0; i<N; i++){ x ^= as[i]; } int ans = 0; for(int i=0; i<N; i++){ if(as[i] > (x ^ as[i])){ ans++; } } return ans; } int main(){ while(init()){ printf("%d\n", solve()); } return 0; }