02 牛客小白月赛75

陈小白     2023.07.02     算法相关     抢沙发     109人打酱油
比赛地址:https://ac.nowcoder.com/acm/contest/60063 先说好消息,搞出模拟了。 再说坏消息,就A了三个.......DE真的很巧妙,尤其D D:大意是给出给出n*m的矩阵,从11走到nm。求最小花费时间。 两类操作,向上下左右四个反向走,...

29 D. Tenzing and His Animal Friends 好题当赏

陈小白     2023.06.29     算法相关     抢沙发     205人打酱油
题目链接:https://codeforces.com/contest/1842/problem/D 借鉴:https://blog.csdn.net/Tanya_xiaomai/article/details/131393112 没看懂这个题 大意:丁真和他的n个动物朋...

03 松鼠的新家 LCA+树上差分

陈小白     2023.05.03     算法相关     抢沙发     170人打酱油
题目链接:https://www.luogu.com.cn/problem/P3258 大意:从a1走到an,所经过的位置+1,求每个位置的值。 重点在于利用lca进行树上差分,考虑对于x走到y,令x走到公共祖先的点+1,y走到公共祖先的点+1。公共祖先只加一次,所以减去,公共...

29 P1351 [NOIP2014 提高组] 联合权值

陈小白     2023.04.29     算法相关     抢沙发     162人打酱油
题目链接:https://www.luogu.com.cn/problem/P1351 大意是给出一个无向图,求距离为2的相乘权值之和,和最大相乘。 根据公式可以推导 显而易见,这个公式是很容易推导的。 剩下的就是遍历所有的节点,然后去寻找这些值,很水(标签...

28 AtCoder Beginner Contest 291 (D、E)

陈小白     2023.02.28     算法相关     抢沙发     177人打酱油
比赛链接:https://atcoder.jp/contests/abc291/tasks D题:大意是给出n张卡片的正面和反面的数值,卡片正反面为不同数字,求翻某些卡片的一面使得向正的一面的数值全都不一样的集合的数量。 解决方法:考虑使用01动态规划解决。f[i][0/1],...

24 拓扑排序(旅行计划+神经网络)

陈小白     2023.02.24     算法相关     抢沙发     158人打酱油
旅行计划 题意 大意是给出n个城市以及他们之间的道路,求从1点到其他各点(以各点为终点)所经过的最多城市的数量 思路 其实很明显可以想到dp的部分。但是如何dp是一个问题。这个dp的状态转移其实并不难,只需要从源点转移过来就ok。但是我们需要想到应该从哪个点开始去d...

26 状压dp 解决 哈密顿回路问题

陈小白     2022.12.26     算法相关     抢沙发     161人打酱油
步骤: 确定采用状压dp范围20左右。 状态转移f[i][j]表示对于第i个节点,它走到的第j个状态。对于任意状态,遍历任意节点,找到此节点并确定另一节点与其重合。 路径确定i>>j&1路径重合i-(1<<j)>>k&1 ...

12 cf E. Split Into Two Sets

陈小白     2022.07.12     算法相关     抢沙发     261人打酱油
题目链接:https://codeforc.es/contest/1702/problem/E 第一次cf周赛做到了图论的题,真的挺开心的。 这道题题的大意就是,给出一个数n,然后给出n对数a,b。让我们构造两组数,这两组数的元素都是1-n,且没有重复元素。 soluti...

28 拓扑排序BFS实现思路疑惑

陈小白     2022.04.28     算法相关     抢沙发     273人打酱油
拓扑排序bfs的实现既可以使用队列也可以使用栈,当路径唯一时,两者结果并无差异。原因是因为后排的元素是相互独立的。 模板题:http://poj.org/problem?id=1094 思路: 找度为0的元素,入列查找关系 对应关系减度 反复直到队列为空 没太...

18 天梯赛L2—紧急救援

陈小白     2022.04.18     算法相关     抢沙发     252人打酱油
题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840 一道迪杰斯特拉的变形题,之前我这个弱鸡基本只做了模板或接近模板的题。这道题可以很好的帮助我消化最短路径。 在看了一遍题...

16 SPFA算法求最短路径

陈小白     2022.04.16     算法相关     抢沙发     406人打酱油
算法适用场景:非负权,负权非负环。 算法的实现在贝尔曼福特算法的基础上适用队列优化(类似于广度优先搜索的方法)将修改后的点放入队列后设置标记,防止下一次再利用该点进行松弛,直到改点被使用后为止。 需要用到的空间:vector领接表,队列(存放点),dis[]单源最短路径,sig...

04 贝尔曼福特(负权优化)

陈小白     2022.04.04     算法相关     抢沙发     269人打酱油
题目链接:https://www.acwing.com/problem/content/description/855/ 贝尔曼福特负权模板,额外占用的空间就是n的数量,用覆盖的方式实现。 实现起来挺容易的,在贝尔曼福特上面改改就可以了 #include<bits/st...

30 洛谷周赛 最短路径

陈小白     2022.03.30     算法相关     抢沙发     255人打酱油
题目链接https://www.acwing.com/problem/content/description/4321/ 意思就是一个机器人通过输入的字符串进行上下左右走动 如果满足:可以构造一个地图且行走的路径是起点到终点的最短路径 输出YES否则输出NO 如果你...

29 洛谷oi普及+ 最短路计数

陈小白     2022.03.29     算法相关     抢沙发     303人打酱油
题目链接:https://www.luogu.com.cn/problem/P1144 求到达每个点的最短路个数,从层次出发,采用bfs进行每一次搜索,通过vis控制回路问题 题目数据范围较大,采用动态建图 借鉴dalao代码 #include<cstdio&g...