1.数组构造
题目描述
小红的数组构造小红希望你构造一个数组满足以下条件:
1.数组共有 n个元素，且所有元素两两不相等。
2.所有元素的最大公约数等于 k。
3.所有元素之和尽可能小。请你输出数组元素之和的最小值。
输入描述:
两个正整数 n 和 k。
输出描述：
一个正整数，代表数组元素之和的最小值,
输入示例：
3 1
输出示例：6
分析：
数组只能是 1k,2k,3k,……,(n-1)k,nk
求和可以用等差数列求和公式 (n+1)nk/2
代码：
#include <iostream>
using namespace std;
int main() {
long long result = 0;
int n, k;
cin >> n >> k;
// 使用等差数列求和公式进行计算
result = k * (n * (n + 1LL) / 2);
cout << result << endl;
return 0;
}2.精华帖子
题目描述
小红书的推荐帖子列表为 [0,n)，其中所有的帖子初始状态为"普通"，现在运营同学把其中的一些帖子区间标记为了“精华"。
运营同学选择了固定长度 k，对整个帖子列表截取，要求计算在固定的截取长度k下，能够截取获得的最多精华帖子数量。
输入描述
第一行输入三个正整数 n，m，k，分别代表初始帖子列表长度，精华区间的数量，以及运营同学准备截取的长度。
接下来的 m 行，每行输入两个正整数,| 和r，代表第i个左闭右开区间。
1 <= k<=n<= 20000000.
1<= m <= 100000.
0 <=l<ri<= n，保证任意两个区间是不重复的。
输出描述
一个正整数，代表截取获得的最多的精华帖子数量。
输入示例
5 2 3
1 2
3 5
输出示例2
思路：
1.按照n，m，k构造输入序列v
2.先遍历前k个，统计精华帖子数量，再便利第k+1个，每次加上第i个，减掉第i-k个的值即可
3.返回最大的数量
代码：
#include<iostream>
#include <vector>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>> p;
while(m--){
int a,b;
cin>>a>>b;
vector<int> p1 = {a,b};
p.push_back(p1);
}
vector<int> v(n,0);
for(auto it:p){
for(int i = it[0];i<it[1];i++){
v[i] = 1;
}
}
int res = 0;
int sum = 0;
for(int i = 0;i<k;i++){
res +=v[i];
}
sum = res;
for(int i = k;i<n;i++){
sum = sum + v[i] - v[i-k];
res = max(res,sum);
}
cout<<res<<endl;
}3.连续子数组最大和
题目描述
小红拿到了一个数组，她希望进行最多一次操作:将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少?
输入描述
第一行输入一个正整数t，代表询问次数。对于每次询问，输入两行:
第一行输入两个正整数n和x。代表数组的大小，以及小红可以修改成的元素。第二行输入n个正整数a_i，代表小红拿到的数组
输出描述
输出t行，每行输出一个整数，代表连续子数组的最大和。
输入示例
3
5 10
5 -1 -5 -3 2
2 -3
-5 -2
6 10
4 -2 -11 -1 4 -1
输出示例15
-2
15
思路：（代码随想录）
动态规划：最大子序和 的方法，先求出 [0 - i) 区间的 最大子序和 dp1 和 (i, n)的最大子序和dp2
然后在遍历一遍i， 计算 dp1 + dp2 + vec[i] 的最大值就可以。
正序遍历，求出 [0 - i) 区间的 最大子序，dp[ i - 1] 表示 是 以 下标 i - 1为结尾的最大连续子序列和为dp[i - 1]。
所以 在计算区间 (i, n)即 dp2 的时候，我们要倒叙。因为我们求的是以 包括下标i + 1为起始位置的最大连续子序列和为dp[i + 1]。
这样 dp1 + dp2 + vec[i] 才是一个完整区间。
代码：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int t, n, x;
cin >> t;
while (t--) {
cin >> n >> x;
vector<int> vec(n);
for (int i = 0; i < n; i++) cin >> vec[i];
vector<int> dp1(n);
dp1[0] = vec[0];
int res = vec[0];
// 从前向后统计最大子序和
for (int i = 1; i < n; i++) {
dp1[i] = max(dp1[i - 1] + vec[i], vec[i]); // 状态转移公式
res = max(res, dp1[i]);
}
res = max(res, vec[n - 1]);
// 从后向前统计最大子序和
vector<int> dp2(n);
dp2[n - 1] = vec[n - 1];
for (int i = n - 2; i >= 0; i--) {
dp2[i] = max(dp2[i + 1] + vec[i], vec[i]);
}
for (int i = 0 ; i < n ; i++) {
int dp1res = 0;
if (i > 0) dp1res = max(dp1[i-1], 0);
int dp2res = 0;
if (i < n - 1 ) dp2res = max(dp2[i+1], 0);
res = max(res, dp1res + dp2res + x);
}
cout << res << endl;
}
}
