本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderE - Balanced Groups in Tournament Partition【题目描述】2 N 2^N2Nstudents are standing in a row from left to right, and each student is wearing either a red hat or a white hat. The hat colors of the students are represented by a stringS SSof length2 N 2^N2N. For thei ii-th student from the left, if thei ii-th character ofS SSis0, they are wearing a red hat, and if it is1, they are wearing a white hat.Takahashi, in preparation for the sports festival, can perform the following operationat most once:Choose an integerl ll(1 ≤ l ≤ 2 N − K 1 1 \leq l \leq 2^N - K 11≤l≤2N−K1), and rearrange theK KKconsecutive students from thel ll-th to the( l K − 1 ) (lK-1)(lK−1)-th from the left. As a result of the rearrangement, all students with red hats within the interval are placed consecutively on the left side of the interval, and all students with white hats are placed consecutively on the right side of the interval. The positions of students outside the interval do not change.After the operation (or as-is if no operation is performed), the students are recursively divided into groups according to the following rules:Initially, all students from the1 11-st to the2 N 2^N2N-th from the left form one group.A group with2 22or more people is split into two groups: one consisting of the first half of students (counted from the left) and one consisting of the second half.This splitting is repeated until each group contains exactly1 11person.Consider all groups that appear during this process (including the initial whole group, groups at each intermediate stage, and the final single-person groups — a total of2 N 1 − 1 2^{N1} - 12N1−1groups). A group is called a “balanced group” if the number of students with red hats and the number of students with white hats within the group are equal. Note that a single-person group cannot satisfy this condition, so it is never a balanced group.Find the maximum possible number of balanced groups when Takahashi optimally chooses whether to perform the operation and the position of the interval.有2 N 2^N2N名学生从左到右站成一排每名学生戴着一顶红帽子或白帽子。学生的帽子颜色由一个长度为2 N 2^N2N的字符串S SS表示。对于从左数第i ii名学生如果S SS的第i ii个字符是0则他戴红帽子如果是1则戴白帽子。高桥为准备体育节最多可以进行一次如下操作选择一个整数l ll1 ≤ l ≤ 2 N − K 1 1 \leq l \leq 2^N - K 11≤l≤2N−K1并重新排列从第l ll名到第( l K − 1 ) (lK-1)(lK−1)名学生的连续K KK名学生。重新排列后区间内所有戴红帽子的学生被连续地放置在区间的左侧所有戴白帽子的学生被连续地放置在区间的右侧。区间外的学生位置不变。操作后或不进行操作学生按照以下规则递归地分组初始时从左数第1 11名到第2 N 2^N2N名学生组成一个组。一个包含2 22人以上的组被分割成两个组一个由前一半学生从左数组成另一个由后一半学生组成。重复此分割直到每个组恰好包含1 11人。考虑在这个过程中出现的所有组包括初始的整个组、每个中间阶段的组以及最终的单人组——总共2 N 1 − 1 2^{N1} - 12N1−1个组。如果一个组内戴红帽子的学生数量和戴白帽子的学生数量相等则该组被称为“平衡组”。注意单人组不可能满足此条件因此永远不会是平衡组。求当高桥最优地选择是否进行操作以及区间位置时可能得到的最大平衡组数量。【输入】N NNK KKS SSThe first line contains the integerN NN, which represents the parameter for the number of students, and the integerK KK, which represents the length of the interval to be rearranged in the operation, separated by a space. The second line contains the stringS SSof length2 N 2^N2Nrepresenting the hat color of each student.【输出】Output the maximum number of balanced groups as a single integer.【输入样例】2 2 0110【输出样例】3【核心思想】问题分析给定长度为2 N 2^N2N的二进制串S SS0表示红帽子1表示白帽子最多进行一次操作选择长度为K KK的区间将区间内所有0移到左边1移到右边。然后将整个序列递归二分分组完全二叉树结构求平衡组0和1数量相等的最大数量。这是一个线段树 滑动窗口问题关键在于利用线段树维护区间和并通过滑动窗口枚举操作位置来最大化平衡组数量。算法选择线段树Segment Tree维护每个区间的和节点值等于其子树叶子节点之和即区间内1的数量滑动窗口Sliding Window枚举所有可能的长度为K KK的操作区间模拟操作后的效果完美二叉树性质递归分组形成完全二叉树线段树节点天然对应分组结构。第d dd层从叶子向上的节点对应大小为2 d 2^d2d的组层级计数val从 1 开始每层左移一位1→2→4→8…表示该层节点应包含的叶子数。若节点值等于v a l / 2 val/2val/2即一半0一半1则为平衡组关键步骤初始化读取N NN二进制位数、K KK窗口大小、S SS二进制串siz 1 N线段树大小为2 N 2^N2N初始化线段树根据S SS设置叶子节点0或1acc统计当前平衡组数量处理初始状态统计前K KK个位置中1的数量cnt模拟操作将前c n t cntcnt个位置设为1后K − c n t K-cntK−cnt个位置设为0res max(res, acc)更新最大平衡组数滑动窗口枚举操作位置窗口从位置K 1 K1K1滑动到2 N 2^N2N移出窗口左端位置i − K i-Ki−K若 $S[i-K] $1且窗口未满需要恢复该位置为1并调整窗口内1的分布移入窗口右端位置i ii若 $S[i] $0且窗口非空需要将该位置设为0并调整窗口内1的分布更新cnt窗口内1的数量res max(res, acc)更新最大平衡组数输出答案res时间/空间复杂度时间复杂度O ( 2 N × N ) O(2^N \times N)O(2N×N)共有O ( 2 N ) O(2^N)O(2N)个窗口位置每次更新沿树高O ( N ) O(N)O(N)空间复杂度O ( 2 N ) O(2^N)O(2N)线段树需要2 × 2 N 2 \times 2^N2×2N的空间线段树 滑动窗口的核心思想完美二叉树与线段树的对应递归二分分组天然形成完全二叉树线段树的每个节点正好对应一个组。通过维护区间和可以快速判断每个组是否为平衡组层级条件判断对于大小为2 d 2^d2d的组第d dd层平衡条件为节点值1的数量等于2 d − 1 2^{d-1}2d−1即一半0一半1。val每层翻倍通过比较tr[i] val/2判断平衡滑动窗口模拟操作操作的本质是将区间内所有0移到左边1移到右边。这等价于将区间内的1集中到右侧。通过滑动窗口和单点更新可以高效模拟这一操作对所有组的影响增量更新维护平衡组数每次单点更新时自底向上更新线段树同时维护acc。若某节点在更新前后跨越了平衡条件则相应增减acc适用于完全二叉树结构、区间操作模拟、组合优化类问题【算法标签】#线段树【代码详解】#includebits/stdc.husingnamespacestd;constintN1205;intn,m,siz;// n: 二进制位数m: 窗口大小siz: 线段树大小string s;// 输入字符串inttr[N1];// 线段树数组intacc;// 满足条件的子集数量voidupdate(inti,intx)// 更新线段树{i--;tr[i|siz]x;// 定位到叶子节点intval1;// 初始值while(i1)// 向上更新{if(tr[i]val)// 如果当前节点原本满足条件acc--;// 减少计数tr[i]tr[i1]tr[i1|1];// 更新节点值if(tr[i]val)// 如果更新后满足条件acc;// 增加计数val1;// 更新val}}intmain(){cinnm;// 输入位数和窗口大小cins;// 输入字符串s s;// 在字符串前加空格使下标从1开始siz1n;// 计算线段树大小intres0,cnt0;// 结果和当前窗口内1的数量for(inti1;isiz;i)// 初始化{if(s[i]0)// 如果为0continue;update(i,1);// 更新为1if(im)// 如果在窗口内cnt;// 计数}resmax(res,acc);// 更新结果for(inti1;im-cnt;i)// 调整前m个位置update(i,0);for(intim-cnt1;im;i)// 调整前m个位置update(i,1);resmax(res,acc);// 更新结果for(intim1;isiz;i)// 滑动窗口{if(s[i-m]1cnt!m)// 如果移出的为1且窗口未满{update(i-m,1);// 更新移出位置update(i-cnt,0);// 更新移入位置}if(s[i-m]1)// 如果移出的为1cnt--;// 计数减少if(s[i]0cnt!0)// 如果移入的为0且窗口不为空{update(i-cnt,0);// 更新移入位置update(i,1);// 更新移出位置}if(s[i]1)// 如果移入的为1cnt;// 计数增加resmax(res,acc);// 更新结果}coutresendl;// 输出结果return0;}【运行结果】2 2 0110 3