绝世好题系列

· · 个人记录

带标号标号计数

给定 n，请求出有 n 个点的有标号无向简单图有多少种不同的标号。

带度数限制荒漠计数

给定 n，请求出有 n 个点的，每个点的度数小于 1 的有标号无向荒漠有多少种。

crn 的构造题

给定 n，构造一个数列，满足以下条件：

  1. 每个数都是数。
  2. 其长度为 n。
  3. 其恰好有 n 个数。

输出一种方案。

恐怖蜜蜂问题

此题无人通过。

挑战 NPC

众所周知，最大团是一个 NP-hard 的问题，但在一些图上，其具有很好的性质。

现在，给你一个二分图，请求出它的最大团大小。

挑战图同构

给定你两个无向连通圈，请判断这个两张图是否同构。

七元环计数问题

众所周知，图的三元环计数可以做到 O(m\sqrt m) 复杂度。

现在，给你一个二分图，请求出它的七元环数量。

可持久化可并堆

你需要维护若干个集合，支持：

  1. 新建一个集合，仅包含一个数 x。
  2. 合并两个集合。
  3. 查询一个集合的最大值。

刻意构造的 DAG 问题

给定一个 DAG，保证：

  1. 其不存在自环。
  2. 不存在一个点 x，满足 x 向 x 有连边。
  3. 不存在一个长为 n 的数列 a_{1,...,n} 使得 a_i 向 a_{i+1} 有连边（1\le i<n），a_n 向 a_1 有连边。
  4. 从一个点出发沿边移动任意步无法回到其自身。

你需要求有多少个点对 (x,y) 使得 x 可以到达 y，且 y 可以到达 x。

高精度乘法

给定十进制长度为 100000000 的大整数 A,B（不含前导零）。判断 A\times B 是否是质数。

LIS Ultimacy（区间动态 LIS）

给定一个序列，你需要支持：

  1. 单点修改。
  2. 求区间的 LIS 的 LDS 的长度，若有多个 LIS，它们 LDS 长度最大值。

最大团问题 II

有些复杂的图上的问题很难。

给定一个仙人掌或竞赛图，请求出其最大团大小。

无向图定向问题

给你一张无向图，你需要为其定向使得其成为一张有向图。

如果有多种方案，你要输出最有向的那一种。