logo
publist
写文章

简介

该用户还未填写简介

擅长的技术栈

可提供的服务

暂无可提供的服务

UVa 12881 Ricochet Robots

本文探讨了一个多机器人运输问题的解法,要求在矩形网格中通过滑动移动将特定机器人引导至目标位置,且移动次数不超过限定值。使用广度优先搜索(BFS)遍历状态空间,其中状态由各机器人位置组成。移动模拟遵循"遇障碍停止"的规则,目标格不视为障碍物。通过枚举每个机器人的四个移动方向生成新状态,利用集合去重避免重复搜索。算法在限定步数内返回最优解,否则判定无解。代码实现中处理了输入解析、状态转移和边界条件,适

文章图片
#算法
UVa 11156 Continuous Drawing

题目要求在5×5单位网格上不抬笔连续绘制给定线段,求最少墨水用量。每条线段需拆分为相邻整数点间的单位线段,构建无向图。解题步骤包括:检查图的连通性,处理奇度顶点配对以形成欧拉路径,计算最短重复路径长度。若图不连通或无法形成欧拉路径则输出~x(,否则输出总墨水用量(原始线段总长加重复路径长)。样例1通过奇度顶点配对得到8.24,样例2因不连通输出~x(。

文章图片
#算法
UVa 101 The Blocks Problem

本文分析了机器人手臂在方块世界中的操作模拟问题。题目给出了五种操作命令,包括移动单个方块或整个堆栈到指定位置。解题思路采用二维数组存储方块堆栈,实现了归位操作、位置查找以及四种移动操作。算法时间复杂度为O(mn),空间复杂度O(n²)。代码通过初始化状态、处理命令和输出结果三个步骤,准确模拟了方块操作过程。关键点在于理解每种操作的具体含义并正确处理无效命令,保证程序的正确性和鲁棒性。

文章图片
#算法#c++#青少年编程
UVa 13214 The Robot‘s Grid

本文探讨了机器人在发光网格上的路径计数问题。通过分析机器人仅能右转和直走的限制,发现所有合法路径实际上都是由向上和向右移动组成的单调路径,从而将问题转化为计算组合数。具体解法是预处理杨辉三角,直接输出C(R+C-2, R-1)。该算法时间复杂度为O(50^2 + T),空间复杂度O(50^2),巧妙利用数学性质避免了暴力搜索的高复杂度。

文章图片
#算法#青少年编程
UVa 967 Circular

本题的关键在于高效地判断循环素数并快速回答范围查询。通过欧拉筛法预处理素数,然后对每个素数检查其所有循环移位是否都是素数。循环移位的计算通过数值操作完成,避免了字符串转换的开销。使用二分查找在有序素数数组中快速判断一个数是否为素数。最后,通过前缀和数组实现O1O(1)O1的范围查询。整体算法在给定数据规模下运行效率高,时间复杂度约为OMAXNπMAXN×LOMAXNπMAXN×L,空间复杂度为OM

文章图片
#算法
UVa 12040 Again Lucky Numbers

该题目要求计算不包含给定不吉利数字 $M$ 作为子串的 $N$ 位数的个数。通过构建基于 KMP 自动机的动态规划方法,可以高效解决这一问题。具体步骤包括:1) 构建 KMP 自动机转移表;2) 使用动态规划递推允许前导零的数字串数目;3) 通过容斥处理首位为零的情况得到最终答案。该方法的时间复杂度为 $O(T \cdot N \cdot |M| \cdot 10)$,适用于题目给定的约束条件。

文章图片
#算法#青少年编程
UVa 1622 Robot

题目要求在N×M网格中,所有机器人按四种方向指令移动,移出网格的机器人被摧毁。目标是合理安排指令顺序,使机器人执行指令的总次数最大化。关键在于优先执行不增加历史跨度的配对指令(如NORTH-SOUTH交替),再处理剩余单向指令。通过贪心策略比较行列剩余空间,每次选择收益更大的方向执行。算法复杂度为O(总指令数),适用于大规模输入。样例中,当优先执行配对指令时,总执行次数达到最大。

文章图片
#算法#青少年编程
UVa 731 Numerical Summation of a Series

本文讨论如何高效计算级数ψ(x)=∑(k=1→∞)1/[k(k+x)]在x=0.0到300.0范围内的值,要求相对误差小于10⁻¹⁰。直接计算会遇到收敛慢和舍入误差问题。通过将ψ(x)转化为digamma函数ψ(x)=[γ+digamma(x+1)]/x,其中γ为欧拉常数,并利用递推关系和大x渐近展开式进行高效计算。对于x=0,直接取ψ(0)=π²/6。算法使用long double保证精度,输出

文章图片
#算法#青少年编程
UVa 11253 Fractal

本文探讨了龙曲线(Dragon Curve)分形路径下机器人移动坐标的计算问题。给定递归生成的二进制字符串序列 ( s_n ),机器人根据字符串指令移动和转向。由于直接模拟 ( n ) 步(( n \leq 10^9 ))不可行,我们利用分形结构的自相似性设计递归算法:预计算各层级完整路径的位移和方向,再通过分解问题规模快速求解任意时刻的坐标。核心在于递归处理路径前缀时,结合向量运算和方向旋转,将

文章图片
#算法#青少年编程
The Pragmatic Programmer 读书笔记之一 DRY-Don’t Repeat Youself

The PragmaticProgrammer读书笔记之一DRY-Don’t RepeatYouself 虽然自己买了很多软件工程方面的书,但是因为时间的问题,一直没有静下心来充充电。最近因为感觉自己在编程方面迫切需要有进一步的提高,于是打算好好的研读一下AndrewHunt和David Thomas合著的《ThePragmatic Prog

#软件工程
    共 95 条
  • 1
  • 2
  • 3
  • 10
  • 请选择