惆怅客123-CSDN博客

原创 UVa1457/LA4746 Decrypt Messages

题目要求根据已知参数p,q,a，计算从2000年1月1日00:00:00至今经过x秒的所有可能值，使得x^q ≡ a mod p。当a=0时有唯一解x=0。对于a≠0的情况，需要使用离散对数算法求解高次模方程，涉及原根、大步小步法等数论知识。题目还考虑了闰年和闰秒的特殊时间计算规则。若无解则输出"Transmission error"。测试数据可通过提供的Python脚本生成，而AC代码采用C++实现，包含主要算法步骤和详细的时间格式化输出。

2025-05-31 19:31:51 459

原创 UVa1384/LA3700 Interesting Yang Hui Triangle

本文分析了UVa1384/LA3700题目，要求计算杨辉三角第N+1行中不能被素数P整除的数的个数。核心思路是利用Lucas定理，将组合数分解为P进制各位数字的乘积，若所有位满足条件则该数不被P整除。具体计算时只需将N转换为P进制，每位数加1后相乘，结果模10000并格式化输出前导0。代码简洁高效，时间复杂度为O(logP N)。

2025-05-29 21:57:13 1028

原创 UVa1060/LA2397 Collecting Luggage

本文分析了ICPC 2007世界总决赛E题"Collecting Luggage"的解题思路。题目要求计算人在多边形外以固定速度行走，追赶传送带上匀速运动的行李的最短时间。文章指出标准题解中二分上界设置存在优化空间，建议使用min{d[i]}/vp + perimeter/(vl+vp)作为更精确的上界。此外，提出通过预计算Dijkstra算法优化效率的方法。文章还详细介绍了生成测试数据的算法，重点讲解了如何构造逆时针简单多边形：包括点排序方法、处理特殊情况（如相同斜率）以及调整多边形尾部顺序的技巧。

2025-05-26 01:30:52 256

原创 UVa1075/LA4125 Painter

本文介绍了UVa1075/LA4125 Painter问题的解法。题目要求判断画家在画布上绘制互不相交三角形时需要的颜色层数。采用扫描线算法处理三角形边的事件点，通过动态维护线段集合来检测相交情况。若出现相交则输出ERROR，否则计算颜色层数。关键点在于选择合适的eps阈值（1e-6）进行浮点比较，并使用multimap维护当前活跃线段。算法时间复杂度主要取决于排序和事件处理，适用于大规模数据。

2025-05-20 14:13:22 944

原创 UVa1065/LA3809 Raising the Roof

本文介绍了ICPC 2007世界总决赛题目"Raising the Roof"的解题思路。题目要求计算多个三角形屋顶在俯视时可见部分的总面积，需要考虑遮挡关系。作者指出该题与经典圆面积并问题类似，可采用离散扫描法解决。文章提供了详细的测试数据生成方法，包括三维几何运算避免三角形退化或相交。最后给出了完整的Python测试数据生成脚本，涉及向量叉积、点积、线段相交检测等三维几何计算。该题在OJ上尝试人数较少，本文旨在填补测试数据和可视化方面的空白。

2025-05-08 18:40:26 656

原创 UVa1367/LA3532 Nuclear Plants

本题要求计算矩形领土内可种植大麦的面积，需排除核电厂周围禁区。小核电厂禁区半径0.58公里，大核电厂1.31公里。解法采用离散化扫描法计算圆的面积并，处理多个圆相交情况。关键点包括：消除数值异常、处理圆弧交点、特殊计算单圆弧区域。代码实现中，通过排序和扫描线算法高效计算禁区面积，最后用总面积减去禁区得到可用面积。测试数据验证了算法的正确性。

2025-04-11 16:24:15 285

原创 UVa12303 Composite Transformations

题目要求对三维空间中的点和平面进行一系列变换操作，包括平移、旋转和缩放。关键点在于正确实现旋转矩阵变换，并处理平面方程的参数归一化问题。输入可能包含浮点数，需使用double类型接收。平面变换通过三点式求解，选取不共线的三点进行计算。最终输出坐标和归一化的平面方程，允许一定的浮点误差。核心难点在于旋转矩阵的构造和平面变换的数学处理。

2025-03-11 22:24:08 764

原创三维仿射变换矩阵

本文介绍了三维仿射变换矩阵的两种表示形式（3×4和4×4），重点分析了平移、缩放和旋转三种基本变换。给出了平移变换矩阵和缩放变换矩阵的具体公式，详细推导了绕单轴（x、y、z）旋转的变换矩阵及其组合运算，并提供了绕任意轴旋转的变换矩阵公式。其中特别强调了旋转变换矩阵的顺序重要性，并推导了连续旋转的复合变换矩阵。文章还提供了相关参考博客链接，便于读者深入了解旋转变换的详细推导过程。

2025-03-10 22:24:38 1070

原创平面的四种方程及一些应用

本文介绍了平面的四种方程形式：1)点法式方程，通过已知点和法向量确定；2)一般式方程，由点法式推导得出；3)三点式方程，利用不共线三点的混合积为零确定；4)截距式方程，通过坐标轴截距表示。此外还给出了应用示例：从一般式方程中找出三个不共线的平面点。这些方程形式为平面几何问题提供了多种解决方案。

2025-03-10 17:57:52 1034

原创 UVa10572 Black & White

UVa10572 Black & White题目要求在m×n网格中填充黑白格子，满足：1) 任意2×2子网格不全黑或全白；2) 所有黑格和白格各自四连通。输入包含部分已填格子，需输出方案总数和任意一组解。关键解法是插头DP，使用最小表示法处理连通性状态（共1430种状态）。需处理连通分量的新增、合并和消失，特别注意最后两格的情况。代码实现复杂，需处理各种边界条件和状态转移。时间复杂度主要取决于状态数，适用于小规模网格（m,n≤8）。输出时需构造可行解并统计方案总数。

2024-10-14 01:07:37 748

原创 UVa1214/LA3620 Manhattan Wiring

本文介绍了UVa1214/LA3620 Manhattan Wiring问题的解法。题目要求在n×m网格中用不相交的折线连接两对2和3，求最小总长度。采用轮廓线动态规划（插头DP）方法，将问题转化为多阶段决策问题，使用11种积木拼装方式表示状态转移。状态用轮廓线表示，每个位置有3种可能（无线、2线、3线）。代码通过动态规划求解最小长度，无解时输出0。该方法有效处理了状态转移的复杂性和合法性检验。

2024-09-14 12:17:49 366

原创 UVa1389/LA3709 Hard Life

最大密度子图是一种分数规划问题，需要用二分法求解。二分找零点的过程需要建图求最小割，可以转化为最大权闭合子图来求，不过有更好的办法：对原图的边(u,v)从u向v连一条容量为1的边（反向边容量也是1）；源点s向每个结点x连容量为m（原图边数）的有向边；结点x向汇点t连容量为2λ−d x+m的边。

2024-09-06 08:44:52 794

原创 UVa1104/LA5131 Chips Challenge

上下界循环费用流问题：将行i看成结点xi，列j看成结点yj，已经放了芯片的格子(i,j)对应上下界均为1费用为0的有向边i→j，可以放或者不放的格子(i,j)对应容量为1费用为0的有向边xi→yj；yi向xi连容量为inf费用为-1的有向边来满足第i行的总芯片个数等于第i列的约束。

2024-09-06 04:22:04 839

原创 UVa1440/LA4597 Inspection

每个滑坡至少被检查一次，因此本题是容量有下界的网络流求最小流，按照上下界网络流中的有源有汇有容量上下界网络的最小流求解即可。本题首先要添加源点s和汇点t并结合原始边信息建图，然后汇点向源点连无限边形成无源无汇的上下界网络，最后还要附加源S和汇T将其转化成有源有汇有容量上下界网络的最小流。求出最小流后得到了第一个答案，但是还要输出方案，遍历s的出边(s,ui)，若其流量fi非0，则从ui出发有fi条检查路径：沿着流量f≥0（因为要加上下界1）的路径走到t就可以输出一条路径（不需要输出t，并且路径上的每条边流量

2024-09-03 03:49:35 454

原创循环流网络的费用问题

本文介绍了循环流网络的费用问题，重点讲解了含负权边时如何消除负权圈。针对负权边可以取也可以不取以及负权边必须取这两种不同情况在建图处理上的不同做了详细分析并结合实际题目画图帮助理解。

2024-08-30 02:34:05 751 1

原创分数规划问题

分数规划用来求一个分式的极值。形象一点就是，每种物品有两个权值 a 和 b，选出若干个物品使得∑a/∑b最小/最大。分数规划问题的通用解法是二分。

2024-08-28 16:27:19 809

原创差分约束问题

差分约束系统是一种特殊的n元一次不等式组，它包含n个变量 x1,x2,…,xn以及m个约束条件，每个约束条件是由两个其中的变量做差构成的，形如xi−xj≤ck，ck是常数（可以是非负数，也可以是负数）。如果 {a1,a2,…,an}是差分约束系统的一组解，那么对于任意的常数d，{a1+d,a2+d,…,an+d}也是一组解。一般使用Bellman–Ford / SPFA判断图中是否存在负环，最坏时间复杂度为 O(mn)，不存在负环时{d[1],d[2],…,d[n]}就是一组解。

2024-08-28 12:50:37 744

原创 UVa1670/LA5920 Kingdom Roadmap

首先统计叶结点数c，即可知道答案是⌈c/2⌉，然后将叶结点两两配对连边即可，不过注意要优先将不在同一个枝杈的两叶结点配对。可以遍历每个叶结点找出它连接到的枝杈点，这样就统计出了每个枝杈点有哪些叶结点，然后对每一个枝杈点先拿出一个叶结点做配对，其他叶结点存着等后面再任意配对即可。还可以任取一个非叶结点作为根对树做dfs遍历，遍历过程遇到叶结点就存起来，将存起来的叶结点看成循环队列则可以发现属于同一个枝杈点的叶结点处在队列连续的一段。这时候就很容易对叶结点做配对了：将第i个叶结点和第i+⌊c/2⌋个叶结点配对

2024-08-26 22:38:27 611

原创 UVa1667/LA3405 Network Mess

先处理1、2号叶结点，其距离为a[1][2]，则有a[1][2]-1个初始非叶结点，且每个非叶结点i到1、2号叶结点的距离d[i][1]、d[i][2]都知道。再考虑加入3号叶节点多出来的那一个分支：先找出是从初始的a[1][2]-1个非叶结点哪一个结点开始延伸出来的，假设是结点x，则a[1][3]-a[2][3] == d[x][1]-d[x][2]，后面需要再添加a[1][3]-d[x][1]-1个非叶结点，并且新添加的每个非叶结点k到1、2、3号叶结点的距离已知。

2024-08-22 18:44:40 679

原创 UVa1668/LA6039 Let’s Go Green

本题表面是图论题，实际考的是数据结构——并查集。先分析本题的一个简单版本：如果树上只有一个点的度大于1，其余点的度都是1，最少的路径数是多少呢？计所有边权和为s，最大边权为x，思考一下可知最小路径数为max(⌈s/2⌉,x)。考虑每个点i关联的所有边，权和为si，最大边权为xi，则其关联边构成的子图最小路径数为ci=max(⌈si/2⌉,xi)，枚举每条边(u,v,w)，用并查集将两端点各自关联的所有边子图依次合并就可以得出答案，u,v合并的子图最小路径数为cu+cv−w。

2024-08-22 17:48:26 678

原创 UVa1664/LA6070 Conquer a New Region

本题直接思路是：找到边权最小的边(u,v)，记其边权为w，将此边拿掉后变成两棵子树，设两子树的结点数分别为c[u]、c[v]，两子树的最大容量之和分别为d[u]、d[v]，根节点要么在子树u要么在子树v，因此答案为max(c[u]∗w+d[v],c[v]∗w+d[u])，递归处理子树即可求出d[u]、d[v]最终得到答案。但这时候的递归就不好写了，如果主体思路还是上面这样的话，考虑到结点数很大（n≤200000），不超时的方法应该是遍历排序后的树边顺便就把答案求出来了：利用并查集消除递归。

2024-08-20 20:51:33 1049

原创 UVa1662/LA3513 Brackets Removal

先利用栈判定某层括号能否删除：此括号内无+、-运算或者左括号前无*、/ 且右括号后无*、/则可删除（注意删除括号后，其内+、-变成外层括号内的了）；再利用栈处理去括号后运算符的变化并输出结果。去括号规则如下：若A和B是表达式，则A+(B)可变为A+B，A-(B)可变为A-B’，其中B’为B把顶层“+”与“-”互换得到；若A和B为乘法项（term），则A*(B)变为A。B，A/(B)变为A/B’。

2024-08-18 19:19:49 368

原创 UVa1661/LA4047 Equation

本题需要把后缀表达式转化成表达式树然后反复进行等式变换最后解出方程，输出是分数形式，要注意30个字符内的后缀表达式在计算中分子分母可能超出32位整数，因此要用64位整数。题目说“保证不会出现除以常数0的情况，即至少存在一个x，使得f(x)不会除0”说明在不含x的常数表达式运算中不会出现除以0（可以不进行运算合法性检验），但是含x的等式（0×f(x)=p/q, f(x)×0=p/q, 0÷f(x)=p/q）就需要检验了：p≠0时无解，p=0时有多解。

2024-08-15 22:31:35 719

原创 UVa1660/LA3031 Cable TV Network

本题可以用最小割模型建图求解，有意思的是，一开始我想出了直接解法：检测当前图是否只有一个连通分量，若不止一个连通分量则不再需要删点，否则找出要删的点并且删除之，答案计数加1。找出当前要删除的点的贪心想法：找到度最小的点后删除其邻接的度最大的那个点（度最小的点有多个时找他们邻接的度最大的那个点删）。给定一个n（n≤50）个点的无向图，求它的点连通度，即最少删除多少个点，使得图不连通。如下图所示，a）的点连通度为3，b）的点连通度为0，c）的点连通度为2（删除1和2或者1和3）。

2024-08-14 20:01:21 318

原创上下界网络流

上下界网络流的可行流及最大最小流求解，包括：无源无汇有容量上下界网络的可行流、有源有汇有容量上下界网络的可行流、有源有汇有容量上下界网络的最大流、有源有汇有容量上下界网络的最小流

2024-08-12 22:29:14 851

原创二分图匹配灵活运用

本文主要介绍了二分图匹配的灵活运用，包括最小覆盖点方案、增广路算法、最大权匹配、无奇环性质的运用、利用SCC求最大匹配的必须边和可行边以及不同匹配方案的求解方法。通过具体例题和代码实现，展示了二分图匹配在实际问题中的应用和技巧。

2024-07-24 13:59:41 339

原创图论建模技巧搜集

文介搜集了图论建模技巧的经典题目和各种知识点，包括：找可达路径、最小割建模和费用流建模、平面图最小割=对偶图最短路、上下界网络流、循环流网络的费用问题、二分图、差分约束、费用与流量的幂成正比、区间k覆盖问题、混合图的欧拉回路、最大权闭合子图和最大密度子图。

2024-07-16 17:50:24 617

原创 UVa1459/LA4748 Flowers Placement

求二分图字典序第k最大匹配方案，用dfs枚举并剪枝求解。找出每列可以放的花的编号，连边，接着跑一下二分图匹配，看能否完美匹配，如果不能的话，表示无法摆放。跑这个二分图匹配不是白跑的，后面用得上。因为要第k个字典序，所以要枚举每一列所能摆放的花。这里需要一个剪枝，如果当前枚举的列为第j列，往后的j+1到第N列如果无法进行匹配的话，那么就可以剪掉了。

2024-07-11 20:58:08 265

原创 UVa1327/LA2966 King’s Quest

经典问题：已知二分图的一个最大匹配方案，怎么求其他匹配方案。不过作为婚姻问题，本题只有男方有候选列表，女方被动等待分配结果。可以借助有向图强连通分量的Tarjan算法求解（求出所有scc后，如果某男和某女在同一个scc且可以匹配——此女在某男的候选列表，则两者匹配后，其他男女间仍然存在最大匹配方案），说一下建图方法：利用男方候选列表加单向边𝑥𝑖→𝑦𝑗，利用一个完美匹配的方案加单向边𝑦𝑖→𝑥𝑗。

2024-07-11 12:39:42 498

原创 UVa12275/LA4960 Sensor network

本题和UVA1395 Slim Span相同，但数据规模变大，如果依次枚举最小边后跑kruskal更新答案会超时。首先想到了滑动窗口的办法，求一次最小生成树得出初始答案和n-1条边，然后递增最小边形成滑动窗口：将n-1条边中最小边x拿掉，得到两棵树，然后枚举x之后的边加入进来如果构成一棵树则更新答案以及新的最小边，然后继续滑动。这样做虽然最小边总在前进，但是枚举的过程中有回溯，时间复杂度介于𝑂(𝑚𝑛)和𝑂(𝑚^2)之间。对kruskal求解过程加以改造可得到复杂度稳定为𝑂(𝑚𝑛)的算法。

2024-07-05 14:18:06 1011

原创 UVa1265/LA4848 Tour Belt

首先可以想到如果最大权边唯一，那么其两端点构成的子图是候选子图，否则要看沿两端点延伸的其他边对应的端点是否要包含到候选子图中，找到初始候选子图容易想到将其缩成一点继续迭代，不过这样在本题的数据规模下会超时。仔细分析以上缩点迭代的过程，其实就是边权从大到小排序后求最大生成树（也可以是森林）的过程，当前边合并进来后，检查其所在的连通分量是否满足候选子图的要求然后更新答案计数即可。不过这种做法其实复杂度为𝑂(𝑚𝑛)，感觉数据刁钻一点的话也会超时，没想到提交AC了并且才几十毫秒。

2024-07-05 12:59:47 596

原创 UVa1321/LA2925 Dice contest

sample数据和uDebug上标程的输出不一致。骰子不管在哪个网格，有24种状态，乘上行数4，总共96，起点到终点的横坐标跨度𝑑𝑥可能很大，考虑稀疏表可将复杂度优化到𝑂(96^3 log𝑑𝑥)：记𝑎[𝑦1][𝑠1][𝑦2][𝑠2][𝑖]表示骰子在第𝑦1行状态为𝑠1，翻转到第𝑦2行状态为𝑠2且横向移动量为2^𝑖（1≤𝑦1,𝑦2≤4,0≤𝑠1,𝑠2

2024-07-01 12:26:24 886

原创 UVa1311/LA2666 Servers

本题其实是Dijkstra加一点优化，可将复杂度优化到𝑂(𝑎𝑛𝑠 log𝑛)，但仍然可以出卡O(n^2 logn)的数据导致tle。说一下优化方法：对服务器按rank从大到小排序，记𝑒𝑖为排名比i大的所有结点到i的最小距离，依次枚举排序后的服务器作为Dijkstra求最短路的起点，Dijkstra的松弛条件增加𝑑𝑣

2024-06-26 17:34:05 416

原创 UVa12227/LA4618 Wormholes

由于穿过虫洞后时间的迁移量d可能为负数，一旦经过某虫洞存在负圈，那么即便首次到达虫洞入口的时间晚于其形成时间t，只要绕着此圈不停地来回，到达虫洞两端点的最早时间将回退到t和t+d。因此只要预处理虫洞，看每个虫洞是否能找出负圈，如果能找到负圈那么达到虫洞两端的最早时间为𝑡𝑠=𝑚𝑖𝑛(𝑆𝑎𝑠,𝑡)和𝑚𝑖𝑛(𝑡𝑠+𝑆𝑠𝑒,𝑡+𝑑)。预处理之后，跑一边Bellman Ford就能得到答案。

2024-06-19 19:02:30 736

原创 UVa1516/LA5906 Smoking gun

题目原文已经对sample做了解释，可以想到构建差分约束求解：ti − tj < sqrt((xj−xk)^2+(yj−yk)^2) − sqrt((xi−xk)^2+(yi−yk)^2)。这和一般的差分约束不太一样，一般的差分约束不等式带等号，无解等价于有向图存在负权圈，这里差分约束不带等号，那么0权圈也是无解的。并且本题有解时还需要判断拓扑排序结果是否唯一，考虑顶点数n并不大（2≤n≤100），可以用Floyd算法预处理之后，有0权圈或负权圈（即w[i][i]≤0）则无解，有解时利用dp找最长路。

2024-06-17 12:02:53 366

原创 UVa1348/LA3310 Tomato Automata

首先构建有向图判断程序是否可以死循环，只需要从顶点1出发跑tarjan算法看是否能找到双连通分量。建图时把loop命令当成pass命令，对于ifgo、pass、loop建边𝑖→𝑖+1（注意i=n时，𝑛→1)，对ifgo、jump建边𝑖→𝑥。没有死循环时求起点为1的最长路，分析下Dijkstra、Bellman_Ford、SPFA都用不上，根据题目交代的对循环的限制，其实有复杂度𝑂(𝑛)的直接解法：备忘录dp。

2024-06-14 12:22:07 919

原创 UVa1116/LA2429 Puzzle

本题目其实是要区分哪些边是原凸多边形的外边，哪些边是内边（对角线）。仔细分析选出的对角线互不相交这个条件，就能找到突破口：一定至少有两个顶点的度为2。

2024-06-07 11:56:49 948

原创 UVa1310/LA2664 One-way traffic

在每个点双连通分量内，各顶点间双向可达，意味着每个点的出度和入度均非0，那么对这个分量的原始所有有向边做一个遍历可以算出每个顶点的出度入度。然后对于出度入度至少有一者为0且只有一条双向边可选的顶点先处理（此时双向边的改造结果唯一确定）。最后剩下的顶点再依次遍历时，若其出度为0，则可选首条关联无向边改向补偿出度向并对另一端的顶点更新入度即可，这时候可能入度也为0，则继续找第二条边改向。像这样处理后，已经保证了双向可达，但可能仍然有部分无向边没使用到，这些边任意选定一个方向即可。

2024-06-05 14:28:00 441

原创 UVa12273/LA4958 Palindromic DNA

对每个子序列，要满足回文形式，则必然是原DNA序列某些位置最终要变成相同的，这可以用并查集处理。然后考虑每个集合里面原始的不同碱基情况：如果四种都有，显然无法修改，无解；如果有三种，或者有两种并且是相对碱基（AT/GC），则一定要把相对碱基都做修改；如果有两种并且是相邻碱基，则一定要修改一个并且另外一个不能修改；如果只有一种，则已经是回文形式，无需修改。

2024-06-02 17:28:32 794

原创 UVa11604 General Sultan

很好的一道图论建模题目！将每个模式串的每一个字符看成一个结点，并额外增加起点s、终点t两个虚拟结点。首先起点与每个模式串的首字母连一条有向边。对于第i个模式串，考虑其第ℎ个字符开始的子串（对应节点u），若其与第j个模式串做匹配（注意ℎ=0时，𝑗≠𝑖）满足至少一者匹配到结尾，则连有向边：两者都匹配完，𝑢→𝑡；模式串j的首个未匹配节点是v，𝑢→v；子串h的首个未匹配节点是w，𝑢→w。

2024-05-29 21:14:54 2238