企业官网建设流程全解析

一维前缀和

问题描述：

本题为一维前缀和模板。

给定一个长度为 n 的序列 a。

再给定 q 组查询，对于每次查询：

给定一对 l,r，你需要输出​ 的结果

解题思路：

这个题目就是标准的前缀和模板题，详细解释可以看代码注释。

#include <iostream> #include <vector> using namespace std; int main(){ int n, q; cin >> n >> q; //定义一个长度为n的数组用来存储数字 vector<int> nums(n); //定义一个新数组ans用来存储前缀和的值 vector<long long> ans(n + 1); //输入数字 for(int i = 0; i < n; i++){ cin >> nums[i]; } //长度为n+1原因就是第0个位置用0来占位置 //这样后边l所对应的就是前l-1个数字的和 ans[0] = 0; //前缀和公式 后一项 = 前一项 + 该项 for(int i = 0; i < n; i++){ ans[i + 1] = ans[i] + nums[i]; } //开始输入l r while(q != 0){ int l, r; cin >> l >> r; long long sum = 0; //用最右边的前去前l-1个值就是l到r的值之和 sum = ans[r] - ans[l - 1]; cout << sum << endl; q--; } return 0; }

丽丽的询问

问题描述：

丽丽有一个长度为 N 的序列 A1,A2,…,AN。今天，她想用根据这个序列，对你进行 Q 次询问。每次查询丽丽会给你三个整数 L、R 和 X。请你对于每个询问，回答在序列的 L 到 R 之间值为 XX 的元素有多少个。

解题思路：

这个主要是二维数组的应用，将每个位置每个值出现的次数记录下来，然后对应查询即可。有几个关键步骤我已经标注在代码注释中

#include <iostream> #include <vector> using namespace std; int main(){ int n; cin >> n; //定义一个二维vector数组用来记录第几个位置和每个元素出现的次数 //全零初始化 定义n+1大小是因为不用再取默认sum[0]了 vector<vector<int>> sum(n+1, vector<int>(n+1,0)); //输入的同时进行前缀和计算 for(int i = 1; i <= n; i++){ int val = 0; cin >> val; //这一步是利用了cpp中的深拷贝 //直接读取了第[i - 1]个vector的地址并直接完全赋值给[i] sum[i] = sum[i - 1]; //出现的值的次数加一 sum[i][val]++; } int q; cin >> q; while(q--){ int l = 0, r = 0, x = 0; cin >> l >> r >> x; //前缀和公式 相减即可得到所求区间的元素出现的次数 cout << sum[r][x] - sum[l - 1][x] << endl; } return 0; }

其他元素的乘积

题目描述：

给定一个数组，对于数组的每个位置，实现一个算法求数组中除当前元素的所有元素的乘积。介绍如下：

• 例如数组为 [0, 1, 2]，除当前元素的所有元素乘积为 [1*2, 0*2, 0*1]，结果为 [2, 0, 0]。

解题思路：

这个题目我自己第一遍写没用到前缀和的相关知识，完全是按照自己的思路来的。我是先遍历整个数组，然后分类讨论：如果0出现了两次，那么整个数组每个元素的位置的乘积都为0；如果只有一个0，那么只有0的位置有值，其他位置都为0；如果没有0，那就用所有元素的乘积除以当前位置元素的值就可以得到。

#include <iostream> #include <vector> using namespace std; int main() { //1 2 3 4 int n; cin >> n; vector<int> nums(n); for(int i = 0; i < n; i++){ cin >> nums[i]; } int allprod = 1; //记录0出现的个数和位置 int cnt0 = 0; vector<int> pos0; //遍历整个数组 求出除了0之外其余所有元素的乘积 for(int i = 0; i < n; i++){ if(nums[i] == 0){ cnt0++; pos0.push_back(i); continue; } allprod *= nums[i]; } vector<int> ans(n); //超过两个数字为0 则全部结果为零 if(cnt0 > 1){ ans = {0}; for(int i = 0; i < n; i++){ cout << ans[i] << " "; } cout << endl; } //只有一个数字为0 则除了该数字的位置 其余位置全为0 //该位置的值等于allprod else if(cnt0 == 1){ ans = {0}; ans[pos0[0]] = allprod; for(int i = 0; i < n; i++){ cout << ans[i] << " "; } cout << endl; } //没有0出现的情况 就用allprod除以每个位置对应的数值即可 else{ for(int i = 0; i < n; i++){ ans[i] = allprod / nums[i]; cout << ans[i] << " "; } cout << endl; } return 0; }

显然我这个办法有很大的局限性，于是我询问了一下ai有没有结合前缀和思路写的方法；ai用的前缀积和后缀积，就是找到一个中间值mid然后将它左边的全部相乘，将他右边的全部相乘，然后两者相乘，我一开始也这么想过但因为觉得有0存在就会导致全部的乘积为0，但其实事实就是这样的，0的存在以及0的个数都会导致整个结果的走向，因此可以采用前缀积和后缀积，于是我自己又尝试了一下，代码如下。

#include <iostream> #include <vector> using namespace std; int main(){ int n; cin >> n; vector<int> nums(n); for(int i = 0; i < n; i++){ cin >> nums[i]; } //计算mid左边所有值相乘的结果 vector<int> ans(n, 1); int leftprod = 1; for (int i = 0; i < n; ++i) { ans[i] *= leftprod; leftprod *= nums[i]; } // 计算后缀积并更新结果 int rightprod = 1; for (int i = n - 1; i >= 0; --i) { ans[i] *= rightprod; rightprod *= nums[i]; } for(int i : ans){ cout << i << " "; } return 0; }

A · B Problem

题目描述：

设有两个二维向量 A(XA​,YA​),B(XB​,YB​)。给定 L，求 (XA​,YA​),(XB​,YB​) 有多少种不同的取值，使得：

1. XA​,YA​,XB​,YB​ 均为正整数；

2. A⋅B≤L，其中 A⋅B 表示 A,B 的内积，即 XA​⋅XB​+YA​⋅YB​。

解题思路：

这个题目比较难，也是用到了前缀和，但是还有数学思维。首先我们可以设u = XA*XB，v = YA * YB; 这样就将XA​⋅XB​+YA​⋅YB的关系转为了u+ v；这个时候就满足u + v <= L; u和v是完全相同的，因此我们可以先考虑u。对于u来说，要想满足所有情况，肯定是从最小的逐个网上增加，那么当u取1的时候，则有ＸＡ＊ＸＢ＝１，那么这个时候XA和XB取（1，1）；这个时候我们可以定义一个新数组cnt[k] 来表示u取k时，有多少个XA*XB，则有如下：

cnt[1] = 1：乘积恰好等于 1，只有(1, 1)这 1 种；

cnt[2] = 2：乘积恰好等于 2，有(1, 2)和(2, 1)共 2 种；

cnt[3] = 2：乘积恰好等于 3，有(1, 3)和(3, 1)共 2 种。

这是代码求cnt数组个数：

// cnt[k] 表示：两个正整数 x 和 y 相乘，结果【恰好等于 k】的组合数 std::vector<long long> cnt(L, 0); for (int x = 1; x < L; ++x) { for (int y = 1; x * y < L; ++y) { int k = x * y; // 计算当前的乘积 k cnt[k]++; // 乘积恰好为 k 的方案数加 1 } }

接着我们定义一个sum数组，用来求cnt的前缀和。sum[k]的含义是：两个正整数相乘，乘积“小于或等于k（即等于1、等于2……一直到等于k）的所有组合加起来总共有多少种。也就是说，sum[k]本质上就是把cnt[1]到cnt[k]全部加起来：sum[k] = cnt[1] + cnt}[2] +····· + cnt[k]；

// sum[k] 表示：两个正整数相乘，结果【小于等于 k】的组合总数 // 也就是 cnt[1] + cnt[2] + ... + cnt[k] 的累加和 std::vector<long long> sum(L, 0); for (int k = 1; k < L; ++k) { // 前 k - 1 个数的总和 (sum[k - 1])，加上当前恰好等于 k 的数量 (cnt[k]) sum[k] = sum[k - 1] + cnt[k]; }

假设 L = 4，我们把左边的 u 固定为 1（即 XA ·XB = 1）：

此时左边 (XA, XB) 的选法是固定的，就是“乘积恰好等于 1”的选法数，即cnt[1]种。既然左边已经是 u = 1 了，为了满足 u + v <= 4，右边的 v 只要满足 v <= 4 - 1（即 v = 3）就行！

• 那么 v <= 3 意味着什么？意味着右边的 $v$ 不是只能取一个数，它可以有三种选择：

  1. v 恰好等于 1：右边有cnt[1]种选法，左配右共有cnt[1] * cnt[1]种；

  2. v 恰好等于 2：右边有cnt[2]种选法，左配右共有cnt[1] * cnt[2]种；

  3. v 恰好等于 3：右边有cnt[3]种选法，左配右共有cnt[1] * cnt[3]种。

如果直接按这个逻辑写代码，左右两边确实全都是用cnt的，代码如下：

// 【直观版代码：左右全都用 cnt，但有两层循环】 long long ans = 0; // 外层循环：固定左边的乘积恰好等于 u for (int u = 1; u < L; ++u) { // 内层循环：当左边固定为 u 时，右边的乘积 v 可以取 1 到 L - u 之间的任意值 for (int v = 1; v <= L - u; ++v) { // 左边恰好等于 u 有 cnt[u] 种，右边恰好等于 v 有 cnt[v] 种 ans += cnt[u] * cnt[v]; } }

但是这样双层循环会超时，因此我们需要优化一下。

ans增加的值 = cnt[u] * cnt[1] +cnt[u] * cnt[2] +cnt[u] * cnt[3] + ·····+cnt[u] * cnt[L-u];提取公因式得

ans增加的值 = cnt[u] * （cnt[1] + cnt[2] + ... + cnt[L - u]）；这一段刚好等于sum[L-u];所以最终

ans增加的值 = cnt[u] * sum[L - u]; 下边是完整代码

#include <iostream> #include <vector> using namespace std; int main(){ int L = 0; cin >> L; if(L <= 1) { cout << 0 << endl; } vector<long long> cnt(L, 0); for(int x = 1; x < L; x++){ for(int y = 1; x * y < L; y++){ cnt[x * y]++; } } vector<long long> sum(L, 0); for(int k = 1; k < L; k++){ sum[k] = sum[k - 1] + cnt[k]; } long long ans = 0; for(int u = 1; u < L; u++){ ans += cnt[u] * sum[L - u]; } cout << ans << endl; return 0; }