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     

解法

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

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

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

递归表达式：
$$draw(depth,x,y)=\{\begin{array}{rlrl}& ans[x+i][y+j]=tep[i][j]& & (depth==1)\\ & draw(depth-1,x+i\ast size,y+j\ast size)& & (depth>1)\end{array}$$
其中，$i,j\in [0,N),size=pow(N,depth-1)$，$ans$ 是目标图形，$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 动态规划 第一讲 数字三角形模型

基础

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

计算顺序——拓扑序

方格取数

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

某人从图中的左上角 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 种情况的最大值