西西软件园多重安全检测下载网站、值得信赖的软件下载站!
西西首页 常用软件 软件下载 安卓软件 游戏下载 安卓游戏 MAC应用 驱动下载 安卓电视
系统工具网络工具媒体工具图形图像聊天工具应用软件编程开发手机软件安卓应用电脑安全字体素材

HNOI2014题解及数据

  • HNOI2014题解及数据
  • 软件大小:25M
  • 更新时间:2014-05-17 11:13
  • 软件语言:中文
  • 软件厂商:
  • 软件类别:国产软件 / 免费软件 / 电子资料
  • 软件等级:4级
  • 应用平台:WinAll, Win7
  • 官方网站:http://www.cr173.com
好评:50%
坏评:50%

软件介绍

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;
}

软件标签: 试题

软件截图

HNOI2014题解及数据
HNOI2014题解及数据

    其他版本下载

    热门评论

    最新评论

    发表评论 查看所有评论(0)

    昵称:
    表情: 高兴 可 汗 我不要 害羞 好 下下下 送花 屎 亲亲
    字数: 0/500 (您的评论需要经过审核才能显示)

    下载帮助下载帮助西西破解版软件均来自互联网, 如有侵犯您的版权, 请与我们联系。

    TOP
    软件下载