CSDN 编程竞赛四十六期题解

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6

地址CSDN 编程竞赛四十六期


在这里插入图片描述
思路通过找规律可以知道在周期第一个位置的数的下标都有一个规律除以三的余数为 1 。而第二个位置第三个位置的余数分别为 2 0 。 因此可以开一个长度为 3 的总和数组以原下标的余数作为总和数组的下标用来记录总和。

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
int n, a[200];
long long s[3];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		s[i % 3] += a[i];
	}
	if(s[1] > max(s[2], s[0])) cout << 'J';
	else if(s[2] > max(s[0], s[1])) cout << 'H';
	else if(s[0] > max(s[1], s[2])) cout << 'B';
	return 0;
}

在这里插入图片描述
思路平面欧拉公式 点数 - 面数 + 线数 = 联通块数 + 1

点即线段的两个端点或者射线的一个端点线即线段或射线或直线面即被线分割成的不同平面。联通块即线构成的联通块。

在这道题连通块数一定为 1 。点数为 n + C n 4 n+C_n^4 n+Cn4 C n 4 C_n^4 Cn4 为交点数即新增点数 线数为 C n 2 C_n^2 Cn2 + 2 * 交点数因为 n 为奇数所以任意线段交点一定不会重合每一个交点会使两个线段分割为四个线段根据以上条件就能得到面数记得要把外面那个无限的面去掉。

代码

n = int(input())
p = int(1e9 + 7)
print((1 + n * (n - 1) // 2 + n * (n - 1) * (n - 2) * (n - 3) // 24 - n + p) % p)

在这里插入图片描述
思路可以发现不管如何旋转对于最小值都是无影响的因此求一下数组的最小值即可。

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
int solution(int n, std::vector<int>& vec){
	int result = 1e9;
	for(int x : vec) result = std::min(result, x);
	return result;
}
int main() {
	int n;
	std::vector<int> vec;
	std::cin>>n;
	std::string line_0, token_0;
	getline(std::cin >> std::ws,line_0);
	std::stringstream tokens_0(line_0);
	while(std::getline(tokens_0, token_0, ' ')){
		vec.push_back(std::stoi(token_0));
	}
	int result = solution(n,vec);
	std::cout<<result<<std::endl;
	return 0;
}

在这里插入图片描述
思路从前缀和的角度考虑设 nums 数组的前缀和数组为 pre 。

对于以 n u m s i nums_i numsi 结尾的连续子数组最大值为 max ⁡ j = 0 i − 1 { p r e i − p r e j } \max_{j=0}^{i-1}\{ pre_i-pre_j \} maxj=0i1{preiprej}

那么连续子数组的最大和就等价于 max ⁡ i = 1 n { max ⁡ j = 0 i − 1 { p r e i − p r e j } } = max ⁡ i = 1 n { p r e i − min ⁡ j = 0 i − 1 { p r e j } } \max_{i=1}^n\{ \max_{j=0}^{i-1} \{ pre_i-pre_{j} \}\}=\max_{i=1}^n\{ pre_i-\min_{j=0}^{i-1} \{ pre_{j} \}\} maxi=1n{maxj=0i1{preiprej}}=maxi=1n{preiminj=0i1{prej}} 问题转化为求每一个前缀的前缀和最小值可以一边更新答案一边计算当前前缀最小值。

代码

#include <iostream>
#include <set>
#include <sstream>
#include <vector>
using namespace std;
int a[1010], pre[1010];
set<int> st = {0};
int main() {
	int n, ans = -1e9; cin >> n;
	for(int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
		ans = max(ans, pre[i] - *st.begin());
		st.insert(pre[i]);
	}
	cout << ans;
	return 0;
}
阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6