标签：bar 题解 sum trick 括号 集合 Hash

trick 集合

1. 基础

• 判断是否 \(\forall i\) 有 \(x < a_i\)：

  • 转化为是否 \(x < \min (a_i)\)。大于类似。

  • P9868 & 题解，ABC223F & 题解

• 括号序列：

  • 是括号序列的条件：

    • 总共的左括号和右括号数量相等；
    • 任意前缀的左括号数量 \(\ge\) 右括号数量。

  • 若将序列中左括号看作 \(1\)，右括号看作 \(-1\)，则两个条件变成了：

    • 总和为 \(0\)；
    • 任意前缀和 \(\ge 0\)。

  • ABC223F & 题解

• 求有多少区间和为 \(0\)：

  • 令 \(s_i = \sum_{j = 1}^i a_j\)，那么区间 \([l, r]\) 和为 \(0\) 即 \(s_r - s_{l - 1} = 0\)，也即 \(s_r = s_{l - 1}\)。找满足这样的数对即可。

• 有多少区间和是 \(k\) 的倍数：

  • 令 \(s_i = \sum_{j = 1}^i a_j\)，那么区间 \([l, r]\) 为 \(k\) 的倍数即 \((s_r - s_{l - 1}) \bmod k = 0\)，也即 \(s_r \equiv s_{l - 1} \pmod k\)。再令 \(t_i = s_i \bmod k\)，然后找有多少 \(t\) 相同的数对即可。

  • AT_abc105_d

• 给定 \(\{a\}, \{b\}\)，求有多少区间 \([l, r]\) 满足 \(\sum_{i = l}^r a_i = \sum_{i = l}^r b_i\)。

  • 令 \(c_i = a_i - b_i\)，条件变成了 \(\sum_{i = l}^r c_i = 0\)。然后就是上一个的问题。

  • P10033

• 判断一个字符串中是否存在回文子串：

  • 如果存在 \(s_i = s_{i + 1}\) 或 \(s_i = s_{i + 2}\) 即存在回文子串。否则没有。
  • P3413

2. DP

• 转移成环：

  • 尝试将 DP 方程展开解方程。

  • AT_abc333_f & 题解，AT_abc263_e

3. 图论

4. 数据结构

5. 数学

• 杨辉三角：

  • \(\sum_{j = 0}^i (10^{j} \times C_i^j) = 11^i\)。
  • 加法方案题解

• \(\gcd\)，当一个数 \(a_x\) 是所有 \(a_i(a_x \in \{a_i\})\) 的约数时：

  • \(a_x = \min(a_i) = \gcd (a_i)\)。
  • 选拔赛题解

• 方差：

  • \(\dfrac 1n \sum_{i = 1}^n(x_i - \bar x)^2 = \dfrac 1n( \sum_{i = 1}^n x_i^2) - \bar x^2\)。

  • AT_abc332_e & 题解

• 预处理 \(i^k\)：

  • 题解

• \(x_1, x_2, \dots, x_k\) 的平均值为 \(\bar x\)，与 \(k\) 无关的转化：

\[\bar x = \dfrac {\sum_{i = 1}^k x_i}{k}\\ \sum_{i = 1}^k x_k = k\bar x\\ \sum_{i = 1}^k (x_k - \bar x) = 0 \]

6. 其它算法

• 字符串 Hash：

  • \(\text{Hash of S} = \sum_{i = 1}^{n}S_i \times c^{n-i}\)；

  • \(\text{Hash of S}_{l \sim r} = hs_r - hs_{l - 1} \times c^{r - l + 1}\)；

  • 线段树上字符串 Hash：ABC331F & 代码。

• 启发式合并：

  • 将小集合合并到大集合中，如有需要可以直接交换。
  • ABC329F & 题解。

标签：bar,题解,sum,trick,括号,集合,Hash
From： https://www.cnblogs.com/2huk/p/17975718