题解：P11010 『STA - R7』Divide and Merge Game

· · 题解

P11010 解题报告

前言

很好猜的结论题。

这是篇和官解证明思路略有出入的题解。

思路分析

结论题当然要手玩数据了

设 p 表示 n 的最大真因子，即不等于自身的最大因子。特别地，当 n 为质数时，p=1。

结论：Alice 获胜当且仅当 n-k+1 > p。

考虑怎样证明。

（注：为方便表述，下述集合 A 等价于 序列 a）

充分性

即 n-k+1 > p \Rightarrow Alice 获胜。

考虑构造这样一个集合 A = \left \{ n-k+1,1,1,…,1 \right \} 。

不难发现，Bob 想要划分的非空集合，其元素之和至大为 p。当 n-k+1 > p 时，集合 A 中元素 n-k+1 无法被划分至任何一个集合。

必要性

即 n-k+1 \le p \Rightarrow Alice 失败。

考虑构造一种合法的划分方式。设 p 为所划分的集合的元素和。将集合 A 分为 1 和 非 1 元素。不难发现，Bob 获胜当且仅当非 1 元素之和可被划分为 m 个集合，且每个集合的元素和不超过 \ \lfloor \frac{n}{m} \rfloor。

弱化条件：限定 Bob 所划分的集合元素和为 p。

当 p=2 时，Bob 只需要构造一个和恰好为 p 的集合即可。不妨将集合 A 中极大元素和与所有 1 划分至同一集合。其中，极大元素和定义为不大于 p 的最大可能的元素和。

因为集合 A 中最大的元素不大于 p，所以只需要保证极大元素和与所有 1 的和不小于 p 即可。

不难发现，极大元素和是一个 01 背包问题，这启发我们打表验证（在 IOI 赛制中，其实可以交一发来验证）。

打表验证可知，当 p=2 时，在题目限定的数据范围内，结论成立。

然后改变弱化条件：限定 Bob 所划分的集合元素和为 \frac{n}{p}。

当 p = 3 时，构造如下：将非 1 元素升序排序，找到一个位置 pos，使得 \sum_{i=1}^{pos} a_i \le \frac{n}{p},a_{pos} \le \frac{n}{p},\sum_{i=pos+1}^{n} a_i \le \frac{n}{p}。因为 n-k+1 \le p，所以 pos 一定存在。

当 p >3 时，将 p=3 中所构造的集合拆分，结果一定不劣。

代码实现

我采用了线性筛 O(V) 预处理 p 和 O(1) 回答询问的实现方式，总体复杂度为 O(V+T)。但是可能有点卡空间。

AC code

#include<bits/stdc++.h>
using namespace std;
int t,n,k;
bool not_prime[100000005];
int prime[50000005],maxn[100000005],cnt;
void seive(int n){
    for(int i=2;i<=n;i++){
        if(!not_prime[i]) prime[++cnt]=i,maxn[i]=1;
        for(int j=1;j<=cnt && i*prime[j]<=n;j++){
            not_prime[i*prime[j]]=1;
            maxn[i*prime[j]]=i;
            if(i%prime[j]==0) break;
        }
    }
}
int main(){
    seive(100000000);
    cin>>t;
    while(t--){
        cin>>n>>k;
        if(n-k+1>maxn[n]) cout<<"Alice"<<'\n';
        else cout<<"Bob"<<'\n';
    }
}

后记

在考场上，证明结论可以采用证明与打表验证结合的做法，可能会有奇效。

祝点赞的各位 CSP / NOIP rp++ 。