HJ喜欢切数组的红

两个解法解法1提前预处理用空间换时间importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);if(!in.hasNextInt())return;intnin.nextInt();long[]redsnewlong[n];// 元素可能很大用 long 防止溢出longtotalSum0;for(inti0;in;i){reds[i]in.nextLong();totalSumreds[i];}// 1. 不能被3整除绝对无法平分if(totalSum%3!0){System.out.println(0);return;}longtargettotalSum/3;// 2. 预处理 nextPos 数组nextPos[i] 表示从索引 i 开始右侧第一个正数的位置int[]nextPosnewint[n];intlastPositiveIndexn;// 用 n 代表无穷大没找到for(intin-1;i0;i--){if(reds[i]0){lastPositiveIndexi;}nextPos[i]lastPositiveIndex;}// 3. 预处理 suffixCount 数组统计合法的第三段数量// suffixCount[j] 表示以 j 作为第三段的起点有多少种合法方案int[]suffixCountnewint[n1];longcurrentSuffixSum0;booleansuffixHasPosfalse;// 从右向左遍历j 最小到 2给第一段和第二段各留至少1个位置for(intjn-1;j2;j--){currentSuffixSumreds[j];if(reds[j]0)suffixHasPostrue;// 继承后面的数量suffixCount[j]suffixCount[j1];// 如果当前后缀满足条件和为 target 且有正数数量 1if(currentSuffixSumtargetsuffixHasPos){suffixCount[j];}}// 4. 从左向右寻找第一段并累加答案longans0;longcurrentPrefixSum0;booleanprefixHasPosfalse;// 第一段终点 i 最大到 n-3for(inti0;in-3;i){currentPrefixSumreds[i];if(reds[i]0)prefixHasPostrue;// 如果找到合法的第一段if(currentPrefixSumtargetprefixHasPos){// 中间段从 i1 开始找它里面的第一个正数位置 pintpnextPos[i1];// 如果中间段能找到正数且不是数组最后一个元素要给第三段留位置if(pn-1){// 第三段的起点 j 必须在 p 之后 (即 j p 1)// 这样才能保证索引为 p 的那个正数稳稳地落在了中间段里anssuffixCount[p1];}}}System.out.println(ans);}}解法2暴力验证法importjava.util.*;classSolution{publicvoidredCutToTreeParts(int[]reds,intnum){if(redsnull||num3){System.out.print(0);return;}longsum0;for(intred:reds){sumred;}if(sum%3!0){System.out.print(0);return;}longtargetsum/3;// 前缀和与前缀正数计数long[]prefixSumnewlong[num1];int[]prefixPositiveCountnewint[num1];for(inti0;inum;i){prefixSum[i1]prefixSum[i]reds[i];prefixPositiveCount[i1]prefixPositiveCount[i](reds[i]0?1:0);}// 获取包含正数的有效左切点ArrayListint[]leftCutsnewArrayList();// [index, positive_count_in_segment]for(inti0;inum-2;i){if(prefixSum[i1]target){intposCountprefixPositiveCount[i1];if((target0posCount0)||(target!0posCount0)){leftCuts.add(newint[]{i,posCount});}}}// 获取包含正数的有效右切点ArrayListint[]rightCutsnewArrayList();// [index, positive_count_from_right]for(intinum-1;i1;i--){if(prefixSum[num]-prefixSum[i]target){intposCountprefixPositiveCount[num]-prefixPositiveCount[i];if((target0posCount0)||(target!0posCount0)){rightCuts.add(newint[]{i,posCount});}}}Collections.reverse(rightCuts);longcount0;for(int[]leftData:leftCuts){intleftIdleftData[0];intleftPosCountleftData[1];// 二分查找满足 rightId leftId 1 的起始位置intl_idx0,r_idxrightCuts.size();while(l_idxr_idx){intmid(l_idxr_idx)/2;if(rightCuts.get(mid)[0]leftId1){r_idxmid;}else{l_idxmid1;}}// 检查从 l_idx 开始的每个 rightId验证中间段是否包含正数for(intkl_idx;krightCuts.size();k){intrightIdrightCuts.get(k)[0];// 中间段 [leftId 1, rightId - 1] 的正数计数intmiddlePosCountprefixPositiveCount[rightId]-prefixPositiveCount[leftId1];if(middlePosCount0){count;}}}System.out.print(count);}}publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();int[]redsnewint[n];for(inti0;in;i){reds[i]in.nextInt();}SolutionsolutionnewSolution();solution.redCutToTreeParts(reds,n);in.close();}}