【蓝桥杯2022省赛】2022省赛求和、修剪灌木、卡片
【蓝桥杯2022省赛】2022省赛求和、修剪灌木、卡片
一、求和
问题描述📕
给定 n 个整数 1,2,⋅⋅⋅,a1,a2,⋅⋅⋅,an ，求它们两两相乘再相加的和，即：
S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅an
输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数 a1,a2,⋯,an。
输出格式
输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。
样例输入
4
1 3 6 9样例输出
117评测用例规模与约定
对于 30%30% 的数据，1≤n≤1000,1≤ai≤100 。
对于所有评测用例， 1≤n≤200000,1≤ai≤1000 。
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
解题步骤🚀🚀
问题描述： 给定 n 个整数 1,2,⋅⋅⋅,a1,a2,⋅⋅⋅,an ，求它们两两相乘再相加的和，即： S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅an 解题思路： 首先读取数组A[]。计算数组的前缀和。(所谓前缀和就是a[i]前面元素的和。记presum[]为前缀和数组。presum[1]=a[0],presum[2]=a[1]+a[2]=presun[i-1]+a[2]....;）presun[i]=presum[i-1]+a[i];
- 计数组的和为S。
- a1*a2+a1*a3+....+a1*an=a1*(S-a1)=a1(S-presum[1]);
- a2*a3+a2*a4+...+a2*an=a2*(S-a1-a2)=a2*(S-presum[2])....
- an-1*an=an-1*(S-presum[n-1]);
利用数组和跟前缀和进行计算，即可得到答案。
解题代码💡💡
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
//输入数组长度n;11
int n=scan.nextInt();
//最终结果可能为long型，我们定义long数组方便计算
long[] num=new long[n];
for(int i=0;i<n;i++){
num[i]=scan.nextLong();
}
long[] presum=new long[n+1];
//计算前缀和
for(int i=1;i<n+1;i++){
presum[i]=presum[i-1]+num[i-1];
}
long sum=0;
//计算和sum
for(int i=1;i<n;i++){
sum+=(presum[n]-presum[i])*num[i-1];
}
System.out.println(sum);
scan.close();
}
}
二、修剪灌木
问题描述📕
爱丽丝要完成一项修剪灌木的工作。
有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌 木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开 始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晩会长高 1 厘米, 而其余时间不会长高。在第一天的 早晨, 所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
输入格式
一个正整数 N, 含义如题面所述。
输出格式
输出 N 行, 每行一个整数, 第 i 行表示从左到右第 i 棵树最高能长到多高。
样例输入
3样例输出
4
2
4解题思路💡💡
问题解析： 1,2,...,n 。1最大的时候是从2到n，再从n到1。即是2*(n-1)； 而n最大时是从n-1到1，再从1到n。即使2*(n-1)。 (实际前后两部分是对称的)； 下面给出代码
解题代码🚀🚀
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n=scan.nextInt();
int[] max=new int[n];
int[] nums=new int[n];
int number=1;
//首先计算从1到n再从n到1的前半部分。将最大值记录再max数组中
for(int i=0;i<n;i++){
nums[i]=2*(n-i-1);
max[i]=Math.max(max[i],nums[i]);
}
//然后计算从n到1后半部分的最大值(实际前后两部分是对称的)
for(int i=n-1;i>=0;i--){
nums[i]=2*i;
max[i]=Math.max(max[i],nums[i]);
}
for(int i=0;i<n;i++){
System.out.println(max[i]);
}
scan.close();
}
}
三、卡片
问题描述📕
小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。
给定n, 请问小蓝的卡片至少有多少种?
输入格式
输入一行包含一个正整数表示n 。
输出格式
输出一行包含一个整数, 表示答案。
样例输入
6样例输出
3样例说明
小朋友们手中的卡片可能是: (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) 。
评测用例规模与约定
对于 5050 的评测用例, 1≤n≤10e4 。
对于所有评测用例, 1≤n≤10e9 。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
解题步骤💡💡
问题描述： 小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。 给定n, 请问小蓝的卡片至少有多少种? 解题思路： 首先组和不能重复，只能出现一次(即不能有(a,b) ,(b,a))。组合内的元素可以相同。即是可以出现(a,a),(b,b),... 所以最少卡片的排序只能是每个卡片能最多参与的次数即(a,b,c)为：(a,a),(a,b),(a,c),(b,b),(b,c),(c,c)...
解题代码🚀🚀
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n=scan.nextInt();
int sum=0;
for(int i=1;;i++){
sum+=i;
if(sum>=n){
System.out.println(i);
break;
}
}
scan.close();
}
}