2019年4月

昨天突发奇想想在笔记本的VSCode里搞个Live Share,本以为装个插件就完事,结果遇到很多锅折腾了很久。先装完插件,插件那栏倒是有,但是重启了几次都没有看到左下角的Live Share按钮。就先直接点“开始协作会话”,然后报错:command 'liveshare.startFromActivityBar' not found以为是没有登录,就在浏览器里先登录,然后点击“遇到问题”,...
软件 其它-Ubuntu 其它-VSCode
题意给 $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&...
题解 算法-二分/三分 图论-负环
省选/NOI-
题意给一个 $N\times N$ 网格图,汽车从 $(1,1)$ 走到 $(N,N)$ 。网格图中有加油站,汽车到了加油站就会被强制加油花费 $A$ ;如果没油了也可以设立一个油库并加油,花费 $C+A$ ;如果往回走( $X,Y$ 坐标有一个减小)会花费 $B$ 。汽车邮箱容量为 $K$ ,每走一条边消耗 $1$ 单位的油。求花费的最小值。题解朴素的 $bfs$ 就可以过,不过会成为反向...
题解 算法-搜索 题目-网络流24题
省选/NOI-
题意给出一个有向图,需要从 $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]$ 表示 $...
题解 算法-搜索 算法-状态压缩 题目-网络流24题
省选/NOI-
题意有一个无向带权连通图,每条边是黑色或白色。求一棵最小权的恰好有 $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[]$...
题解 图论-最小生成树
省选/NOI-
因为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$...
题解
NOI/NOI+/CTSC
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划52 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP16 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP3 图论4 图论-LCA4 图论-Tarjan11 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束4 图论-强连通分量2 图论-最小环1 图论-最小生成树6 图论-最短/最长路19 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点5 图论-负环4 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集2 数据结构-栈1 数据结构-树状数组6 数据结构-树链剖分10 数据结构-线段树5 数据结构-队列1 比赛-Codeforces21 比赛-JX Round1 比赛-NOIp/CSP5 算法-KM算法1 算法-二分/三分12 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序2 算法-排序3 算法-搜索21 算法-模拟5 算法-状态压缩4 算法-贪心10 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2