AI刷题-融合目标计算问题
目录
问题描述
输入格式
输出格式
输入样例
样例 1
样例 2
输出样例
样例 1
样例 2
数据范围
解题思路：
问题理解
数据结构选择
算法步骤
代码实现：
1.单独写一个函数来查找数组中第一个不小于给定值的数：
2.单独写一个函数来生成所有可能的结果：
举个例子：
3.在组合完成之后，就是通过二分进行筛选
最后：
最终代码：
运行结果：
问题描述
在推荐系统中，对于一件物品会使用若干模型预估若干个目标，如点击率，观看时长等，然后将这些目标结合起来形成一套融合公式并以此来给出推荐物品的序。
小茗同学最近对融合公式很感兴趣，为每个预估目标设计了 2 种变换形式，每种形式输出一个变换值。小茗同学需要从 2 种变换形式中选择 1 种合并进融合公式中。出于简化系统的考虑，小茗同学将各种预估目标转换值连续相乘作为融合公式的输出值。
然而，小茗同学只考虑了单个预估目标变换值的值域，导致最后的融合公式可能会输出非常小或非常大的数值。从可维护性和便于统计的角度来说，小茗同学希望融合公式的输出值尽可能“合理”，更具体地，小茗同学需要统计融合公式输出值在[L,R]中的方案数。
小茗同学还有其他的工作，需要你来帮助他完成这项统计。
输入格式
- 第一行为一个整数 N(2≤N≤40)N(2≤N≤40)，表示预估目标的数量。
- 第 2 行至第 N+1 行，每行两个整数 fi,1,fi,2(1≤fi,1,fi,2≤109)fi,1,fi,2(1≤fi,1,fi,2≤109)，表示小茗同学为第 i 个目标设计的两种变换形式输出值。
- 第 N+2 行包含两个整数 L,R(0≤L≤R≤1018)L,R(0≤L≤R≤1018)，表示融合公式值的统计范围。
输出格式
输出一个整数，表示融合公式统计范围内的方案数。
输入样例
样例 1
2
1 2
3 4
1 6
样例 2
2
1 2
3 4
4 6
输出样例
样例 1
3
样例 2
2
数据范围
- 45% 数据：2≤N≤202≤N≤20；
- 100% 数据：2≤N≤402≤N≤40。
解题思路：
问题理解
你有一个推荐系统，其中每个物品有多个预估目标，每个目标有两种变换形式，每种形式输出一个变换值。你需要从每种目标的两种变换形式中选择一种，将所有选择的变换值相乘，得到一个融合公式的输出值。你需要统计这些输出值在给定范围 [L, R] 内的方案数。
数据结构选择
- 输入数据：你需要存储每个目标的两种变换值，可以使用二维数组或向量来存储。
- 输出数据：你需要统计满足条件的方案数，最终输出一个整数。
算法步骤
- 输入处理：读取输入数据，包括目标数量
N、每个目标的两种变换值、以及范围[L, R]。 - 生成所有可能的组合：由于每个目标有两种选择，总共有
2^N种组合。你可以使用递归或迭代的方式生成所有可能的组合。 - 计算每种组合的乘积：对于每种组合，计算所有选择的变换值的乘积。
- 统计满足条件的组合：检查每种组合的乘积是否在
[L, R]范围内，如果是，则计数加一。 - 输出结果：输出满足条件的组合数。
代码实现：
1.单独写一个函数来查找数组中第一个不小于给定值的数：
int bisect_left(const vector<long long>& arr, long long x) {
return lower_bound(arr.begin(), arr.end(), x) - arr.begin();
}2.单独写一个函数来生成所有可能的结果：
vector<long long> gen(const vector<vector<int>>& a) {
int n = a.size();
vector<long long> b;
for (int st = 0; st < (1 << n); ++st) {
long long m = 1;
for (int i = 0; i < n; ++i) {
m *= a[i][(st >> i) & 1];
}
b.push_back(m);
}
sort(b.begin(), b.end());
return b;
}对于整个外循环来说，需要进行2^n次循环，也就是：
st < (1 << n)而内循环则是进行组合，
- 对于每个组合
st，内层循环遍历每个目标指标i。 (st >> i) & 1用于判断当前组合st中第i个目标指标是否被选中（即二进制表示中第i位是否为1）。- 如果选中，则乘以对应的变换值
a[i][1]，否则乘以a[i][0]
举个例子：
假设 n = 2，a = [[1, 2], [3, 4]]，那么 st 的取值范围是 0 到 3（即 00, 01, 10, 11）：
- 当
st = 0（00）：m = 1 * 1 * 3 = 3
- 当
st = 1（01）：m = 1 * 2 * 3 = 6
- 当
st = 2（10）：m = 1 * 1 * 4 = 4
- 当
st = 3（11）：m = 1 * 2 * 4 = 8
因此，向量 b 中会存储 [3, 6, 4, 8]。
3.在组合完成之后，就是通过二分进行筛选
int ans = 0;
++R;
for (long long x : u) {
ans += bisect_left(v, (R + x - 1) / x) - bisect_left(v, (L + x - 1) / x);
}
(R + x - 1) / x和L + x - 1) / x 就是简单的向上取整，用函数反正是一样的
调用函数也就是为了找到大于等于R / x和L / x的值，然后二者相减
最后：
- 通过计算这两个二分查找结果的差值，我们可以得到所有使得
L <= v[i] * x <= R的v[i]的数量。 - 这个差值表示在区间
[L, R]内的有效组合数量，并将其累加到ans中。
至此也就实现了题目要求
最终代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
int bisect_left(const vector<long long>& arr, long long x) {
return lower_bound(arr.begin(), arr.end(), x) - arr.begin();
}
vector<long long> gen(const vector<vector<int>>& a) {
int n = a.size();
vector<long long> b;
for (int st = 0; st < (1 << n); ++st) {
long long m = 1;
for (int i = 0; i < n; ++i) {
m *= a[i][(st >> i) & 1];
}
b.push_back(m);
}
sort(b.begin(), b.end());
return b;
}
int solution(int n, const vector<vector<int>>& f, int L, int R) {
assert(n == f.size() && L <= R && f[0].size() == 2);
vector<vector<int>> l(f.begin(), f.begin() + n / 2);
vector<vector<int>> r(f.begin() + n / 2, f.end());
vector<long long> u = gen(l);
vector<long long> v = gen(r);
int ans = 0;
++R;
for (long long x : u) {
ans += bisect_left(v, (R + x - 1) / x) - bisect_left(v, (L + x - 1) / x);
}
return ans;
}
int main() {
cout << (solution(2, {
{1, 2}, {3, 4}}, 1, 6) == 3) << endl;
cout << (solution(2, {
{1, 2}, {3, 4}}, 4, 6) == 2) << endl;
cout << (solution(3, {
{1, 2}, {3, 5}, {2, 4}}, 10, 50) == 7) << endl;
return 0;
}
运行结果：
