题解：P10582 [蓝桥杯 2024 国 A] 最强策略家

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