B_M

分类

Codeforces(5) java课(7) 分治(1) 动态规划(1) 图论(1) 数学(11) 数据结构(2) 算法课(13)

/ 注册

全部文章（共41篇）

图论-曼哈顿距离最小生成树

问题给出平面上若干个点，两点之间的距离为两点之间的曼哈顿距离，求这些点的最小生成树例题传送门两点的曼哈顿距离：定理对于图上任意一个环，环上边权最大的边一定不在最小生成树上证明：环上至少有一条边不在最小生成树上，若环上所有边都在最小生成树上，那不满足树的性质在树上任意断开一条边，最小生成...

2020-03-31

0 1071

算法课-平面最近点对

问题给出平面上一系列点，求任意两点之间欧几里得距离的最小值解析记作两点之间的欧几里得距离暴力做法很容易想到对这个问题暴力求解的方法，对于每一个点,计算它与其余所有点之间的距离，取最小值即可时间复杂度为分治策略首先按照分治策略的基本套路，一般都是将问题分解为若干个子问题，然后将子问题的...

2020-03-28

0 2887

算法课-归并排序

问题二分归并排序：对个不同的数构成的数组进行排序，其中解析归并将任意的两个升序序列和合并为一个升序序列主要步骤比较序列中的首元素和序列中的首元素若则将加到序列末尾，否则将加到序列末尾重复以上操作直到序列或序列为空将非空序列直接加到序列末尾正确性证明对于升序序列和，将两个序列的首元素分别记为和...

2020-03-22

0 495

动态规划-数位DP

问题一般问题的形式为给出一个条件，问一段区间内符合要求的数的个数举例 HUD-2089 不要62 题意给出一个区间，求区间内没有连续"62"且没有"4"的数的个数思路暴力直接暴力枚举区间内每一个数来统计搜索用深搜的思想实现，比如求0~234之间符合条...

2020-03-18

0 501

算法课-搜索算法

问题给出一个长度为的按升序排序的序列，询问一个数在序列中的出现位置，若未出现，则返回解析顺序查找对于给定一个长度为的序列，要在其中寻找一个数，最简单的方法就是逐个遍历，当匹配到相应数后，返回对应下标，如果没有找到，则返回二分查找由于给出的是一个按升序排序的序列，对于任意的下标，如果则所有...

2020-03-15

0 523

算法课-最短路算法

最短路问题最短路问题又可以分为单源最短路和多源最短路两种，其中单源最短路指的是一个从一个起点出发到达其他所有的点的问题，多源最短路指的是从每个点出发到达其他点的最短路。对每个点求一遍单源最短路就可以求得多源最短路最短路算法的一些技巧对于不同的算法有不同的存图方式，一般采用邻接链表和邻接矩阵的方...

2020-03-08

0 866

1316E Team Building

题目传送门题目大意：个人，从中选择个作为球员，第个人产生，个作为观众，第个人产生的价值解题思路不难想，通过对用二进制进行状态压缩，到一个简单的过程这种做法的复杂度大约是显然是不可接受的然后不难发现作为观众的人，其实只要贪心的在没有选为球员的人里面选最大的个就好了于是又得以去掉的复杂度，于...

2020-03-06

0 527

算法课-最小生成树

最小生成树问题对于给出的一张图求一个生成子图使得最小，其中表示边的边权这里用一个在线画图工具来作图：传送门解析最小生成树问题其实就是在一张图中扣出一棵树来，这棵树有最小的边权和对于最小生成树问题有两种常用的方法，一是kurskal算法，二是prim算法，下面给出两种算法的推导与图示 Krus...

2020-02-27

0 547

数学 tsy's number

题目传送门题目大意求解题思路欧拉函数有一条性质一个整数可以表示为因为欧拉函数是积性函数，所以上下约分后同理所以原式等于枚举，原式用换个元交换一下枚举顺序最右边求个和，用其中所以最右边记作原式变为令交换一下枚举顺序，原式变为合并一下中间部分是一个迪利克雷卷积的形式，是...

2020-02-27

0 516

数学-Polynomial

题目传送门题目大意给出,个询问，每个询问求解题思路很明显的拉格朗日插值但是一直化简不出来之后看题解发现了一个常识之前也用过，但是死活想不起来，果然还是我太菜有了这个常识这题就变得简单了，先插值求然后做前缀和此时就变成了前缀和所表示的多项式的前项；此时再插值求出来的就是前缀和的值了即可...

2020-02-26

1 691