2015年5月27日 星期三

[CF 494E] Sharti

作法:

詳細的作法在官方解已經講的很清楚了,這裡講一下為什麼 grundy number 長那樣的證明。

首先考慮$k$是無限大的情形,也就是這個遊戲可以選擇任意大的正方形,我們要證明當只有$(i,j)$有石頭的時候其 grundy number $g_{i,j}=min(lowbit(i),lowbit(j))$。當$i=1$或$j=1$時是顯然的,以下用數學歸納法,假設以$(1,1)$為左上角,$(x,y)$為右下角的矩形中,除了$(x,y)$以外的格子的 grundy number 都知道了,並且設$(x,y)$這格的理論值為$2^i$,那麼我們要證明兩件事:「只有$(x,y)$有石頭這個狀態」的後繼狀態中的 grundy number 裡沒有出現$2^i$,還有有出現$0,1,...,2^i-1$。

首先是沒有出現$2^i$,因為他的後繼狀態是一個正方形的每格裡都有一個石頭,除了$(x,y)$那格,因此這個命題就可以等價為:考慮一張方格表,上面寫上每個格子的理論上的 grundy number ,則任意圈一塊正方形把裡面的所有數全部 xor 起來都不會是$0$。用反證法,如果某一塊正方形內所有的數 xor 起來等於$0$,因為格子中的數都是$2$的冪次,所以等於是這塊正方形中每種數字都出現了兩次。首先看如何計算某塊區域中有多少個$2^i$,設$a_i$為這塊區域中$x,y$座標均被$2^i$整除的格子的數量,那麼這塊區域中的$2^i$的數量就會是$a_i-a_{i+1}$,而因為對於每個$i$,這塊正方形中的$2^i$都是偶數個,所以所有$a_i$的奇偶性相同,當$i$足夠大時$a_i$顯然$=0$,因此所有$a_i$都是偶數。假設這塊正方形的邊長是$2^x\cdot y$,其中$y$是奇數,那麼不難證明$a_y$是奇數,矛盾。

再來是證明出現了$0,1,...,2^i-1$(其中$0$是顯然的),這可以用數歸解決,假設現在$(1,1)$和$(2^r,2^r)$形成的正方形內部都是對的,那麼現在要推到$(2^{r+1},2^{r+1})$以內都是對的。把$(1,1)(2^{r+1},2^{r+1})$這個正方形切成四塊,那麼對於任意一個落在左下角那塊的格子$(x,y)$來說,考慮$(x-2^r,y)$,可以得到$(x-2^r,y)$能夠到達的後繼狀態的 grundy number $(x,y)$都能到達,所以$(x,y)$的 grundy number 和$(x-2^r,y)$的一樣。對於其他三塊也可以這樣處理,除了$(2^{r+1},2^{r+1})$這一格,我們要證明他的 grundy number 是$2^{r+1}$。在計算他的後繼狀態的值時,因為整張表格是沿對角線對稱的,所以兩邊的 xor 值會抵消,只剩下對角線上的,此時就化為一維的問題了,也就是證明當有個數列$b$滿足$b_i=lowbit(i),i=1,2,...,2^{r+1}-1$的話,令集合$S=\{ b_i\bigoplus ...\bigoplus b_{2^{r+1}-1} | 1\leq i<2^{r+1}\}$,則$S$裡出現了$1,2,...,2^{r+1}-1$(其中$\bigoplus $代表 xor 運算)。這件事的證明可以對$r$數歸,還算蠻顯然的所以略去,因此這樣成功證完$k$是無限大的情形了。

當$k$不是無限大時其實也類似,一樣也是先考慮每個格子的理論值形成的表,證明用邊長$\leq k$的正方形蓋下去的話所有的值 xor 起來不會是$0$。這次要注意到的是,假設$t$滿足$2^t\leq k<2^{t+1}$,那麼整張表其實是由$(1,1),(2^t,2^t)$形成的正方形裡面的值一直複製來的,證法和剛才類似,這裡省略。至於後繼狀態出現了$0,1,...,2^i-1$就變得很顯然了,因為每一格都可以對應回正方形$(1,1)(2^t,2^t)$內的其中一格,所以顯然是對的。

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
struct rec
{
    int x1,y1,x2,y2 ;
    void scan(){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);}
}r[maxn],r2[maxn];
 
struct P
{
    int x,d,u,val ;
    bool operator < (const P &rhs) const
    {
        return x<rhs.x ;
    }
}ev[maxn];
 
int ST[4*maxn],tag[4*maxn] ;
vector<int> v ;
void modify(int l,int r,int L,int R,int id,int val)
{
    if(l==L && r==R) { tag[id]+=val ; return ; }
    int mid=(L+R)/2 ;
    if(r<=mid) modify(l,r,L,mid,2*id,val) ;
    else if(l>=mid) modify(l,r,mid,R,2*id+1,val) ;
    else
        modify(l,mid,L,mid,2*id,val) ,
        modify(mid,r,mid,R,2*id+1,val) ;
    ST[id]= (tag[2*id] ? v[mid]-v[L] : ST[2*id]) +
            (tag[2*id+1] ? v[R]-v[mid] : ST[2*id+1]) ;
    ST[id]%=2 ;
}
 
int getarea(int num)
{
    if(!num) return 0 ;
    memset(ST,0,sizeof(ST)) ;
    memset(tag,0,sizeof(tag)) ;
    v.clear() ;
    for(int i=0;i<num;i++) v.push_back(r2[i].y1) , v.push_back(r2[i].y2+1) ;
    sort(v.begin(),v.end()) ;
    v.resize(unique(v.begin(),v.end())-v.begin()) ;
    for(int i=0;i<num;i++)
    {
        int id1=lower_bound(v.begin(),v.end(),r2[i].y1)-v.begin() ;
        int id2=lower_bound(v.begin(),v.end(),r2[i].y2+1)-v.begin() ;
        ev[2*i]=(P){r2[i].x1,id1,id2,1} ,
        ev[2*i+1]=(P){r2[i].x2+1,id1,id2,-1} ;
    }
    sort(ev,ev+2*num) ;
    int x=0 , val=0 , ret=0 ;
    for(int i=0;i<2*num;i++)
    {
        ret+=(ev[i].x-x)*val ; ret%=2 ;
        modify(ev[i].d,ev[i].u,0,maxn-1,1,ev[i].val) ;
        x=ev[i].x ;
        val=ST[1] ;
    }
    return ret ;
}
 
int a[60] ;
main()
{
    int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
    for(int i=0;i<m;i++)  r[i].scan() ;
 
    int i=0 ;
    for(int j=1;j<=k;i++,j*=2)
    {
        int cnt=0 ;
        for(int z=0;z<m;z++)
        {
            int x1=(r[z].x1-1)/j+1 , y1=(r[z].y1-1)/j+1 ;
            int x2=r[z].x2/j , y2=r[z].y2/j ;
            if(x1>x2 || y1>y2) continue ;
            r2[cnt++]=(rec){x1,y1,x2,y2} ;
        }
        a[i]=getarea(cnt) ;
    }
    for(int j=0;j<i;j++)
    {
        a[j]=(a[j]-a[j+1]+2)%2 ;
        if(a[j]){printf("Hamed\n") ; return 0 ;}
    }
    printf("Malek\n") ;
}
 

沒有留言:

張貼留言