灵异背包？ 思路 拿到这题先想想：给你一堆正整数，选若干个放背包里，要求总和是偶数，还要尽可能大。那第一反应是什么？ 全选不就最大了吗？ 对，先把所有正整数加起来。如果总和本身就是偶数，那直接就是答案，完事。 那要是总和是奇数呢？想想什么时候总和会是奇数——一定是奇数个奇数的贡献。那我们只要"去掉"一个奇数，总和的奇偶性就翻转成偶数了。为了让结果尽可能大，我们应该去掉哪个？当然是最小的那个奇数。 特殊情况 还有一种边界：如果所有数都是奇数且只有一个，总和是奇数，去掉它之后就是 0。题目说"一个数也不选，则背包和为 0"，而 0 是偶数，所以输出 0 就行...

小红背单词 思路 题意很直接：小红按顺序背单词，当她已经记住了 k 个单词时，一个新单词需要出现 k+1 次才能记住。问最终记住了多少个单词？ 那我们怎么模拟这个过程呢？ 关键观察：我们需要追踪两个东西——每个单词累计出现了几次，以及当前已经记住了几个单词（也就是"记忆门槛"）。 模拟过程：遍历输入序列，对每个单词：  如果已经记住了，跳过（不需要再背了） 否则把它的出现次数 +1 检查出现次数是否达到了门槛 total + 1（total 是当前已记住的单词数），达到了就记住它，total++  拿示例来走一遍：输入 you thank queue queue thank...

【模板】二维前缀和 思路 拿到这题，先想一个最朴素的做法：每次查询都遍历子矩阵求和，时间复杂度  每次查询，查询多了肯定超时。 那怎么优化？如果你学过一维前缀和，应该能想到——能不能把同样的思路推广到二维？ 答案是可以的。我们先来回忆一维前缀和怎么做的：s[i] = a[1] + a[2] + ... + a[i]，区间 [l, r] 的和就是 s[r] - s[l-1]。核心思想是预处理一次，查询 O(1)。 二维也一样。我们定义 s[i][j] 为从 (1,1) 到 (i,j) 这个矩形区域所有元素的和。那问题就变成两个： 第一个问题：怎么求 s[i][j]？ 画个图你就能看出来，s[i]...

交换到最大 思路 操作的本质是：选一个非首位、非零的数字，减 1 后和左邻交换。反复操作就是把一个数字  往左移  步，代价是值减少 ，到达后变成 （需要 ）。 关键观察：数字最大是 9，所以任何数字最多只能左移 9 步。 这意味着对于结果的第  位，候选人只来自剩余数字序列中的前 10 个元素。贪心策略很自然：  从左到右确定每一位 对当前位，查看剩余序列中前 10 个数字（偏移量 ） 选「到达值 」最大的那个放到当前位 从序列中删掉被选中的数字  当一个数字被移到前面时，它经过的那些数字会自然右移一位，维持相对顺序不变——这和链表中"删除节点"的效果完全一致。 用链表维...

BGN58: 空间跃迁 思路 有  个城市排成一条线，相邻城市之间有行走耗时。你从城市 1 出发要到城市 ，中途可以使用一次空间跃迁，半径为 ，也就是从城市  瞬间跳到城市  或 （不花时间）。 先想一下：如果不用跃迁，总耗时就是所有相邻城市之间耗时的总和。用了跃迁之后呢？从城市  跳到城市 ，相当于跳过了从  到  这一段连续  条边的费用。往回跳到  没有意义，因为我们最终还是要往前走。 所以问题就变成了：在  条边中，找一段连续  条边，使得它们的费用之和最大，然后从总费用中减去这个最大值。 这不就是经典的滑动窗口嘛！维护一个大小为  的窗口，滑过去找最大的窗口和就行了。 特殊情况： 时...

回文日期 思路 拿到这道题，先想想什么是回文日期？就是把日期写成 8 位数字 YYYYMMDD，从左读和从右读完全一样。 那关键问题来了：我们要怎么高效地找出所有回文日期？ 暴力做法是枚举区间里每一天，判断它是不是回文。但日期范围可能跨很多年，逐天枚举太慢了。 换个角度想——如果 YYYYMMDD 是回文，那 8 位数字满足：d1=d8, d2=d7, d3=d6, d4=d5。也就是说，只要知道了年份 YYYY，月份和日期就完全确定了：  月份 MM = d4d3（年份第 4 位 + 第 3 位） 日期 DD = d2d1（年份第 2 位 + 第 1 位）  比如年份 2011，d1=2, ...

小红的回文串 思路 题目给了三种操作：拆分（w→vv，m→nn）、轴对称（b↔d，p↔q）、翻转（b↔q，d↔p，n↔u），问经过若干次操作后能不能变成回文串。 先别急着写代码，想想这些操作到底在干嘛？ 第一步：找等价类。 把所有能互相转换的字符归成一组：  b、d、p、q 通过轴对称和翻转可以互相转换，它们是一类 n、u 通过翻转可以互换，它们是一类 其他字母各自独立  所以判断回文的时候，b 和 q 算"相同"，n 和 u 也算"相同"。 第二步：处理拆分操作。 w 可以拆成两个 v，m 可以拆成两个 n。注意这里改变了字符串长度！也就是说，w 可以...

【模板】差分 思路 拿到这题，最直接的想法是什么？每次操作都遍历 [l, r]，把每个元素加上 c。这样每次操作是 ，总共  次就是 ，数据一大肯定超时。 那有没有办法让每次"区间加"变成 ？ 这就要用到差分数组了。差分是前缀和的逆运算——前缀和是"求区间和"的利器，差分就是"区间修改"的利器。 什么是差分数组？ 定义差分数组 d[]，其中 d[i] = a[i] - a[i-1]（d[1] = a[1]）。差分数组有一个关键性质：对 d 做前缀和，就能还原出原数组 a。 差分怎么实现"区间加"？ 想给 a[l] ...

多项式输出 思路 拿到这题先想一下：给你一个一元 n 次多项式的系数，要你按标准数学格式输出，听起来简单对吧？但实际上坑还挺多的——符号怎么处理？系数为 1 或 -1 怎么办？系数为 0 的项要跳过？首项和后续项的符号规则不一样？ 别急，我们一个个捋清楚。 每一项需要考虑什么？ 对于第 i 个系数（对应次数为 n-i 的项），输出时要处理三件事：符号、系数绝对值、变量部分。 符号规则：  如果是首个非零项（首项）：正数不输出 +，负数输出 - 如果不是首项：正数前面加 +，负数前面加 -  系数绝对值规则：  如果当前项是常数项（次数为 0）：直接输出绝对值 如果当前项次数 >= 1 且...

九倍平方数 思路 拿到这道题先想想，一个数能被 9 整除有什么等价条件？没错，就是各位数字之和能被 9 整除。 题目允许我们把某一位数字 （）替换成 。那每个数字替换后会变成什么？  ，：替不替都一样 ：数字和多了 2 ：数字和多了 6（等价于 mod 9 减了 3） ：不能操作，只能保持原样  所以问题转化成：设原始数字和为 ，有  个 2 和  个 3，每个 2 可以选择给总和加 2，每个 3 可以选择给总和加 6。问是否存在 ， 使得： $$ 关键优化  最多只有 9 种取值（ 就能覆盖所有可能）， 同理。所以不管 、 多大，只需要枚举到  和  就够了。 算法流程：  遍历字符串统计数...

三角形取数(Hard Version) 思路 拿到题先理解这个"三角形"的结构：第  行有  个数，视觉上就是一个正三角形，每往下一行两边各多一个数。 从顶点出发，每一步可以往左下、正下、右下三个方向走。记左下走了  次、右下走了  次，要求最终 ，问路径上数字之和的最大值。 关键观察： 每一步的列变化量分别是 （左下不变列号，但因为下一行比当前行左边多了一个位置，相当于相对位移 ）、（正下）、（右下）。起始在第  行正中央，设"偏移量"为 ，那么到第  行时，列号 。 约束  就等价于最终列号满足 ，即 。 这个观察把问题彻底简化了——约束只作用在最后...

二进制数1 思路 题目非常直白：给一个非负整数，数一下它的二进制表示里有几个 1。 比如 3 的二进制是 11，有 2 个 1；65 的二进制是 1000001，也有 2 个 1。 怎么数？最经典的做法就是逐位检查——每次看最低位是不是 1，看完之后右移一位，直到整个数变成 0。具体来说：  用 n & 1 取出最低位（如果是 1 就计数 +1） 用 n >>= 1 把 n 右移一位，相当于"扔掉"已经看过的最低位 重复上面两步，直到 n 变成 0  其实还有一个更巧妙的做法：n & (n - 1) 能把 n 最低位的 1 变成 0。每做一次就消...

游游的排列构造 思路 这题要我们构造一个长度为 n 的排列，使得恰好有 k 个"好元素"（即前缀最大值），而且任意两个好元素不能相邻。 先想想好元素的性质：好元素就是从左往右扫的时候，每次遇到一个比之前所有值都大的位置。第一个位置一定是好元素（它自己就是前缀最大值）。 那怎么让好元素不相邻呢？最直觉的想法是把好元素放在偶数位置（第 1、3、5、... 个位置），这样相邻的两个好元素之间至少隔了一个非好元素。 具体构造方法：把 1 到 n 这些值分成 k 个块。  前 k-1 个块，每块 2 个数：第 i 个块（0-indexed）包含 ，我们先输出大的 （作为好元素），再输...

二进制不同位数 思路 题目很直白：给两个正整数，把它们转成二进制，从最低位对齐，数一下有多少个位置上的数字不一样。 这不就是异或（XOR）吗？异或的性质就是：相同为 0，不同为 1。所以 a ^ b 的结果里有几个 1，答案就是几。 那问题就变成了：怎么数一个数的二进制里有多少个 1？这就是经典的 popcount（population count）问题。 方法有很多：  最简单的：不断 x & (x - 1) 消掉最低位的 1，消了几次答案就是几 偷懒的：直接用语言内置函数。C++ 有 __builtin_popcountll()，Java 有 Long.bitCount()  举个...