夢に僕らで帆を張って
来るべき日のために夜を超え

2019年10月

October 31, 2019

洛谷P3831/SHOI2012 回家的路

题意$n \times n$的网格图中有$m$个点可转向,求最短路数据范围:$n \le 20000,m \le 100000$题解分层图两层图,每层只建一种方向的边(纵/横),连接两层之间表示转向代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring&g...
October 31, 2019

洛谷P1948/USACO08JAN 电话线Telephone Lines

题意无向图中,可选择$k$条边将边权变为$0$,求最小瓶颈最短路数据范围:$1 \le n,k \le 1000,1 \le m \le 10000$题解分层图每层内建原图,在层之间建边权为$0$的单向边,意为一次变化,因此共$k+1$层为统计答案,由每一层的终点向超级汇点连一条权值为$0$的单向边代码:#include<iostream> #include<cstdio&...
October 31, 2019

洛谷P1768 天路

题意最优比率环数据范围:$1 \le n \le 7000,1 \le m \le 20000$题解$0/1$分数规划要求$$ans=\frac{\sum_i^{i \in E} v_i}{\sum_i^{i \in E} p_i}$$二分这个答案$mid$,将每条边的边更改为$$mid \cdot p_i-v_i$$跑负环即可代码:#include<iostream> #in...
October 31, 2019

洛谷P2850/USACO06DEC 虫洞Wormholes

题意判负环数据范围:$1 \le n \le 500,1 \le m \le 2500$题解$\text{dfs SPFA}$判负环即可代码:#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=510; const int M=5210...
October 31, 2019

洛谷P1849/USACO12MAR 拖拉机Tractor

题意略数据范围:$1 \le n \le 50000$题解优先队列$\text{bfs}$,以移动的干草堆数升序代码:#include<iostream> #include<cstdio> #include<queue> using namespace std; #define mp make_pair typedef pair<int,int>...
October 31, 2019

洛谷P3966/TJOI2013 单词

题意给出$n$个单词,求每个单词共出现几次数据范围:单词总长度$\le 10^6$题解多模匹配,使用$\text{AC}$自动机解决需要注意的是,可能出现重复的单词;为避免字典树的值被覆盖,只记录第一个编号,而将其他相同的单词指向这个编号统计答案时,在该前缀的所有后缀上($\text{Fail}$树上的祖先节点上),将其自身答案累加上去,就是总共出现的次数代码:#include<ios...
October 31, 2019

CF786B Legacy

题意有$3$种连边方式$u \rightarrow v$ 点向点$u \rightarrow [l,r]$ 点向区间$[l,r] \rightarrow u$ 区间向点求从$s$出发的最短路数据范围:$1 \le n,q \le 10^5$题解显然对于向区间建边不能一个一个建,那么能不能直接向整个区间建边呢?联想到线段树的一个节点维护一个区间的信息,那么可以向这个节点建边;这便是线段树优化建...
October 31, 2019

洛谷P1983 车站分级

题意略数据范围:$1 \le n,m \le 1000$题解由题意“则始发站、终点站之间所有级别大于等于火车站$x$的都必须停靠”可知未停靠的站级别一定比$x$的级别小将大小关系转化为图:将车站视为点,由级别小的车站向级别大的车站连边随后从入度为$0$的点入手,用拓扑排序求出答案代码:#include<iostream> #include<cstdio> #inclu...