题意给出一个有向图，需要从 $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$...
话说我题目难度的数据该更新了，这个bug信息先鳖管它 UPD2019.4.12:更新完毕不得不说洛谷评测机真的慢，loj和jxoj都跑过了，在洛谷我硬是试了半天才过。JXOJ比你们洛谷不知道高到哪里去了我做法跟大部分题解一样，其实是看了题解我才会做的。还是应用连续异或的性质，直接存异或的前缀和 $s[i]$ ，求区间 $\left[ l,r \right]$ 的异或即为：$$\bigoplu...
这道题做法还是比较容易想到的，就是码量有点大。不严格次小生成树的思路就是先得到最小生成树，然后枚举每一条不在树里的边，找到所构成的环上权值最大的边替换掉。而这道题要求严格次小，那么权值最大的边就不能与枚举的边权值相同，如果相同就替换环上次大的边即可。我还是敲了树剖，对于最大和次大边我用pair来存，可能是STL的缘故不开O2只有90。在合并（线段树合并和lca两侧合并）时对最大和次大的处理如...
题意给一棵有 $n$ 个节点的树，然后再连 $m$ 条不重合的附加边，可以删除一条树边和一条附加边，问有多少种删除方法可以使树断裂。题解显然，每次加一条边以后树上一定会形成环，这个环任意断附加边就可以形成树，而树上任意断一条边就可以使树断裂。但是有可能会形成很多有重叠部分的环，这样按照上述方法不一定可以让树断裂。所以我们可以对每一条树边 $i$ 记录包含它的环的个数 $f[i]$ ，然后进行...
这似乎是个很经典的题，但因为我很菜所以现在才做。显然，一个 $\le 10^{5}$ 的数最多经过 $6$ 次开方就一定可以变成 $1$ ，所以我们可以用线段树对每次询问进行单点修改，如果区间最大值 $\le 1$ 就不需要进行修改了。这样最多每个数修改 $6$ 次，查询直接区间查询，总时间复杂度是 $O(n\times \log n + 6n)$ 。struct Tree{
ll ...
肝总结肝的我肝疼。10026.电路维修把题意转化一下，可以把每个端点看成节点，有导线相连的对角线就连一条边权为0的边，不相连的对角线就连一条边权为1的边。然后用最短路什么的做就行了。看题解里面说最短路比较慢，再加上本来就该练习广搜，我就写了双向广搜。struct Edge{
int next,to,w,from;
} edge[1000005];
int n,m,t,cnt,head...