题目  https://ac.nowcoder.com/acm/contest/4862/K  类似题推荐：小雨坐地铁 思路 题目的意思是给你m条单向巴士线路和n个站点，然后从1到n最少要换乘多少次。 很容易想到使用最短路Dijkstra算法，但是难点在于如何建图。这边需要有一个分层图的思想，分离站点和巴士线路，具体见样例：  3 76 74 7 3 62 1 3 5  对应建立图则表达为：  由于需要使换乘次数最少，不妨令上车时需要1元钱，下车不要钱。图中绿色的均为巴士线路，橘色的是各个站点，箭头表示方向，上面的数字是权值，那么该图表示的便是前面的所述。 struct Node { int ...

题意 给一串1..N的序列，顺序任意，然后从中取出连续k个数字，把他们替换成其中最小的数字。 解析 不难看出，最终所有数字都会变成1。 那么首先我们就会想到先去替换包含1的连续k区间，剩下的就左右跑就行了。但最优的情况一定发生在重叠的长度最少的时候。 不妨假设都只重叠1个数字(最优解的情况)，那么此时我们只需要将k --，然后用剪完之后的k再去铺满剩余没有铺满的数字即可。 例如  10 42 3 4 5 1 6 7 8 9 10.........++++++++++........++++++  在这个例子中我们首先选取的是5 1 6 7，然后是2 3 4 5和7 8 9 10，其中5和7都是...

分析 根据题意，我们可以得出是要求两两数字之间的差值的平方，由于数据很多，的暴力是肯定不行的。 那么我们只能写一个O(n)的算法，所以会想到求前缀和。 求解 这边由于都是差值，所以得进行一个转化，使得他成为前缀和的形式。 先排序，再两两做差即可。 int n; scanf("%d",&n); ll a[500010]; for (int i = 0;i < n;i ++) scanf("%lld",a + i); // 读入 sort(a,a + n); // 排序 n --; // 由于两两做差之后，数字个数就会减少1 for (int i = 0;i < n;i ++)...

题意 由题目的意思可得，他是将一个6位字符串转化为一个数字，然后再取mod。 观察主要的公式：res = (res * 26 + str[i] - 'a') % mod;是不是和字符串转化为数字的公式似曾相识呢。 平时我们转化一个字符串的时候正是使用类似的方法： string str = "123"; int ans = 0; for (int i = 0;str[i] != 0;i ++) { ans = ans * 10 + str[i] - '0'; } 同样的，对于这个res = (res * 26 + str[i] - 'a') % mod;公式来说，也是一个字符串转化成数字的过程，...