好题合集

· · 个人记录

  1. 二分图 p 元环计数，p 是质数。

  2. 求长为 n 的回文合法括号序列个数。

  3. 任意区间修改，区间查询所有子区间的 \text{mex}\times \min 之和。

  4. 区间所有数乘上自己的逆元，任意区间查询。

  5. 给定一张无向图，求这张图的哈密顿回路数量 \pmod 2。

  6. 给定质数 p，求 \sum_{i=1}^{p-1} \dfrac{1}{i} \pmod p。

  7. 任意区间修改，区间查询 \max 是否等于 \text{mex}。

  8. 给定一个数组 a，设 b_i=10^{a_i}-1，q 次询问，每次给出 l,r，求 \sum_{i=l}^r \mu(b_i)。

  9. 定义一个序列 a 的 “波动程度” 为：\dfrac {\sum_{i=1}^n(a_i-\overline a)} {n}，\overline a 表示 a 的平均数，求所有值域为 [1,m] 的长度为 n 的整数序列中，波动程度为奇数的序列的个数。

  10. 证明：若 p_1,p_2 是相邻奇素数，则 \dfrac{p_1+p_2}{2} 是合数。

  11. 给定一张图，流量只能为整数，保证最大流 \ge 1，求它的严格次大流。

  12. 给出一个 1\sim n 的排列 p，支持单点修改，查询 LIS 长度，保证任意时刻是排列。

选取一些个人觉得比较有趣的题加入。

2024.11.17：增加笑点解析。

笑点解析：

  1. 二分图没有奇环，记得特判 p=2。
  2. 合法括号序列都不回文。
  4. 等价区间推平成 1。
  5. 每条哈密顿回路反过来还是哈密顿回路。
  9. 不知道大家有没有想过方差为什么要平方一下（
  11. 最大流 -1。
  12. 需要保证是排列，所以单点修改相当于没修改。