ゆめぼくらでって
きたるべきのためによる


November 11, 2019

洛谷P1122 最大子树和

题意求树上联通块的最大权值和数据范围:$n \le 16000$题解树形$\text{dp}$用$dp[u]$表示以$u$为根的子树中的最大权值和代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; co...
November 11, 2019

CF543B Destroying Roads

题意在这个国家有$n$个城市,城市间由$m$条双向公路连接。城市被编号为$1$到$n$ 。如果城市$a$和$b$被公路连接,那么你可以双向通行。你可以在这个公路网上通过公路从一个城市移动到另一个城市。走过每条公路均耗时$1$小时你想要破坏最多的公路,但是破坏后必须满足从指定城市$s_1$ 到$t_1$最短不超过$l_1$小时,且从指定城市$s_2$到$t_2$最短不超过$l_2$​ 小时计算...
November 11, 2019

CF449B Jzzhu and Cities

题意$n$个点,$m$条带权边的无向图,另外还有$k$条特殊边,每条边连接$1$和$i$问最多可以删除这$k$条边中的多少条,使得每个点到$1$的最短距离不变数据范围:$1 \le n,k \le 10^5,1\le m \le 3\times 10^5$题解最短路计数,判断这几条边是否再最短路上或这几个点有没有别的最短路可以达到代码:#include<iostream> #in...
November 9, 2019

洛谷P4015 运输问题

题意有$m$个仓库和$n$个零售商店。第$i$个仓库有$a_i$个单位的货物;第$j$个零售商店需要$b_j$个单位的货物从第$i$个仓库运送每单位货物到第$j$个零售商店的费用为$c_{ij}$试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少数据范围:$1 \le n,m \le 100$题解建立超级源点与超级汇点由超级源点向每个仓库建流量为$a_i$,费用为$0$的边...
November 9, 2019

洛谷P4009 汽车加油行驶问题

题意略数据范围:$2 \le n \le 100,2 \le k \le 10$题解将油量视为状态,分层建图之后跑最短路即可(也可跑费用流)代码:#include<iostream> #include<cstdio> #include<queue> #include<memory.h> using namespace std; const in...
November 8, 2019

洛谷P2710 数列/洛谷P2042/NOI2005 维护数列

题意维护一个数列,共$7$种操作区间插入区间删除区间翻转区间覆盖区间求和单点查询区间最大连续子序列和数据范围:$1 \le n \le 200000,1 \le m \le 20000$题解使用$\text{fhq-Treap}$维护为每一个节点记录区间和与前缀/后缀/整体最大连续字段和,更新时考虑左右是否相接注意最大连续字段和至少选一个inline void node::pushUp(){...
November 7, 2019

洛谷P2534/AHOI2012 铁盘整理

题意给出一个数列,一次可以翻转$1 \dots i(i\in[1,n])$的数,求最少操作多少次使得数列单增数据范围:$1 \le n \le 50,1 \le r \le 100$题解先离散化,原数列转化为$1 \dots n$的一个排列此时进行一次翻转最多只能改变一对相邻数的差,而最终状态即为相邻数的差都为$1$因此将估价函数定为inline int eva(){ int res...
November 7, 2019

洛谷P2324/SCOI2005 骑士精神

题意给出一个初始棋盘,要求移动成目标棋盘,询问是否能在$15$步内做到;若能,输出最少步数;否则输出$-1$数据范围: 棋盘为$5 \times 5$题解移动马则考虑的情况过于复杂,因此选择移动空位迭代加深搜索:逐步加大搜索的步数;但对于$-1$情况仍然需要搜完增加估价函数,计算有多少个位置不同(即所需的可能最小步数)inline int eva(){ int res=0; ...