[枚举] aw3785. 战舰(枚举+前缀和+经典好题+CF965B)

2021/7/31 23:39:03

本文主要是介绍[枚举] aw3785. 战舰(枚举+前缀和+经典好题+CF965B),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • 1. 题目来源
    • 2. 题目解析

1. 题目来源

链接:3785. 战舰

2. 题目解析

暴力题确实暴力方法做就行了。 O ( n 2 ) O(n^2) O(n2) 的话可以 递推+前缀和预处理 出来每个点四个方向上的可达长度,要注意,算上该点本身最长的长度是 k

思路:

  • 枚举每个安全区域点,都可能放战舰,枚举可行的方案数。
  • 该点可以横着放,竖着放。即,有两种方案数需要计算。
  • 找到横向该点的连续安全区域,注意别越过边界,同时不可距离该点太远,不可超过 k
  • 假设该点的横向连续的安全区域为 ( l , r ) (l, r) (l,r),那么区间长度就是 r-l-1,同时一个长度为 k 的军舰在此的摆放方案就是 r-l-1-k+1 种方案。
  • 因为我们使用 while 循环一直横向探索的话,指针终将停在非法位置,所以在此为了和代码相同,采用的是开区间。
  • 注意方案数要和 0 取个 max,因为可能根本就放不下军舰,相减为负值。
  • 同理竖直方向,也这样计算。
  • 两者方案数相加,即可得到该点的总的方案数。维护一个最大答案和坐标即可

时间复杂度: O ( n 3 ) O(n^3) O(n3)

空间复杂度: O ( n 2 ) O(n^2) O(n2)


#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int n, k;
char g[N][N];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> g[i] + 1;
    
    int cnt = 0, x = 1, y = 1;              // 不满足,输出任意位置均可
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= n; j ++ ) {
            if (g[i][j] == '#') continue;
            int l = j, r = j;               // 计算水平方向到达什么位置
            while (l >= 1 && g[i][l] == '.' && j - l + 1 <= k) l -- ;
            while (r <= n && g[i][r] == '.' && r - j + 1 <= k) r ++ ;
            int t = max(0, r - l - 1 - k + 1);      // 方案数,r,l最终停留位置为非法位置
            l = r = i;
            while (l >= 1 && g[l][j] == '.' && i - l + 1 <= k) l -- ;
            while (r <= n && g[r][j] == '.' && r - i + 1 <= k) r ++ ;
            t += max(0, r - l - 1 - k + 1);
            if (t > cnt) cnt = t, x = i, y = j;
        }
    
    cout << x << ' ' << y << endl;
    
    return 0;
}


这篇关于[枚举] aw3785. 战舰(枚举+前缀和+经典好题+CF965B)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程