第一题

给定 $n$ 个怪物，每个怪物都有各自的血量上限，一开始所有怪物都是满血。你有两个技能：

1. 消耗法力 $1$ 点，对所有怪物造成 $1$ 点伤害
2. 消耗法力 $2$ 点，秒杀一只不满血的怪物

要把所有怪物杀死，最少消耗多少法力？两个技能随便用，不限次数。$1\le n\le10^5$

思路：一开始肯定要放一次一技能，然后排序。对于所有当前血量小于等于 $2$ 的用一技能，剩下的用二技能这种策略是不对的，比如 $3$ 个血量是 $4$ 的怪物。应该是按照怪物的血量枚举一技能放多少次，后面的用二技能，一个阶梯一个阶梯的枚举。

第二题

定义两个数组互补，当且仅当数组每个位置的数字之和都相同。给定两个长度为 $n$ 的数组，问有多少个子序列（下标）对应的数组是互补的。$1\le n\le10^5$，数组元素范围 $1\sim10^9$，答案需要对 $10^9+7$ 取模。

思路：分组，a[i]+b[i]相同的是一组，哈希表记录组内下标个数。必须在一个组内选才是互补的，所以对于每一组，假设有 $m$ 个下标，那么就是求 $C_m^1+C_m^2+\cdots+C_m^m=2^m-1$，快速幂。每一组的结果加起来即可。
这里要计算 $(2^m-1)\mod10^9+7$，实际算的是 $(2^m\mod10^9+7)-1$，由于最小是 $2^1$，减一之后不会出现负数，所以直接算就行了。

第三题

定义一个数字的权值为该数字的因子的个数。给定正整数 $x$，希望将 $x$ 分解为若干个不是 $1$ 的正整数，使得这些正整数的乘积等于 $x$，且所有数字的权值之和尽可能大，问最大是多少。输入包含 $T$ 组测试数据，每组数据是一个 $x$，$1\le T\le10^4$，$2\le x\le2\times10^5$

思路：把分解出来的正整数看成是物品，正整数的权值是价值。预处理每个正整数的权值。用记忆化搜索实现这个背包问题可能就行了。