1.点差分： 求解问题： 给一棵树，和一些路径的起点和终点，求树上的每个点被路径经过的次数。 求解步骤：   1.假设路径的起点：     s    s   s ，终点：     t    t   t，     a   =   l   c   a   (   s   ,   t   )    a=lca(s,t)   a=lca(s,t) ，     f   a   [   a   ]    fa[a]   fa[a] 为      a    a   a 的父亲节点,     p   u   m   [   x   ]    pum[x]   pum[x] 为每个点别路径的经过次数，那么对于每...

总的来说，应该是前三场中最难的了。 题解 A.牛牛的DRB迷宫I：    现在来看，很明显的状态递推，第一次看的是竟然没有想到，一直到最后才突然发现。（棋盘型      d   p    dp   dp）。 #include <bits/stdc++.h> using namespace std; const int mod=1e9+7; typedef long long ll; char ss[55][55]; ll dp[55][55]; int main() { int n,m; scanf("%d%d",&n,&m); for(int ...

G.判正误： 牛可乐有七个整数      a   ,   b   ,   c   ,   d   ,   e   ,   f   ,   g    a,b,c,d,e,f,g   a,b,c,d,e,f,g ，并且他猜想       a   d    +    b   e    +    c   f    =   g    a^d+b^e+c^f=g   ad+be+cf=g。但 牛可乐无法进行如此庞大的计算。 请验证：牛可乐的猜想是否成立。 输入： 第一行一个正整数      T    T   T，表示有      T    T   T 组数据。 每组数据输入一行七个整数      a   ...

定义：   将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。就是一种技巧，为了方便处理问题。   形式：重链剖分，长链剖分等。此处讲述重链剖分。 重链剖分：   可以将树上的任意一条路径划分成不超过      l   o   g   n    logn   logn 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的      L   C   A    LCA   LCA 为链的一个端点）。还能保证划分出的每条链上的节点      D   F   S    DFS   DFS 序连续。   树上每个节点都属于且仅属于一条重链 。 性质： （1）重...

题目链接 J. u’s的影响【矩阵快速幂+欧拉降幂】 首先，先推出前几项：      1   :   x    1:x   1:x      2   :   y    2:y   2:y      3   :   x   y    a   b     3:xya^b   3:xyab      4   :   x    y   2     a    2   b      4:xy^{2}a^{2b}   4:xy2a2b      5   :    x   2     y   3     a    4   b      5:x^{2}y^{3}a^{4b}   5:x2y3a4b      6...

区间每个点的值都开方。   由于数据范围，开方的次数较小。一个点开方的次数不超过7次，所以可以做到每个点都修改，同时注意限制修改次数。 #include <bits/stdc++.h>//线段树区间不等更新 using namespace std; const int N=1e5+5; typedef long long ll; ll a[N],tree[N<<2]; void build(int l,int r,int rt) { if(l==r) { tree[rt]=a[l]; return; } int mid=(l+r)>>1; build(l,m...

定义：   1.找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。   2.从树中去掉某点以及和该点相连的所有边后，整棵树变为许多"块"。去掉任意一个重心（相比于去掉其他点）可以使得生成的各个"块"的节点数的最大值最少。   3.对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。   实际上树的重心在树的点分治中有重要的作用, 可以避免N^2的极端复杂度（从退化链的一端出发），保证NlogN的复杂度, 利用树型dp可以很好地求树的重心。 <m...

树的直径：   树的直径指树上距离最远的两点间的距离，它在树上问题上有许多应用，往往通过树的直径的性质可以将一个高时间复杂度的解法变为线性求解。 树的直径的性质：      (   1   )    (1)   (1).对树上的任意一点而言，树上与它距离最远的点一定为树的直径的两个端点的其中之一;      (   2   )    (2)   (2).直径两端点一定是两个叶子节点;      (   3   )    (3)   (3).对于两棵树，如果第一棵树直径两端点为     (   u   ,   v   )    (u,v)   (u,v)，第二棵树直径两端点为     (   x...

题意：   一串数共     n    n   n个，排成一列，有      n    n   n个人对数进行操作，每次去数列的第一个或最后一个。现在你的位置是第     m    m   m个，并且你可以控制任意      k    k   k 个人的选择。问你所能取到的最大的数的最小值是多少？ <mark>关键还是在于思考的角度！</mark>   由于有些人是不能控制的，所以他们的选择的所有情况都要考虑。   如果      k   >   =   m   −   1    k>=m-1   k>=m−1 ,那么最终结果是可以控制的。否则，就要枚...

  一开始认为根节点和深度最深的节点一定要选择（其实是错的），确定了两个点后枚举第三个点，用倍增求深度最深的点和枚举的点的lca,确定第三个点。 正解：   用两次      d   f   s    dfs   dfs 求出树的直径的两个端点，即可求得两个点。如果直径长度     =   n   −   1    =n-1   =n−1，那么第三个点可以任意选择。如果不是，用多源      b   f   s    bfs   bfs 求出离直径最远的点即为第三个点。 #include <bits/stdc++.h> using namespace std; const int ...

算法学习： dp 记忆化搜索 莫比乌斯反演(1) 狄利克雷卷积(1) 杜教筛 卢卡斯定理 概率与期望 FFT NTT FWT LCA(1) 树上差分 差分约束(1) 树上问题 线段树（权值线段树，可持久化线段树） 树状数组 笛卡尔树 分块 点分治 字符串： 拓展KMP(1) AC自动机(1) 字符串哈希 后缀数组 Manacher 补题： 区域赛： 2019 ICPC Asia Nanchang Regional  2019 ICPC Asia Xuzhou Regional 2019 ICPC Asia Nanjing Regional  2019 ICPC Asia Yinchuan Re...

具体见此

定义：   最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 性质： 1.     L   C   A   (   u   )   =   u    LCA(u)=u   LCA(u)=u; 2.      u    u   u是     v    v   v的祖先，当且仅当     L   C   A   (   u   ,   v   )   =   u    LCA(u,v)=u   LCA(u,v)=u； 3. 如果     u    u   u不为     v    v   v的祖先并且  ...

定义： 即：两个积性函数的狄利克雷卷积仍为积性函数。   数论函数是积性及加性函数。 运算法则：  狄利克雷卷积的时间复杂度：     O   (   n   ∗   l   o   g   n   )    O(n*logn)   O(n∗logn) 计算狄利克雷卷积      h   (   n   )    h(n)   h(n)： 如果再像暴力计算那样，复杂度将达到恐怖的     O   (   n    n    )    O(n\sqrt{n})   O(nn ​)。 但是我们可以从质数筛（埃式筛）的想法入手，我们可以直接枚举一个i，再为它的倍数上的值加上对应的贡献就好。 时间复杂...