题意

给定一棵树，A 在 $x$ 点，B 在 $y$ 点，B 追 A，两人每次可以往相邻点移动，A 先跑，问 A 最晚什么时候被追上。

Solution

结论：找到一个点，满足 $dis_B > dis_A$ 且 $dis_B$ 最大，即为最终落脚点。

题目

有 $n$ 个敌人，你现在的武器的耐久度为 $m$,杀每个敌人要消耗 $a_i$ 点耐久度，同时得到可以再杀死 $b_i$ 个人的权利。问最多可以杀死多少人，在杀人最多的情况下最少要消耗多少耐久度？

Solution

首先会想到对人进行分类，一类是 $b_i$ 为 $0$ 的，一类是 $b_i$ 不为 $0$ 的。

题目

一个 $A$ 每天可以生产 $x1$ 个 $B$，$y1$ 个 $C$，一个 $B$ 每天可以生产 $x2$ 个 $A$，$y2$ 个 $C$，一个 $C$ 每天可以生产 $x3$ 个 $A$，$y3$ 个 $B$，最开始各有 $x,y,z$ 个，问 $n$ 天后各有多少个？ $n = 1e9$

Solution

$B$ 和 $C$ 每天可以生产 $x2 + x3$ 个 $A$，那么第一天：$x$，第二天：$x(x2+x3)$，第三天：$(x(x2+x3))*(x2+x3)$ … 显然是等比数列求和。

题目

给定一个 $n$ 元有向完全图，每次操作可以翻转一条边。求最少的操作次数，使得图中不存在三元环。$(n <= 10)$

Solution

题目

问二维矩阵中是否存在相同字母构成的环。

Solution

判环问题，显然可以想到并查集。遍历矩阵，若该点与之前遍历过的相邻点字符相同且是同一个根的话，说明存在环，否则合并这两个点。

题目

构造一个长度为 $n$ 的序列，每个数字大小必须满足 $l <= a[i] <= r$，且和被 3 整除，问有多少种方法？

Solution

题目

给你两个队列$a$和$b$，问你能否构造出给定的队列$c$。

Solutuon

很经典的动态规划，$dp[i][j]$ 表示第一个队列的前 $i$ 个数和第二个队列的第 $j$ 个数能否组成第三个队列的前 $i+j$ 个数。状态转移方程：$dp[i][j] = (dp[i - 1][j]$ $and$ $a[i] == c[i + j]$ $or$ $dp[i][j - 1]$ $and$ $b[j] == c[i + j])$。

题目

求 $n$ 个节点，高度不超过 $h$ 的二叉树的个数，结果模 $1e9 + 7$。

Solution

题目

$n$ 个物体，每个物品都有 $k$ 个属性，实际上就是 $a[n][k]$ 的数组，满足 $a[i][0]+a[j][0]=a[i][1]+a[j][1]=…=a[i][k−1]+a[j][k−1]$ 的物体 $i$ 和物体 $j$ 称为一对完美对，求完美对对数。

Solution

题目

给你长度为 $n$ 的序列，你有一种能力可以将序列中的任意一个数变为相反数，在你不超过 $k$ 次使用能力的情况下，长度为 $len$ 的子区间的和的绝对值的最大值是多少？

Solution

用两个multiset维护区间前k大的负数，扫一遍就好了，细节略多。