程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1729 Stone Game (SG函數)

HDU 1729 Stone Game (SG函數)

編輯:C++入門知識

給出一些盒子,盒子有容量限制,有初始容量,每次給某一個盒子中添加石頭。
添加的數量必須小於等於盒子中已有數量的平方。
感覺上有一點像 Wythoff Game。當然肯定比那個復雜
對於上限為S,當前容量如果為C,如果C+C*C<S&&(C+1)+(C+1)*(C+1)>=S,那麼對於(S,C)顯然是一個必敗態
因為你不管一次取多少,不可能直接獲勝,而對方都能直接獲勝。
那麼就繼續遞歸求C狀態。
如果最大的必敗T>當前的C,那麼就求出C後繼中最小,也就是S-C
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
#include<algorithm> 
#define N 10005 
#define LL long long 
#define inf 1<<29 
#define eps 1e-7 
using namespace std; 
int get_sg(int s,int c){ 
    int q=sqrt((double)s); 
    while(q+q*q>=s) 
        q--; 
    if(c>q) return s-c; 
    else return get_sg(q,c); 

int main(){ 
    int n,cas=0; 
    while(scanf("%d",&n)!=EOF&&n){ 
        int s,c; 
        printf("Case %d:\n",++cas); 
        int ans=0; 
        while(n--){ 
            scanf("%d%d",&s,&c); 
            ans^=get_sg(s,c); 
        } 
        if(ans) 
            puts("Yes"); 
        else 
            puts("No"); 
    } 
    return 0; 

作者;ACM_cxlove

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved