学习笔记_25_03_12

学习笔记_25_03_12

本次笔记将分为两部分，Python练习（全部来源于洛谷）和PHP语法学习

Reference

Python练习

P2404 自然数的拆分问题

题目描述

任何一个大于 $1$ 的自然数 $n$，总可以拆分成若干个小于 $n$ 的自然数之和。现在给你一个自然数 $n$，要求你求出 $n$ 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式

输入：待拆分的自然数 $n$。

输出格式

输出：若干数的加法式子。

输入输出样例 #1

输入 #1
1
7
输出 #1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

说明/提示

数据保证，$2\leq n\le 8$。

问题解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def MyPrint(t):
    for i in range(1, t):
        print(a[i], end='+')
    print(a[t], end='\n')

def dfs(s, t): # s表示要拆分的数，t来确定a数组的索引
    for i in range(a[t-1], s+1):
        if i < n: # 防止输出n自身
            a[t] = i
            s -= i
            if s == 0:
                MyPrint(t)
            else:
                dfs(s, t+1)
            s += i  # 进行回溯以输出所有可能的结果


if __name__ == '__main__':
    n = int(input())
    a = [1] * 1000 # 开辟储存拆分结果的数组

    dfs(n, 1)

P1596 [USACO10OCT] Lake Counting S

题目描述

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.

输入格式

Line 1: Two space-separated integers: N and M * Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

输出格式

Line 1: The number of ponds in Farmer John’s field.

输入输出样例 #1

输入 #1
1
2
3
4
5
6
7
8
9
10
11
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出 #1
1
3

说明/提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
sys.setrecursionlimit(10000 + 13)  #限制递归层数，否则有一个点RE

dir_x = [-1, -1, -1, 0, 0, 1, 1, 1]
dir_y = [-1, 0, 1, -1, 1, -1, 0, 1]

def dfs(x, y):
    geo[x][y] = '.'
    for i in range(8):
        nx = x + dir_x[i]
        ny = y + dir_y[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= m or geo[nx][ny] == '.':
            continue
        dfs(nx, ny)


if __name__ == '__main__':
    n, m = map(int, input().split())
    geo = [['' for i in range(101)] for i in range(101)]
    for i in range(n):
        string = input()
        for j in range(m):
            geo[i][j] = string[j]

    count = 0
    for i in range(n):
        for j in range(m):
            if geo[i][j] == 'W':
                dfs(i, j)
                count += 1

首先要介绍的是setrecursionlimit()函数，这个函数可以用来设置最大递归深度，可以用来避免RuntimeError: Maximum recursion depth exceeded类型的报错。

其次是想写一些我对P1596类型题目的理解，这些问题的本质其实都是染色问题，题目要求出的不是路径或解决方案的个数，而是“色块”的个数，这个时候就往往只需要有搜索并标记的过程而不需要有回溯的步骤，类似的题目还有P1101 单词方阵和P1162 填涂颜色。

而关于求解决方案数的题目，例如迷宫中点与点之间有多少种路可以走、一个数字能有多少种拆分和的方法等，这些问题往往都可以用树来表示，那么在我们进行深度优先搜索的时候，我们往往需要在一条枝干上走到头的时候重新走到另一条枝干上，这种时候我们就需要进行回溯。这种类型的题目有P1605 迷宫和P2404 自然数的拆分问题等。

PHP学习

NULL合并运算符

NULL合并运算符会判断变量是否存在且值不为NULL，如果是，它将返回自身的值，否则将返回它的第二个操作数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?php
// 获取 $_GET['site'] 的值，如果不存在返回 '菜鸟教程'
$site = $_GET['site'] ?? '菜鸟教程';

print($site);
print(PHP_EOL); // PHP_EOL 为换行符


// 以上代码等价于
$site = isset($_GET['site']) ? $_GET['site'] : '菜鸟教程';

print($site);
print(PHP_EOL);
// ?? 链
$site = $_GET['site'] ?? $_POST['site'] ?? '菜鸟教程';

print($site);
?>

// 输出：
// 菜鸟教程
// 菜鸟教程
// 菜鸟教程

$errors数组的使用

完整表单的验证

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
include_once 'includes/header.php';
$errors = [];

if(isset($_POST['submit']))
{
    // 点击"Submit"按钮之后就到了这一步
    // 如果下边代码为空的话页面将会崩溃
    if(count($errors == 0))
    {
        // 如果没有错误就正常运行，处理表单数据
    }
    else
    {
        // 如果有错误就重新加载表单，重新输入正确数据
        include_once 'includes/data_form.php';
    }
}
else
{
    include_once 'includes/data_form.php';
}
include_once 'includes/footer.php';

// 不难发现其实所有要被引用的文件都不会丢失
// 这样写的好处是相当于写了个While True循环直到问题被解决为止

报错功能的实现

如果在有需求的输入场景下，例如表单中要求用户输入自己的姓名，但他输入了一串数字，这显然是不能接受的，我们需要通过一种方式来提醒他按照目标格式进行输入。那么我们就要尝试实现报错功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
$errors = []; //创建一个error数组用来存储错误信息
if(isset($_POST['submit']))
{
    $fname = trim($_POST['fname']??''); // 在不输入特定字符的情况下，trim()函数用来删除字符串两侧的空格
    if(strlen($fname) == 0)
    {
        $errors['fname'] = 'Missing the first name!';
    }
    else if(!ctype_alpha($fname)) // Ctype是PHP中实现判断字符串类型的函数
    {
        $errors['fname'] = 'Please enter alpha charactors!';
    }
}

在实际应用中我们可以将PHP嵌入到HTML当中：

1
2
3
4
5
6
7
8
<label>First Name:
    <span class="error">
        <?=$errors['fname']??'';?>
    </span>
</label>
<input type="text" name="fname" maxlength="30" value="<?=$fname??'';?>" />
// 在HTML当中，input标签中的value属性的用法是与type属性紧密相关的
// 详细用法请移步Reference中给出的友情链接

ClassActivity 3：

学习笔记
#dfs #python #洛谷
学习笔记_25_03_12
http://example.com/2025/03/12/note05/
作者
谢斐
发布于
2025年3月12日
许可协议