postive-deviation

摘要： 看到题目条件找一下性质然后将其转化掉。 任何东西都只是方向，不一定是正解。 如果感觉他答案不大并要求输出类似最小步数的时候可以猜一下答案上界。 可以从最特殊的东西入手。 可以适当找一下必要条件或充分条件。 可以考虑一下补集（类似容斥）。 当方向较多的时候可以想象哪些最有可能是对的。 可以先做一下简化 阅读全文

摘要： 题目大意： 有一个长度为 \(2n\) 的 \(01\) 序列 \(a\)，你可以对他进行一下操作（不超过10步）。 输出一个长度为 \(2n\) 的括号匹配字符串 \(s\)，假设每个左括号 \(i\) 与右括号 \(p_{i}\) 匹配，那么将 \(a\) 中 \(i \sim p_{i}\) 阅读全文

摘要： 题目大意： 你现在有一棵树，每次你可以选择一个点，将这个点变成根，然后递归处理他的大小不为 1 的儿子们。 请问度数为 1 的点的数量最多有多少。 \(n \le 2 \times 10^5\)。 解题思路： 考虑简化他的题意，考虑什么时候停止，就是当他任意一条边上的两个点至少有一个被选择当根的时候 阅读全文

摘要： T2 题目大意； 有一棵大小为 \(n\) 的树和 \(m\) 个关键点，你要从这 \(m\) 个关键点中随机选择 \(k\) 个点，问这 \(k\) 个点两两之间最长距离的期望是多少。 \(n \le 2000, m \le 300\) 解题思路： 最暴力的做法肯定是直接 dp，但时间复杂度是 \ 阅读全文

摘要： 题目大意： 给你一个长度为 \(2 \times n\) 的由 \(\text{(}\) 和 \(\text{)}\) 构成的串，再给你 \(n\) 个二元组 \(a < b\)，保证所有的 \(a\) 与 \(b\) 构成了一个长度为 \(2 \times n\) 的排列。 问能否选出一个长度为 阅读全文

摘要： 题目大意： 有一棵 \(n\) 个节点的树，你初始在 \(1\) 节点，每次你可以选择以下某一步。 移到与 \(x\) 相邻的点，花费 \(1\) 的时间。 移到 \(1\)，不花费时间。 第二种操作最多执行 \(k\) 次，求最小遍历完整棵树的时间。 \(n \le 2 \times 10^5, 阅读全文

摘要： 题目大意： 有两个排列，长度分别为 \(n,m\)，每次你可以选择两个整数 \(1 \le i \le n, 1 \le j \le m\)，并交换 \(p_{1} \sim p_{i - 1}\) 和 \(p_{i + 1} \sim p_{n}\) 两个整体，\(q,j\) 同理。 请构造出一种 阅读全文

摘要： 题目大意： 设一个长度为 \(n\) 的数组是 “Fancy” 的，当且仅当它满足下面条件。 \(|a_{i} - a_{i - 1}| \le k\) 存在 \(i\) 满足 \(x \le a_{i} \le x + k - 1\) \(a_{i} \ge 0\) 给定 \(n,k,x\)，求 阅读全文

摘要： 题目大意： 给定一个长为 \(n\) 的字符串 \(S\)，你要找到最大的 \(k\)，使得存在 \(s_{1} \sim s_{k}\) 使得 \(s_{1}\) 是 \(S\) 子串 且 \(s_{i}\) 在 \(s_{i - 1}\) 中作为子串至少出现两次。 \(n \le 2 \time 阅读全文

摘要： 凡是在循环前面加了特判的东西，都要检查一下循环内部要不要判。 可以再读一遍题来调代码。 递归的时候全局变量会改动，如果中途 return 可能会忘记后面的回溯语句。 数据结构要及时 push_down。 合并的时候要仔细考虑是否等价 注意特判的顺序 当写到某个地方有很多变量的定义很类似的时候，一定要 阅读全文