CF521E Cycling City 题解
Description 给定一张 nnn 个点 mmm 条边的无向简单图。 问图中能否找到两个点，满足这两个点之间有至少三条完全不相交的简单路径。 n,m≤2×105n,m \le 2 \times 10^5n,m≤2×105，图不保证连通。 Solution 容易发现有解地充要条件是存在两个环有边交，考虑在 dfs 树上做这件事。 注意到非树边一定不会成为边交，所以边交一定为树边。 那么
CF521D Shop 题解
Description 有 kkk 个正整数 a1…ka_{1\dots k}a1…k。 有 nnn 个操作，每个操作给定正整数 t,i,bt, i, bt,i,b，有三种可能： 如果 t=1t = 1t=1，这个操作是将 aia_iai 赋值为 bbb； 如果 t=2t = 2t=2，这个操作是将 aia_iai 加上 bbb； 如果 t=3t = 3t=3，这个操作是将 aia_i
CF516E Drazil and His Happy Friends 题解
Description 有 nnn 个男生 mmm 个女生，编号分别为 0∼n−10 \sim n - 10∼n−1 和 0∼m−10 \sim m - 10∼m−1。 有 bbb 个男生和 ggg 个女生是快乐的，其他人是不快乐的。 在第 iii 天，编号为 i mod ni \bmod nimodn 的男生和编号为 i mod mi \bmod mimodm 的女生会一起玩。 如果他们俩中有
CF512D Fox And Travelling 题解
Description 给定一张 nnn 个点 mmm 条边的无向图。 一个点只有当与它直接相连的点中最多只有一个点未被选择过时才可被选择。 询问对于每个 k∈[0,n]k \in [0,n]k∈[0,n]，有序选择 kkk 个点的方案数。 n≤100n \le 100n≤100，m≤n(n−1)2m \le \frac{n(n-1)}2m≤2n(n−1)，答案对 109+910^9+910
CF506E Mr. Kitayuta's Gift 题解
Description 给定一个长度为 nnn 的小写字符串 sss 和一个正整数 mmm。 要求在 sss 中插入恰好 mmm 个小写字符使其回文的方案数，两个方案不同当且仅当它们得到的串不同，与插入顺序和位置无关。 n≤200,m≤109n \le 200,m \le 10^9n≤200,m≤109，答案对 104+710^4 + 7104+7 取模。 Solution 先考虑 n+mn+
CF1519F Chests and Keys 题解
Description 给定 n,mn,mn,m 表示存在 nnn 个宝箱和 mmm 把钥匙，第 iii 把钥匙需要 bib_ibi 元，第 iii 个宝箱内部有 aia_iai 元。 现在进行一场游戏，Bob 是本场游戏的玩家，而 Alice 则是场景布置者，Alice 可以给每个宝箱上一些锁（第 jjj 种锁需要第 jjj 种钥匙打开） 如果 Bob 可以购买一些钥匙，然后打开一些宝箱，
[ARC080F] Prime Flip 题解
Description 有无限枚硬币，其中有 nnn 枚硬币 x1…nx_{1\ldots n}x1…n。初始时正面朝上，其余均为背面朝上，每次可以选择一段区间 [l,r][l,r][l,r]，将区间内所有硬币翻转，其中 r−l+1r-l+1r−l+1 为一个奇质数。 问最少多少次能将所有硬币全部翻为背面朝上。 1≤n≤100,1≤x1≤x2≤…≤xn≤1071\leq n\leq 100,
P3993 [BJOI2017] 同构 题解
Description 你有 nnn 个点，你可以在这 nnn 个点之间连无向边，两个点之间至多只能连一条边，也不允许连自环，问至多能连多少条边。 但这个问题的答案显然是 n(n−1)2\frac{n(n-1)}{2}2n(n−1) 条。所以有一个额外的限制，要求这个图不存在非平凡的自同构。 一个图 GGG 有非平凡的自同构定义为存在一个 111 到 nnn 的置换 p(1)p(1)p(1)