- 博客(53)
- 资源 (5)
- 收藏
- 关注
RSS订阅原创 UVa1313/LA2693 Ghost Busters
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 非常具有挑战性的一道好题，涉及坐标变换，求圆锥曲线的截面椭圆，求两个椭圆交点，解三次方程。
2024-04-14 09:09:45
661
原创 圆锥曲线标准形式和齐次式（一般式）之间的参数转换的推导与结论
基于坐标转换对椭圆、双曲线、抛物线三种不同的圆锥曲线分别逐步推导出标准形式和齐次式之间的参数转换等式，并给出了一份C++程序实现
2024-04-12 15:19:20
315
原创 求两个二次曲线交点的理论依据和编程实践
最近遇到求两个椭圆交点的的问题，一番搜索发现利用线性代数的二次型（Quadratic form）相关知识可解，于是做了Python和C++两个版本的编程实践。
2024-04-12 00:08:33
941
原创 一元三次/一元二次方程求数值解C++编程实践
一元三次方程求解目前最简明的、最直观的方法是：盛金公式法。这是80年代中国中学数学教师范盛金的研究成果，体现了体现了数学的有序、对称、和谐与简洁美。一元三次方程求数值解涉及判别式Δ与0比大小，求三角反三角以、求平方根和求立方根，因此C++编程涉及两个细节：1、考虑浮点运算精度问题，Δ与0比大小需要设一个阈值eps啊（用Δ>eps取代Δ>0，用Δ>-eps并且Δ
2024-04-11 16:24:18
350
原创 UVa1483/LA5075 Intersection of Two Prisms
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 求两个无限高棱柱的交。对第一个棱柱，依次枚举其凸多边形的每条边，对应一个平行于z轴的无限大矩形，求出此矩形与第二个棱柱相交得到的多边形。同样地依次枚举第二个棱柱凸多边形的每条边，对应一个平行于y轴的无限大矩形，求出此矩形与第一个棱柱相交得到的多边形。这样就求出了相交多面体的每一个面，取相交多面体的第一个面的首个顶点，求此点与各个面的混合积之和，再除以6就是答案。
2024-03-26 20:35:26
515
原创 UVa11826 Shuffle
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 用马尔可夫做状态递推，然后根据上班等概率听[p1,q1]首歌下班等概率听[p2,q2]首歌以及权重变化依次计算f[n-1]、f[n-2]、...、f[0]的递推式求解。本题的数据规模庞大，需要借助dp做预处理，计算f[i]向f[i]、f[i+1]、f[i+2]、...、f[n]的转化概率：用d[n][i][p][q][a]表示总共n首歌已听i首，每次随机播放能等概率听完[p,q]首歌，停止播放时能额外新听a首歌的概率。更多细节，参见AC代码。
2024-03-25 13:14:56
369
原创 UVa1446/LA4640 Origami Through-Hole
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 有一个100mm×100mm的纸片，进行若干次折叠操作：每次给出点P、Q，沿着P、Q的垂直平分线将包含P的部分翻折至P点在Q点上。最后给出一个点的h，从h点打孔，问纸张展开后能看到几个孔。最多折叠10次，折叠有三条规则。
2024-03-18 11:16:59
232
原创 UVa11595 Crossing Streets EXTREME
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 综合了平面区域分割和加权最短路的繁琐题目。本题解决平面区域分割采用“卷包裹”算法比切割多边形算法更合适。根据本题的数据特点，加权最短路用Dijkstra比SPFA更合适一点。
2024-03-07 05:56:31
471
原创 UVa11726 Crime Scene
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 滚边法：在所有图形中找到最低点，多个图形包含最低点时任取一个作为起点即可，初始时假想从起点水平往右的向量作为当前向量，找出逆时针最小旋转量使其刚好贴到下一个图形某点上，下一个图形如果是圆，则可以绕着切点逆时针转一定角度（注意可能会转超过180度）再贴到其他图形的某一点上，依此不停滚边操作，直到回贴到起点。或者求出所有点和圆的切点，然后所有的点和原有的点一起做一次凸包，求出凸包的边长，如果连续的两个点都是同一个圆上的切点，计算长度的方式就要变成求弧长。
2024-03-01 02:13:37
859
原创 UVa1359/LA3491 Hills
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 将每条线段作为两条有向线段做预处理：依次与其他线段求交点（用分数保存叉乘比值）同时保存逆时针夹角的余弦值，最后对多线段交于同一点时保留余弦值最小的那一段。预处理后，遍历并计数：依次遍历有向线段的每一最小分段，当恰好时三条不同线段的最小分段形成环时计数+1。答案是计数结果除以3。
2024-02-18 23:08:20
316
原创 UVa1318/LA2797 Monster Trap
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 《训练指南》上的例题，按照其题解做，发现一个套模板的坑点：本题卡阈值！
2024-01-19 21:02:58
320
原创 UVa1298/LA2218 Triathlon
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 解题思路来自《训练指南》，很巧妙地转化成了半平面求交。Ax+By+C > 0 对应有向直线的方向向量 v = (B, -A)。
2024-01-18 17:44:02
345
原创 UVa1453/LA4728 Squares
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 给定平面上n个边平行于坐标轴的矩形，在它们的顶点中找出两个欧几里得距离最大的点。经典问题：求最远点对。注意到对于平面上的n个点，最远点对必然存在于这n个点所构成的一个凸包上（求点集的直径变成了求凸包的直径），那么可以排除大量点。找最远点对的枚举方法是旋转卡壳（rotating calipers）法：可以想象有两条平行线， “卡”住这个凸包，然后卡紧的情况下旋转一圈，肯定就能找到凸包直径，也就找到了最远点对。
2024-01-17 02:07:57
365
原创 UVa1308/LA2572 Viva Confetti
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 我已经把 n 个圆盘依次放到了桌面上。现按照放置顺序依次给出各个圆盘的圆心位置和半径，问最后有多少圆盘可见？每个可见部分都是由一些“小圆弧”围成的，因此可以先求出所有小圆弧，然后判断每段小圆弧是否可见（在程序实现中，可以用圆弧中点代替整条圆弧进行判断）。小圆弧可见，意味着它所在的圆是可见的。接下来，对于所有可见的小圆弧，看看这段圆弧中点的正下方都有哪些圆盘，则其中最顶部的圆盘也是可见的。所有圆两两求交点，则每个圆上任两个相邻交点之间的圆弧就是所求。
2024-01-12 20:48:07
341
原创 UVa12304 2D Geometry 110 in 1!
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 这是一个拥有6个子问题的2D几何问题集。
2024-01-11 05:30:51
765
原创 UVa12419 Heap Manager
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 利用优先级队列和普通队列即可模拟系统分配内存的过程 内存的分配与释放通过线段树来做，本题交代的内存总量是1e9级别的，因此需要动态开点的线段树来处理。如果区间范围是N，则单次点修改操作涉及到的区间结点数上限是⌈logN⌉+1，单次区间修改操作涉及到的区间结点数上限是4⌈logN⌉。单次操作涉及到的区间结点数上限，乘上不同操作次数上限，就得到了动态开点的结点数上限。
2024-01-07 21:43:21
830
原创 UVa1402/LA3961 Robotic Sort
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 CERC'07的S题，伸展树（splay）模板题，用懒标记表示反转提升效率，需要解决的一个难点：求特定结点的排名。给伸展树结点添加父指针字段，借助父指针可实现单次求特定结点排名的O(logn)时间复杂度算法。说一个用伸展树解题时缩短运行时间的技巧：初始化时将伸展树构建成平衡二叉树。
2024-01-04 21:24:07
342
原创 UVa1365/LA3525 Wild West
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 CERC'05的C题 先求出各个三元组代表的长方体体积并v,则答案就是m^3-v 如果切片操作再累加(即枚举z坐标)则可以转化成矩形面积并 似乎可以套用线段树扫描线模板 本题有一个特殊之处 所有矩形左下角都同一个点(0,0) 利用这一点可以对算法做优化 优化思路和《训练指南》3.5节例题Efficient Solutions相似 加入新点(矩形)时删除那些被其覆盖的矩形 维持点集的单调性(x递增且y递减) 可使用stl的set O(nlogn)
2024-01-03 03:21:11
297
原创 UVa1441/LA4619 Accountant notes
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 CERC 2009的A题 参照官方题解可以写出代码，这里说一些细节：建立trie时还需要辅助数组记录结点深度信息，d[u]表示的是结点u的子节点深度，因此根结点深度为d[1]=1，这样做在bfs计算失配指针和最后遍历答案时将带来便利；为区分终结符（自然数）和非终结符（name）并在结构上统一两者，可以将终结符s的key设定为其自然数的相反数（即-atoi(s)），非终结符的key设置为正值；对每个item，还用到两个结点EQ和ED（等号与换行）
2023-12-27 21:25:33
890
原创 UVa1502/LA5766 GRE Words 坑点
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 坑点：这题数据好像是出了点锅(SPOJ上这么说的)，所以用除了scanf之外的读入方式可能会造成莫名其妙的TLE或者WA。
2023-12-20 23:48:15
329
原创 UVa1462/LA4769 Fuzzy Google Suggest 坑点
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 坑点：如果空前缀（即字典树的根结点）在编辑距离内能变换成查询串，则结果为0。题意还是好理解的，做法也好想到。2009年哈尔滨G题。
2023-12-19 22:26:01
332
原创 UVa1399/LA3907 Puzzle
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 给定m和n，表示有m种不同的字符（大写字母A,B,C⋯），n 个禁止串（n≤1000,每个串长度不超过50），请构造一个不包含任何禁止串的最长字符串并将其输出。如果可以无限长或者无解则输出No，如果存在多解则输出字典序最大那个。AC自动机加记忆化dfs。
2023-12-11 23:47:05
347
原创 UVa1492/LA5694 Adding New Machine
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 给你w*h个格子(1≤w,h≤10000000) 然后给你n(0≤n≤50000)个矩形，表示这些矩形所在的格子被占据。然后需要在同一直线上放一个长为m的新机器（不可经过被占据的格子）。问有多少种放的方法。这是线段树的经典应用：线段树求矩形面积并。具体来说有一个扫描线的的概念对数据做离散化处理，再构建线段树求面积并（其实就处理区间的覆盖与撤销）。
2023-11-27 23:42:57
390
原创 UVa1493/LA5698 Draw a Mess
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 首先线段树可以做，并且行数很少，不需要用二维线段树，按行数开线段树数组即可。 但其实用并查集做更优，并查集在处理一些区间问题（区间合并快速跳表，区间覆盖路径压缩）上有奇效。并查集处理思路：对每行进行并查集路径压缩。倒着处理，相当于先涂上的颜色不会被后涂上的颜色覆盖，pa为下一个未涂色的结点，那么对行处理路径压缩就会跳过已经涂色的结点，比如当前行第i列涂完了下次就要涂pa[i+1]，并且把pa[i+1]也赋给pa[i]。
2023-11-24 19:08:56
327
原创 UVa11987 Almost Union-Find
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 并查集的删除操作可以通过增加结点实现：将所有实际结点的祖先设置为虚拟节点，实际结点删除时，修改其虚拟祖先即可。另外一个增加结点巧妙解决问题的经典例子是树状数组的应用上（Movie collection）。
2023-11-23 21:35:04
413
转载 UVa1513/LA5902 Movie collection
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 给你一叠DV，编号1到n，1在最上面，n在最下面。然后现在给你m个操作，每次都指定一张CD，问要拿走这个CD需要挪走上面多少张CD，并且这个要拿走的CD放在这个叠CD的顶端。将这些CD的上面有多少张CD用数状数组来存储，但是每次要移动的话就有点难办，所以每次移动就将这张CD的pos更新一下，将之前的pos作废，以后查询也是用之后的pos。
2023-11-23 20:41:38
25
原创 康托展开与求逆的一点总结
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 康托展开可以借助树状数组（BIT/Fenwick树）在O(nlogn)复杂度下实现。康托逆展开可以借助线段树在O(nlogn)复杂度下实现。
2023-11-21 06:44:05
16
原创 UVa12130/LA3977 Summits
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 给定一个h * w的地图，每个位置有一个高度值，现在要求出这个图上的峰顶有多少个。峰顶是这样定义的：对于给定d值，一个高度为h的位置，如果它不经过不大于高度为h-d的位置就无法走到更高的山峰，那么它就是峰顶。优化的思路是贪心加bfs：先将所有点按照高度递减排序，再依次遍历每个点做bfs。
2023-11-16 22:34:37
23
原创 UVa12413 Big Decimal Calculator
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 add 和 sub 的计算结果在精度范围内为0时符号按照加数/减数来，但是 mul 和 div 的结果是+0，不受乘数和除数影响。exp, ln, sqrt, asin, acos, atan, sin, cos, tan。使用泰勒展开时，需要配合一些数值技巧以保证级数快速收敛。add, sub, mul, div, pow, atan2。计算atan(x)时要考虑|x|接近1时确保快速收敛的处理方式。先实现加减乘除运算，作为实现后续运算的基础。
2023-09-27 01:08:21
41
原创 UVa1332/LA3139 Kid‘s Problem
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 你的任务是帮助怪盗基德打开下图所示的一个密码锁。该锁一共有k（1≤k≤20）个按钮和k个齿轮，每个齿轮上有n（2≤n≤10）个齿，分别印有整数1~n，其中最上面的那个齿上的数字在外部可见。初始时所有齿轮的可见数（即最上面齿的整数）均为1。每个按钮可以控制多个齿轮，用序列{a1, b1, a2, b2, …, ap, bp}来描述，表示该按钮控制p 个齿轮：a1, a2, …, ap，其中每按一下这个按钮，齿轮ai 将逆时针旋转bi 个齿。
2023-09-05 02:09:09
51
原创 UVa10808 Rational Resistors
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 给你一个包含n个结点，m条导线的电阻网络，求结点a和b之间的等效电阻。a和b的等效电阻等于有一安培电流从a流进b流出时，ab之间的电压值。注意两个结点之间可以有多条导线相连，一条导线的两端也可以是同一个结点。 根据基尔霍夫定律列方程组求解即可。要注意两点：1、分数运算下为了避免long long溢出，高斯消元需要倒着枚举（尽量优先使用未参与消元的方程作为基准，或者使用分数的分子分母最大值最小的方程）2、源点汇点方程的处理也需要注意选更好的方式。
2023-08-28 00:52:00
37
原创 UVa11255 Necklace
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 对于某个置换f，只要其存在（本题指的是可以旋转或者翻转），则不管颜色限制是什么，它给分母贡献加1，只是特定的颜色限制下C(f)可能为0（即此置换在特定颜色限制下循环无法全部得到满足，对分子贡献加0）。计n = a + b + c，本题分母总是2n, (不旋转，n-1种旋转，n种翻转）。有三种不同颜色的珠子，各有a、b、c个3 ≤ a + b + c ≤ 40（a、b、c非负），求将所有珠子连成一串项链能组成的不同方案数。
2023-07-17 12:26:36
38
原创 UVa12387/LA5819 Alphabet Soup
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 给出S（2≤S≤1000）个不同形状的符号，以及一个圆上的P个位置（用极角给出，等分成了360000个角度），选择P个不同的符号放在这P个位置上计算总共有多少种放置方案。注意一种方案如果可以旋转成另外一种方案，则视为同一种方案。输出方案数模100000007。本题虽说是第一道题目，但却是比较难的置换等价类计数题目。注意，题目并未说P个位置已经排序好了，所以需要将P个极角位置排序。找出所有旋转后会重合的（旋转角度）方案，以统计答案。
2023-07-11 22:44:26
38
原创 基于Arduino的ESP32开发环境搭建
完成网址添加后就可以在：工具>开发板>开发板管理器 中搜索并下载esp32开发板数据包。（此过程可能需要科学上网！安装完成后选择：文件>首选项>附加开发板管理器网址 中加入Arduino core for esp32的地址。
2023-07-03 15:19:26
863
1
原创 UVa12164/LA4412 The Great Game
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 问题分成了两个完全独立的部分：如何最大化，以及已知p0之后如何求出状态W的首达概率。 前者解法：二分答案p，看看是否有一种策略使得pwin/(pwin+plose)≥p，即(1-p)*pwin-p*plose≥0。接下来就只需用动态规划计算(1-p)*pwin-p*plose的最大值了。令“胜”的权值为1-p，“负”的权值为-p，则问题转化为最 大化权值的数学期望。设状态d(i，j)表示前i次猜拳，得分为j（注意j可能为负数）时的最 大期望。
2023-05-25 22:07:24
58
原创 UVa1500/LA5760 Alice and Bob
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 仅一个1时：Alice必胜（三数的Nim和为偶数时擦掉1，否则擦掉1和另外任意一数的写上它两的和）。有1时必然Alice胜（最优策略：当另一个数为奇数时擦掉两数写上他们的和，否则擦掉1）；没有1时，两数的Nim和为偶数时Alice胜/奇数时Bob胜（最优策略分析起来复杂一点，但也能想到）。当非1的数量为0时（即全都是1）：n不能被3整除则Alice胜，否则Bob胜。当非1的数量为1时，要考虑1的数量(记为c)的奇偶性以及非1的那个数是否为2。
2023-03-17 22:19:36
57
原创 UVa1341/LA3262 Different Digits
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 一种数字时的求解可以这样做：依次枚举位数x（再枚举数字d）,先求出m=11...1(连续x个1）时对n的余数r（解借助欧拉降幂），如果r==0这就是答案了，不为零时++d，检查d*r%n是否为零更新答案。n为合数时，要考虑其因子情况（含2、含5、其他），因子仅包含一个2不包含5（可以包含其他质数）或者仅包含一个5不包含2时,答案仍然只包含一种数字（比如n=26时答案为222222，n=35时答案为555555)，其他时候的答案最多也只包含两种数字。
2023-03-09 20:49:34
37
原创 UVa1485/LA5092 Permutation Counting
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 若排列的1号位放的数正好是1,则转化成了f[n-1][k]。接下来考虑1也参与交换对结果的变化：若1和某个ai>i的元素交换,则转化成了新的排列但计数结果仍然f[n-1][k]，当ai>i的元素有k个时有k种交换选择；若1和某个ai≤i的元素交换，则新排列的1号位新增一个ai>i的元素，当ai>i的元素有k-1个时有n-k种交换选择。得出递推式：f[n][k] = f[n-1][k] + k*f[n-1][k] + (n-k)*f[n-1][k-1]
2023-01-31 17:07:12
38
原创 UVa10237 Bishops
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 可以定义多维递推状态：f[h1][c1][h2][c2][k](f[N][2][N][2][N])，表示阶梯最大高度为h1,最大高度的列有c1+1个(c1
2023-01-19 19:19:39
57
原创 UVa11139 Counting Quadrilaterals
本人学习icpc算法竞赛时自己对UVa部分题目的解题思路 四边形可按凹凸分类，先考虑凹四边形，它必然是一个三角形和其内一点形成的（见下图），并且三角形内任意一点与三角形的三个顶点能组成三个凹四边形，因此统计凹四边形可以枚举格点三角形和其内格点数（具体需要用到。这种可以借助动态规划单独计算出来：设f[w][h][s]表示宽高比为w:h（w、h互质）并且横向宽度为s的斜线下方的格点计数 在图下图 的10×10 网格中，你可以看到5 个四边形 四边形的4 条边不能相交且没有三点共线
2023-01-11 23:11:52
72
UVa1318/LA2797 Monster Trap 用python写的画图可视化分析数据的脚本
2024-01-19
UVa1318/LA2797 Monster Trap 《训练指南》习题源码
2024-01-19
UVa1308/LA2572 Viva Confetti 用python写的画图可视化分析数据的脚本
2024-01-12
(394页)AMiner-2019人工智能发展报告-191201.pdf
2020-04-13
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人