菜鸡刚开始学习写题解,语言可能不太精炼,请大佬放过。
给你一堆石子,每次最多取k个,要求是先手取完素数,后手取完合数,但是两个人都是最优解知道最后结果,所以赢的人想每次尽量多拿,输的人想每次尽量少拿。
是个模拟题,先打个素数筛预处理下,把n以内包括n的素数存在一个数组里面,然后扫一遍这个素数数组,看有没有两个素数之间差值超过k+1,也就是先手会输的时候,把这个位置记录下来,取最大的下标。
先特判是否n<=2,2以下先手没办法取,直接输出0。然后分两大类,先手输和先手可以赢的情况,如果前面判断先手可以输,就把答案初始化为1,n定在第一次结束的素数,循环每次都是以后手开始的情况,每次把现在的n减去k,然后向上寻找第一个合数,用这个合数再去二分出下一次先手选的素数,n更新为先手现在的素数,一直重复循环直到二分后的结果到达先手输的下标位置。先手赢的情况就是每次尽可能往前取素数,直到现在的n与这个素数差不小于k,看是否超过,差值超过向上回溯到上一个素数,这是先手取完的结果,后手为保证少拿就每次-1,得到下次的结果,直到素数循环到3时后手失败结束循环。