这份代码非常经典，使用到了算法竞赛和日常开发中常用的前缀和思想。为了让刚接触 C++ 的学生能够彻底透彻地理解，我们将整个代码拆解开来。不仅讲“思路”，还会详细解释“为什么用这些 C++ 语法和函数”。
一、 整体解题思路概述
题目要求我们切两刀，把数组分成三段，并且满足：
-
三段的和必须完全相等。
-
每一段里至少得有一个正数（大于 0 的数）。
如果三段和相等，那么整个数组的总和必须能被 3 整除，每一小段的目标和就是总和 / 3。
为了不反复去计算某一段的和，我们使用了前缀和的技巧：也就是边读取数据，边把前面的所有数字加起来。这样，只要看到某个位置的前缀和等于目标和，说明这里可以切第一刀；等于目标和的2倍，说明这里可以切第二刀。
二、 逐行代码拆解与函数详解
1. 头文件与命名空间
#include <iostream> #include <vector> using namespace std;
-
#include <iostream>：这是 C++ 标准输入输出流库。为什么用它？ 因为我们需要使用cin来读取键盘输入的数据，用cout将最终的答案打印到屏幕上。
-
#include <vector>：这是 C++ 标准模板库（STL）中的动态数组容器。为什么用它？ 传统的 C 语言数组（如int a[100]）大小是固定的，如果题目给的数据量很大，容易越界；而vector可以根据变量n动态分配内存，更加安全且功能强大。
-
using namespace std;：告诉编译器我们要使用标准命名空间。这样我们在写cin、cout、vector时，前面就不需要繁琐地加上std::前缀了。
2. 主函数与 I/O 优化
int main() { // 优化 C++ 的输入输出速度，防止超时 ios::sync_with_stdio(false); cin.tie(nullptr);
-
int main()：C++ 程序的入口点，代码从这里开始执行。
-
ios::sync_with_stdio(false);：为什么用它？ C++ 的cin和cout默认为了兼容 C 语言的scanf和printf，会有额外的同步开销，导致读取大量数据时非常慢。这行代码的作用是关闭这种同步，让 C++ 的输入输出速度大幅提升，防止在算法题中因为读写数据太慢而超时（Time Limit Exceeded）。
-
cin.tie(nullptr);：为什么用它？ 默认情况下，cin和cout是绑定的（每次cin之前都会自动刷新cout的缓冲区）。在纯后台算法题中，我们不需要这种交互式的刷新，解除绑定可以进一步加快速度。
3. 读取数组长度并处理特殊情况
int n; if (!(cin >> n)) return 0;
-
int n;：声明一个整数变量n，用来存储数组里有多少个数字。
-
cin >> n：从键盘读取一个整数并赋值给n。
-
if (!(cin >> n)) return 0;：这是一个防御性编程的写法。如果读取失败（比如遇到文件末尾或者异常输入），程序就直接退出（return 0），防止后续代码报错。
4. 核心容器的声明
// 因为数据范围很大，和可能会超出 int 的范围，所以使用 long long vector<long long> a(n); vector<long long> sum(n); // 记录前缀和 vector<int> pos(n); // 记录到当前位置为止，正数的总个数
-
vector<long long> a(n);：为什么用long long？ 题目中每个元素最大是 $10^9$，如果 $2 \times 10^5$ 个元素加起来，最大会达到 $2 \times 10^{14}$，这远远超过了普通int能存储的最大值（约 $2 \times 10^9$）。如果不使用long long（64位整数），数据会溢出变成负数，导致答案全错。a(n)表示初始化一个大小为n的数组。
-
sum(n)和pos(n)：sum用来记录“从开头加到当前位置的总和”，pos用来记录“从开头到当前位置一共出现了多少个正数”。
5. 第一次遍历：计算前缀和与正数统计
long long total_sum = 0; int total_pos = 0; for (int i = 0; i < n; i++) { cin >> a[i]; total_sum += a[i]; if (a[i] > 0) { total_pos++; } sum[i] = total_sum; pos[i] = total_pos; }
-
这部分是一次完整的循环（从 0 到n-1）。
-
cin >> a[i];：读取每一个数组元素。
-
total_sum += a[i]; 和 sum[i] = total_sum;：这就是前缀和的核心。比如数组是{1, 2, 3}，sum数组就会变成{1, 3, 6}。以后想知道整个数组的总和，直接看最后一个元素或者total_sum就可以了。
-
if (a[i] > 0) { total_pos++; }：如果当前读取的数大于 0，就把正数计数器加 1，并存入pos[i]中。
6. 过滤绝不可能成立的情况
if (total_sum % 3 != 0 || total_pos < 3) { cout << 0 << "\n"; return 0; } long long target = total_sum / 3;
-
total_sum % 3 != 0：如果总和除以 3 有余数，说明根本没办法平分成三等份，直接输出 0 种方案。
-
total_pos < 3：题目要求三段里每段至少有一个正数。如果整个数组里的正数加起来都不够 3 个，那怎么分都不够，直接输出 0。
-
target：算出如果切分成功，每一小段应该达到的目标和。
7. 第二次遍历：寻找所有合格的“第一刀”
vector<int> cnt_i(n, 0); int valid_first_cuts = 0; for (int i = 0; i < n; i++) { if (sum[i] == target && pos[i] > 0) { valid_first_cuts++; } cnt_i[i] = valid_first_cuts; }
-
vector<int> cnt_i(n, 0);：我们创建了一个新的数组，名字叫cnt_i，全称为 count of index。
-
为什么需要这个数组？ 为了避免在后续找“第二刀”时，频繁回头去数“前面有几个第一刀”，我们用空间换时间。
-
sum[i] == target && pos[i] > 0：判断第一刀是否合法。条件是：累加和正好等于target，并且这一段里至少包含了 1 个正数（pos[i] > 0）。
-
cnt_i[i] = valid_first_cuts;：把截止到位置i，一共发现了多少个合法的“第一刀”记录下来。
8. 第三次遍历：寻找“第二刀”并计算最终答案
long long ans = 0; int last_pos_idx = -1; for (int j = 0; j < n - 1; j++) { if (a[j] > 0) { last_pos_idx = j; } if (j >= 1) { if (sum[j] == 2 * target && (total_pos - pos[j] > 0)) { if (last_pos_idx > 0) { ans += cnt_i[last_pos_idx - 1]; } } } }
-
int last_pos_idx = -1;：用来实时记录我们在往前走的过程中，最近一次遇到正数是在哪个位置。
-
for (int j = 0; j < n - 1; j++)：我们在寻找第二刀的位置j。为什么是n - 1？ 因为最后必须给第三段留至少一个元素，所以第二刀最多切在倒数第二个元素后面。
-
if (a[j] > 0) { last_pos_idx = j; }：每次遇到正数，更新它所在的位置。
-
if (j >= 1)：第二刀的位置索引至少是 1，因为前面还得给“第一段”留出空间。
-
sum[j] == 2 * target：判断前两段的总和是否达到了target的两倍。如果是，说明第二刀切这里，能保证第二段的和也等于target。
-
total_pos - pos[j] > 0：判断第三段里有没有正数。total_pos是总正数，pos[j]是前两段的正数，两者相减就是第三段的正数个数。
-
最核心的逻辑：if (last_pos_idx > 0) { ans += cnt_i[last_pos_idx - 1]; }
-
此时，第一段和第三段都满足要求了，但是如何保证中间的第二段也有正数？
-
中间段是从“第一刀”后面开始，到j结束的。
-
如果我们想让这一段有正数，第一刀的位置就必须切在 “距离 j 最近的一个正数”的前面。
-
这个最近的正数的位置就是last_pos_idx。第一刀切在这个正数前面，意味着第一刀的索引必须<= last_pos_idx - 1。
-
所以，我们直接去cnt_i数组里查一查，在last_pos_idx - 1之前一共有多少个合法的“第一刀”，把这个数量直接加到最终答案ans里。
-
9. 输出并结束程序
cout << ans << "\n"; return 0; }
-
cout << ans << "\n";：打印最终计算出的组合方案数。为什么用\n而不用endl？ 在 C++ 中，endl除了换行，还会强行刷新缓冲区，这在大量输出时非常耗时。使用\n换行速度更快，是算法题的标准写法。
-
return 0;：告诉操作系统，程序正常结束，没有发生任何错误。
#include <stdio.h>
#define MAXN 200000
void calcsums(long a[], long s[], long c[], long n);
void calcsums(long a[], long s[], long c[], long n){
long i=0;
s[0]=a[0];
if(a[i]>0)c[i]++;
for(i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
c[i]=c[i-1];
if(a[i]>0)c[i]++;
}
}
int main() {
long n;
scanf("%ld",&n);
long i;
long ar[MAXN];
for(i=0;i<n;i++){
scanf("%ld",&ar[i]);
}
long sums[MAXN]={0};
long checker[MAXN]={0};
calcsums(ar,sums,checker,n);
//chc(ar,checker,n);
long cut1,cut2; //end1 end2
long s1,s2,s3;
long m=0;
for(cut1=1;cut1<n-1;cut1++){
if(checker[cut1-1]>0&&3*sums[cut1-1]==sums[n-1]){
s1=sums[cut1-1];
for(cut2=cut1+1;cut2<n;cut2++){
if(checker[n-1]-checker[cut2-1]>0&&checker[cut2-1]-checker[cut1-1]>0){
s2=sums[cut2-1]-sums[cut1-1];
if(s1==s2){
m+=1;
}
}
}
}
}
printf("%ld",m);
return 0;
}
本来是前缀和求子数组值，先判断子数组和都相等，再判断包含正数，超时；
后面先判断包含正数再判断和相等，超时；
思考了一下包含正数也可以用前缀和（本来用遍历），超时；
发现在外层循环就可以获取到第一部分前缀和，通过判断该前缀和是否为原数组值三分之一（本来都没想到，看到讨论里有个大佬在说这个）剪枝，通过
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n,sum=0;
cin>>n;
vector<int> nums(n);
for(int i=0;i<n;i++)
{
cin>>nums[i];
sum+=nums[i];
}
if(sum%3!=0)
{
cout<<0;
return 0;
}
vector<int> dp(n),dp1(n);
if(nums[0]>0)dp[0]=1;
dp1[0]=nums[0];
for(int i=1;i<n;i++)
{
if(nums[i]>0)
{
dp[i]=dp[i-1]+1;
}
else {
dp[i]=dp[i-1];
}
dp1[i]=dp1[i-1]+nums[i];
}
int count=0,target=sum/3;
for(int i=0;i<n-1;i++)
{
if(dp1[i]==target&&dp[i]>0)
{
for(int j=i+1;j<n-1;j++)
{
if(dp1[j]-dp1[i]==target&&dp[j]-dp[i]>0)
count++;
}
}
}
cout<<count;
return 0;
} 使用动态规划，dp[i]定义为前i个元素包含正数的个数，dp1[i]定义为前i个元素的前缀和。
- 使用BufferedReader, PrintWriter StringTokenizer 加快IO速度避免超时
- 使用前缀和快速判断区间内元素和是否满足要求
- 使用整数计数数组快速判断区间内是否包含正数
- 如果总和不能被3整除, 直接返回0
- 两层for循环查找有效分割点
- 第一层 for 找到第一个有效分割点
- 第二层for在第一个分割点后面找有效的第二个分割点
- 通过判断每个分割点后是否还有整数进行剪枝
- 每次找到一对分割点, 结果++
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(System.out);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
long[] nums = new long[n + 1];
for (int i = 1; i <= n; i++) {
nums[i - 1] = Long.parseLong(st.nextToken());
}
Solution solution = new Solution();
int res = solution.cutArray(nums);
pw.println(res);
pw.close();
}
}
class Solution {
public int cutArray(long[] nums) {
int n = nums.length;
long[] preSum = new long[n];
int[] posCnt = new int[n];
preSum[0] = nums[0];
posCnt[0] = nums[0] > 0 ? 1 : 0;
for (int i = 1; i < n; i++) {
preSum[i] = preSum[i - 1] + nums[i];
posCnt[i] = posCnt[i - 1] + (nums[i] > 0 ? 1 : 0);
}
long sum = preSum[n - 1];
if (sum % 3 != 0) return 0;
long target = sum / 3;
int ans = 0;
for (int i = 0; i < n - 2; i++) {
if (preSum[i] != target || posCnt[i] == 0) continue;
if (posCnt[i] == posCnt[n - 1]) break;
for (int j = i + 1; j < n - 1; j++) {
if (preSum[j] - preSum[i] != target) continue;
if (posCnt[i] == posCnt[j] || posCnt[j] == posCnt[n - 1]) continue;
ans++;
}
}
return ans;
}
} 
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
long long sum = 0;
vector<long long> nums(n);
vector<long long> presum(n+1);//前i个数字的前缀和
vector<int> dp(n+1);//前i个数字有几个正数
for (int i = 0; i<n; ++i)
{
cin >> nums[i];
sum += nums[i];
}
//加工前缀和数组，正数统计数组
for (int i = 1; i<=n; ++i)
{
presum[i] = presum[i-1]+nums[i-1];
//真几把无语，这还非得加个括号，我找半天错误，原来是这
dp[i] = dp[i-1] + (nums[i-1] > 0 ? 1 : 0);
}
if (sum%3 != 0 || dp[n] == 0)
{
cout << 0;
return 0;
}
long long target = sum/3;
int ans = 0;
for (int i = 1; i<=n; ++i)
{
//前i个数字累加和为1/3的sum，且有正数
if (presum[i] == target && dp[i] > 0)
{
for (int j = i+1; j<=n; ++j)
{
//前j个数字累加和为2/3的sum，且每段都有正数
if (presum[j] == 2*target && dp[j] - dp[i] > 0 && dp[n] - dp[j] > 0)
{
ans++;
}
}
}
}
cout << ans;
}
// 64 位输出请用 printf("%lld") 
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int nums = in.nextInt();
int array[] = new int[nums];
int sum = 0;
for (int i = 0; i < nums; i++) {
array[i] = in.nextInt();
sum = sum + array[i];
}
int target = sum / 3;
int sumOfPart = 0;
ArrayList<Integer> indexLeftList = new ArrayList<>();
ArrayList<Integer> indexRightList = new ArrayList<>();
boolean positive = false;;
for (int i = 0; i < array.length; i++) {
if (array[i] > 0) {
positive = true;
}
sumOfPart += array[i];
if (sumOfPart == target && positive) {
indexLeftList.add(i);
}
}
sumOfPart = 0;
positive = false;
for (int i = array.length - 1; i >= 0; i--) {
if (array[i] > 0) {
positive = true;
}
sumOfPart += array[i];
if (sumOfPart == target && positive) {
indexRightList.add(i);
}
}
int count = 0;
for(int i = 0;i<indexLeftList.size();i++){
for(int j = j=0;j<indexRightList.size();j++){
if(indexLeftList.get(i)<indexRightList.get(j)){
if(isValid(indexLeftList.get(i),indexRightList.get(j),array,target)){
count++;
}
}
}
}
System.out.print(count);
}
public static boolean isValid(int left,int right,int[]nums,int target){
int sum = 0;
boolean positive = false;
for(int i = left+1;i<=right-1;i++){
if (nums[i] > 0) {
positive = true;
}
sum+=nums[i];
}
if(sum==target && positive){
return true;
}else{
return false;
}
}
} 
num = int(input())
num_list = input().split(" ")
num_list = [int(item) for item in num_list]
obj = sum(num_list) / 3
if not obj == int(obj):
print(0)
exit(0)
sum_prefix = [0] * num
count_prefix = [0] * num
loc_dic = {"m": [], "2m": []}
temp = 0
count = 0
for i in range(0, num):
if num_list[i] > 0:
count += 1
temp = temp + num_list[i]
sum_prefix[i] = temp
count_prefix[i] = count
if temp == obj:
loc_dic["m"].append(i)
if temp == 2 * obj:
loc_dic["2m"].append(i)
res = 0
for L in loc_dic["m"]:
for R in loc_dic["2m"]:
if L < R and count_prefix[R] - count_prefix[L] > 0:
res += 1
print(res) 最后一个过不了, 超时了
这份代码非常经典，使用到了算法竞赛和日常开发中常用的前缀和思想。为了让刚接触 C++ 的学生能够彻底透彻地理解，我们将整个代码拆解开来。不仅讲“思路”，还会详细解释“为什么用这些 C++ 语法和函数”。
一、 整体解题思路概述
题目要求我们切两刀，把数组分成三段，并且满足：
-
三段的和必须完全相等。
-
每一段里至少得有一个正数（大于 0 的数）。
如果三段和相等，那么整个数组的总和必须能被 3 整除，每一小段的目标和就是总和 / 3。
为了不反复去计算某一段的和，我们使用了前缀和的技巧：也就是边读取数据，边把前面的所有数字加起来。这样，只要看到某个位置的前缀和等于目标和，说明这里可以切第一刀；等于目标和的2倍，说明这里可以切第二刀。
二、 逐行代码拆解与函数详解
1. 头文件与命名空间
#include <iostream> #include <vector> using namespace std;
-
#include <iostream>：这是 C++ 标准输入输出流库。为什么用它？ 因为我们需要使用cin来读取键盘输入的数据，用cout将最终的答案打印到屏幕上。
-
#include <vector>：这是 C++ 标准模板库（STL）中的动态数组容器。为什么用它？ 传统的 C 语言数组（如int a[100]）大小是固定的，如果题目给的数据量很大，容易越界；而vector可以根据变量n动态分配内存，更加安全且功能强大。
-
using namespace std;：告诉编译器我们要使用标准命名空间。这样我们在写cin、cout、vector时，前面就不需要繁琐地加上std::前缀了。
2. 主函数与 I/O 优化
int main() { // 优化 C++ 的输入输出速度，防止超时 ios::sync_with_stdio(false); cin.tie(nullptr);
-
int main()：C++ 程序的入口点，代码从这里开始执行。
-
ios::sync_with_stdio(false);：为什么用它？ C++ 的cin和cout默认为了兼容 C 语言的scanf和printf，会有额外的同步开销，导致读取大量数据时非常慢。这行代码的作用是关闭这种同步，让 C++ 的输入输出速度大幅提升，防止在算法题中因为读写数据太慢而超时（Time Limit Exceeded）。
-
cin.tie(nullptr);：为什么用它？ 默认情况下，cin和cout是绑定的（每次cin之前都会自动刷新cout的缓冲区）。在纯后台算法题中，我们不需要这种交互式的刷新，解除绑定可以进一步加快速度。
3. 读取数组长度并处理特殊情况
int n; if (!(cin >> n)) return 0;
-
int n;：声明一个整数变量n，用来存储数组里有多少个数字。
-
cin >> n：从键盘读取一个整数并赋值给n。
-
if (!(cin >> n)) return 0;：这是一个防御性编程的写法。如果读取失败（比如遇到文件末尾或者异常输入），程序就直接退出（return 0），防止后续代码报错。
4. 核心容器的声明
// 因为数据范围很大，和可能会超出 int 的范围，所以使用 long long vector<long long> a(n); vector<long long> sum(n); // 记录前缀和 vector<int> pos(n); // 记录到当前位置为止，正数的总个数
-
vector<long long> a(n);：为什么用long long？ 题目中每个元素最大是 $10^9$，如果 $2 \times 10^5$ 个元素加起来，最大会达到 $2 \times 10^{14}$，这远远超过了普通int能存储的最大值（约 $2 \times 10^9$）。如果不使用long long（64位整数），数据会溢出变成负数，导致答案全错。a(n)表示初始化一个大小为n的数组。
-
sum(n)和pos(n)：sum用来记录“从开头加到当前位置的总和”，pos用来记录“从开头到当前位置一共出现了多少个正数”。
5. 第一次遍历：计算前缀和与正数统计
long long total_sum = 0; int total_pos = 0; for (int i = 0; i < n; i++) { cin >> a[i]; total_sum += a[i]; if (a[i] > 0) { total_pos++; } sum[i] = total_sum; pos[i] = total_pos; }
-
这部分是一次完整的循环（从 0 到n-1）。
-
cin >> a[i];：读取每一个数组元素。
-
total_sum += a[i]; 和 sum[i] = total_sum;：这就是前缀和的核心。比如数组是{1, 2, 3}，sum数组就会变成{1, 3, 6}。以后想知道整个数组的总和，直接看最后一个元素或者total_sum就可以了。
-
if (a[i] > 0) { total_pos++; }：如果当前读取的数大于 0，就把正数计数器加 1，并存入pos[i]中。
6. 过滤绝不可能成立的情况
if (total_sum % 3 != 0 || total_pos < 3) { cout << 0 << "\n"; return 0; } long long target = total_sum / 3;
-
total_sum % 3 != 0：如果总和除以 3 有余数，说明根本没办法平分成三等份，直接输出 0 种方案。
-
total_pos < 3：题目要求三段里每段至少有一个正数。如果整个数组里的正数加起来都不够 3 个，那怎么分都不够，直接输出 0。
-
target：算出如果切分成功，每一小段应该达到的目标和。
7. 第二次遍历：寻找所有合格的“第一刀”
vector<int> cnt_i(n, 0); int valid_first_cuts = 0; for (int i = 0; i < n; i++) { if (sum[i] == target && pos[i] > 0) { valid_first_cuts++; } cnt_i[i] = valid_first_cuts; }
-
vector<int> cnt_i(n, 0);：我们创建了一个新的数组，名字叫cnt_i，全称为 count of index。
-
为什么需要这个数组？ 为了避免在后续找“第二刀”时，频繁回头去数“前面有几个第一刀”，我们用空间换时间。
-
sum[i] == target && pos[i] > 0：判断第一刀是否合法。条件是：累加和正好等于target，并且这一段里至少包含了 1 个正数（pos[i] > 0）。
-
cnt_i[i] = valid_first_cuts;：把截止到位置i，一共发现了多少个合法的“第一刀”记录下来。
8. 第三次遍历：寻找“第二刀”并计算最终答案
long long ans = 0; int last_pos_idx = -1; for (int j = 0; j < n - 1; j++) { if (a[j] > 0) { last_pos_idx = j; } if (j >= 1) { if (sum[j] == 2 * target && (total_pos - pos[j] > 0)) { if (last_pos_idx > 0) { ans += cnt_i[last_pos_idx - 1]; } } } }
-
int last_pos_idx = -1;：用来实时记录我们在往前走的过程中，最近一次遇到正数是在哪个位置。
-
for (int j = 0; j < n - 1; j++)：我们在寻找第二刀的位置j。为什么是n - 1？ 因为最后必须给第三段留至少一个元素，所以第二刀最多切在倒数第二个元素后面。
-
if (a[j] > 0) { last_pos_idx = j; }：每次遇到正数，更新它所在的位置。
-
if (j >= 1)：第二刀的位置索引至少是 1，因为前面还得给“第一段”留出空间。
-
sum[j] == 2 * target：判断前两段的总和是否达到了target的两倍。如果是，说明第二刀切这里，能保证第二段的和也等于target。
-
total_pos - pos[j] > 0：判断第三段里有没有正数。total_pos是总正数，pos[j]是前两段的正数，两者相减就是第三段的正数个数。
-
最核心的逻辑：if (last_pos_idx > 0) { ans += cnt_i[last_pos_idx - 1]; }
-
此时，第一段和第三段都满足要求了，但是如何保证中间的第二段也有正数？
-
中间段是从“第一刀”后面开始，到j结束的。
-
如果我们想让这一段有正数，第一刀的位置就必须切在 “距离 j 最近的一个正数”的前面。
-
这个最近的正数的位置就是last_pos_idx。第一刀切在这个正数前面，意味着第一刀的索引必须<= last_pos_idx - 1。
-
所以，我们直接去cnt_i数组里查一查，在last_pos_idx - 1之前一共有多少个合法的“第一刀”，把这个数量直接加到最终答案ans里。
-
9. 输出并结束程序
cout << ans << "\n"; return 0; }
-
cout << ans << "\n";：打印最终计算出的组合方案数。为什么用\n而不用endl？ 在 C++ 中，endl除了换行，还会强行刷新缓冲区，这在大量输出时非常耗时。使用\n换行速度更快，是算法题的标准写法。
-
return 0;：告诉操作系统，程序正常结束，没有发生任何错误。
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long[] arr = new long[n];
long[] preSum = new long[n+1]; //前缀和
int[] posNum = new int[n+1]; //前i个数中正数的个数
for(int i = 0; i < n; i++) {
arr[i] = in.nextLong();
preSum[i+1] = preSum[i] + arr[i];
posNum[i+1] = posNum[i] + (arr[i] > 0 ? 1 : 0);
}
if(preSum[n] % 3 != 0) {
System.out.println(0);
return;
}
int res = 0;
long oneIn3 = preSum[n] / 3;
for(int i = 0; i < n-2; i++) {
if(preSum[i+1] == oneIn3 && posNum[i+1] > 0) {
for(int j = i; j < n-1; j++) {
if(preSum[j+1] - preSum[i+1] == oneIn3 && posNum[j+1] - posNum[i+1] > 0) res++;
}
}
}
System.out.println(res);
}
} def solve(): n = input() main_list = list(map(int, input().split())) total_sum = sum(main_list) if total_sum % 3 != 0: return 0 target = total_sum // 3 target2 = target * 2 next_choices = 0 current_sum = 0 result = 0 is_one = False is_two = 0 for index, num in enumerate(main_list): current_sum += num if num > 0: if not is_one: is_one = True else: is_two = next_choices if current_sum == target and is_one: next_choices += 1 # print(str(index) + "为 " + str(next_choices)) if current_sum == target2: result += is_two # print(str(index) + "加 " + str(next_choices)) return result print(solve()) # 这个才是python正解，那个排行里面的代码有问题
import sys n=int(input()) nums=list(map(int,input().split())) start=100000 end=0 total=sum(nums) all_t=total//3 sum1=[] sum3=[] count=0 for i in range(n): if nums[i]>0: start=min(i,start) end=max(i,end) front=sum(nums[:start]) after=total-sum(nums[:start]) for i in range(start,end): front+=nums[i] after-=nums[i] if front==all_t: sum1.append(i) if after==all_t: sum3.append(i+1) for i in range(len(sum1)): for k in range(len(sum3)): if sum1[i]<sum3[k]-1: count+=1 print(count)z 找到第一个正数和最后一个正数的位置，刀砍在这两点之间。遍历一边前后的和，记录和为总体/3的位置，再比较位置，前+1（为第二个数组留空）小于后则计次+1.但是过不了第21组，输出会多10，很纳闷
while 1: try: n = int(input()) ls = list(map(int,input().split())) if sum(ls)%3 != 0: print(0) break ans1 = sum(ls)//3 ans2 = ans1*2 sumls = [0] pls = [0] for i in range(n): sumls.append(sumls[-1]+ls[i]) if ls[i]>0: pls.append(pls[-1]+1) else: pls.append(pls[-1]) sumls = sumls[1:] pls = pls[1:] count = 0 ans1ind = [] ans2ind = [] for i in range(n): if sumls[i]==ans1 and pls[i]>0: ans1ind.append(i) elif sumls[i]==ans2 and pls[-1]-pls[i]>0: ans2ind.append(i) for x in ans1ind: for y in ans2ind: if x<y and pls[y]-pls[x]>0: count += 1 print(count) break except: break
#include <stdio.h>
int main() {
int n = 0;
scanf("%d", &n);
int a[200000] = {0};
int sum = 0;
int s[200000] = {0};//前缀和
int d1[200000] = {0};//1/3位置
int d2[200000] = {0};//2/3位置
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
sum += a[i];
s[i] = sum;
}
int result = 0;
if (sum != 0) {
if (sum % 3 == 0) {
int cnt1 = 0;
int cnt2 = 0;
for (int i = 0; i < n ; i++) {
if (s[i] == sum / 3) {
int flag = 0;//前1/3有正数
for (int j = 0; j <= i; j++) {
if (a[j] > 0) {
flag = 1;
break;
}
}
if (flag) {
d1[cnt1++] = i;
flag = 0;
}
}
}
for (int i = n - 1; i >= 0 ; i--) {
if (s[i] == 2 * sum / 3) {
int flag = 0;//后1/3有正数
for (int j = n - 1; j >= i; j--) {
if (a[j] > 0) {
flag = 1;
break;
}
}
if (flag) {
d2[cnt2++] = i;
flag = 0;
}
}
}
//结果
for (int i = 0; i < cnt1; i++) {
for (int j = 0; j < cnt2; j++) {
if (d2[j] > d1[i]) {
//中间1/3有正数
int flag = 0;
for (int k = d1[i]; k <= d2[j]; k++) {
if (a[k] > 0) {
flag = 1;
break;
}
}
if (flag) {
result++;
flag = 0;
}
}
}
}
}
}
// else if (sum == 0) {
// int cnt = 0;
// for (int i = 0; i < n ; i++) {
// if (s[i] == 0) cnt++;
// }
// cnt--;
// result = cnt * (cnt - 1) / 2;
// }
printf("%d", result);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> presum(n + 1, 0);
vector<int> poscount(n + 1, 0);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
presum[i + 1] = presum[i] + a;
poscount[i + 1] = poscount[i] + (a > 0 ? 1 : 0);
}
int sumtotal = presum[n];
if (sumtotal % 3 != 0 ) {
cout << 0 << endl;
return 0;
}
int sum = sumtotal / 3;
int count = 0, result = 0;
for (int i = 1; i <= n - 2; i++) {
int suma = presum[i];
if (sum != suma || poscount[i] <= 0)
continue;
for (int j = i + 1; j <= n - 1; j++) {
int sumb = presum[j] - presum[i];
int numb = poscount[j] - poscount[i];
if (sum != sumb || numb <= 0)
continue;
int sumc = sumtotal - presum[j];
int numc = poscount[n] - poscount[j];
if (sumc == sum && numc > 0)
result++;
}
}
cout << result << endl;
return 0;
}
问题信息
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
