A fresh start.

题意给一个 $N\times N$ 网格图,汽车从 $(1,1)$ 走到 $(N,N)$ 。网格图中有加油站,汽车到了加油站就会被强制加油花费 $A$ ;如果没油了也可以设立一个油库并加油,花费 $C+A$ ;如果往回走( $X,Y$ 坐标有一个减小)会花费 $B$ 。汽车邮箱容量为 $K$ ,每走一条边消耗 $1$ 单位的油。求花费的最小值。题解朴素的 $bfs$ 就可以过,不过会成为反向...
   题解    0 条评论
省选/NOI-
题意给出一个有向图,需要从 $1$ 走到 $N$ ,可以在一个城市买水晶球并在另一个城市卖掉,也可以不买,问最多能赚多少钱。其中 点数$n\le 100000$ ,边数$m\le 500000$ 。题解分层图最短路。对于原图,买卖操作各建一层图,边权为在起点买卖水晶球的花费(买为负卖为正)。给原图、买、卖分别编号为 $1,2,3$ 。已知 $x$ 点买卖水晶球的花费为 $s[x]$ ,对于每...
   题解    0 条评论
提高+/省选-
题意有一个 $N\times M$ 的长方形迷宫,相邻两个单元之间可能有不能通过的墙或可以用第 $Q_i$ 种钥匙打开的门,有的单元中有第 $Q_i$ 种钥匙。从 $(1,1)$ 出发,目标是 $(N,M)$,每次只能移动一个单元,求最短移动时间。其中 $N,M\le 10$ ,钥匙的种类数 $P\le 10$ 。题解钥匙的种类数不多,考虑直接状压搜索。用 $s[x][y][i]$ 表示 $...
   题解    0 条评论
省选/NOI-
题意有一个无向带权连通图,每条边是黑色或白色。求一棵最小权的恰好有 $need$ 条白色边的生成树。保证有解。题解我最开始想的是直接先对白边跑有 $need$ 条边的最小生成树,再对黑边跑剩下的就行了。但打到一半突然发现不行,于是便跑去看题解。显然直接跑最小生成树白边就很可能多或者少。如果多了就说明白边的权值大多比较小,那么我们就可以给所有白边加一个权值 $x$ 然后再跑;如果白边少了同理。...
   题解    0 条评论
提高+/省选-
题意求无向图最小环,要求输出路径。其中点数 $N\le 100$题解本来求最小环挺简单的,恶心的就是这道题还要求输出路径。求最小环的方法就是用 $spfa$ 跑最短路,得到最初的距离 $dis[u][v]$ 和最短路 $mn[u][v]$ 。那么对于每个节点 $x$ ,它与 $u$ 和 $v$ 相邻,那么他们最小环的长度即为:$$mn[u][v]+dis[x][u]+dis[x][v]$$每...
   题解    0 条评论
题意给一个无向图,求严格次小最短路。其中点数 $N\le 5000$ ,边数 $R\le 100000$ 。题解在跑最短路的时候维护一个次短路即可。具体做法是每次枚举的边权先与最短路比较,将较小值给最短路,较大值再与次短路比较。剪枝是如果当前枚举的边比次短路还大就退出。需要注意的是不能用 $vis[]$ 数组来进行判重,可能是因为次短路的缘故不只跑一次吧。#include<bits/s...
   题解    0 条评论
提高+/省选-
题意求 从$1$ 到 $N$ 的一条路径,使得第 $K+1$ 长的边权尽可能小。其中点数 $N\le 1000$ ,边数 $P\le 2000$,权值 $L_i\le 10^{6}$题解直接求肯定没有办法,所以考虑二分答案。对第 $K+1$ 长的边权 $x$ 进行二分,每次检验就跑一次 $Dijkstra$ ,只是把边权变为 $>x$ 的边的条数,这样就可以得到$>x$ 的边最少...
   题解    0 条评论
提高+/省选-
题意给一个无向简单图,求最小生成树的个数,对 $31011$ 取模。其中点数 $n\le 100$ ,边数 $m\le 1000$ 。题解有个性质:在不同的最小生成树中,每种权值的边的数量一定相同。这道题又有个限制:具有相同权值的边不会超过 $10$ 条,那么就可以直接用那个性质来暴力了。先跑出来最小生成树,记录下来每种权值的边的数量 $t\_cnt[]$ 以及每种权值的起始位置 $l[]$...
   题解    0 条评论
省选/NOI-
因为NOIp考爆本来不想去的,然后被建军和徐妈威逼利诱去了,于是还是来划水了。Day1说是 $9$ 点到 $12$ 点报道,然后徐妈觉得是 $9$ 点之前,然后我们一行在早高峰挤地铁那滋味真酸爽,关键是还没吃早饭,直到 $10$ 点报完到才吃。中午点了开封菜的外卖就开始颓废,话说还有一盒土豆泥和一个鸡腿没吃完,太可惜了。下午去水笔试,看了下资料,纯凭感觉,说是考 $1h$ 事实上 $10 m...
   游记    1 条评论
图文无关出道裸题觉得简单了非要上树系列。如果没在树上就是裸的可持久化字典树,在树上写个树剖就完事了。#include<bits/stdc++.h> using namespace std; inline int read() { char ch=getchar(); int f=1,x=0; while (ch<'0' || ch>'9')...
   题解    0 条评论
省选/NOI-