hd2058区间和

发布时间:2026/8/19 15:45:09
hd2058区间和 题目为什么计算起始数的时候sublen要先减1这里的(子序列长度 - 1)本质是为了让 “中间数” 能对称地算出起始数—— 不管子序列长度是奇数还是偶数都能用同一个公式算不用分情况。例子 1子序列长度是「奇数」比如长度 3假设目标和 6子序列是1,2,3和为 6例子 1符合条件的偶数长度sub_len4目标和 10步骤 1算余数10 ÷ 4 2余数 2也就是10 % 4 2。步骤 2验证 “余数 ×2 子序列长度”2 × 2 4正好等于子序列长度 4 → 符合条件。步骤 3算这个子序列的和验证是否等于 10根据公式算出子序列例子 2不符合条件的偶数长度sub_len2目标和 10步骤 1算余数10 ÷ 2 5余数 0也就是10 % 2 0。步骤 2验证 “余数 ×2 子序列长度”0 × 2 0 ≠ 2 → 不符合条件。步骤 3算这个子序列的和验证是否等于 10根据公式算出子序列再举一个例子sub_len6目标和 21步骤 1算余数21 ÷ 6 3余数 321 % 6 3。步骤 2验证 “余数 ×2 子序列长度”3 × 2 6 → 符合条件。步骤 3算和验证大白话解释为什么 “余数 ×2 长度” 就对不用懂数学推导记住这个规律就行当子序列长度是偶数时目标和可以拆成「中间数 × 长度 余数」只有余数刚好是长度的一半时也就是余数 ×2 长度才能把多出来的余数 “平分” 到每个数上让总和刚好等于目标和。比如 sub_len4余数 2正好是 4 的一半总结两边乘 2 就得到余数 × 2 L也就是remainder * 2 sub_len。子序列长度 3中间数 6÷32正好是数列正中间的数要从 “中间数 2” 回到 “起始数 1”需要往左走「(3-1)/21」步所以起始数 2 - 1 1完全正确例子 2子序列长度是「偶数」比如长度 4假设目标和 10子序列是1,2,3,4和为 10子序列长度 4中间数 10÷42整数除法取商要从 “中间数 2” 回到 “起始数 1”需要往左走「(4-1)/21」步因为 (4-1)33÷21整数除法只取商所以起始数 2 - 1 1完全正确。#include stdio.h int main() { // 变量命名更直观 // max_num: 原数列的上限1~max_num // target_sum: 目标和 // sub_len: 连续子序列的长度 int max_num, target_sum, sub_len; // 循环读取输入直到 max_num 和 target_sum 都为 0 时退出 // 用更易读的方式替代逗号表达式 while (1) { // 读取输入 scanf(%d%d, max_num, target_sum); // 终止条件两个数都为 0 if (max_num 0 target_sum 0) { break; } // 第一步找到子序列长度的最大值保证起始数0 // sub_len从1开始递增直到起始数≤0时停止 for (sub_len 1; ; sub_len) { // 计算子序列的起始数 int start_num target_sum / sub_len - (sub_len - 1) / 2; // 起始数≤0时当前sub_len超出有效范围停止循环 if (start_num 0) { break; } } // 第二步从最大有效长度倒序遍历查找符合条件的子序列 // 先把超出范围的sub_len减1得到最大有效长度 sub_len--; while (sub_len 1) { // 计算起始数和结束数 int start_num target_sum / sub_len - (sub_len - 1) / 2; int end_num target_sum / sub_len sub_len / 2; // 边界检查结束数不能超过原数列的上限 if (end_num max_num) { sub_len--; continue; } // 计算 target_sum 除以 sub_len 的余数 int remainder target_sum % sub_len; // 情况1子序列长度为偶数且满足余数*2 长度和为target_sum if (sub_len % 2 0 remainder * 2 sub_len) { printf([%d,%d]\n, start_num, end_num); } // 情况2子序列长度为奇数且能被target_sum整除和为target_sum if (sub_len % 2 1 remainder 0) { printf([%d,%d]\n, start_num, end_num); } // 长度减1继续检查 sub_len--; } // 每组测试用例后输出空行 printf(\n); } return 0; }余数*2 sub_len怎么得到的这个等式是偶数长度连续序列和为target_sum的核心数学推导我用最通俗的方式一步步拆解你看完就能明白第一步先明确偶数长度序列的求和公式假设连续序列长度为sub_len偶数比如长度 4序列a, a1, a2, a3求和a (a1) (a2) (a3) 4a 6 2×(2a3)通用公式长度为偶数L连续序列和 L × 起始数 (012...(L-1))L×a L×(L-1)/2L × (a (L-1)/2)第二步结合目标和target_sum推导我们要求L × (a (L-1)/2) target_sum变形得a (L-1)/2 target_sum / L这里a是正整数(L-1)/2是x.5形式因为 L 是偶数L-1 是奇数所以a x.5的结果必须是y.5形式整数 0.5。也就是说target_sum / L必须等于y.5比如 2.5、4.5 等。第三步把y.5转化为余数形式target_sum / L y.5等价于target_sum L × y L/2两边乘 L我们知道除法的基本关系target_sum L × 商 余数余数 L对比上面的等式商 y余数 L/2情况二sublen为偶数没搞懂别着急情况二里 “sub_len 为偶数” 的判断是最绕的一步我完全不用数学公式只靠举例子 算总和的方式把这一步拆得明明白白保证你一看就懂。先明确我们要验证什么情况二的核心是当子序列长度是偶数时只有满足「余数 ×2 子序列长度」这个子序列的和才等于目标和。