手机网站开发工具6湖南送变电建设公司 网站

手机网站开发工具6,湖南送变电建设公司 网站,嵌入式软件开发平台有哪些,2023年最火简约装修全屋目录 题目#xff1a; 解题思路#xff1a; 代码#xff1a; 问题: 总结#xff1a; 5.花灯调整【算法赛】 - 蓝桥云课 题目#xff1a; 解题思路#xff1a; 从前往后统计其后缀和#xff0c;最后判断与当前位置翻转是否相同即可(偶数相当于没有翻转,奇数翻转) …目录题目解题思路代码问题:总结5.花灯调整【算法赛】 - 蓝桥云课题目解题思路从前往后统计其后缀和最后判断与当前位置翻转是否相同即可(偶数相当于没有翻转,奇数翻转)代码/*out *Stack Integer ArrayList String StringBuffer peek *Collections imports LinkedList offer return *empty polls offerLast pollFirst isEmpty *List Deque append length HashMap *return remove boolean continue charAt *toString static System println nextInt *Scanner System toCharArray contains */ import java.util.*; public class Main { static Scanner sc new Scanner(System.in); public static void main(String[] args) { int t1; while(t--!0){ slove(); } sc.close(); } public static void slove(){ int nsc.nextInt(),ksc.nextInt(); String ssc.next(); int [] pnew int[n]; for(int i0;ik;i){ p[sc.nextInt()-1]; } int[] ciShunew int[n]; ciShu[n-1]p[n-1]; for(int in-2;i0;i--){ ciShu[i]p[i]ciShu[i1]; } char[] tars.toCharArray(); for(int i0;itar.length;i){ int atar[i]-0; if(a%2!ciShu[i]%2){ System.out.println(No); return ; } } System.out.println(Yes); } }问题:总结【算法解析】后缀和解决 “花灯调整” 策略判定问题从问题本质到代码实现在算法竞赛中“操作叠加的状态判定”类问题是高频考点之一 —— 这类问题的核心是 “操作的顺序不影响最终状态仅与操作次数的奇偶性有关”。本文以 “花灯调整” 问题为例从问题拆解、核心规律、后缀和原理、代码实现等维度全面讲解如何用后缀和高效解决这类问题同时深入剖析代码的每一个细节帮助你掌握这类问题的通用解法。一、问题背景与需求拆解在开始代码分析前我们先彻底理解问题的规则与目标这是后续算法设计的基础。1.1 问题规则初始状态n盏花灯全部处于关闭状态用 0 表示游客操作每位游客选择一个 “前缀p”即从第 1 盏到第p盏灯的连续区间将该区间内所有花灯的状态反转0 变 11 变 0目标状态给定一个长度为n的 01 字符串S其中S[i]表示第i1盏灯的目标状态S[i]1表示亮S[i]0表示灭操作顺序游客可以任意调整操作的执行顺序问题目标判断是否存在一种操作顺序使得最终所有花灯的状态与目标串S完全一致。1.2 需求转化为数学模型我们的核心任务是验证 “游客操作对每盏灯的反转次数的奇偶性” 是否恰好等于 “从初始状态0到目标状态S[i]所需的反转次数的奇偶性”。原因很简单反转操作是幂等的反转偶数次等价于未反转反转奇数次等价于反转 1 次操作顺序不影响最终状态因为反转是 “叠加” 的先反转前 3 盏再反转前 5 盏与先反转前 5 盏再反转前 3 盏每盏灯的反转次数完全相同。二、核心规律反转次数的统计与后缀和的应用要解决问题首先需要明确每盏灯的反转次数如何计算—— 这是问题的关键突破口。2.1 每盏灯的反转次数的定义对于第i盏灯索引从 0 开始它的反转次数 选择了 “前缀p ≥ i1” 的游客数量之和因为游客选前缀p时会反转前p盏灯第i盏灯属于前p盏的条件是p ≥ i1。举个例子第 0 盏灯对应实际第 1 盏的反转次数 选了p≥1的游客数量之和第 2 盏灯对应实际第 3 盏的反转次数 选了p≥3的游客数量之和。2.2 为什么用 “后缀和” 统计反转次数统计 “选了p ≥ x的游客数量之和”本质是对 “游客选择的前缀数组” 做 “从 x 到末尾的累加”—— 这正是后缀和的典型应用场景前缀和从左到右累加统计 “前 x 项的和”后缀和从右到左累加统计 “从 x 到末尾的和”。因此我们可以用后缀和快速计算每盏灯的反转次数时间复杂度为O(n)完全满足n ≤ 10^5的规模要求。三、代码整体结构解析我们先从宏观上看代码的模块划分理解代码是如何对应问题需求的java运行import java.util.*;public class Main {static Scanner sc new Scanner(System.in);public static void main(String[] args) {int t1;while(t--!0){ // 兼容多组测试用例此处t1仅执行1次slove();}sc.close();}public static void slove(){// 1. 输入读取与初始化int nsc.nextInt(),ksc.nextInt();String ssc.next();int [] pnew int[n];for(int i0;ik;i){p[sc.nextInt()-1];}// 2. 计算每盏灯的反转次数后缀和int[] ciShunew int[n];ciShu[n-1]p[n-1];for(int in-2;i0;i--){ciShu[i]p[i]ciShu[i1];}// 3. 对比反转次数的奇偶性与目标状态char[] tars.toCharArray();for(int i0;itar.length;i){int atar[i]-0;if(a%2!ciShu[i]%2){System.out.println(No);return ;}}// 4. 输出结果System.out.println(Yes);}}代码分为 4 个核心模块输入读取模块将输入的 “前缀选择” 统计到数组中后缀和计算模块用后缀和得到每盏灯的反转次数奇偶性对比模块验证反转次数的奇偶性是否匹配目标状态输出模块根据验证结果输出 “Yes” 或 “No”。四、输入读取模块结构化存储游客的选择输入处理是算法题的基础结构化存储能避免后续逻辑中 “变量混淆” 的问题我们详细解析这部分代码的设计思路。4.1 输入的对应关系问题的输入分为三部分第一行n花灯数、k游客数第二行目标串S长度为n的 01 字符串第三行k个整数p_1~p_k每位游客选择的前缀。4.2 代码的输入处理逻辑java运行// 读取n和kint nsc.nextInt(),ksc.nextInt();// 读取目标串sString ssc.next();// 定义数组pp[x]表示“选择了前缀x1的游客数量”x是0-based索引int [] pnew int[n];for(int i0;ik;i){// 游客输入的p是1-based比如选前缀3对应实际第3盏转为0-based索引int choose sc.nextInt() - 1;p[choose];}关键细节游客输入的 “前缀p” 是1-based比如选 “前缀 3” 表示前 3 盏灯而代码中数组是0-based索引 0 对应实际第 1 盏因此需要sc.nextInt() - 1将输入转为数组索引数组p的含义p[x]表示 “选择了前缀x1的游客数量”比如p[2]表示选了前缀 3 的游客数。4.3 样例输入的存储结果以样例输入为例plaintext样例输入5 3100104 3 1n5k3目标串s10010游客选择的前缀是 4、3、1转为 0-based 索引是 3、2、0数组p的结果p[0]1选前缀 1 的游客数、p[2]1选前缀 3 的游客数、p[3]1选前缀 4 的游客数其余为 0 → p [1,0,1,1,0]。五、后缀和计算模块核心逻辑的实现这是代码的灵魂部分 —— 用后缀和计算每盏灯的反转次数我们从原理、代码、样例验证三个维度详细解析。5.1 后缀和的原理回顾后缀和的定义是对于数组arr后缀和数组suffixSum满足suffixSum[i] arr[i] suffixSum[i1]从右到左计算。对于我们的问题数组p存储了 “每个前缀被选择的次数”因此第i盏灯0-based的反转次数 p[i] p[i1] ... p[n-1] → 这正是后缀和数组suffixSum[i]的值。5.2 后缀和的代码实现java运行// 定义ciShu数组ciShu[i]表示第i盏灯的反转次数int[] ciShunew int[n];// 初始化最后一盏灯的反转次数只有选了前缀n的游客会影响它ciShu[n-1]p[n-1];// 从倒数第二盏灯往前计算后缀和for(int in-2;i0;i--){ciShu[i] p[i] ciShu[i1];}代码逻辑拆解最后一盏灯in-1的反转次数 选了前缀n的游客数即p[n-1]第i盏灯的反转次数 选了前缀i1的游客数p[i] 第i1盏灯的反转次数因为选前缀≥i2的游客也会影响第i盏灯。5.3 样例的后缀和计算结果以样例的p [1,0,1,1,0]为例ciShu[4] p[4] 0最后一盏灯选前缀 5 的游客数为 0ciShu[3] p[3] ciShu[4] 1 0 1第 4 盏灯选前缀 4 的游客数 第 5 盏的反转次数ciShu[2] p[2] ciShu[3] 1 1 2第 3 盏灯选前缀 3 的游客数 第 4 盏的反转次数ciShu[1] p[1] ciShu[2] 0 2 2第 2 盏灯选前缀 2 的游客数 第 3 盏的反转次数ciShu[0] p[0] ciShu[1] 1 2 3第 1 盏灯选前缀 1 的游客数 第 2 盏的反转次数最终ciShu数组每盏灯的反转次数为[3,2,2,1,0]。六、奇偶性对比模块判定是否可行的核心这部分代码的作用是验证 “每盏灯的反转次数的奇偶性” 是否与 “目标状态所需的反转次数的奇偶性” 一致 —— 这是问题的最终判定条件。6.1 目标状态与反转次数的奇偶性初始状态下所有灯都是 0要达到目标状态S[i]0 或 1若S[i] 0不需要反转或反转偶数次最终状态为 0若S[i] 1需要反转奇数次最终状态为 1。因此目标状态所需的反转次数的奇偶性 S[i] - 0将字符转为整数 0 或 1。6.2 代码的奇偶性对比逻辑java运行// 将目标串转为字符数组方便逐位访问char[] tar s.toCharArray();// 遍历每盏灯for(int i0;itar.length;i){// 将字符0/1转为整数0/1得到目标所需的奇偶性int targetParity tar[i] - 0;// 计算当前灯反转次数的奇偶性int actualParity ciShu[i] % 2;// 若奇偶性不匹配直接输出No并返回if(targetParity ! actualParity){System.out.println(No);return ;}}6.3 样例的奇偶性对比验证样例中目标串s10010 → tar [1,0,0,1,0]目标所需的奇偶性[1,0,0,1,0]实际反转次数的奇偶性ciShu % 2[3%21, 2%20, 2%20, 1%21, 0%20]两者完全一致因此输出 “Yes”与样例结果匹配。七、边界情况与性能分析在算法题中边界处理和性能是衡量代码质量的关键指标我们分析代码在这两方面的表现。7.1 边界情况的处理代码能正确处理以下边界情况所有灯都是 0目标所需的奇偶性全为 0只需验证实际反转次数全为偶数所有灯都是 1目标所需的奇偶性全为 1只需验证实际反转次数全为奇数游客数量为 0此时所有灯的反转次数为 0只需目标串全为 0游客选择的前缀全为 n此时所有灯的反转次数等于游客数量只需验证所有灯的目标奇偶性相同。7.2 性能分析代码的时间复杂度为O(n k)输入处理O(k)遍历 k 个游客的选择后缀和计算O(n)遍历 n 盏灯奇偶性对比O(n)遍历 n 盏灯。空间复杂度为O(n)数组p和ciShu的空间都是O(n)完全满足n ≤ 10^5的题目限制。八、代码的优化与拓展虽然当前代码已经能正确解决问题但我们可以从可读性、扩展性角度做一些优化让代码更通用。8.1 变量名的语义化优化原代码中ciShu次数的变量名不够直观可优化为reverseCount反转次数p可优化为prefixChooseCount前缀选择次数java运行// 优化后int[] prefixChooseCount new int[n];for(int i0;ik;i){int choose sc.nextInt() - 1;prefixChooseCount[choose];}int[] reverseCount new int[n];reverseCount[n-1] prefixChooseCount[n-1];for(int in-2;i0;i--){reverseCount[i] prefixChooseCount[i] reverseCount[i1];}8.2 兼容多组测试用例原代码中while(t--!0)的t1仅支持单组测试用例。若要支持多组只需将t改为sc.nextInt()java运行public static void main(String[] args) {int t sc.nextInt(); // 读取测试用例数while(t--!0){slove();}sc.close();}8.3 拓展处理 “反转区间” 的通用问题这类 “操作区间、统计每点的操作次数” 的问题都可以用差分 前缀和的方式解决后缀和是前缀和的一种变体。例如若操作是 “反转区间[l, r]”可以用差分数组记录区间的变化再用前缀和得到每点的操作次数。九、总结本文以 “花灯调整” 问题为例详细讲解了后缀和在 “操作叠加的状态判定” 类问题中的应用问题拆解将 “状态匹配” 转化为 “反转次数的奇偶性匹配”核心规律操作顺序不影响最终状态仅与操作次数的奇偶性有关算法选择用后缀和快速统计每盏灯的反转次数时间复杂度O(n)代码实现输入处理→后缀和计算→奇偶性对比→输出结果模块清晰。这类问题的通用解题步骤是分析操作对每个元素的影响用前缀和 / 后缀和 / 差分统计每个元素的操作次数验证操作次数的奇偶性是否匹配目标状态。掌握这一思路后你可以轻松解决类似的 “开关灯”“翻转字符串” 等问题 —— 核心是抓住 “操作的幂等性” 和 “区间统计的前缀和 / 后缀和技巧”。