题解bellman-ford算法bellman
经典算法题之手机键盘
这题出的只能说是无语。思路还是很简单的。 只要用一个的tag标记上次是哪个按键即可,然后tag和现在对比,要是相同就多加2。 #include<iostream> #include <map> using namespace std; int main(){ map<char,int>Map={ { ......
贪心算法最优解判定
判断贪心算法得到的解是否是最优解通常取决于具体的问题。在大多数情况下,贪心算法无法保证得到最优解,但在某些特定问题中,贪心算法可以给出最优解。 要判断贪心算法得到的解是否是最优解,可以采取以下几种方法: 数学证明:对于特定问题,可以使用数学方法证明贪心算法得到的解是最优解。这涉及到对问题性质和约束条 ......
Cordic算法
Cordic算法 CORDIC 算法是坐标旋转数字计算的缩写,它最初用于三角函数的坐标变换,经过一定的推广后也可用于计算线形函数和双曲线函数(开平方根)。CORDIC算法只由移位操作和加减操作,因此,非常适合于在硬件使用。 目录Cordic算法一、圆周系统1.1 旋转模式1.1.1 原理1.2 ......
代码随想录算法训练营第二十五天 | 216.组合总和III,17.电话号码的字母组合
一、216.组合总和III 题目链接: LeetCode 216.组合总和III 学习前: 思路: 返回类型和参数: void fun(int n, int k, int start) 终止条件: int len = list.size(); if(len==k){ if(n==0 ){ List< ......
经典算法题-剩下的树C++
#include<iostream> using namespace std; void move (int A[],int head, int tail){ for( ; head <= tail ; head++ ){ A[head]=0; } } int main( ){ int l = 0 ......
P2308题解
题意简述 其实就是每次将相邻两个数替换为它们的和,代价为两个数的和,直到只剩一个数,求最小代价和以及操作方式。 思维路径 我们可以先求出最小代价,很明显可以用 dp 来做。定义 \(f_{i,j}\) 为合并第 \(i\) 个数和第 \(j\) 个数的最小代价,\(s_i\) 表示前 \(i\) 个 ......
P3795题解
思维路径 根据映射,我们可以发现数字的规律必定是两两互换,即若 \(f_a\) 是 \(b\) ,那么 \(f_b\) 一定是 \(a\) 。 我们可以通过手算 \(1\) 到 \(4\) 的数据,观察规律。 观察第 \(4\) 行的数据。 以 \(1\) 为始的数据后面跟的三个数据正好与第三行的顺 ......
P3133题解
题意简述 给定两个点(即 FJ 和 Bessie)和两条路径,让这两个点沿着路径移动,求每移动一次的能量总和。 思维路径 典型的动态规划题,我们设计状态,设 \(f_{i,j}\) 表示 FJ 走到第 \(i\) 个点,Bessie 走到第 \(j\) 个点最少的能量总和。 因为他们两个都可以在某一 ......
P6591 题解
题意简述 给出一棵无根树,求以那些节点为根时,与它直接相连的节点,它们的子树大小都相同。 思维路径 首先,显而易见的是,在 \(1 \le n \le 10^6\) 的数据范围下,我们不可能通过对每个节点作为根判断一次。因此,我们考虑选取一个节点为根计算全部。 我们作图来分析一下。 如上图,我们针对 ......
经典算法之剩下的树C
这题思路可以说是太简单了。 用一个数组表示树,值为1表示有树,值为零表示无就行。、 最后统计1的个数即为剩下的树。 #include <stdio.h> #include <malloc.h> void move (int A[],int head,int tail){ for( ; head <= ......
CF1146B 题解
题目简述 给定一个字符串 \(t\),由一个字符串 \(s\) 和这个字符串去掉所有 a 组成。求字符串 \(s\)。 思路 首先我们分析给定的字符串 \(t\),它由 \(s\) 和 \(s\) 去掉所有 a 形成的字符串 \(s'\) 组成。那么当整个字符串 \(t\) 去掉 a 后,就得到了 ......
CF1068A 题解
其实很简单的一道题。 思维路径 其实题目主要要考虑的就是以下三个条件。 每个人都要送一样多的硬币。 每个硬币都必须是不同的。 所有人送的硬币至少有 \(L\) 个是 Ivan 没有的。 我们一个一个来看。 每个人都要送一样多的硬币。 一共有 \(M\) 个朋友,所以说总共送的硬币的个数为 \(M\) ......
数学相关算法
埃氏筛 #include<bits/stdc++.h> using namespace std; int a[50000005] = {}; int n = 0; int main() { scanf("%d", &n); for(int i=1; i<=n; i++) a[i] = 1; for( ......
CF940F Machine Learning题解
题目链接:洛谷 或者 CF 不是特别难的题,抽象下题意就是算区间次数出现的次数 mex 和带单点修改。看到范围 \(1e5\) 还带修改,传统的 mex 求法里貌似就莫队类算法好带修,考虑带修莫队。 然而涉及到 mex 问题,你可能不由自主地想到回滚莫队求 mex 只删不加的板子题:P4137 Rm ......
CF940FMachine Learning题解
题目链接:洛谷 或者 CF 不是特别难的题,抽象下题意就是算区间次数出现的次数 mex 和带单点修改。看到范围 \(1e5\) 还带修改,传统的 mex 求法里貌似就莫队类算法好带修,考虑带修莫队。 然而涉及到 mex 问题,你可能不由自主地想到回滚莫队求 mex 只删不加的板子题:P4137 Rm ......
经典算法之-英文日期C++版
因为考研机试的原因,C和C++最好都准备一下,所以有C++版本。 #include <iostream> #include <cstring> #include <map> using namespace std ; int cmp(int year,int mouth,int day){ if(y ......
【算法题】对称数判断
题目描述 输入一个整型数,判断是否是对称数,如果是,输出yes,否则输出no,不用考虑这个整型数过大,int类型存不下,不用考虑负值; 例如 12321是对称数,输出yes,124421是对称数,输出yes,1231不是对称数,输出no 题解 #include <stdio.h> int main( ......
经典算法之英文日期问题
这题其实就是多了一个字符串转化成数字而已。 用一个字符串数组和字符串比较函数就可以得出数字月份然后就简单了。 然后最后一个难点就是确定是星期几,可以根据今天的日期的星期当作固定点,找相差几天然后得出具体星期。 #include <stdio.h> #include <stdbool.h> #incl ......
LOJ2294 银河英雄传说 题解
Question LOJ2294 银河英雄传说 Solution 算是带权并查集一个比较典的题目了 定义 \(d[x]\) 表示战舰 \(x\) 与 \(fa[x]\) 之间边的权值,在路径压缩把 \(x\) 的 \(fa[x]\) 修改为根节点时,把 \(d[x]\) 更新成从 \(x\) 到树根 ......
一套模板搞定二叉树算法题--二叉树算法讲解001
1、二叉树定义 2、二叉树存储结构 2.1、经典题目代码构建 代码构建: 代码对应的二叉树的图: 一行代码搞定lettcode2236,运行通过;就是考察对二叉树结构的理解: 3、深度优先遍历DFS和广度优先遍历BFS概念 3.1、深入讲解广度优先遍历BFS 树的 广度优先遍历BFS 也可以称之为层 ......
(坚持每天都写算法)算法基础复习part1基础算法1-2——归并排序
前言:本来想着找模板,但是第一篇的观感我自己觉得还可以(摆烂),所以就不搞了。 归并排序,是一种分治算法。当问题具有最优子结构并且子问题之间是互相独立的再加上子问题的规模可以是很小以至于很容易解决的以及子问题可以合并成整个问题的解,那么就可以考虑使用分治算法。子问题互相独立,即各个子问题所占的资源是 ......
2023-2024学年上学期算法设计与分析题期末考试模拟卷
2023-2024学年上学期算法设计与分析题期末考试模拟卷 目录2023-2024学年上学期算法设计与分析题期末考试模拟卷单选题程序填空题输入格式:输出格式:输入样例1:输出样例1:主观题 注意:该题集非标准答案,仅供参考,如果异议,请在评论区提出或私信。 单选题 ()关于分治法描述不正确的是: A ......
CF1665E MinimizOR 题解
CF1665E 直接做不是很好下手,考虑找些性质。 有一个比较显然的贪心,就是按位从高到低的考虑,如果当前位至少有 \(2\) 个 \(0\),就可以去掉该位为 \(1\) 的数。但是时间上显然是不行的。 假如没有重复的数,可以发现扫到最后一位时,剩下的数的数量是 \(\log V\) 的,证明省去 ......
P8512 [Ynoi Easy Round 2021] TEST_152 题解
P8512 直接做不好做,考虑离线。这个覆盖操作和这道题很像,可以直接对某些段暴力修改,可以直接上 ODT。发现当 ODT 执行这些操作时,是容易求出不执行某些操作后带来的值的影响的,即可以直接用树状数组维护每个位置现在是被那个操作覆盖,求出 \(1\) 到 \(x\) 操作还覆盖了那些位置,以及这 ......
CF1870F Lazy Numbers 题解
CF1870F 题意:给一个长度为 \(n\) 的排列,求在其在 \(k\) 进制下按字典序排序后 \(\sum[p_i=i]\) 的值(\(n\le10^{18}\))。 直接做是不好办的,只能在一些数中找到 \(p_i\) 的大小关系。 在手摸的过程中会发现一些长度相等的数之间会插入一些其它长度 ......
P4700 [CEOI2011] Traffic 题解
P4700 简单的,但是考试的时候没看到是平面图,就只想到了缩点后 DAG 判断能到达哪些点。用 bitset 维护做到 \(\mathcal{O}(\frac{nm}{w})\) 的时空复杂度,但是空间会炸。 由于这个图是平面图,稍微推一下就可以知道所有能它最终所能到达的点一定是从西侧出发所能到达 ......
P4657 [CEOI2017] Chase 题解
P4657 树形 dp。 首先,追逐者遇到的铁球的数量显然不会少于逃亡者遇到的铁球数量。 令 \(ss_i\) 表示与 \(i\) 相邻的点的权值之和。\(\mathcal{O}(n^2v)\) 的 dp 是很简单的。 令 \(dp_{i,j,0/1}\) 表示根节点到 \(i\) 的路径上,用了 ......
P9715 「QFOI R1」头 题解
P9715 不一样的线段树做法。 假如只有 \(t=1\) 的操作是容易的。考虑加上 \(t=0\) 后怎么做。显然地,我们对每一个操作附上一个时间 \(tim\),不妨令 \(tim\) 小的数能覆盖掉 \(tim\) 大的数。这时候就只需要维护区间取 min 和最后的 \(n\) 次求 \(c\ ......
P8386 [PA2021] Od deski do deski 题解
P8386 platelett 讲的题欸。 先考虑给定序列怎么做。 问题显然可以转化为能否将序列分成若干个子序列。令 \(f_i\) 表示前 \(i\) 个数是否能够删完。则有 \(f_i = f_j[a_i=a_j, f_j=1]\)。这样是 \(n^2\) 的,也无法扩展至所有数列的情况。 建立 ......