Legacyhttps://ac.nowcoder.com/acm/problem/111975 problem 给 n 个点。m 个操作。 从 x 点到 y 点连权值为 w 的边。 从 x 点到 [L, R] 的点连权值为 w 的边。 从 [L, R] 的点到 x 连权值为 w 的边。 问从 s 点到其他点的最短路，无法到达输出 -1。 idea 毫无疑问，建边求最短路。但是暴力建边超时，于是引出新知识点，线段树优化建图。 掌握此题的必备知识：dijkstra求最短路、dijkstra堆优化、spfa、线段树基础。 点到区间连边官方讲解已经讲得很清楚了，在此先引用每日一题栏目...

小A与欧拉路https://ac.nowcoder.com/acm/problem/22618 idea 小 A 给你了一棵树，对于这棵树上的每一条边，你都可以将它复制任意（可以为 0）次（即在这条边连接的两个点之间再加一条边权相同的边），求所有可能新形成的图中欧拉路的最短长度。欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次。 考虑最简单的回路的情况。每条边就一定是经过两次。那么遍历完过后，每条边就需要复制一次。由于不是欧拉回路而是欧拉路径所以可以减去从起点到终点的路径。所以我们要使起点到终点的路径最长。所以问题就是找到树的直径，因此答案就是 ，记得开 ...

数学考试https://ac.nowcoder.com/acm/problem/15553 idea 题意是求两段不连续的区间，使其和最大。 我们预处理出原数组的前缀和后，我们求出两个数组：、。 ：代表位置 之前最大的区间和。 ：代表位置 之后最大的区间和。 最后线性 求得结果。由于数据范围较大，需要开 ，记得初始化 数组为负无穷。 时间复杂度： code #include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 2e5 + 10; int num[...