首页 > 编程语言 >【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场

【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场

时间:2024-10-09 22:14:04浏览次数:9  
标签:arr 23 int cnt C++ 蓝桥 ans 505 dp

【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场

题目链接跳转:点击跳转

前置知识:

  1. 了解过基本的动态规划。
  2. 熟练掌握二进制的位运算。

题解思路

这是一道典型的状压动态规划问题。设 \(dp_{i, j}\) 表示遍历到第 \(i\) 行的时候,当前行以 \(j_{(base2)}\) 的形式排列乌龟可以构成的方案数。

对于每一行的方案,我们可以用一个二进制来表示。例如二进制数字 \(10100\),表示有一个横向长度为 \(5\) 的场地中,第 \(1, 3\) 号位置分别放置了一只小乌龟。因此,每一种摆放状态都可以用一个二进制数字来表示。我们也可以通过遍历的方式来遍历出二进制的每一种摆放状态。

首先,我们预处理出横排所有放置乌龟的合法情况。根据题意,两个乌龟不能相邻放置,因此在二进制中,不能有两个 \(1\) 相邻。如何预处理出这种情况呢?我们可以使用位运算的方法:

如果存在一个二进制数字有两个 \(1\) 相邻,那么如果我们对这个数字 \(x\) 进行位运算操作 (x << 1) & x 的结果或 (x >> 1) & x 的结果必定大于等于 \(1\)。我们通过把这种情况排除在外。同时,我们还需要注意有些格子中不能放置乌龟。这一步也可以通过二进制的方法预处理掉,如果网箱在第 \(i\) 一个格子中不能放置乌龟,那么在枚举所有方案数的时候直接忽略掉第 \(i\) 位为 \(1\) 的情况即可。

接下来如何保证上下两行的乌龟不冲突?假如上一行的摆放状态是 \(y\),当前行的摆放状态为 \(j\),如果 i & j 的结果大于等于 \(1\),也可以证明有两个数字 \(1\) 在同一位置上。因此我们也需要把这种情况排除在外。

综上所述,我们可以得出状态转移方程:\(dp_{i, j} = dp_{i, j} + dp_{i-1, k}\)。其中,\(j\) 和 \(k\) 表示所有横排合法的方案。答案就是 \(\mathtt{ANS} = \sum_{j=0}^{2^M-1}{dp_{N, j}}\)。

状态的初始化也很简单,另 \(dp_{0, 0} = 1\)​,表示一只乌龟都不放有一种摆放方案。

时间复杂度

通过观察上述代码,在枚举所有状态和转移状态的时候有三层循环,分别是枚举当前行、枚举当前行的合法摆放情况以及枚举上一行的摆放情况。因此总时间复杂度约为 \(O(n \times 2^M \times 2^M) = O(n \times 2^{M^2}) = O(n \times 4^M)\)。但由于合法的摆放数量远远少于 \(2^M\),因此实际情况下程序运行的速度会快许多。

代码实现

本题的代码实现如下。在输出的时候需要减一,因为不放置也是一种合法情况,根据题目要求需要把这一合法情况排除。

#include <iostream>
using namespace std;

const int MOD = 1e9+7;
int n, m, ans;
int arr[505][505];
// 所有横排合法的情况。
int terrain[505];
int ok[1050], cnt;
int dp[505][1050];

int main(){
    cin >> n >> m;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            cin >> arr[i][j];
        }
    }
    
    // 预处理非法地形。
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            terrain[i] = (terrain[i] << 1) + !arr[i][j];
        }
    }
    
    // 预处理出所有横排的合法情况。
    for (int i=0; i<(1<<m); i++){
        if (((i<<1)|(i>>1)) & i) continue;
        ok[++cnt] = i;
    }
    dp[0][1] = 1;

    // 枚举。
    for (int i=1; i<=n; i++){
        for (int s1=1; s1<=cnt; s1++){  // 枚举当前行。
            if (ok[s1] & terrain[i]) continue;
            for (int s2=1; s2<=cnt; s2++){  // 枚举上一行。
                if (ok[s2] & terrain[i-1]) continue;
                if (ok[s1] & ok[s2]) continue;
                dp[i][s1] = (dp[i][s1] + dp[i-1][s2]) % MOD;
            }
        }
    }

    // 统计答案。
    int ans = 0;
    for (int i=1; i<=cnt; i++)
        ans = (ans + dp[n][i]) % MOD;
    
    cout << ans - 1 << endl;
    return 0;
}

本题的 Python 代码如下,Python 可以通过本题的所有测试点:

MOD = int(1e9 + 7)
n, m, ans = 0, 0, 0
arr = [[0] * 505 for _ in range(505)]
terrain = [0] * 505
ok = [0] * 1050
dp = [[0] * 1050 for _ in range(505)]
cnt = 0

def main():
    global n, m, cnt, ans
    
    # 输入 n 和 m
    n, m = map(int, input().split())
    
    # 输入 arr 数组
    for i in range(1, n + 1):
        arr[i][1:m + 1] = map(int, input().split())
    
    # 预处理非法地形
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            terrain[i] = (terrain[i] << 1) + (1 - arr[i][j])
    
    # 预处理出所有横排的合法情况
    for i in range(1 << m):
        if ((i << 1) | (i >> 1)) & i:
            continue
        cnt += 1
        ok[cnt] = i
    
    dp[0][1] = 1
    
    # 枚举
    for i in range(1, n + 1):
        for s1 in range(1, cnt + 1):  # 枚举当前行
            if ok[s1] & terrain[i]:
                continue
            for s2 in range(1, cnt + 1):  # 枚举上一行
                if ok[s2] & terrain[i - 1]:
                    continue
                if ok[s1] & ok[s2]:
                    continue
                dp[i][s1] = (dp[i][s1] + dp[i - 1][s2]) % MOD
    
    # 统计答案
    ans = 0
    for i in range(1, cnt + 1):
        ans = (ans + dp[n][i]) % MOD
    
    print(ans - 1)

if __name__ == "__main__":
    main()

再提供一个暴力解法用于对拍:

#include <iostream>
using namespace std;

const int MOD = 1e9+7;
int n, m, ans;
int arr[505][505];
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};

// 深度优先搜索 Brute Force
void dfs(int x, int y){
    if (x > n) {
        ans += 1;
        ans %= MOD;
        return ;
    }
    if (y > m){
        dfs(x+1, 1);
        return ;
    }
    if (arr[x][y] == 0){
        dfs(x, y+1);
        return ;
    }
    // 不放鱼
    dfs(x, y+1);

    // 放鱼
    for (int i=0; i<4; i++){
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (cx < 1 || cy < 1 || cx > n || cy > m) continue;
        if (arr[cx][cy] == 2) return ;
    }
    arr[x][y] = 2;
    dfs(x, y+1);
    arr[x][y] = 1;
    return ;
}

int main(){
    cin >> n >> m;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            cin >> arr[i][j];
        }
    }
    // dfs 暴力
    dfs(1, 1);
    cout << ans-1 << endl;
    return 0;
}

标签:arr,23,int,cnt,C++,蓝桥,ans,505,dp
From: https://www.cnblogs.com/Macw07/p/18455275

相关文章

  • codeforces round 974(div.3)E(优先队列实现dijstra算法,devc++的优先队列用greater报
    解题历程:看到两边同时移动,计算最终的相遇时间,我就想到两边同时计算各点到起点的最短距离,就是使用dijstra算法,最后所有节点取两次计算的最大值,再对所有节点取最小值,就是最终答案了,可是这个思路没有考虑有马的情况,思考一番后发现可以多列一个数组记录有马的情况下的行走最短路,然后......
  • C++类
    C++类类//public成员提供类的接口,暴漏给外界,供外界使用//private:提供各种实现类功能的细节方法,但不暴漏给使用者,外界无法使用//注意:struct是成员默认为public的class、class成员默认是privateclassstudent{public:intnumber;charname[100];};c......
  • 实验一 现代C++基础编程
    1.实验任务1task1.cpp1//现代C++标准库、算法库体验2//本例用到以下内容:3//1.字符串string,动态数组容器类vector、迭代器4//3.函数模板、const引用作为形参56#include<iostream>7#include<string>8#include<vector>9#include<algorithm>......
  • 实验1 现代C++编程初体验
    实验任务1:task1.cpp:1//现代C++标准库、算法库体验2//本例用到以下内容:3//1.字符串string,动态数组容器类vector、迭代器4//2.算法库:反转元素次序、旋转元素5//3.函数模板、const引用作为形参67#include<iostream>8#include<string>......
  • 实验1 现代C++编程初体验
    任务1 task1.cpp1//现代C++标准库、算法库体验2//本例用到以下内容:3//1.字符串string,动态数组容器类vector、迭代器4//2.算法库:反转元素次序、旋转元素5//3.函数模板、const引用作为形参67#include<iostream>8#include<string>......
  • 实验1 现代C++基础编程
    任务1:源代码task1.cpp1#include<iostream>2#include<string>3#include<vector>4#include<algorithm>56usingnamespacestd;78//声明9//模板函数声明10template<typenameT>11voidoutput(constT&c);1213......
  • 20222303 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    1.实验内容在本周的学习中,重新回顾了栈和堆的概念,还学习了安全漏洞的相关概念,然后聚焦在其中的缓冲区溢出漏洞上,明白了缓冲区溢出的定义及发生的原理,并了解了缓冲区溢出发展历史上的一些经典攻击案例,收获颇丰。在本次的实验中,我掌握了反汇编与十六进制编程器相关知识,同时对NOP,......
  • ROS通信方式之Topic话题与Message消息的关系与C++实现
    ros由于其分布式模块化的设计理念,会将一个完整任务分解成多个节点去实现,这些节点之间的协作通过topic话题和message消息.相关概念有节点(Nodes):节点是一个可执行文件,它可以通过ROS来与其他节点进行通信。消息(Messages):订阅或发布话题时所使用的ROS数据类型。话题(Topics):节点可以将......
  • 【C++】string (STL)
    string介绍字符串是表示字符序列的类标准的字符串类提供了对此类对象的支持,其接口类似于标准字符容器的接口,但添加了专门用于操作单字节字符字符串的设计特性。string类是使用char(即作为它的字符类型,使用它的默认char_traits和分配器类型(关于模板的更多信息,请参阅basic_s......
  • 【C++】类和对象(3)(默认成员函数--拷贝构造&赋值重载)
    引言前文介绍了C++中默认成员函数中的构造函数和析构函数,相信已经对它们的功能与用法有了基本认识,本文接着介绍也很常见的拷贝构造函数和赋值重载函数,便于对C++进一步的学习。拷贝构造函数补充知识:深浅拷贝深拷贝和浅拷贝是C++中对象拷贝的两种不同方式。浅拷贝是指将......