专栏文章

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

zzybgml_AFO
P13221题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miowh0jk
此快照首次捕获于
2025/12/03 02:17
3 个月前
此快照最后确认于
2025/12/03 02:17
3 个月前
查看原文
题目链接：P13221 [GCJ 2015 #1C] Brattleship
这题代码不长，主要靠 博弈论 模拟找规律。我们来一步一步推导：

推导过程

我们设有棋盘有 rr 行，cc 列，战舰宽为 ww。

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

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

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

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

总结推导公式

2.在多行的情况下，我们需要用 r×⌊c÷w⌋r\times\lfloor c\div w\rfloor 回合才能击中战舰，如果 c mod w=0c\bmod w=0 需要 w−1w-1 个回合将弟弟的战舰击沉，如果 c mod w≠0c\bmod w\ne0 需要 ww 个回合将弟弟的战舰击沉。
终于推导出公式了！
代码实现也十分简单：

详细代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...