【力扣】中国银联专场周赛
中国银联专场
银联-03. 理财产品
某公司计划推出一批投资项目。 product[i] = price 表示第 i 个理财项目的投资金额 price 。客户在按需投资时，需要遵循以下规则：
- 客户在首次对项目
product[i]投资时，需要投入金额price - 对已完成首次投资的项目
product[i]可继续追加投入，但追加投入的金额需小于上一次对该项目的投入(追加投入为大于0的整数) - 为控制市场稳定，每人交易次数不得大于
limit。(首次投资和追加投入均记作1次交易)
若对所有理财项目中最多进行 limit 次交易，使得投入金额总和最大，请返回这个最大值的总和。
注意：
- 答案需要以
1e9 + 7 (1000000007)为底取模，如：计算初始结果为：1000000008，请返回1
示例 1：
输入：
product = [4,5,3], limit = 8输出：
26解释：满足条件的一种情况为：
第一个理财项目进行金额为 4，3，2 的交易；
第二个理财项目进行金额为 5，4，3 的交易；
第三个理财项目进行金额为 3，2 的交易；
得到最大投入金额总和为 5 + 4 * 2 + 3 * 3 + 2 * 2 = 26。
示例 2：
输入：
product = [2,1,3], limit = 20输出：
10解释：可交易总次数小于
limit，因此进行所有交易
第一个理财项目可交易 2 次，交易的金额分别为 2，1；
第二个理财项目可交易 1 次，交易的金额分别为 1；
第三个理财项目可交易 3 次，交易的金额分别为 3，2，1；
因此所得最大投入金额总和为 3 + 2 * 2 + 1 * 3 = 10。
提示：
1 <= product.length <= 10^51 <= product[i] <= 10^71 <= limit <= 10^9
二分
我们把 p 看作不同高度的柱子，我们需要确定某个高度划一刀，高的全选，少的从这个高度补。如果比这个高度低，那么就会超过 limit 个。
class Solution:
def maxInvestment(self, p: List[int], limit: int) -> int:
# 二分上界和下界
a, b = 0, max(p)
while a < b:
mid = (a + b) // 2
# 高的高度
count = 0
for tmp in p:
if tmp > mid:
count += tmp - mid
# 多了，不行
if count > limit:
a = mid + 1
# 少了，行
else:
b = mid
print(b)
ans, count = 0, 0
for tmp in p:
if tmp > b:
# 记录个数
count += tmp - b
# 高的全选，等差数列求和
ans += (tmp - b) * (b + 1 + tmp) // 2
# 不足的从这一层选
ans += b * (limit - count)
return ans % 1000000007
银联-04. 合作开发
为了不断提高用户使用的体验，开发团队正在对产品进行全方位的开发和优化。
已知开发团队共有若干名成员，skills[i] 表示第 i 名开发人员掌握技能列表。如果两名成员各自拥有至少一门对方未拥有的技能，则这两名成员可以「合作开发」。
请返回当前有多少对开发成员满足「合作开发」的条件。由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。
注意：
- 对于任意
skills[i]均升序排列。
示例 1：
输入：
skills = [[1,2,3],[3],[2,4]]输出:
2解释：
开发成员[1,2,3]和成员[2,4]满足「合作开发」的条件，技能1和4分别是对方未拥有的技术
开发成员[3]和成员[2,4]满足「合作开发」的条件，技能3和4分别是对方未拥有的技术
开发成员[1,2,3]和成员[3]不满足「合作开发」的条件，由于开发成员[3]没有对方未拥有的技术
因此有2对开发成员满足「合作开发」的条件。
示例 2：
输入：
skills = [[3],[6]]输出:
1解释：
开发成员[3]和成员[6]满足「合作开发」的条件
因此有1对开发成员满足「合作开发」的条件。
提示：
2 <= skills.length <= 10^51 <= skills[i].length <= 41 <= skills[i][j] <= 1000skills[i]中不包含重复元素
逆向考虑 + 哈希
假如 a 和 b 不能合作，而且 a 的技能比 b 多（或相等），那么说明什么， b 的技能 a 都有。那么 a 的技能是 1 2 3 ，b 的技能就是 1，2，3 的子集。
class Solution:
def coopDevelop(self, skills: List[List[int]]) -> int:
# 排序后 a 不能合作的都在前面，后面也会有不能和 a 合作的
# 把这个看成有序方便讨论
skills.sort(key=lambda x : len(x))
n = len(skills)
hash = defaultdict(int)
# 所有组合个数
ans = n * (n - 1) // 2
# print(skills)
# list is unhashable，tuple is hashable
hash[tuple(skills[0])] += 1
# 遍历每个员工
for i in range(1, n):
# 得到所有子集
for j in range(len(skills[i])):
# combinations(skills[i], j + 1) skills[i] 中 j + 1 个元素的所有组合
for c in combinations(skills[i], j + 1):
ans -= hash[tuple(c)]
# 进入哈希表
hash[tuple(skills[i])] += 1
return ans % 1_000_000_007
如果是 cpp 呢？怎么搞？好在最多只有 4 个 skill ，数值在 1 到 1000 ，也就是说一个 skill 可以用 10 bit 表示，最多需要 40 bit 。
class Solution {
unordered_map hash;
public:
int coopDevelop(vector>& skills) {
sort(skills.begin(), skills.end(), [&](vector &a, vector &b){return a.size() < b.size();});
int n = skills.size();
long long ans = n;
ans = ans * (n - 1) / 2;
long long s = 0;
for (int i = 0; i < n; i++) {
// 二进制枚举，确定每个数选或者
for (int j = 1; j < 1 << skills[i].size(); j++) {
s = 0;
for (int k = 0; k < skills[i].size(); k++) {
if (((j >> k) & 1) == 1) {
s = (s << 10) + skills[i][k];
}
}
ans -= hash[s];
}
hash[s] += 1;
}
return ans % 1000000007;
}
};