[HAOI2015]数组游戏

C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 601ms, 内存消耗: 1132K, 提交时间: 2023-01-28 15:37:24

#include<iostream>
#include <bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<climits>
#include<ctime>
using namespace std;
template<typename T>bool chkmax(T &_,T __){return _<__ ? (_=__,1) : 0;}
template<typename T>bool chkmin(T &_,T __){return _>__ ? (_=__,1) : 0;}
#define REP(i,a,b) for(register int i=a;i<=b;++i)
#define DREP(i,a,b) for(register int i=a;i>=b;--i)
#define MREP(i,x) for(register int i=beg[x];i;i=E[i].last)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define inf INT_MAX
const int maxn=1e9+10;
const int maxm=100+10;
int n,q,m,a[maxm],SG[maxm*maxm],L[maxn/10000],R[maxn/10000],cnt;
int va1[maxn/10000],va2[maxn/10000],block;
bool in[maxn/10000];
int get(int x){return x<=block ? va1[x] : va2[n/x];}
void into(int x,int va){
    if(x<=block)va1[x]=va;
    else va2[n/x]=va;
}
void init(){
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        ++cnt;
        L[cnt]=l;
        R[cnt]=r;
    }
    DREP(i,cnt,1){
        mem(in);
        int b=n/L[i],sum=0;
        for(int l=1,r;l<=b;l=r+1){
            int c=b/l,tmp=get(L[i]*l);
            r=b/c;
            in[sum]=1;
            in[sum^tmp]=1;
            if((r-l+1)%2)sum^=tmp;
        }
        REP(j,0,maxn)if(!in[j]){
            into(L[i],j);
            break;
        }
    }
}
int main(){
    scanf("%d%d",&n,&q);
    block=sqrt(n);
    init();
    REP(i,1,q){
        int ans=0;
        scanf("%d",&m);
        REP(j,1,m){
            int u;
            scanf("%d",&u);
            ans^=get(u);
        }
        if(ans)puts("Yes");
        else puts("No");
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 889ms, 内存消耗: 984K, 提交时间: 2019-09-16 16:53:22

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=1e6+100;
int n,q,w,SG[2][N],ans,blk,b[N],id,vis[N];
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il int getSG(re int x)
{
  x=n/(n/x);
  if(x<=blk) return SG[0][x];else return SG[1][n/x]; 
}
il void Pre()
{
    for(re int i=1;i<=n;i=n/(n/i)+1) b[++b[0]]=n/(n/i);
    fq(i,b[0],1)
    {
        re int x=b[i],now=0;++id;vis[0]=id;
        for(re int j=x+x;j<=n;)
        {
            re int t=(n/(n/j))/x*x,tmp=(t-j)/x+1;
            vis[now^getSG(j)]=id;
            if(tmp&1) now^=getSG(j);
            j=t+x;
        }
        re int tmp=0;while(vis[tmp]==id) ++tmp;
        if(x<=blk) SG[0][x]=tmp;else SG[1][n/x]=tmp;
    }
}
int main()
{
  n=gi();q=gi();blk=sqrt(n)+1;
  Pre();
  while(q--)
  {
      ans=0;w=gi();
      fp(i,1,w) ans^=getSG(gi());
      puts(ans?"Yes":"No");
    }
  return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 552ms, 内存消耗: 700K, 提交时间: 2022-09-19 16:35:57

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int a[N];
int sg[N][2],mex[N];
int n,m;
int next(int x,int y)
{
    return x==y?x+1:y/(y/(x+1));
}
void init()
{
    for(int i=1;i<=n;i=next(i,n))
    {
        for(int k=2,tmp=0;k<=i;k=next(k,i))
        {
            int x=i/k;
            int t=(x>m)?sg[n/x][1]:sg[x][0];
            mex[tmp^t]=i;
            if((i/x-i/(x+1))&1) tmp^=t;
        }
        int tmp=1;
        while(mex[tmp]==i) tmp++;
        ((i>m)?sg[n/i][1]:sg[i][0])=tmp;
    }
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>n;
    m=floor(sqrt(n));
    init();
    cin>>t;
    while(t--)
    {
        int k;
        cin>>k;
        int ans=0;
        for(int i=1;i<=k;i++)
        {
            int x;
            cin>>x;
            ans^=(n/x>m?sg[n/(n/x)][1]:sg[n/x][0]);
        }
        if(ans) puts("Yes");
        else puts("No");
    }
}

详情