题目链接 题意 一个有边权的树，提问两点间路径上的边权小于等于某个数的个数 题解 树上主席树模板题，每个节点从他的父亲继承即可 代码 #include<bits/stdc++.h> #define N 100010 #define INF 0x3f3f3f3f #define eps 1e-7 #define pi 3.141592653589793 #define mod 998244353 // #define P 1000000007 #define LL long long #define pb push_back #define fi first #define se s...

带修改主席树的模板题 主席树和树状数组都是维护前缀和，树状数组的每一个结点表示一颗权值线段树，当然要动态开点 每次修改      p   o   s    pos   pos， 则将      p   o   s   ,   p   o   s   +   l   o   w   b   i   t   (   p   o   s   )   .   .   .    pos,pos+lowbit(pos)...   pos,pos+lowbit(pos)... 一并修改 询问时，用到      p   o   s   ,   p   o   s   −   l   o   w   b   i...

HDU 3007 最小圆覆盖 #include<bits/stdc++.h> #define N 1000010 #define INF 0x3f3f3f3f #define eps 1e-7 #define pi 3.141592653589793 #define mod 998244353 #define P 1000000007 #define LL long long #define pb push_back #define fi first #define se second #define cl clear #define si size #define lb lowe...

题意 数轴上有两个人，告诉你每个人的指令，即向左/右/不动维持多久，可以随意选择出发点，使得两人在整点位置的见面次数最多 题解 设时刻      i    i   i ,     a    a   a 的位置为      A   [   i   ]   =   A   [   i   −   1   ]   +    R   a    [   i   ]    A[i]=A[i-1]+R_a[i]   A[i]=A[i−1]+Ra​[i] ,     b    b   b 的位置为      B   [   i   ]   =   B   [   i   −   1   ]   +    R ...

题意 给一棵树，初始都是白色，让你染黑色，每个点有两个限制       A   i    ,    B   i     A_i,B_i   Ai​,Bi​ ,即点      i    i   i 的子树黑点的个数不少于       A   i     A_i   Ai​,除了点      i    i   i 的子树，黑点的个数不少于       B   i     B_i   Bi​ 求最少染的黑点的个数 题解 二分答案 则每个点子树的黑点的个数有一个区间范围      [    A   i    ,   m   i   d   −    B   i    ]    [A_i,mid-B_i...

题意 n个线段，覆盖一段区间，附带有两个属性       A   i    ,    B   i     A_i,B_i   Ai​,Bi​ 要求，选出一个线段集合，使得覆盖      [   1   ,   t   ]    [1,t]   [1,t] 并且        ∑    A   i      ∑    B   i       \frac{\sum A_i}{\sum B_i}   ∑Bi​∑Ai​​ 最小 题解 01分数规划 二分答案 设二分的答案为      x    x   x 将属性变为       A   i    −   x   ∗    B   i     A_i-x...

提交链接 题解 分为      n     \sqrt{n}   n ​ 个块，每个块预处理出起点到 n 的回文树，需要保存的信息有区间的回文串种类个数、区间的某种结点出现的最早位置以及区间的最长回文前缀对应的结点 后两个都是为了向前插入准备的 这是因为，如果向前插入的过程中，产生的一个新的结点，我们需要看这个结点在区间内是否出现过， 此外，向前插入，需要从最长回文前缀开始 这道题需要对回文树有深入的理解，并且要用到翁文涛在论文里讲的另一种快速插入的方式      q   u   i   c   k    quick   quick,所以最好对论文有深入理解才能解决本题 代码 #include...

题意 给出两个串， s 和 t ，可以翻转 s 中的任意个不相交的区间，求变为 t 的最少操作次数 题解 变成       s   1     t   1     s   2     t   2    .   .   .    s   n     t   n     s_1t_1s_2t_2...s_nt_n   s1​t1​s2​t2​...sn​tn​ 的形式 转变为求最小的划分，使得每个部分都是回文串 Codeforces 932G 是求划分方案数的，这里把求和变为求最小值即可 注意 输出答案要把方案输出 所以，用      f   [   i   ]    f[i]   f[i] 不是...

题意 给一个串，划分成k个部分，使得这k个部分整体是回文 题解 转化为       s   1     s   n     s   2     s    n   −   1     .   .   .    s    n   /   2      s    n   /   2   +   1      s_1s_ns_2s_{n-1}...s_{n/2}s_{n/2+1}   s1​sn​s2​sn−1​...sn/2​sn/2+1​ 变为划分为k个部分，每个部分内部是回文      d   p    dp   dp 方程很好想，      d   p   [   i   ]   =   ∑ ...

题意 有AGTC四种字符，一开始有一个空串，每次操作，可以在首或尾加任意个字符，或者将已有字符镜面复制（左右两种复制方法），要求最少的操作步数使得得到给出的字符串 题解 首先，最后的串一定是从他的回文子串向两侧添加得到的 所以，只需要考虑构成回文串的最小操作数 设回文树中一节点      u    u   u, 其答案为      d   p   [   u   ]    dp[u]   dp[u],长度为      l   e   n   [   u   ]    len[u]   len[u],其父亲为      v    v   v 那么，什么样的串才能得到回文串呢？  从它的回文子串得...

题意 一开始一个空串，4中操作 1.首部添加一个字符 2.尾部添加一个字符 3.询问当前串的回文串种类数 4.询问当前串的回文串个数 题解 对回文树进行改造 对于指向串尾的指针，这时需要两个变量维护      L   ,   R    L,R   L,R ，从中间位置开始先两侧扩展 同理，指向上一个回文串结点的      l   a   s   t    last   last 也需要变为两个      l   a   s   t   [   0   ]   ,   l   a   s   t   [   1   ]    last[0],last[1]   last[0],last[1] 还...

题意 给出一个递推式：      g   (   i   )   =   0  <mtext>                                                 </mtext>  (   0   ≤   i   ≤   m   )   g   (   i   )   =   i   −   1   +    2   i   <munderover>  ∑    j   =   0     i   −   1   </munderover>  g   (   j   )  <mtext>         ...

题意 给出一个 串      S    S   S,求一个串      T    T   T, 要求，等长，所有区间的      L   I   S    LIS   LIS 相等，0 的个数尽可能多 题解 从后向前，保证后面的解都是合法的情况下 如果当前位置的数字是 0 那么，他一定是后面以他为起点的区间的      L   I   S    LIS   LIS 的一部分，这就要求      T    T   T 的对应位置必须为 0, 否则      L   I   S    LIS   LIS 长度必然减少 如果当前位置的数字为 1 考虑，以他为起点的所有区间 对于那些      L  ...

题意 给出n个数，取任意个数加一起，将和的十进制表达中 4 的个数加到答案，问这       2   n     2^n   2n个和的4的个数的和 题解 分别计算      4   ×   1    0   i     4\times10^i   4×10i 的答案 将一半的数放在A 中，另一半放在 B 中，分别暴力出所有组合 当      (    A   i    +    B   j    )  <mtext>   </mtext>  m   o   d  <mtext>   </mtext>  1    0    i   +   1  ...