VoidJackLee

题解

/ 注册

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

小雨坐地铁

题意告诉你车站数n，地铁线路数m，起点s，终点t，然后m行描述每一条地铁的上车价格a，每坐一站价格b，车站数c，以及c个车站号，求最小花费。题解显然，是一个很裸的最短路。但是直接以站点为节点，地铁线路作为边是不能简单的用Dij过的，毕竟贪心算法，直接这么莽会wa的（我还真试过，wa了，自己也找...

2020-05-06

1 783

最优乘车

题目 https://ac.nowcoder.com/acm/contest/4862/K 类似题推荐：小雨坐地铁思路题目的意思是给你m条单向巴士线路和n个站点，然后从1到n最少要换乘多少次。很容易想到使用最短路Dijkstra算法，但是难点在于如何建图。这边需要有一个分层图的思想，分离站...

2020-05-06

1 1021

序列最小化

题意给一串1..N的序列，顺序任意，然后从中取出连续k个数字，把他们替换成其中最小的数字。解析不难看出，最终所有数字都会变成1。那么首先我们就会想到先去替换包含1的连续k区间，剩下的就左右跑就行了。但最优的情况一定发生在重叠的长度最少的时候。不妨假设都只重叠1个数字(最优解的情况)，那么此...

2020-05-05

0 616

J-建设道路

分析根据题意，我们可以得出是要求两两数字之间的差值的平方，由于数据很多，的暴力是肯定不行的。那么我们只能写一个O(n)的算法，所以会想到求前缀和。求解这边由于都是差值，所以得进行一个转化，使得他成为前缀和的形式。先排序，再两两做差即可。 int n; scanf("%d",&n);...

H题解

2020-04-18

2 627

2020牛客寒假算法基础集训营5 H-Hash题解

题意由题目的意思可得，他是将一个6位字符串转化为一个数字，然后再取mod。观察主要的公式：res = (res * 26 + str[i] - 'a') % mod;是不是和字符串转化为数字的公式似曾相识呢。平时我们转化一个字符串的时候正是使用类似的方法： string str = "123"...

H题解

2020-02-13

3 473