阿里服务器怎么做网站服务器,自适应网站欣赏,庆阳网红宝军,唐山市住房城乡建设部网站主页1.数组构造 题目描述 小红的数组构造小红希望你构造一个数组满足以下条件: 1.数组共有 n个元素#xff0c;且所有元素两两不相等。 2.所有元素的最大公约数等于 k。 3.所有元素之和尽可能小。请你输出数组元素之和的最小值。 输入描述: 两个正整数 n 和 k。 输出描述#xff… 1.数组构造 题目描述 小红的数组构造小红希望你构造一个数组满足以下条件: 1.数组共有 n个元素且所有元素两两不相等。 2.所有元素的最大公约数等于 k。 3.所有元素之和尽可能小。请你输出数组元素之和的最小值。 输入描述: 两个正整数 n 和 k。 输出描述 一个正整数代表数组元素之和的最小值, 输入示例 3 1 输出示例 6 分析
数组只能是 1k,2k,3k,……,(n-1)k,nk
求和可以用等差数列求和公式 (n1)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下能够截取获得的最多精华帖子数量。 输入描述 第一行输入三个正整数 nmk分别代表初始帖子列表长度精华区间的数量以及运营同学准备截取的长度。 接下来的 m 行每行输入两个正整数,| 和r代表第i个左闭右开区间。 1 kn 20000000. 1 m 100000. 0 lri n保证任意两个区间是不重复的。 输出描述 一个正整数代表截取获得的最多的精华帖子数量。 输入示例 5 2 3 1 2 3 5 输出示例 2 思路
1.按照nmk构造输入序列v
2.先遍历前k个统计精华帖子数量再便利第k1个每次加上第i个减掉第i-k个的值即可
3.返回最大的数量
代码
#includeiostream
#include vector
using namespace std;
int main(){int n,m,k;cinnmk;vectorvectorint p;while(m--){int a,b;cinab;vectorint p1 {a,b};p.push_back(p1);}vectorint v(n,0);for(auto it:p){for(int i it[0];iit[1];i){v[i] 1;}}int res 0;int sum 0;for(int i 0;ik;i){res v[i];}sum res;for(int i k;in;i){sum sum v[i] - v[i-k];res max(res,sum);}coutresendl;}
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;vectorint vec(n);for (int i 0; i n; i) cin vec[i];vectorint 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]);// 从后向前统计最大子序和vectorint 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[i1], 0);res max(res, dp1res dp2res x);}cout res endl;}}
