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


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

洛谷P1337/JSOI2004 平衡点

题意略数据范围:$1 \le n \le 1000$题解模拟退火#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> using namespace std; const int N=1000+10; const double D=0.998; const i...
November 5, 2019

洛谷P4151/WC2011 最大XOR和路径

题意给出一张无向图,求$1 \rightarrow n$的最大异或和路径数据范围:$n \le 50000,m \le 100000,d_i \le 10^{18}$题解考虑没有环的情况,答案为$dis[n]$若存在环,由于从$1 \rightarrow n$的路径上到环上的路径需要走两遍(去/回),相当于没有计算因此统计图上环的异或和,再与$dis[n]$异或求最大值而多个值异或的最大值可...