题目链接 题意 有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。 现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。 在每次行程开始时，你手上有价值为 c 的珠宝，每经过一个城市时（包括 u 和 v ），假如那个城市中售卖的珠宝比你现在手上的所有珠宝的最大值要优秀（价值更高，即严格大于），那么你就会选择购入。现在你想要对每一次行程，求出会进行多少次购买事件。 思路 保证v在u通往首都的最短路上，也就是说v是u,v的lca，从u到v，每经过一个珠宝价...

题意 给定一个值 s 和一棵树。在树的每个节点有一个权值，第 i 个点的权值为a[i]，问有多少条路径的节点权值总和为 s。路径中节点的深度必须是升序的。假设节点 1 是根节点，根的深度是 0，它的儿子节点的深度为 1。路径不必一定从根节点开始。 思路 路径必须是从低深度到高深度，也就是路径端点一定是祖先儿子关系，考虑倍增思路，预处理出f[i][j]：i节点的第2^ j个父亲是谁，dp[i][j]：i节点到第2^ j个父亲之间路径节点和（不包括i，包括2^j）。dfs枚举每一个节点，f[i][j] = f[f[i][j - 1]][j - 1] ；dp[i][j] = dp[i][j - 1]...

传送门 题意 给你一个N*N（2≤N≤100）的方格中，‘x’表示障碍，‘.’表示没有障碍（可以走），牛牛可以从一个格子走到他相邻的四个格子，但是不能走出这些格子。问牛牛从A点到B点最少需要转90度的弯几次。 思路 拐弯才要花费，把一个点拆成四个点，上下左右，从上到下 和 从左到右建双向边，边权为0；从上到左、从上到右、从下到左、从下到右建双向边，边权为1。建一个源点S和一个汇点T，S向A的四个方向的点建边，边权为0，B的四个方向的点向T建边，边权为1。最后跑dijkstra。 #include <bits/stdc++.h> using namespace std; const ...

传送门 题意 栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A’， 满足(a’1+b1)%k = (a’2+b2)%k = …… = (a’m + bm)%k。 思路 按照题目给的条件式只能暴力做，暴力做又超时。那么对满足式进行修改，(a[i]+b[i])%k=(a[i+1]+b[i+1])%k --> ((a[i]-a[i+1])%k+(b[i]-b[i+1])%k)%k = 0，问一个序列里有多少个满足条件的连续子序列，显然用kmp，匹配成功的条件改为(a[i]+b[i])%k == 0 就行。 #include <bits/stdc...

传送门 题意 n个点m条边，q次询问求任意两点之间的距离。（n<=1e5，m<=n+100，所有边权为1，保证图连通）。 思路 这个多出的100多条边就很怪，先考虑如果没有多出边，就只有n-1条边，图连通，那么可以建立最小生成树，用LCA来做，任取一点为根，len[i]为i点到根的距离，dis(u,v) = len[u]+len[v]-2 * len[LCA(u,v)]。思考多出来的边(x,y)对答案有什么影响？两种情况：1.在u到v的最短路上 2.不在u到v的最短路上。如果在最短路上的话，那么可以求出以x和y为源点的单源最短路，dis(u,v) = min(len[u]+len[...

传送门 题意 n个城镇，有一些城镇被派兵***，求从1到n通过***的城镇不超过k次的最短距离。 解法 将在某个城镇通过了多少次***的城镇设为一个状态。 d[i][j]：从1到i通过了j次***的城镇。 （或者是分层图的做法，建图的时候定义n*k个点，对于加入的一条边，连接能到达的所有状态。） 用dijkstra算法把每个状态看做一个点跑一遍即可。 需要注意的是题中说的通过了一个***的城镇是 从一个***的点出发到达任意一个点，都会使得次数加1 #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std...