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


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]$异或求最大值而多个值异或的最大值可...
November 5, 2019

洛谷P3857/TJOI2008 彩灯

题意每个开关能控制若干个彩灯(亮/暗),求这些彩灯有多少种样式数据范围:$n,m \le 50$题解将每个开关控制的彩灯视为一个$01$串,开关之间进行的相当于异或操作,求最后有多少不同的$01$串容易想到线性基设线性基内元素数为$k$,答案即为$2^k$代码:#include<iostream> #include<cstdio> #include<algori...
November 5, 2019

洛谷P4427/BJOI2018 求和

题意给出一棵树,$m$个询问,求从点$u$到点$v$的路径上所有节点深度的$k$次方和$\bmod \ 998244353$数据范围:$1 \le n,m \le 300000,1 \le k \le 50$题解对每一个$k$求一个树上前缀和答案为$$u+v-lca(u,v)-fa[lca(u,v)]$$代码:#include<iostream> #include<cstd...
November 5, 2019

洛谷P1505/国家集训队 旅游

题意给出一颗有边权的树,有$5$种操作:覆盖一条边的边权将$u$到$v$路径上的边权变为相反数询问$u$到$v$路径上的边权和询问$u$到$v$路径上的边权最大值询问$u$到$v$路径上的边权最小值数据范围:$n,m \le 20000$题解考虑将边权下放,随后此问题可用树链剖分解决线段树维护和,最大值,最小值及相反数标记区间处理的时候注意是否处理到$\text{LCA}$代码:#inclu...