昨天突发奇想想在笔记本的VSCode里搞个Live Share，本以为装个插件就完事，结果遇到很多锅折腾了很久。先装完插件，插件那栏倒是有，但是重启了几次都没有看到左下角的Live Share按钮。就先直接点“开始协作会话”，然后报错：command 'liveshare.startFromActivityBar' not found以为是没有登录，就在浏览器里先登录，然后点击“遇到问题”，...
题意给 $N$ 个人分糖。有 $K$ 个要求，格式为 $(X,A,B)$ ，表示对第 $A$ 个人和第 $B$ 个人有第 $X$ 种限制，用 $S_i$ 表示第 $i$ 个人分得的糖数：$X=1$ ， $S_A=S_B$$X=2$ ， $S_A<S_B$$X=3$ ， $S_A\geq S_B$$X=4$ ， $S_A>S_B$$X=5$ ， $S_A\le S_B$求最少需要准...
题意给一个有向图，如果有负权回路输出-1，否则输出从起点 $S$ 到各个点的最短路长度，如果不连通输出NoPath。其中点数 $N\le 1000$ ，边数 $M\le 100000$ 。题解做法很显然，就是判负环+最短路。最开始我用的深搜 $spfa$ 判负环，求最短路就顺便继续用，然后就很开心的被卡超时了。正解就是用广搜 $spfa$ ，但我又不想删判负环的所以就写了两个。#includ...
题意定义圈的平均值为一个环上所有边的权值和 $\div$ 边的个数。给出一个有向图，求最小圈的平均值，保留 $8$ 位小数。其中点数 $n\le 3000$ ，边数 $m\le 10000$ 。题解$0/1$ 分数规划，直接二分答案 $mid$ ，然后对每条边减去 $mid$ 再跑 $spfa$ 判负环。如果有负环就缩小上界，否则增大下界。#include<bits/stdc++.h&...
题意给一个 $N\times N$ 网格图，汽车从 $(1,1)$ 走到 $(N,N)$ 。网格图中有加油站，汽车到了加油站就会被强制加油花费 $A$ ；如果没油了也可以设立一个油库并加油，花费 $C+A$ ；如果往回走（ $X,Y$ 坐标有一个减小）会花费 $B$ 。汽车邮箱容量为 $K$ ，每走一条边消耗 $1$ 单位的油。求花费的最小值。题解朴素的 $bfs$ 就可以过，不过会成为反向...
题意给出一个有向图，需要从 $1$ 走到 $N$ ，可以在一个城市买水晶球并在另一个城市卖掉，也可以不买，问最多能赚多少钱。其中 点数$n\le 100000$ ，边数$m\le 500000$ 。题解分层图最短路。对于原图，买卖操作各建一层图，边权为在起点买卖水晶球的花费（买为负卖为正）。给原图、买、卖分别编号为 $1,2,3$ 。已知 $x$ 点买卖水晶球的花费为 $s[x]$ ，对于每...
题意有一个 $N\times M$ 的长方形迷宫，相邻两个单元之间可能有不能通过的墙或可以用第 $Q_i$ 种钥匙打开的门，有的单元中有第 $Q_i$ 种钥匙。从 $(1,1)$ 出发，目标是 $(N,M)$，每次只能移动一个单元，求最短移动时间。其中 $N,M\le 10$ ，钥匙的种类数 $P\le 10$ 。题解钥匙的种类数不多，考虑直接状压搜索。用 $s[x][y][i]$ 表示 $...
题意有一个无向带权连通图，每条边是黑色或白色。求一棵最小权的恰好有 $need$ 条白色边的生成树。保证有解。题解我最开始想的是直接先对白边跑有 $need$ 条边的最小生成树，再对黑边跑剩下的就行了。但打到一半突然发现不行，于是便跑去看题解。显然直接跑最小生成树白边就很可能多或者少。如果多了就说明白边的权值大多比较小，那么我们就可以给所有白边加一个权值 $x$ 然后再跑；如果白边少了同理。...
题意求无向图最小环，要求输出路径。其中点数 $N\le 100$题解本来求最小环挺简单的，恶心的就是这道题还要求输出路径。求最小环的方法就是用 $spfa$ 跑最短路，得到最初的距离 $dis[u][v]$ 和最短路 $mn[u][v]$ 。那么对于每个节点 $x$ ，它与 $u$ 和 $v$ 相邻，那么他们最小环的长度即为：$$mn[u][v]+dis[x][u]+dis[x][v]$$每...
题意给一个无向图，求严格次小最短路。其中点数 $N\le 5000$ ，边数 $R\le 100000$ 。题解在跑最短路的时候维护一个次短路即可。具体做法是每次枚举的边权先与最短路比较，将较小值给最短路，较大值再与次短路比较。剪枝是如果当前枚举的边比次短路还大就退出。需要注意的是不能用 $vis[]$ 数组来进行判重，可能是因为次短路的缘故不只跑一次吧。#include<bits/s...
题意求 从$1$ 到 $N$ 的一条路径，使得第 $K+1$ 长的边权尽可能小。其中点数 $N\le 1000$ ，边数 $P\le 2000$，权值 $L_i\le 10^{6}$题解直接求肯定没有办法，所以考虑二分答案。对第 $K+1$ 长的边权 $x$ 进行二分，每次检验就跑一次 $Dijkstra$ ，只是把边权变为 $>x$ 的边的条数，这样就可以得到$>x$ 的边最少...
题意给一个无向简单图，求最小生成树的个数，对 $31011$ 取模。其中点数 $n\le 100$ ，边数 $m\le 1000$ 。题解有个性质：在不同的最小生成树中，每种权值的边的数量一定相同。这道题又有个限制：具有相同权值的边不会超过 $10$ 条，那么就可以直接用那个性质来暴力了。先跑出来最小生成树，记录下来每种权值的边的数量 $t\_cnt[]$ 以及每种权值的起始位置 $l[]$...
因为NOIp考爆本来不想去的，然后被建军和徐妈威逼利诱去了，于是还是来划水了。Day1说是 $9$ 点到 $12$ 点报道，然后徐妈觉得是 $9$ 点之前，然后我们一行在早高峰挤地铁那滋味真酸爽，关键是还没吃早饭，直到 $10$ 点报完到才吃。中午点了开封菜的外卖就开始颓废，话说还有一盒土豆泥和一个鸡腿没吃完，太可惜了。下午去水笔试，看了下资料，纯凭感觉，说是考 $1h$ 事实上 $10 m...
图文无关出道裸题觉得简单了非要上树系列。如果没在树上就是裸的可持久化字典树，在树上写个树剖就完事了。#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')...
又看了一圈题，感觉只有这个和树有关的题貌似可以做。然并卵，靠自己还是只有打暴力，甚至把链都推错了。我最开始认为链就是所有点之和，然后很开心的WA了。看了题解才醒悟过来根节点 $1$ 不一定在链的端点，对于链应该对根节点两端建堆，然后贪心从两端各取一个取较大值计入答案。正解就是对每个子树作链的操作，一遍dfs就出来了。具体做法是对每个节点建堆，在回溯时对当前节点 $x$ 枚举所有子节点 $y$...