P17761 「奶龙OI」Round 3 - 红石大佬

Simon439747 · 2026-10-24 15:01:31 · 题解

这题一眼看上去，只能 \Theta(1) 计算：数据范围太大了！

那么只能推式子了。我们先给出答案：

当 2k\not=n 时，ans=\min(3k,2n-k);

反之，ans=3k-1 或 2n-k-1。

::::info[证明]

1. 两个关键上界

设 S 为种子集合，|S|=k；W 为长出西瓜的空格集合，|W|=ans。

覆盖能力上界：在 2\times n 的网格中，一个内部种子最多有 3 个邻居（左、右、对侧）。因此，理想情况下 k 个种子最多覆盖 3k 个格子。即 ans \le 3k。
剩余空间上界：西瓜只能长在空格里，总格子数为 2n，种子占了 k 个，所以空格总数为 2n-k。即 ans \le 2n-k。

综上，理论最大值恒满足：

ans \le \min(3k, 2n-k)

2. 分类讨论构造

情形一：2k \neq n

当 3k \le 2n-k（即 k \le n/2）时： 我们需要验证是否能实现 ans=3k。这意味着每个种子都必须贡献 3 个独特的西瓜格。
- 构造策略：采用"错位隔离"摆法。将种子放在 (1, 1), (2, 3), (1, 5), \dots 这样的位置。
- 图示解析：
  
  如图所示，红色种子之间互不相邻，且每个种子都占据了"左、右、对侧"三个方向。由于 k \le n/2，我们有足够的列空间来容纳这种稀疏排列，不会产生边界浪费或重叠浪费。
- 结论：此时 ans = 3k。
当 3k > 2n-k（即 k > n/2）时： 此时种子的覆盖能力过剩，瓶颈在于"空地不够用"。
- 构造策略：采用"紧密填充"摆法。优先填满所有空位，多余的种子随意放置（甚至相邻放置，虽然效率降低，但不影响已满的空位）。
- 图示解析：
  
  如图所示，只要种子分布足够均匀，就能激活所有 2n-k 个空格。因为 k > n/2，种子密度足够大，不存在"孤岛空格"。
- 结论：此时 ans = 2n-k。

小结：当 2k \neq n 时，两种子情形均能取到上界，故 ans = \min(3k, 2n-k)。

情形二：2k = n（特殊情况）

这是本题唯一的"陷阱"。此时 3k = 2n-k = 1.5n，理论上界重合。但实际无法同时满足"全覆盖"和"无重叠"。

矛盾分析：要达到 3k，要求所有种子互不相邻且不在边界（否则邻居数<3）。要达到 2n-k，要求所有空格都被覆盖。当 2k=n 时，种子密度恰好处于临界点。若采用错位摆法（如情形一），两端必然出现边界种子或覆盖死角；若采用紧密摆法，必然有种子相邻导致覆盖重叠。
最优构造与损失：无论怎么摆，在 2k=n 的约束下，必然会有恰好 1 个单位的效率损失。
- 图示解析：
  
  如图所示，为了覆盖尽可能多的格子，我们不得不牺牲一个种子的"完美三面覆盖"属性，或者接受一个空格无法被覆盖。数学归纳法可证，这个损失下界为 1。
- 结论：ans = 3k - 1 （等价于 2n - k - 1）。

3. 最终公式

ans = \begin{cases} \min(3k, 2n-k) & \text{if } 2k \neq n \\ 3k - 1 & \text{if } 2k = n \end{cases}

:::info[声明] 本部分使用千问 AI 进行优化。 ::: ::::

放上代码：

:::success[AC Code]

//��ʾ���ˣ�ʮ��OIһ���գ�����long long������
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define AC 0
using ll=long long;
using pll=pair<int,int>;
template<typename T>
inline void readinVector(vector<T>& vec,int l,int r){
    for(int i=l;i<=r;i++)cin>>vec[i];
}
template<typename T>
class matvec{
public:
    vector<vector<T> >mat;
    matvec(){}
    matvec(int n){
        mat.resize(n+1);
    }
    void rs(int n){
        mat.resize(n+1);
    }
    matvec(int n,int m){
        mat.resize(n+1,vector<T>(m+1));
    }
    matvec(int n,int m,T v){
        mat.resize(n+1,vector<T>(m+1,v));
    }
    vector<T>& operator[](int i){
        return mat[i];
    }
    void p_b(const vector<T>&vec){
         mat.push_back(vec);
    }
};
int T=1;
void solve(){
    int n,a;
    cin>>n>>a;
    if(n==a*2){
        cout<<3*a-1<<endl;
        return;
    }
    cout<<min(3*a,2*n-a)<<endl;
}
signed main(){
//  freopen("xxx.in","r",stdin);
//  freopen("xxx.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)solve();
    return AC;
    //AK IOI!;
}

:::