BGN83 完美异或 思路 题目要求构造一个长度为  的非递减数组，使得所有元素的异或和是  的因子。如果无法构造就输出 -1。 先想想，有没有什么万能的构造方法？ 关键观察 我们可以用大量的 1 来"填充"数组，然后在末尾放一个较大的数来调整异或和。 具体来说：前  个元素都是 1，最后一个元素设为 。数组自然是非递减的（只要 ）。 那异或和是多少呢？ 个 1 异或在一起：  如果  是偶数（即  是奇数）：异或和为 0，总异或和就是  如果  是奇数（即  是偶数）：异或和为 1，总异或和就是   分情况构造  为奇数时： 前面  个 1 异或得 0，令 ，总异或和 ，...

小红的整数配对 思路 题意：给 n 个整数和一个阈值 m，每次可以选两个还没被选过的数配对，条件是两数之差的绝对值不超过 m，配对得分为两数之积。问最大总得分是多少。 贪心策略很直觉——大数配大数，收益最高。具体怎么做？  排序。排完序后，能配对的数一定是"挨得近"的，因为差值不超过 m。 从右往左贪心配对。从最大的数开始看，如果它和前一个数的差 <= m，就把它俩配上（乘积最大化），然后跳过这两个继续往左看；如果差值 > m，说明当前这个数找不到合法的配对伙伴（左边的只会更小，差值只会更大），只能放弃它，往左移一位。  为什么从右往左贪心是对的？排序后，最大的...

BGN41 判断质数 思路 题目很直白：给你一个正整数 ，判断它是不是质数，是的话输出 Yes，否则输出 No。 那什么是质数？大于 1 的整数，且只能被 1 和自身整除。 怎么判断呢？最朴素的方法是从 2 遍历到 ，看有没有能整除  的数。但这样太慢了，有没有更快的办法？ 试除法优化 关键观察：如果  有一个因子 （），那  也是  的因子。 和  这两个因子，至少有一个 。 所以我们只需要从 2 枚举到  就够了。如果在这个范围内没有找到任何因子， 就是质数。 注意数据范围 这道题有个小坑：输入数据可能超过 int 的范围（测试用例中出现了 274876858367 这样的大数）。所以 C...

被打乱的异或和 思路 题目说的是：有一个长度为  的原始数组，把所有元素异或起来得到 ，然后把  追加到数组末尾变成长度  的数组，再随机打乱顺序给你。问原始数组的异或值是多少。 乍一看好像得想办法把  从打乱的数组里"找出来"，但仔细想想会发现一个关键性质： 打乱后数组所有  个元素的异或值一定是 0。 为什么？设原始数组为 ，那么 。打乱后的数组包含这  个元素加上 ，全部异或起来就是： $$ 这意味着什么呢？对于数组中的任意一个元素 ，把它当作被追加的那个 ，剩下的  个元素的异或值恰好就是  本身（因为总异或是 0，去掉  后异或值就是 ）。 所以每种拆分方式都是合...

BGN27 谐距下标对 思路 先想一个问题：什么叫"谐距"？题目说的是下标 ，满足 ，也就是两个元素的"值的差"恰好等于"下标的差"。你可以理解成：如果把数组画在坐标系上，这两个点刚好在同一条斜率为 1 的直线上。 那怎么找这样的下标对呢？暴力枚举所有  肯定能做，但  在数据量大的时候就扛不住了。 关键转化 把条件  移项一下： $$ 发现了吗？只要定义 ，那问题就变成了：数组  中有多少对相等的元素？ 这就是经典的"计数相同元素对数"问题了。用哈希表统计每个值出现的次数 ，每个值贡献  对，加起来就是答案。 举...

最长异或公共子段 思路 题目给了两个不同的非负整数 ，分别生成两个无限序列  和 （）。要求找到最长的公共连续子段长度 。 "公共连续子段"意味着存在  使得对所有 ，有 ，即： $$ 两边同时异或，等价于： $$ 其中  是个固定值。 关键转化 问题变成：找最大的 ，使得存在 ，对连续  个  值都有 。 取 ，设 ，则条件变为  对连续  个  成立。 当我们选  时，条件变成 。什么时候  呢？恰好是  和  没有公共的 1-bit，即  的时候。 所以问题进一步简化为：最长的连续整数段 ，满足每个数与  按位与为 0。 lowbit 就是答案 设  的最低位的 1 ...

BGN77 构造数列 思路 这题让你构造一个长度为  的数组，前一半是互不相同的偶数，后一半是互不相同的奇数，且两半的和相等。 先想一个关键问题：前半部分的和与后半部分的和，奇偶性能对上吗？ 取最小的  个偶数和奇数来分析：   个偶数的和一定是偶数（偶数之和必为偶数）  个奇数的和呢？ 个奇数相加，当  为偶数时和为偶数， 为奇数时和为奇数  不管你怎么换数字，只要保持偶数/奇数的身份不变，奇偶性就不会变。所以：  当  是奇数时（即 ），偶数和是偶数、奇数和是奇数，两者永远不可能相等，输出 NO 当  是偶数时（即 ），两边的和奇偶性相同，有可能构造出来  那  呢？，是奇数情况，直接 N...

植树节 思路 题目在说什么？有  个志愿者，每人负责给编号  的树苗各浇一次水，问被浇水次数最多的树苗被浇了多少次。 这是经典的差分数组问题。对区间  全部加 1，等价于在差分数组上 ++ 和 --。所有操作做完后，对差分数组求前缀和就能还原每个位置的实际值，取最大值即可。 复杂度  时间：，其中  是坐标上界（） 空间：  代码    C++   Java   Python3   JavaScript   #include <bits/stdc++.h> using namespace std; int main(){ int n; scanf("%d", &...

BGN75 构造三角形 思路 题目给了四个正整数 ，要我们从三个区间 、、 各取一个数 ，使得它们能构成一个非退化三角形。 三角形的核心条件就是任意两边之和大于第三边。由于 （因为区间本身就是递增的），最紧的约束一定是 。 那怎么让  最容易满足呢？很自然的想法：让  和  尽量大， 尽量小。   最大取   最大取   最小取   所以直接取 。 验证一下三角形条件：  ，因为 ，所以  恒成立 ✓  ✓  ✓（同第一条）  三个条件全部满足，而且不需要任何特判。题目保证有解，我们的构造也确实总是合法的，完美！ 构造题就是这样，找到一个巧妙的取值方式，比暴力枚举优雅多了。 代码    C++...

染色 思路 题目说的是：有  个油漆桶，初始都是白色。进行  次操作，每次往区间  的油漆桶里加一种颜料（1=黄色，2=蓝色，3=红色）。颜料混合规则：黄+蓝=绿，黄+红=橙，蓝+红=紫，三色全加=棕。问最终有多少桶是绿色的。 绿色的条件是什么？有黄、有蓝、没有红。 这是一个典型的差分数组问题。区间加操作用差分数组来做是最自然的。 关键在于：三种颜料是独立的，每种颜料只需要知道"有没有被加过"。所以我们对三种颜料分别维护一个差分数组。 具体做法：  开三个差分数组 ，分别对应黄、蓝、红三种颜料。 对于每次操作 ，在对应的差分数组上做 ++，--。 最后扫一遍，对三个差分数组...

变幻莫测 思路 拿到这道题先别急，想一下：两种操作——交换 (X, Y) -> (Y, X) 和变换 (X, Y) -> (X+Y, X-Y)，要让 X 等于 Y，什么情况下做得到？ 关键观察：变换操作 (X, Y) -> (X+Y, X-Y) 之后，新的两个数的乘积是 (X+Y)(X-Y) = X^2 - Y^2。如果 X != Y 且 X != -Y 且 XY != 0，那变换之后两个数都不为零，且绝对值也不相等。交换操作只是翻转顺序，不改变这个性质。 所以不管你怎么折腾，只要初始 X 和 Y 既不相等、也不互为相反数、也没有谁是零，那就永远凑不出 X = Y，直接输出 ...

特殊的科学计数法 思路 拿到这道题，先想一下要干什么？把一个可能非常大的正整数转成科学计数法 a.b*10^c，小数点后只保留一位，而且要四舍五入。 那具体怎么拆？假设输入是字符串 s（因为数字可能很大，不能用 int/long 存），那么：  a 就是第一个字符（首位数字） b 就是第二个字符（第一位小数），如果只有一位数就是 0 四舍五入看第三个字符（第二位小数），>=5 就进位 c = 字符串长度 - 1  唯一需要注意的坑：进位连锁 比如输入 995，表示 9.95  10^2。第三位是 5，要进位，b 从 9 变成 10，又要往前进：a 从 9 变成 10。这时候就变成了 1....

数颜色 思路 这题有啥好想的？给你一个只含 R、G、B 三种字符的字符串，分别数一下各出现了几次，按 (R个数,G个数,B个数) 的格式输出就行。 怎么做？  读入字符串 遍历每个字符，碰到 R 就 r++，碰到 G 就 g++，碰到 B 就 b++ 按格式拼好输出  纯模拟，没有任何坑点。唯一要注意的就是输出格式带括号和逗号，别漏了。 代码    C++   Java   Python3   JavaScript   #include <iostream> #include <string> using namespace std; int main() { stri...

小红的夹吃棋 思路 这道题在说什么？给你一个棋盘，上面有黑子（o，小红执）和白子（*，小紫执），要你判断谁的棋子被"夹吃"了。 什么叫夹吃？就是一颗棋子在横向或纵向上，左右（或上下）紧挨着的都是对方棋子——三连珠，中间那颗就被吃了。 那胜负怎么判？  只有一方的棋子被夹吃了，另一方赢 双方都被吃了，或者都没被吃，平局  具体做法  读入  的棋盘（第一行的长度就是 ） 遍历每个格子，如果是棋子（不是 .），检查它是否被夹吃：   - 水平方向：左边和右边都是对方棋子？  - 垂直方向：上边和下边都是对方棋子？  分别记录黑子（o）和白子（*）是否有被夹吃的情况 根据结果输出...