HDU 2188 문 천 대지 진 사망 동포 512 추모 - 자원 봉사자 선발 (바 시 게임 이론)

제목: HDU 2188
누 드 바 시 게임 모델.
n = m + 1 일 때 한 번 에 최대 m 개 만 얻 을 수 있 기 때문에 선 취 자가 몇 개 를 가 져 가든 지 간 에 후 취 자 는 한 번 에 남 은 물건 을 가 져 갈 수 있 고 후 자 는 이 길 수 있 기 때문에 한편 으로 는 n% (m + 1) = 0 일 때 반드시 패 하 는 상황 에 직면 한다.그래서 n = (m + 1) * r + s, (r 는 임 의 자연수, s ≤ m) 시, 선 취 자가 s 개 아 이 템 을 가 져 가 려 면, 후 취 자가 x (≤ m) 개 를 가 져 가면 선 취 자가 m + 1 - k 개 를 가 져 가 고, 결 과 는 (m + 1) 개 (r - 1) 개 를 남 겨 두 고, 이후 에 이런 취 법 을 유지 하면 선 취 자 는 반드시 승리 한다. 한 마디 로 상대방 에 게 (m + 1) 의 배 수 를 남 겨 두 면 마지막 에 이 길 수 있다.
코드 는 다음 과 같 습 니 다:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
int main()
{
    int t, n, m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(n%(m+1)==0)
            puts("Rabbit");
        else
            puts("Grass");
    }
    return 0;
}

좋은 웹페이지 즐겨찾기