2024年3月11日 算法刷题记录

2024年3月11日

习题 2.4 Repeater(北京大学复试上机题)

链接

题目大意

给你一个仅包含一种字符和空格的模板,模板显示如何创建无尽的图片,将字符用作基本元素并将它们放在正确的位置以形成更大的模板,然后不断进行该操作。

样例

输入:
3
# #
 # 
# #
1
3
# #
 # 
# #
3
4
 OO 
O  O
O  O
 OO 
2
0

输出:
# #
 # 
# #
# #   # #         # #   # #
 #     #           #     # 
# #   # #         # #   # #
   # #               # #   
    #                 #    
   # #               # #   
# #   # #         # #   # #
 #     #           #     # 
# #   # #         # #   # #
         # #   # #         
          #     #          
         # #   # #         
            # #            
             #             
            # #            
         # #   # #         
          #     #          
         # #   # #         
# #   # #         # #   # #
 #     #           #     # 
# #   # #         # #   # #
   # #               # #   
    #                 #    
   # #               # #   
# #   # #         # #   # #
 #     #           #     # 
# #   # #         # #   # #
     OO  OO     
    O  OO  O    
    O  OO  O    
     OO  OO     
 OO          OO 
O  O        O  O
O  O        O  O
 OO          OO 
 OO          OO 
O  O        O  O
O  O        O  O
 OO          OO 
     OO  OO     
    O  OO  O    
    O  OO  O    
     OO  OO     

解法

很显然,这里需要用到递归。其次,由于图形复杂,需要一个数字用来缓存图形,我们一点一点填进去。

大的绘图由小的模块组成,每个小的模块都可以再次拆分,直到每个小的模块只剩下单个字符,因此考虑使用递归。递归考虑为给定当前的模块的起始绘图区域,指定符号,交给下一个递归去绘制;空白,则直接绘制。

空白似乎也可以当作一种符号,没有必要分开处理

递归表达式:
d r a w ( d e p t h , x , y ) = { a n s [ x + i ] [ y + j ] = t e p [ i ] [ j ] ( d e p t h = = 1 ) d r a w ( d e p t h − 1 , x + i ∗ s i z e , y + j ∗ s i z e ) ( d e p t h > 1 ) \left. draw(depth,x,y)=\left\{\begin{aligned}&ans[x+i][y+j]=tep[i][j] &&(depth==1)\\&draw(depth-1,x+i*size,y+j*size) &&(depth >1)\end{aligned}\right.\right. draw(depth,x,y)={ans[x+i][y+j]=tep[i][j]draw(depth1,x+isize,y+jsize)(depth==1)(depth>1)
其中, i , j ∈ [ 0 , N ) , s i z e = p o w ( N , d e p t h − 1 ) i,j\in [0,N),size=pow(N,depth-1) i,j[0,N),size=pow(N,depth1) a n s ans ans 是目标图形, t e p tep tep 是模板图形

代码

#include <iostream>
#include <cmath>

using namespace std;

int N, q;
char tep[3001][3001];
char ans[3001][3001];

void blank(int deep, int bx, int by) {
    for (int i = 0; i < pow(N, deep); i ++ ) {
        for (int j = 0; j < pow(N, deep); j ++ ) {
            ans[bx+i][by+j] = ' ';    
        }
    }
}

void pic(int bx, int by) {
    for (int i = 0; i < N; i ++ ) {
        for (int j = 0; j < N; j ++ ) {
            ans[i+bx][j+by] = tep[i][j];
        }
    }
}

void help(int deep, int bx, int by) {
    if (deep == 1) {
        pic(bx, by);
        return;
    }
    for (int i = 0; i < N; i ++ ) {
        for (int j = 0; j < N; j ++ ) {
            int nx = i * pow(N, deep-1);
            int ny = j * pow(N, deep-1);
            if (tep[i][j] == ' ') {
                blank(deep-1, bx+nx, by+ny);    
            }
            else {
                help(deep-1, bx+nx, by+ny);
            }
        }
    }
}

int main() {
    while (cin >> N) { // 注意 while 处理多个 case
        if (N == 0) break;
        getchar();
        for (int i = 0; i < N; i ++ ){
            for (int j = 0; j < N; j ++ ) 
                scanf("%c", &tep[i][j]);
            getchar();
        }

        cin >> q;
        help(q, 0, 0);
        int size = pow(N, q);
        for (int i = 0; i < size; i ++ ) {
            for (int j = 0; j < size; j ++ ) {
                printf("%c", ans[i][j]);
            }
            cout << '\n';
        }
    }
}
// 64 位输出请用 printf("%lld")

AcWing 动态规划 第一讲 数字三角形模型

基础

image-20240311212835052

着重学习了 DP 的思考方式——基于集合的思考

image-20240311213057095

计算顺序——拓扑序

方格取数

设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:

2.gif

某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。

在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。

此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。

输入格式

第一行为一个整数N,表示 N×N 的方格图。

接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。

行和列编号从 11 开始。

一行“0 0 0”表示结束。

输出格式

输出一个整数,表示两条路径上取得的最大的和。

数据范围

N≤10

输入样例:
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出样例:
67
分析:

第一反应是两次 DP,但是经弹幕提醒,这样是不行的。这样属于贪心的思路,但是无法证明这样是对的,没有办法说明最优解是两个最大值的和(就好像一个集合最大值不能分解成两个子集的最大值的和)

正解是一次 DP:

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

核心问题:

  1. 走两次?—— 用一个状态统一,变成同时走
  2. 不能重复选?—— 体现在状态转移时,走到同一个点只做一次加法

状态表示:一个人分身,同时从起点出发走k步,分别走到(i1, k-i1), (i2, k-i2)时,路径数字之后的最大值。

状态转移:四种可能

代码
#include<iostream>

using namespace std;

const int N = 12;

int a[N][N], f[2*N][N][N];
int n;


int main(){
    cin >> n;
    
    int x, y, z;
    while (cin >> x >> y >> z, x || y || z){
        a[x][y] = z;
    }
    
    for (int k = 2; k <= n + n; k ++ )
        for (int i1 = 1; i1 <= n; i1 ++ ) 
            for (int i2 = 1; i2 <= n; i2 ++ ) {
                int j1 = k - i1, j2 = k - i2;
                if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
                    int t = a[i1][j1];
                    if (i1 != i2) t += a[i2][j2];
                    
                    int &x = f[k][i1][i2];
                    x = max(x, f[k-1][i1-1][i2-1] + t);
                    x = max(x, f[k-1][i1-1][i2] + t);
                    x = max(x, f[k-1][i1][i2-1] + t);
                    x = max(x, f[k-1][i1][i2] + t);
                }
            }
            
    cout << f[n+n][n][n] << endl;
    return 0;
}

要点

  1. 三维 DP,实质上利用了步数相同进行了降维。
  2. 输入中,while 的用法
  3. 循环从 k 开始,逻辑更加清晰,便于计算j1,j2
  4. 利用 t 表示两种情况
  5. 利用引用 x 简化代码
  6. 利用 4 个 max 函数求 4 种情况的最大值

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/453523.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Windows C++ 使用WinAPI实现RPC

demo下载地址&#xff1a;https://download.csdn.net/download/2403_83063732/88958730 1、创建IDL文件以及acf文件&#xff08;创建helloworld.idl helloworld.acf&#xff09; 其中IDL文件&#xff1a; import "oaidl.idl"; import "ocidl.idl"; [ …

AI日报:一个新的“科技超级周期”正在出现

文章目录 技术周期预测可连接设备 技术周期 未来学家艾米韦伯表示&#xff0c;人工智能和其他两种通用技术将迎来一个新的“技术超级周期”&#xff0c;预计将在经济中创造“实质性和持续性”的变化。 她在SXSW 2024上表示&#xff0c;过去的科技超级周期是由通用技术引发的&…

鸿蒙开发之快速入门

一:下载开发工具 鸿蒙的开发工具叫DevEco 下载点击 其他部分都一直next 就行,这个页面出现的install 建议都点击install 然后单独选择安装目录 可能存在的问题 就是之前安装nodejs&#xff08;比如自己开发web或者RN等情况&#xff09;版本低 等情况 所以建议你单独安装一次 …

【数学】【C++算法】780. 到达终点

作者推荐 视频算法专题 本文涉及知识点 数学 LeetCode780. 到达终点 给定四个整数 sx , sy &#xff0c;tx 和 ty&#xff0c;如果通过一系列的转换可以从起点 (sx, sy) 到达终点 (tx, ty)&#xff0c;则返回 true&#xff0c;否则返回 false。 从点 (x, y) 可以转换到 (x…

Go语言中的锁与管道的运用

目录 1.前言 2.锁解决方案 3.管道解决方案 4.总结 1.前言 在写H5小游戏的时候&#xff0c;由于需要对多个WebSocket连接进行增、删、查的管理和对已经建立连接的WebSocket通过服务端进行游戏数据交换的需求。于是定义了一个全局的map集合进行连接的管理&#xff0c;让所有…

Netty架构详解

文章目录 概述整体结构Netty的核心组件逻辑架构BootStrap & ServerBootStrapChannelPipelineFuture、回调和 ChannelHandler选择器、事件和 EventLoopChannelHandler的各种ChannelInitializer类图 Protocol Support 协议支持层Transport Service 传输服务层Core 核心层模块…

操作系统内功篇:硬件结构之CPU是如何运行的?

本文分5个小结&#xff0c;分别是图灵机工作方式&#xff0c;冯诺依曼结构&#xff0c;总线线路位宽和CPU位宽&#xff0c;程序执行的基本过程&#xff0c; a12的具体执行过程。 一 图灵机的工作方式 图灵机由纸带&#xff0c;读写头组成。读写头上有一些部件例:存储单元&#…

嵌入式驱动学习第三周——linux内核链表

前言 在 Linux 内核中使用最多的数据结构就是链表了&#xff0c;其中就包含了许多高级思想。 比如面向对象、类似C模板的实现、堆和栈的实现。 嵌入式驱动学习专栏将详细记录博主学习驱动的详细过程&#xff0c;未来预计四个月将高强度更新本专栏&#xff0c;喜欢的可以关注本博…

智能指针的讲解

1.为什么要智能指针 首先我们分析一段代码&#xff1a; 1、如果p1这里new 抛异常会如何&#xff1f; 2、如果p2这里new 抛异常会如何&#xff1f; 3、如果div调用这里又会抛异常会如何&#xff1f; int div() {int a, b;cin >> a >> b;if (b 0)throw invalid_ar…

CVE-2024-2074 SpringBoot迷你天猫商城Mini-Tmall sql注入漏洞分析

漏洞简介 Mini-Tmall是一个基于Spring Boot的迷你天猫商城。Mini-Tmall在20231017版本及之前存在一个严重的漏洞&#xff0c;攻击者可以利用该漏洞通过远程执行特定操作来注入恶意SQL语句&#xff0c;从而获取敏感信息或控制数据库。此漏洞影响文件?rtmall/admin/user/1/1的一…

下载API文档

在线看&#xff1a;Overview (Java SE 17 & JDK 17) 离线下载&#xff1a;Java Development Kit 17 Documentation

Python 单元测试

本篇为Python的单元测试的方法及示例 目录 概念 结果 示例 对函数进行测试 创建函数文件 创建测试文件 测试结果 对类进行测试 创建待测试类 创建测试文件 文档测试 创建函数 进行测试 总结 概念 用来对一个函数、一个类或者一个模块来进行正确性校验工作 结果 …

为什么选择线上展览馆,搭建线上展览馆要注意什么

引言&#xff1a; 线上展览馆是一种利用互联网技术&#xff0c;将实体展览馆的展示内容以数字化形式呈现出来的在线观展方式。它打破了时间和空间的限制&#xff0c;使得更多的人可以随时随地参观展览&#xff0c;领略文化的魅力。 一、线上展览馆的优势 1.成本效益高&#x…

【安卓】Android开发入门 你的第一个apk应用

本文介绍如何写一个入门的安卓apk应用, 以嵌套一个网页为例。 开发ide&#xff1a;Android studio 语言&#xff1a;Kotlin tips: 最好别下载新版本的 Android studio &#xff0c;因为新版的界面有所改动 遇到问题去网上搜 新手刚入门可能界面都找不到在哪里&#xff1b;其次…

05-延迟任务精准发布文章-黑马头条

延迟任务精准发布文章 1)文章定时发布 2)延迟任务概述 2.1)什么是延迟任务 定时任务&#xff1a;有固定周期的&#xff0c;有明确的触发时间延迟队列&#xff1a;没有固定的开始时间&#xff0c;它常常是由一个事件触发的&#xff0c;而在这个事件触发之后的一段时间内触发…

银河麒麟V10SP3操作系统-网络时间配置

1、动态网络配置 打开终端&#xff0c;以网口 eth0 为例&#xff1a; nmcli conn add connection.id eth0-dhcp type ether ifname eth0 ipv4.method auto其中“eth0-dhcp”为连接的名字&#xff0c;可以根据自己的需要命名方便记忆和操作 的名字&#xff1b;“ifname eth0”…

Realsense 相机SDK学习(一)——librealsense使用方法及bug解决(不使用Ros)

一.介绍 realsense相机是一个intel开发出来的一款深度相机&#xff0c;我之前使用他来跑过slam&#xff0c;也配置过他的驱动&#xff0c;在此附上realsense的相机驱动安装方法&#xff1a;Ubuntu20.04安装Intelrealsense相机驱动&#xff08;涉及Linux内核降级&#xff09; …

redis-操作数据库

0 序言 一个Redis服务器可以包含多个数据库。在默认情况下&#xff0c;Redis服务器在启动时将会创建16个数据库&#xff1a;这些数据库都使用号码进行标识&#xff0c;其中第一个数据库为0号数据库&#xff0c;第二个数据库为1号数据库&#xff0c;而第三个数据库则为2号数据库…

Leetcode101对称的二叉树

如何去检查对称&#xff1f; 思路是check(n1->left,n2->right)&&check(n1->right,n2->left) 直接手算这题&#xff0c;该懂就懂了&#xff01; /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* Tre…

【一】【设计模式】类关系UML图

1. 继承&#xff08;Generalization&#xff09; 继承是对象间的一种层次关系&#xff0c;允许子类继承并扩展父类的功能。 UML线&#xff1a;带有空心箭头的直线&#xff0c;箭头指向基类&#xff08;父类&#xff09;。 class Parent {public void parentMethod() {System.…