也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 原题链接 概括一下题意 给一颗有     n    n   n个点带边权的树，有     m    m   m个询问，每次询问     u   ,   v    u,v   u,v两点间的权值和，你可以将树中任意一条边的边权变为     0    0   0，问经过一次修改，这     m    m   m个询问中最大的权值和最小可以是多少      S   o   l   u   t   i   o  ...

也许更好的阅读体验 树的重心 树的重心的定义 找到这样一个节点，使以其作为根节点时，最大的子树所含节点数最少 解决方法很简单，随便扯一个节点作为根节点，然后算一个点时考虑完所有儿子后再考虑一下父亲作为子树的答案即可 两种打法 int dfs (int x,int fa,int m)//m为树的节点数 { son[x]=1,ms[x]=0;//ms max_num_of_son int tans=2000; for (int e=head[x];e;e=nxt[e]){ if (to[e]==fa) continue; int t=dfs(to[e],x,m); if (ms[tans]>...

也许更好地阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 经典的约瑟夫问题 一开始有      n    n   n 个人围成一个圈,他们的编号从     0    0   0到     n   −   1    n-1   n−1, 从      1    1   1 开始顺时针报数, 报出      m    m   m 的人被机关处决. 然后下一个人再从      1    1   1 开始报数, 直到只剩下一个人. 问最后剩下的人的编号.      n ...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 原题链接 题目大意 该题目有两个问题        T   a   s   k  <mtext>   </mtext>  1    Task\ 1   Task 1,有     n    n   n个人     n    n   n个座位，每个人都有一个对应的座位，每个人排队进入去坐座位，小     A    A   A是第一个，然而小     A    A   A忘记了自己的位置...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 给定一张      n    n   n 个点      m    m   m 条边的无向图，每条边连接两个顶点，保证无重边自环，不保证连通。 你想在这张图上进行若干次旅游，每次旅游可以任选一个点      x    x   x 作为起点，再走到一个与      x    x   x 直接有边相连的点      y    y   y，再走到一个与      y    y   y 直接有边相连的点     ...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description  复杂度要求     O   (   n   )    O(n)   O(n)      S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution 有一个显而易见的定理  在中间过程若     A    A   A让     B    B   B往前移动，那么之后两者都是只让对方往前移动 若自己往前移动，那么两者都是只往前移动  因为都采...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description 原题链接: Comet OJ 洛谷 大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩（记为D）上去。河心有几片菏叶（分别记为     Y   1   ​   …   Y   m   ​   ）    Y1​…Ym​）   Y1​…Ym​）和几个石墩（分别记为     S   1   …   S   n   ）    S1…Sn）   S1…Sn）。图示如下：  青蛙的站队和移动方法规则...

也许更好的阅读体验      D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description        S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution 这里就不用     N   ,   M    N,M   N,M，还是     n   ,   m    n,m   n,m写的习惯些 直接计算一个方案是十分不方便的 所以考虑容斥 设     g    (   d   )     g\left(d\right)   ...

也许更好的阅读体验  文章目录  前置知识 中国剩余定理(CRT)  目的 求法 Code  扩展中国剩余定理(EXCRT)  目的 解法 code     前置知识 快速乘 扩展欧几里得定理 同余方程 中国剩余定理(CRT) 目的 求最小的正整数     x    x   x，使其满足      {     <mstyle displaystyle="false" scriptlevel="0">   x   ≡    a   1     (   m   o   d  <mtext>   </mtext>  m   ...

也许更好的阅读体验  文章目录  作用与使用前提 求法 举例  $\mu$ $\varphi$    作用与使用前提 对一个积性函数     f    f   f，我们要求     f    f   f的前     n    n   n项和      S   n     S_n   Sn​，并且要求在比线性复杂度更低的复杂度情况下求出 若有数论函数     g   ,   h    g,h   g,h，满足      h   =   f   ∗   g    h=f*g   h=f∗g 其中     ∗    *   ∗为狄利克雷卷积 并且     h    h   h的前缀非常好求，    ...

也许更好的阅读体验  文章目录  定义  集合幂级数 约定 卷积运算  加法 减法 乘法   快速求法  分治 快速莫比乌斯变换(FMT) 快速沃尔什变换(FWT)     本文主要内容是对武汉市第二中学吕凯风同学的论文《集合幂级数的性质与应用及其快速算法》的理解 定义 集合幂级数 为了更方便的研究集合的卷积，引入集合幂级数的概念 集合幂级数也是形式幂级数的一种，只是集合的一种表现形式，无需考虑收敛或发散的含义 定义一个集合      S    S   S 的集合幂级数为      f    f   f ，那么我们就可以把集合      S    S   S 表示为如下形式       &lt...

主线任务    NOIP历年题目      ←   d   o   i   n   g    \leftarrow doing   ←doing   生成函数 (BOSS)   多项式 (BOSS)   FWT   FMT   可持久化Trie树   分治FFT      ←   50   %    \leftarrow 50\%   ←50% 未打代码   任意模数NTT   斯特林数 (BOSS)   斯特林数习题 (BOSS)      ←   80   %  <mtext>   </mtext>  p   a   s   s    \leftarrow 80\%...

也许更好的阅读体验 问题描述 给一张     n    n   n个点，     m    m   m条边的简单无向图，求解有多少个三元环 三元环：一个三元组     (   i   ,   j   ,   k   )    \left(i,j,k\right)   (i,j,k)表示三个点，要求存在边      (   i   ,   j   )    ,    (   i   ,   k   )    ,    (   j   ,   k   )     \left(i,j\right),\left(i,k\right),\left(j,k\right)   (i,j),(i,k),(j,...

也许更好的阅读体验  文章目录  表达 证明   表达 若有     f   (   n   )   =    ∑    i   =   0    n     (    n   i    )    g   (   i   )    f(n)=\sum_{i=0}^n\binom{n}{i}g(i)   f(n)=∑i=0n​(in​)g(i) 则有     g   (   n   )   =    ∑    i   =   0    n    (   −   1    )    n   −   i      (    n   i    )    f   (   i   )    g(n)=\s...