coder-River

题解

归纳(12)

/ 注册

全部文章 / 题解（共82篇）

Nowcoder 进来学习树的重心求法来自专栏

一、题意一棵树有n个结点（n<=1e6），每个结点的权重为其深度，根节点深度为0。给这棵树选一个根节点，使得它的权重和最小。二、解析即使没学过树的重心这个概念，凭直觉就能感受到，以“重心”为根节点的树的权重和应该是最小的。事实上也是如此。树的重心：定义：对于一棵树的每一个结点u，它们...

2020-09-10

0 396

Nowcoder 使用费马小定理求解带模的组合数来自专栏

一、题意求以x结尾的长度为l的不下降正整数数列一共有多少个。对911451407取模。输入共有kase（kase<=1e5）组数据，每组数据满足x、l<=1e6。二、解析这是一道数学类题目。一开始看到题目的第一直觉是用动态规划，即dp[l][x]表示以x为结尾的长度为l的不下降正...

2020-09-10

1 774

Poj 3159 进来学习差分约束问题以及利用链式向前星加快读图来自专栏

一、题意输入n（n<=3000）和m（m<=150 000）表示有n个小朋友进行分糖。然后是m对关系，(A B w)表示A的糖果最多比B少w个。求1号和n号最多能差多少个糖果。二、解析这是一道差分约束问题，将原题目转化一下就是：给出n个数的m个约束关系，每个关系(A B w)表示...

2020-09-05

0 429

Uva 567 进来复习Floyd算法模板来自专栏

一、题意每组数据有20个城市，给出每个城市与之相邻的城市，距离为1，不相邻的城市认为不可达。然后有q个询问，每次询问任意两个城市之间的距离。二、解析由于要询问任意两个城市之间的距离，因此这是一个多源最短路问题，即需要得到每两个点之间的最短路。这样的问题只能使用Floyd算法。算法复杂度为O(n...

2020-09-04

0 476

Poj 3259 进来复习spfa算法模板来自专栏

一、题意农夫有n块田地, 编号 1...n(1<=N<=500)，田地间有m1条双向路径，每条路径有一个经过所需要的时间wi。同时有m2个单向虫洞, 每条虫洞走完后时间倒回wi。问农夫是否能在田地中遇到以前的自己。二、解析这道题的情景非常有意思，m1条双向路径的权值为w，而m2条...

2020-09-04

0 431

Poj 2397 进来复习Dijkstra算法模板来自专栏

一、题意输入一个n个点m条边的无向图，每条边给出边权，求从点1到点n的最短路径。二、解析最短路径模板题。用来复习一下Dijkstra算法的模板正好。Dijkstra算法的时间复杂度为O(mlgn)，一般对于边权为正的单源最短路问题就它就没错了。同时适用于有向图和无向图。三、代码 #inclu...

2020-09-04

0 473

Uva 1395 最“苗条”的生成树来自专栏

一、题意给出一个n（n<=100）结点的图，求苗条度（最大边减最小边的值）尽量小的生成树二、解析其实就是要求边权极差最小的生成树。我们知道求最小生成树是用Kruskal算法，这里其实也是一样：我们枚举生成树的最小边E[l]，然后每次只从边权大于这条最小边边权的边中进行最小生成树的生成，这...

2020-09-04

0 595

Uva 10600 进来复习一下次小生成树的算法来自专栏

一、题意输入一个n个点m条边的图，要求你计算出图中的最小生成树和次小生成树的权值和。二、解析最小生成树比较简单，直接上Kruskal算法模板即可。主要是次小生成树应该如何求解？其实也比较简单，按照以下步骤即可：求出最小生成树mst 通过以每个点为根分别进行dfs，得到maxW[maxn]...

2020-09-04

0 420

Uva 10034 进来复习一下最小生成树模板来自专栏

一、题意输入n表示有n个点，然后输入每个点的实数坐标（xi, yi），求连通所有点的最小长度和。二、解析这是一道裸的最小生成树问题，边权就是两点间的距离。直接上Kruskal算法模板。总是得来一道模板题复习复习的。三、代码 #include <iostream> #include...

2020-09-04

0 578

Hdu 1059 背包问题之进来复习多重背包问题来自专栏

一、题意有6堆石头，第i堆石头中每个石头的价值都是i。然后输入每堆石头的数量num[i]。要求你判断是否可以将所有石头分成总价值相等的两堆。二、解析首先算出所有石头的总价值V，若V为奇数，则无解。若V为偶数，则我们的目标就是拿一个体积为V/2的背包，然后尽可能装满它。若装得满，说明原问题可以分...

2020-09-03

0 555