짐 바둑 평론 (Nim)

3622 단어 ACM알고리즘
왜 이 블 로 그 를 씁 니까?
       나 는 이 나 를 괴 롭 히 는 세 계 를 고소 할 것 이다!인터넷 에서 찾 은 짐 게임 의 기본 적 인 말 은 모두 "누가 이렇게 강하 게 이 물건 을 2 진법 과 연결 시 켰 는 지 모르겠다" 는 것 이다. 아니면 큰 사람 이 한 마디 로 다른 것 이나 짐 과 함께 쓰 면 된다.
       흥!나 로 하여 금 30 분 넘 게 유도 하 게 했다!
       다행히 알 아 차 렸 지만 사실은 간단 했다.
       짐 게임 에 관 한 문 제 는 모두 가 본 적 이 있 을 것 이 라 고 믿는다. 그렇지 않 으 면 나의 이 허튼소리 하 는 글 을 보 러 오지 않 을 것 이다.여기 서 제목 을 요약 하 자 면 지금 세 무더기 의 돌 이 있다 고 한다. 그리고 두 사람 은 돌아 가면 서 가 져 갈 수 있다. 매번 에 그 중의 한 무 더 기 를 가 져 갈 수 있 고 매번 에 적어도 하 나 를 가 져 갈 수 있다. 기껏해야 이 무 더 기 를 직접 가 져 갈 수 있 고 마지막 돌 을 가 져 갈 수 있 는 사람 이 승리 하 는 것 이다.AB 두 사람 을 가정 하면 A 선수.[둘 다 똑똑 해] - 게임 이론 필수 조건.
       우리 가 여기 서 간단하게 말하자면, 단지 두 무더기 의 돌 만 있다 고 가정 하 자.그러면 두 무더기 의 돌 수량 이 같 을 때 우리 의 A 동 지 는 반드시 패 할 것 이다.(이 점 에 대해 믿 지 못 하 겠 으 면 몇 가지 간단 한 상황 을 찾 아 종이 에 그림 을 그 려 보 세 요. 둘 다 똑똑 한 조건 에서 지고 싶 지 않 으 면 A 는 이 럴 때 지 는 것 밖 에 없어 요)
       좋아!우 리 는 이미 매우 강 한 규칙 을 찾 았 다!두 무더기 의 돌 이 수량 이 같 을 때, 먼저 지면 반드시 진다!
       그러면 우 리 는 다시 이런 문 제 를 생각해 보 자. 만약 에 세 번 째 돌 이 존재 한다 고 가정 하면 앞의 두 개의 돌 은 수량 이 같 고 마지막 에 한 무더기 의 돌 수량 이 다르다. 예 를 들 어 1, 1, 3. 우리 가 한번 보 자. 이때 A 동 지 는 반드시 이 길 수 있다. 이것 은 왜 일 까?우 리 는 세 번 째 돌 A 더 미 를 직접 가 져 갈 수 있 고 B 선수 로 바 뀌 었 으 며 두 무더기 의 돌 수량 이 같은 상황 을 발견 할 수 있다.
       그렇다면 1, 1, 1 의 경우?너 는 A 가 사실 반드시 이 길 것 이라는 것 을 쉽게 발견 할 수 있다.
       자, 상황 열 거 는 여기까지 입 니 다. 이제 우 리 는 추론 을 시작 하 겠 습 니 다.
       [임의의 두 무더기 의 수량 이 같은 돌 바둑 상황 을 선수 필 패 로 한다] 게다가 1, 1, 1 상황 을 선수 필 승 으로 합치 면 우 리 는 총 결 을 시작 합 니 다.
       우 리 는 세 번 째 돌 을 뽑 을 때 앞의 두 무더기 의 돌 이 지 는 상황 을 고려 해 야 한다. 물론 여기 서 돌 을 뽑 는 방법, 순 서 는 우리 가 결정 할 수 없다. 우 리 는 반드시 이 길 수 있 는 상황 이 있 는 지 없 는 지 를 계산 할 뿐이다.
       지금!소 가 몰 아 붙 이 는 녀석 이 이 물건 을 2 진법 과 연결 시 키 려 고 한다!
       우 리 는 돌의 수량 이 틀림없이 마이너스 정수 라 는 것 을 알 고 있다. 그러면 틀림없이 이 진 표시 가 있 을 것 이다!
       예 를 들 어 두 무더기 의 돌 수량 은 각각 7 과 5 이다.
       이 진 은 각각 111 과 101 이다.그러면 7 은 4 + 2 + 1, 5 는 4 + 1 로 볼 수 있다.맞다!2 진 분할!
       111=100+10+1,101=100+1。
       10 진법 으로 바 꾸 면:
       7=4+2+1,5=4+1。
       지금!돌무더기 가 바 뀌 었 다!두 무더기 아니 야!다섯 무더기 의 돌 이다!그 중 두 무더기 의 수량 은 4 이 고, 두 무 더 기 는 1 이다. 이 두 무더기 의 선 수 는 반드시 질 수 있다. 그리고 마지막 무 더 기 는 얼마든지 직접 가 져 가서 승 리 를 얻는다!
       이 물건 이 왜 2 진법 과 연결 되 어 있 는 지 설명 한다.
       그럼 이 귀신 이 왜 2 진법 과 연결 되 어 있 는 지 다시 한 번 설명해 주세요.우 리 는 상술 한 변형 을 보 았 기 때문에 우 리 는 수량 이 4 와 1 인 그 몇 무 더 기 를 알 았 기 때문에 선 수 는 그곳 에서 반드시 져 야 한다. 그러면 우 리 는 이 진 연산 에서 그들 을 직접 0 으로 돌려 놓 을 수 있 습 니까?
       맞다!네!다른 것 을 쓰 거나 간단 하 다!그리고 C 언어 에 서 는 이 또는 연산 을 직접 쓸 수 있 습 니 다!편리 하고 빠 르 며 편리 하 다!그리고 2 진법 으로 계산 하 는 거 야!이 단 계 는 바로 바 이 너 리 같은 것 을 모두 끝 냈 다.
       상기 예 에 따 르 면 7 과 5, 이 또는 계산 후 답 은 2 이다.정 답 은 2!이 2 가 얼마나 익숙 한가!두 숫자 가 같 거나 결과 가 0 이면 먼저 진다.반대로 0 이 아니면 선 수 는 반드시 이 길 수 있다.0 은 가짜 이 고 0 은 진짜 가 아니다!그리고 이상 하거나 뒤의 결 과 는 무엇 일 까요?바 이 너 리 를 모두 분리 한 후 수량 이 같은 돌 더 미 를 제거 하고 남 은 돌 입 니 다.
       n. 돌 더미 의 상황 을 다시 한 번 확장 해 보 겠 습 니 다.
       n 이 3 이 라 고 가정 하면 세 무더기 의 돌 수량 은 각각 a, b, c 이다.만약 우리 a ^ b = = 0 이 라면 c 가 0 이 아니라면 A 는 반드시 이 길 수 있 습 니 다. 왜냐하면 앞의 A 는 반드시 질 수 있 기 때 문 입 니 다.뒤에 A 는 누 워 서 이 길 수 있어 요.그래서 만약 에 a ^ b ^ c! =0, A 는 반드시 이 길 수 있다.왜 일 까요?우 리 는 ab 를 한 무더기 로 합성 해서 보 았 는데, 이때 문제 가 두 무더기 의 돌 로 간략화 되 었 다 는 것 을 발견 할 수 있 을 것 이다.돌 두 무더기!돌 두 무 더 기 는 수량 만 다 르 면 된다 는 거 야!
       같은 이치 로 n = 1, 2, 3, 4, 5... 모두 가능 합 니 다.a ^ b ^ c ^ d ^......! =0, 그러면 A 는 반드시 이 길 수 있다!
       emm.
       코드 시간 OvO:
#include
int main()
{
	int n,a=0,b;//   a 0            
	scanf("%d", &n);//    
	while (n--)
	{
		scanf("%d", &b);
		a ^= b;//  !!!
	}
	printf(a ? "YES
" : "NO
");// return 0; }

좋아요, 콜 렉 션, 좋아요, 용 한 마리. 큐.

좋은 웹페이지 즐겨찾기