题解：P13221 [GCJ 2015 #1C] Brattleship

zybgml_AFO · 2025-07-14 09:39:05 · 题解

题目链接：P13221 [GCJ 2015 #1C] Brattleship

这题代码不长，主要靠 博弈论 模拟找规律。我们来一步一步推导：

推导过程

我们设有棋盘有 r 行，c 列，战舰宽为 w。

击中战舰所需回合数的推导

1.在 r=1 的情况下（如下图），我们至少需要 c/w 个回合才能击中战舰。

击沉战舰所需回合数的推导

而击沉的推导较为复杂，我们需要分类讨论：

• 如果 c\bmod w=0 说明我们是在第 c 列击中战舰，弟弟无法犯规，我们只需在再用 w-1 个回合即可将弟弟的战舰击沉。（如上图）
• 反之说明我们在击中战舰后，弟弟还有犯规的用来移动战舰的空间，必须在击中战舰的下一列再消耗一回合防止弟弟犯规，所以我们共需要 w 回合才能将弟弟的战舰击沉。（如下图）

总结推导公式

2.在多行的情况下，我们需要用 r\times\lfloor c\div w\rfloor 回合才能击中战舰，如果 c\bmod w=0 需要 w-1 个回合将弟弟的战舰击沉，如果 c\bmod w\ne0 需要 w 个回合将弟弟的战舰击沉。

终于推导出公式了！
代码实现也十分简单：

详细代码

#include <bits/stdc++.h>
using namespace std;
int t;//t表示测试用例数
int r,c,w;//r,c,w分别表示棋盘的行数,列数和战舰的宽度.
int main(){
    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>r>>c>>w;
        int ans;//ans代表答案
        ans=(c/w)*r;//计算击中战舰所需回合
        if(c%w==0) ans+=w-1;
        else ans+=w;//计算击沉战舰所需回合
        cout<<"Case #"<<i<<": "<<ans<<endl;
        //注意输出格式
    }
    return 0;
}