HNOI2014题解及数据

HNOI2014题解及数据，包括标程及试题

solution: 

明显的组合游戏，暴力N^2求出所有的状态的SG值，复杂度就是O（N^2） 可以70分
然而我们发现在可以分开枚举：最小的数字小于等于sqrt(N)，分割的数目小于sqrt(N)所以可以做到O(Nsqrt(N))可以过掉本题，不过很多细节需要处理确实比较恶心
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;
}