方格取数与传纸条-双人网格路径问题

24年在洛谷刷刷题,遇到过一个双人路径问题,P1004 [NOIP 2000 提高组] 方格取数,题解的4维数组对于博主这样一个菜鸟,实在难以理解,于是就搁置了。然而25年的时候又遇到了P1006 [NOIP 2008 提高组] 传纸条这样一个题目,于是死去的记忆突然开始攻击我。结合题解,尝试自己画了几张图帮助理解,也分享在博客里。

方格取数与传纸条-双人网格路径问题

假设两个人同时从1,1位置出发,第一个人用绿点表示,第二个人用红点表示,可以发现,两个人走同样多的步数之后,他们的落点必然会在一条45度的斜线上。这条斜线上的x,y坐标之和始终是相同的。将这个和用变量k来表示的话,两人走出第一步时,k等于3,走出第二步时,k=4,以此类推。

而因为该斜线上的点,单独对比x坐标(或y坐标)均不相同,所以我们可以用一个三维数组来同时表示两个点,比如上图中间的部分,第三步时k值为5,第一个绿点x坐标为4,第二个红点x坐标为3,两个点的位置可以表示为:

5,4,3

方格取数与传纸条-双人网格路径问题

而想要到达[k][i][i],可能会有以下4种途径:
两条路径都从左方移动过来:[k-1][i-1][j-1]
两条路径都从上方移动过来:[k-1][i][j]
第一条路径从上方,第二条路径从左方移动过来:[k-1][i][j-1]
第一条路径从左方,第二条路径从上方移动过来:[k-1][i-1][j]

标签: c++

移动端可扫我直达哦~

推荐阅读

thumbnail 2025-09-05

P1088 [NOIP 2004 普及组] 火星人与康托展开

变进制数我们的目标是把全排列转化成一个变进制数,以方便我们进行加法。对于第 i 根手指,它有 n−i+1 种选择,根据位值原理,要想让每个数对应一个全排列,就要让这一位数是 n−i+1 进制的。那么,整个过程分为三步:将火星数变成变进...

少儿编程 c++

thumbnail 2025-09-04

用C++求全排列的几种方法

交换法交换法的优点:不需要额外的标记数组,空间复杂度更低,代码更简洁。需要注意的是,这个方式生成的全排列并非是字典序。#include <iostream> #include <algorithm> using...

少儿编程 c++

thumbnail 2025-08-30

关于 c++ 中的 unique() 函数

unique() 是C++标准库中一个非常实用的算法,用于去除相邻的重复元素。使用它之前需要先引入必须包含的头文件:#include<algorithm>基本语法#include <algorithm> // ...

少儿编程 c++

thumbnail 2025-08-30

lower_bound 为什么结果要减去数组名

lower_bound 结果减去数组名是为了将返回的迭代器(指针)转换为数组下标(索引)。lower_bound 返回的是一个迭代器(对于数组来说就是指针),指向找到的元素位置。int arr[] = {10, 20, 30, 40,...

少儿编程 c++

thumbnail 2025-08-25

c语言中的 fstream 与 freopen 区别

fstream(C++风格)和 freopen(C风格)都是用于文件输入/输出的工具,但它们在设计理念、用法和灵活性上有根本性的区别。核心概览 特性fstream (C++)freopen (C)所属语言标准C++C编程范式面向对象 ...

少儿编程 c++

thumbnail 2025-08-24

c++面向对象--类的学习笔记

在学习类之前,相信很多人跟博主一样,已经学习过结构体。在 C++ 中,struct 和 class 的区别非常小,几乎只是默认访问权限的不同。默认访问权限/继承权限:struct 的默认成员访问权限和默认继承方式都是 public。c...

少儿编程 c++

thumbnail 2025-08-23

栈上数组和堆上数组

对比表格 特性栈上数组堆上数组内存位置栈内存堆内存声明方式int arr[10];int* arr = new int[10];生命周期所在作用域结束自动释放需要手动delete[]释放大小确定编译时确定(必须是常量)运行时确定(可以...

少儿编程 c++

thumbnail 2025-07-16

二分查找无解为什么用 n+1

二分查找是一种在有序数组中查找特定元素的高效算法。它的基本思想是通过不断地将查找范围减半来快速定位目标元素。然而,在某些情况下,二分查找可能无法找到目标元素,这时就需要处理无解的情况。关于二分查找无解时使用 n+1 的原因,可以从以下...

少儿编程 c++

thumbnail 2025-07-16

关于后缀和的哨兵值

在二分查找结合后缀和(Prefix Sum / Suffix Sum)的问题中,哨兵值(Sentinel Value) 的作用是:处理边界情况(如所有元素都不满足条件时)。防止数组越界访问(如 sum[-1] 或 sum[n+1])。...

少儿编程 c++

thumbnail 2025-02-13

CSP-J/S认证有年龄限制吗

刚在朋友圈看到这则通知,去官网确认了一下属实,个人觉得这是好事,童年该有童年应有的样子。学习计算机科学有益于培养青少年的逻辑思维及用计算机解决实际问题的能力。但是,这需要一定的基础和认知能力,并非越早越好。近年来,参加CCF非专业级软...

少儿编程 c++