CSDN 编程竞赛四十六期题解

地址：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$ （$C_n^4$ 为交点数即新增点数） ，线数为 $C_n^2$ + 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 。

对于以 $num{s}_i$ 结尾的连续子数组，最大值为 max ⁡ j = 0 i − 1 { p r e i − p r e j } \max_{j=0}^{i-1}\{ pre_i-pre_j \} maxj=0i−1​{prei​−prej​}

那么连续子数组的最大和，就等价于 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=0i−1​{prei​−prej​}}=maxi=1n​{prei​−minj=0i−1​{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;
}