HNOI2014題解及數(shù)據(jù)

HNOI2014題解及數(shù)據(jù)，包括標(biāo)程及試題

solution: 

明顯的組合游戲，暴力N^2求出所有的狀態(tài)的SG值，復(fù)雜度就是O（N^2） 可以70分
然而我們發(fā)現(xiàn)在可以分開(kāi)枚舉：最小的數(shù)字小于等于sqrt(N)，分割的數(shù)目小于sqrt(N)所以可以做到O(Nsqrt(N))可以過(guò)掉本題，不過(guò)很多細(xì)節(jié)需要處理確實(shí)比較惡心
code:
#include
#include
#include
#include
#define MAXN 100010
int f,n,m,T,a,g,ans,now;
using namespace std;
int sg[MAXN],vis[MAXN];
int init(){
    scanf("%d%d",&T,&f);
    for (int i=0;i
    for (int i=f;i<=MAXN-10;i++){
        int q=(int)ceil(sqrt(i));
        for (int j=1;j
            int a=j,b=j+1;
            int x=i/a, y=i-x*a;
            x-=y;
            now=sg[(x&1)*a]^sg[(y&1)*b];
            vis[now]=i;
            if (a%2 && x>=b){
                vis[now^sg[b]]=i;
            }
            if (a%2==0 && b*(y+a)<=i){
                vis[now^sg[a]]=i;
            }
        }
        for (int m=2;m<=q;m++){
            int a=i/m,b=a+1;
            int y=i-a*m,x=m-y;
            vis[sg[(x&1)*a]^sg[(y&1)*b]]=i;
        }
        for (int j=0;j<=MAXN-10;j++){
            if (vis[j]!=i){
                sg[i]=j;
                break;
            }
        }   
    }
    return 0;
}

int main()
{
    init();
    while (T--){
        scanf("%d",&n);
        ans=0;
        int x;
        for (int i=1;i<=n;i++){
            scanf("%d",&x);
            ans=ans^sg[x];
        }
        printf("%d%c",ans?1:0,T?' ':'\n');
    }
    return 0;
}