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


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; ...
November 6, 2019

洛谷P2633 Count on a tree

题意给出一棵带点权的树,$m$个询问,求$u \rightarrow v$路径上第$k$小的点权数据范围:$n,m \le 100000$ [强制在线]题解树上静态区间第$k$小,使用主席树维护序列上的主席树使用的是前缀和思想;那么自然,在树上的情况就要用到树上前缀和建树的时候在其父节点的基础上拷贝包含$u \rightarrow v$路径上的信息的应为$$T[u]+T[v]-T[lca(u...
November 6, 2019

洛谷P3850/TJOI2007 书架

题意给出一个序列,$2$种操作指定位置插入询问第$k$个数据范围:$1 \le n \le 200,1 \le m \le 10^5,1 \le q \le 10^4$题解$\text{fhq-Treap}$,按排名分割代码:#include<iostream> #include<cstdio> using namespace std; const int N=200...
November 6, 2019

洛谷P4318 完全平方数

题意求第$k$个不含完全平方数因子的数数据范围:$k \le 10^9$题解二分这个数,然后验证其排名是否$\ge k$对于计算$n$以内的无平方因子数的个数,可以用到容斥原理$$ans=含0个质数的平方因子的个数-含1个质数的平方因子的个数+含2个质数的平方因子的个数 \dots$$注意到每个数的容斥系数恰好为莫比乌斯函数$\mu(i)$,上式即为$$\sum_{i=1}^{\lfloor...