自动搬运

查看原文

来自洛谷，原作者为

	Aiopr_2378 沿湍流兮望归舟

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

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

以下是正文

解题思路

由于先手每次只能放置两个棋子，而随着轮数增加，后手能抹去的棋子个数期望越来越高。而不难发现，每一轮中，后手一定能抹去至少一颗棋子。而在第 $k$ 轮后，后手一定能抹去至少两颗棋子。也就是说，从第 $k$ 轮开始，棋盘的棋子个数一定不会再增加。而我们的目标就是找到这个轮数 $k$，最大出现的棋子个数就是 $k+2$，因为前 $k$ 轮先手都可以积累一颗棋子，在第 $k+1$ 轮放置两颗棋子后，此时为最大状态，然后后手取走两颗以上棋子……

发现我们要找的轮数 $k$ 有单调性。$k$越大，后手越有机会在一局之内拿走大于一颗棋子。于是我们二分答案，而分出局数 $x$，转化成判定性问题：在第 $x$ 局中，先手是否有一种布设方式，使得后手没有办法一次就拿走大于一颗棋子。

发现这个是好解决的，对于一个 $n\times n$ 的棋盘，第 $x$ 局中要求：先手在任意一个 $x\times x$ 的格子内不能放置大于一颗棋子。所以放置的棋子最大数量就是

将其与应该放置的棋子个数 $x$ 比较即可确定是否合法。

为什么先手按照这样决定一定有可行的出棋方式？因为棋盘在一开始就是确定的，那先手就可以在下棋之前直接确定所有下棋方案，与下棋过程无关。

参考代码

#include<iostream>
using namespace std;
int T,n;
int myceil(int x,int y){
    if(x%y) return x/y+1;
    else return x/y;
}
void solve(){
    cin>>n;
    if(n==1){
        cout<<1<<endl;
        return;
    }
    int l=1,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        int val=myceil(n,mid)*myceil(n,mid);
        if(val>=mid+1) l=mid;
        else r=mid-1;
    }
    cout<<l+2<<endl;
}
int main(){
    cin>>T;
    while(T--) solve();
    return 0;
}