分析 因为有 条可以免费，所以我们朴素的最短路算法不太好做。现在题解中有了二分最短路的题解。这里换一种思路。分层图。每一层和原图是相同的，层与层之间由边权为 的边链接。最后一层的终点的权值就是我们要求的最小值。 代码 #include<bits/stdc++.h> using namespace std; const int N=2020,P=10011,INF=0x3f3f3f3f; struct node { int v,Next,w; }e[N*P]; int head[N*N],ecnt; void add(int u,int v,int w) { e[...

分析 对于这张图的关键点非常少，对于每一个点对我们可以求出之间的距离，我们考虑状压转移。 ，表示节点 为根节点，已经走过的节点集合为 所需要的最小步数。总的复杂度为 ， 表示有多少个坏掉的电线杆。 代码 #include<bits/stdc++.h> using namespace std; const int N = 210,inf = 0x3f3f3f3f; #define LL long long struct Node{int x,y;}p[21]; int vis[N][N]; int dp[N][101000];int n,m,t,top,f[21][21...

B 乐***对 分析 考虑 ， 表示以 结尾可划分出的最多队伍数。对于不合法的方案只有可能最大的那个人的要求大于了总人数。而对于 转移只有两种决策。 加入上一组。 新开一组。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 100; int f[N],n,a[N]; int main() { cin >> n; for(int i = 1;i <= n;i++) cin >> a[i]; sort(a+1,a+1+n); for(int i...

A 巨木之森 分析 先有一个思路，考虑一个点的答案记录。因为除了起始节点之间的路径，其它的路径都要经过两次。所以一个节点的答案为 ， 表示总路径的长度， 表示从节点 开始的最长路径。现在就只需要考虑快速算出所有的节点的答案，这里我们抛出一个引理:对于树上的每个节点，距离他最远的点一定是树的直径的某一个端点。这里也非常好证明，考虑反证法，若不为直径一端点，考虑两条路径相交、不相交两种情况，可以证明出一定有比直径更长的路径。所以只要求出一个节点到直径端点的距离就可以了。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std...

分析 读完题，我们发现这道题就是让你求出在一张混合图中的单源最短路。因为有负环，直接考虑 算法。因为题面上已经保证是没有负环的，所以一定有解。考虑到朴素的 算法容易被卡，这里使用 。将原队列改成双端队列，对要加入队列的点 ，如果 小于队头元素 的 ，将其插入到队头，否则插入到队尾。 代码 #include<bits/stdc++.h> using namespace std; const int N = 8e4 + 100,inf = 0x3f3f3f3f; int n,P,R,S,dis[N],vis[N]; deque<int> Q; vector&l...

分析 对于一个节点从 恰好走 步走到 之类的都可以用 来处理。定义 代表第 步，到节点 ，当前方向是 的总方案数。那么一个节点可以从 个方向转移过来，再枚举自己的方向。时间复杂度为 。还有第一维可以用滚动数组优化空间。 代码 #include<bits/stdc++.h> using namespace std; const int N = 210,mod = 1e9 + 7; int dx[5] = {0,0,0,1,-1},dy[5] = {0,1,-1,0,0}; int f[N][N][5],res[N][N][5],n,m,t,X1,X2,Y1,Y2,...

分析 一个节点到左上，右上，左下，右下的最大值路径是确定的。那么我们考虑见面的点是哪个点。因为见面点是不能计算贡献的，所以我们考虑第一个人和第二个人是分别从哪个方向来的。经过讨论也只有两种可能。枚举每一个点算出值就可以了。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();} while...

 题意 安排摆渡车出发的时间，使这些同学的等车时间之和最小。 分析  一 根据题意我们就有如下转移式子，令 $f_i$ 是以时间点 $i$ 为结尾的最小等车时间。那么  $$f_i = \min_{j\le i-m} \lbrace f_j+\sum_{j<t_k\le i} (i-t_k) \rbrace$$ 这样的时间复杂度为 $O(t^3)$ 必须优化。  二 考虑前缀和优化，令 $sum_i$ 为从 $1$ 到 $i$ 的总时间是多少， $cnt_i$ 为从 $1$ 到 $i$ 有多少个人，那么转移方程优化为 $$...

分析 数据范围很小，可以考虑快排，再通过去重函数一下直接求解。时间复杂度为 。也可以开四个变量 扫一次得出答案。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 10010; LL a[N],n,m; int main() { scanf("%lld",&m); for(int i =1;i <= m;i++ )scanf("%lld",&a[i]); sort(a+1,a+1+m); n = unique...