CF1407D「Discrete Centrifugal Jumps」 1. 题目 题目链接：CF1407D「Discrete Centrifugal Jumps」 。 Description There are nnn beautiful skyscrapers in New York, the height of the iii-th one is hih_ihi. Today some villains have set on fire first n−1n- 2020-09-10 Technique ACM 题解 Technique ACM 题解
CF991F「Tree Destruction」 1. 题目 题目链接：CF991F「Tree Destruction」 。 Description You are given an unweighted tree with nnn vertices. Then n−1n - 1n−1 following operations are applied to the tree. A single operation consists of the 2020-09-09 Technique ACM 题解 Technique ACM 题解
CF1405D「Tree Tag」 1. 题目 题目链接：CF1405D「Tree Tag」 。 DESCRIPTION Alice and Bob are playing a fun game of tree tag. The game is played on a tree of nnn vertices numbered from 111 to nnn. Recall that a tree on nnn vertices i 2020-09-08 Technique ACM 题解 Technique ACM 题解
LCM与GCD算法 LCM（最小公倍数）和 GCD（最大公因数）在做 ACM 题时经常会用到，求两个整数的 LCM 和 GCD 有两种方法。 1. 辗转相除法（欧几里得算法） 定理：对于任意的两个整数 a,b(a≥b)a,b (a \geq b)a,b(a≥b)， 有 (a,b)=(b,a%b)(a,b) = (b, a\%b)(a,b)=(b,a%b) 。（(a,b)(a, b)(a,b) 表示 aaa 和 b 2020-09-08 Technique ACM 算法 数学 Technique ACM 算法 数学
LCM与GCD算法 LCM（最小公倍数）和 GCD（最大公因数）在做 ACM 题时经常会用到，求两个整数的 LCM 和 GCD 有两种方法。 1. 辗转相除法（欧几里得算法） 定理：对于任意的两个整数 a,b(a≥b)a,b (a \geq b)a,b(a≥b)， 有 (a,b)=(b,a%b)(a,b) = (b, a\%b)(a,b)=(b,a%b) 。（(a,b)(a, b)(a,b) 表示 aaa 和 b 2020-09-08 Technique ACM 算法 数学 Technique ACM 算法 数学
树的直径 1. 简介 树中所有简单路径的最大值即为树的直径，可以通过两次 DFS 或者树形 DP 在 O(n)O(n)O(n) 时间内求解。 2. 思路 2.1 两次 DFS 首先将任意一个结点 uuu 看作是树根，然后进行 DFS 求出最远的结点 sss；则 sss 一定是树的直径的其中一个端点。 证明 假设结点 s′s's′ 和 t′t't′ 之间唯一的简单路径为树的直 2020-09-08 Technique ACM 算法 图论 树 Technique ACM 算法 图论 树
树的直径 1. 简介 树中所有简单路径的最大值即为树的直径，可以通过两次 DFS 或者树形 DP 在 O(n)O(n)O(n) 时间内求解。 2. 思路 2.1 两次 DFS 首先将任意一个结点 uuu 看作是树根，然后进行 DFS 求出最远的结点 sss；则 sss 一定是树的直径的其中一个端点。 证明 假设结点 s′s's′ 和 t′t't′ 之间唯一的简单路径为树的直 2020-09-08 Technique ACM 算法 图论 树 Technique ACM 算法 图论 树
P2014「[CTSC1997]选课」 1. 题目 题目链接：P2014「[CTSC1997]选课」 。 题目描述 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 NNN 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 aaa 是课程 bbb 的先修课即只有学完了课程 aaa，才能学习课程 bbb）。一个学生要从这些 2020-09-07 Technique ACM 题解 Technique ACM 题解
P1352「没有上司的舞会」 1. 题目 题目链接：P1352「没有上司的舞会」 。 题目描述 某大学有 nnn 个职员，编号为 1…n1 \ldots n1…n 。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 rir_iri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 2020-09-07 Technique ACM 题解 Technique ACM 题解
P5357「【模板】AC自动机（二次加强版）」 1. 题目 题目链接：P5357「【模板】AC自动机（二次加强版）」 。 题目描述 给你一个文本串 SSS 和 nnn 个模式串 T1..nT_{1..n}T1..n，请你分别求出每个模式串 TiT_iTi 在 SS 中出现的次数。 输入格式 第一行包含一个正整数 nnn 表示模式串的个数。 接下来 nnn 行，第 iii 行包含一个由小写英文字母构成的字符串 TiT_iTi 。 最后一行包 2020-09-06 Technique ACM 题解 Technique ACM 题解