自动搬运

查看原文

来自洛谷，原作者为

	Kenma 入得此门不回首，无需宣之于口

搬运于2025-08-24 23:03:26，当前版本为作者最后更新于2024-08-26 21:06:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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++$ 。