HDU 2177 취 (2 더미) 돌 게임 (위 조 프 게임)

5281 단어 게임 이론ACM
돌멩이 놀이
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2280    Accepted Submission(s): 1384
Problem Description
두 무더기 의 돌 이 있 는데, 수량 이 임의로 다 를 수 있다.게임 은 두 사람 이 돌아 가면 서 돌 을 채취 하기 시작 했다.게임 규정 에 따 르 면 매번 두 가지 서로 다른 취 법 이 있 는데 하 나 는 임의의 한 무더기 에서 임의의 많은 돌 을 가 져 갈 수 있다.둘 째 는 두 더미 에서 같은 양의 돌 을 동시에 가 져 갈 수 있다.마지막 으로 돌 을 모두 가 져 온 자가 승자 다.지금 은 최초의 두 무더기 의 돌 수 를 제시 합 니 다. 만약 당신 이 먼저 취 할 차례 라면 쌍방 이 모두 가장 좋 은 전략 을 취한 다 고 가정 하고 마지막 에 당신 이 승자 인지 패자 인지 물 어보 세 요.만약 네가 이기 면, 너 는 첫 번 째 로 어떻게 자식 을 얻 니? 
 
Input
몇 줄 을 포함 하 는 지 입력 하면 몇 가지 돌의 초기 상황 을 나타 낸다. 그 중에서 한 줄 에 두 개의 부정 정수 a 와 b 를 포함 하고 두 개의 돌의 수 를 나타 낸다. a 와 b 는 모두 1, 000, 000 보다 크 지 않 고 a < = b.a = b = 0 종료.
 
Output
출력 도 몇 줄 이 있 습 니 다. 마지막 에 당신 이 패자 라면 0 입 니 다. 반대로 1 을 출력 하고 당신 을 이 긴 당신 이 첫 번 째 로 돌 을 뽑 은 후에 남 은 두 무더기 의 돌 수량 x, y, x < = y 를 출력 합 니 다.만약 에 임의의 한 무더기 에서 돌 을 가 져 가면 이 길 수 있 고 두 무더기 에서 같은 수량의 돌 을 동시에 가 져 가도 이 길 수 있다. 먼저 같은 수량의 돌 을 가 져 가 는 상황 을 수출 한다.
 
Sample Input 
 
   

     1 2 5 8 4 7 2 2 0 0
 

Sample Output 
 
   

     0 1 4 7 3 5 0 1 0 0 1 2

   思路：威佐夫博弈，遇到奇异局势则必败第k个奇异局势(a(k), b(k))，a(k)是前面没有出现过的最小自然数（a(k)=(int)(k*(sqrt(5.0)+1)/2），b(k)=a(k)+k，采用适当的方法，这里不再证明，接下来只要判断就行了
同时从两堆中取相同数量的石头或者从一堆中取一定数量的石头，可以将非奇异局势变为奇异局势

#include 
#include 
#include 
using namespace std;

double g = (sqrt(5.0) + 1) / 2;  //      1.618...

int main()
{
    int a, b;
    while(scanf("%d %d", &a, &b) == 2) {
        if(a == 0 && b == 0)
            break;

        int k = b - a;
        if(a == (int)(g * k))    //     a  ，  b=a+k     
        {
            printf("0
");
        }
        else
        {
            printf("1
");
            //             
            for(int i=1; i<=a; i++) //               ，      1 a  
            {
                int x = a - i, y = b - i;
                int k = y - x;
                if(x == (int)(g * k))
                    printf("%d %d
", x, y);
            }
            for(int i=b-1; i>=0; i--)   //             ，    b-1     0
            {
                int x = a, y = i;
                if(x > y)
                    swap(x, y);

                int k = y - x;
                if(x == (int)(g * k))
                    printf("%d %d
", x, y);
            }
        }
    }
    return 0;
}

인터넷 에서 코드 를 보 니 귀 찮 지만 모든 상황 을 다 썼 다.
#include
#include
#include
#include
#include

using namespace std;

int vis[1000005]= {0};

int main()
{
    //freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
    for(int i=1; i<1000005; i++)
        vis[i]=(int)(i*1.0*(1+sqrt(5))/2);
    int n, m;
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        int k=m-n;
        if(vis[k]==n)
        {
            printf("0
");
            continue;
        }
        printf("1
");
        if(n>vis[k]&&m>vis[k]+k)
            printf("%d %d
",vis[k],vis[k]+k);
        for(int i=1; i<1000005; i++)
            if(vis[i]==n)
            {
                if(m>vis[i]+i)
                    printf("%d %d
",vis[i],vis[i]+i);
                break;
            }else if(vis[i]==m)
            {
                if(n>vis[i]+i)
                    printf("%d %d
",vis[i],vis[i]+i);
                break;
            }
        for(int i=1; i<1000005; i++)
            if(vis[i]+i==m)
            {
                if(n>vis[i])
                    printf("%d %d
",vis[i],vis[i]+i);
                break;
            }else if(vis[i]+i==n)
            {
                if(m>vis[i]+i)
                    printf("%d %d
",vis[i],vis[i]+i);
                break;
            }
    }
    return 0;
}
Thread 클래스 와 Runable 인터페이스
위 역 을 구 하 는 세 가지 방법: 직접, SVD, QR

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage