题目链接 题意 给出一个长串，提问n个串，输出在长串中出现的次数 题解 将n个询问的串建立AC自动机，拿长串去匹配 首先不能暴力跳      f   a   i   l    fail   fail 去统计了，因为，答案的总和肯定是       n   2     n^2   n2 级别的，所以肯定不是暴力跳      f   a   i   l    fail   fail 一个一个去累加答案的 根据      f   a   i   l    fail   fail 的含义，如果当前结点匹配成功，那么他的      f   a   i   l    fail   fail 指向的结点一定也...

题意 给出一个长串      t    t   t ,n个短串       s   i     s_i   si​ ，问两两连接成的       s   i    +    s   j     s_i+s_j   si​+sj​ 在      t    t   t 的出现次数的和为多少 题解 从另一个角度分析，每次的匹配，在      t    t   t 中的      s   i     s_i   si​和      s   j     s_j   sj​ 的连接位置 +1， 我们枚举      t    t   t 的每一个对应连接的位置，看有多少对能匹配上 若在位置      k  ...

题意 给一些点，找4个点，要求1个点在剩余三个点围成的三角形的内部，问方案数 题解 写得我有种不想碰几何的冲动。。。。 太迷了，精度迷，同一种意思的不同表达迷，明明那么简洁的思路，为什么写出来这么多特殊情况 😐 哭了 枚举每一个点当做三角形内部的点，看有多少个三角形能包住他  1号能和（4,5）（3,5）（2,5）组成 明显，1号之外的2个点的夹角不能大于180（逆时针转过去） 所以，我们要求出来每个点逆时针转180度以内有多少个点 另      f   [   i   ]    f[i]   f[i] 表示上述函数 1的180度内的点有2、3、4 答案就是      f   [   2  ...

题意 一开始n棵树，每棵树只有一个根节点，标号为1。多次操作，每次在区间      [   l   ,   r   ]    [l,r]   [l,r] 的树中的结点      u    u   u 下增加一个结点      v    v   v ,多次询问，问区间      [   l   ,   r   ]    [l,r]   [l,r] 的树的结点      u    u   u 的子树的大小求和 题解 肯定不能模拟建树了 题目说增加的结点      v    v   v 是互不相同的，所以可以建成一棵树，在结点加一个区间，表示在      [   l   ,   r   ]    [...

题意 数轴上，从0跳到n，其中有n-1个石头，每次至少跳d米，还有m个限制，     (    t   i    ,    p   i    )    (t_i,p_i)   (ti​,pi​) 表示不能第       t   i     t_i   ti​ 次跳到       p   i     p_i   pi​ 的位置，求方案数 题解 先不考虑限制，转移方程为     f   [   i   ]   =   f   [   0   ]   +   f   [   1   ]   +   …   +   f   [   i   −   d   ]    f[i]=f[0]+f[1]+\ld...

题意 一个无向图，每条边有一个区间，数值在此区间内才能通过，为从1到n可行的数值有多少个 题解 离散化线段树+并查集优化 思路清奇 每条路有个区间，我们将这个区间插入到线段树中，实际插入的是路径 怎么理解呢 对于线段树中的某个结点，它所包含的路径都在它表示的区间的范围内 进一步说，这么多的路径连成的网络是可以互通的 线段树在向下走的过程中，我们便将包含的路径合并 当到达叶子结点时，如果1和n还是互通的，表明这个结点表示的区间是合法的 由于数值范围较大，所以要先进行离散化 由于线段树向上时，要把合并的操作恢复，所以不能进行路径压缩，需要另一个优化，按秩合并 代码 #include<bits...

题意 三维空间中，两种操作，意思标记一个点，二是询问一个点，要求输出询问点与标记点的最小曼哈顿距离 题解1 分块Orz 先假设所有询问都在标记之后，那么我们一边 bfs 就可以求出答案 我们将操作每       q     \sqrt{q}   q ​ 分成一块来处理 分为两类，标记和询问 当前块的标记操作先不标记，等整块的询问结束后再统一标记 每块，先 bfs 求出一个答案，复杂度      n   m   h    nmh   nmh， 但这个并不是正确的答案，因为在这一块内有一些的询问之前要标记的点没有算，于是块内两两暴力就行了，复杂度      q    q   q 总复杂度     ...

题目链接 题意 给出一个有向图，每次询问一些点，问哪些点无法直接到达该次询问的所有点 题解 思路清奇，还是太菜了Orz，看别人代码懂了 每次的询问是一段标号连续的点，即一个区间      [   l   ,   r   ]    [l,r]   [l,r] 中的点 这是一个关键的信息，必须要用上 考虑一个点能和周围的点共存的范围，首先，肯定不是无限大的，因为它一旦跟自己能到达的点在一起，自己肯定就是非法的了，所以应该用一个区间表示 形象地说，这是一个安全的范围，不能容纳再扩充的点了 考虑点      x    x   x 的安全区间      [    l   x    ,    r   x ...

题意 给一个长度为n的字符串，m次询问(l,r)求l到r内本质不同的回文子串数量 题解 看各路题解，一脸懵逼 终于在《金策 字符串算法选讲》中找到了关键疑惑答案 先说暴力 离线询问对r排序，考虑增加一个字符，右边界到了r，每次在回文树上暴力跳fail统计以r为结尾的新增回文串。注意到每一个回文串影响的左端点是一个区间 比如说当前枚举到的回文串为b，那么左区间落在     [   上   次   b   出   现   的   位   置   的   起   点   +   1   ,   本   次   b   的   起   点   ]    [上次b出现的位置的起点+1,本次b的起点]  ...

题意       X   i    =   a   ⋅    X    i   −   1     +   b  <mtext>    </mtext>  (   m   o   d  <mtext>    </mtext>  p   )    X_i=a \cdot X_{i-1} + b \ \ (mod \ \ p)   Xi​=a⋅Xi−1​+b  (mod  p) 给出       X   0     X_0   X0​，序列长度      n   ,   a   ,   b   ,   p    n,a,b,p   n,a,b,p 的...

题意 给出     n    n   n个数，询问一个区间      [   L   ,   R   ]    [L,R]   [L,R]，在这个区间内找     [   l   ,   r   ]    [l,r]   [l,r] 做     N   I   M    NIM   NIM游戏，问先手必胜的      [   l   ,   r   ]    [l,r]   [l,r] 种类数 首先，     N   I   M    NIM   NIM游戏的判断条件为 ，所有数字的     x   o   r    xor   xor和大于零就是先手必胜，否则先手必败 根据     x   ...

题意 一个n个数字的序列，要分给k个人，使每个人和的最大值最小，注意可以舍弃最后的任意多个数字 题解 二分答案 考虑二分最小值为      K    K   K      d   p   [   i   ]    dp[i]   dp[i] 表示前      i    i   i 个数最多能分成几段，则      d   p  <mtext>   </mtext>  [   i   ]   =   m   a   x   {  <mtext>   </mtext>  d   p   [   j   ]   +   1  <mtext>...

题意 给出一个DAG，入度为0的点为控制点，现在有两个点要沿边走向控制点，问破坏哪些点可以使其中一个无法到达，求点的个数 题解 支配树模板题，可惜之前没听说过 😦 逆向建图，然后让0号点连接所有控制中心，对于     a   、   b    a、b   a、b两点，     a   +   b   −   L   C   A   (   a   ,   b   )    a+b-LCA(a,b)   a+b−LCA(a,b) 就是答案 由于是DAG，建图方式比较简单 代码 #include<bits/stdc++.h> #define N 100010 #define INF ...

题意 定义      r   e   v   (   S   )    rev(S)   rev(S) 为串      S    S   S 的颠倒，如      r   e   v   (   a   b   a   c   )   =   c   a   b   a    rev(abac)=caba   rev(abac)=caba 现给出一个串，在他的所有子串中，任意两个串      a   ,   b    a,b   a,b，不能出现      a   =   b   或   a   =   r   e   v   (   b   )    a=b或 a=rev(b)   a=b或...