小红的好数 [题目链接](https://www.nowcoder.com/practice/a4e3706a856644289a7a60b8d93fa5fc) 思路 一个整数  是"好数"，当且仅当存在一种拆分方式，使得 ，其中  是回文数， 是完全平方数（）。 枚举完全平方数 枚举所有满足  的完全平方数，判断  是否为回文数：  从  开始，令 ； 计算 ； 判断  是否为回文数（将数字转为字符串，与其反转比较）； 若是，输出 YES 及  和 ；若遍历完所有平方数都未找到，输出 NO。  复杂度分析 枚举平方数最多  次，每次判断回文数为 ，总体复杂度 。 注意事项...

因数分解 (11294767) 题目链接: https://www.nowcoder.com/practice/ecfcba5a9da14f5d82c79ca5727a4113 题意 给定正整数 ，构造一个数 ，满足：   的质因数个数（含重复）恰好为 ，且这些质因子之积等于  最大化  的"优秀因子"数量  优秀因子定义：若  的某个因子能被  的每一个质因子整除，则称为优秀因子。 输出最大优秀因子数量，对  取模。 分析 设 ，其中  为不同的素数，，。 一个"优秀因子"必须能被所有  整除，即形如 ，其中 。 因此优秀因子的数量为： $$ 问题转化...

棋盘 [题目链接](https://www.nowcoder.com/practice/b8e7884e2cba4646806a90c4a26a65c5) 题意 给定一个  的棋盘，每格写有  或 ：  小球在格子为  时向下移动一格； 小球在格子为  时向右移动一格； 直到移出子矩阵边界为止。  每次询问给定子矩阵 ，小球从  出发，求其滚出子矩阵的位置。 思路 关键观察 小球的运动路径是确定的：从当前格子出发，若格子为  则持续向右，遇到  则转而向下；若格子为  则持续向下，遇到  则转而向右。整个路径由若干段"连续向右"和"连续向下"交替组成。 ...

翻转01 题目链接: https://www.nowcoder.com/practice/2058328e7de94037b556fd4d892820d3 题意 给定一个长度为  的仅由 0、1 构成的字符串  和整数 。每次操作可以选择字符串中任意一个字符并将其翻转（0 变 1，1 变 0）。问经过恰好  次操作后，字符串  是否能成为回文字符串。 思路分析 关键观察：  统计字符串中不匹配的对数 diff：即对于所有 ，满足  的对数。   最少需要 diff 次操作才能将字符串变为回文（每个不匹配的对需要翻转其中一个字符）。   如果 ，则无论如何也无法达成，输出 NO。   如果 ，设...

11285772 生成树 链接: https://www.nowcoder.com/practice/66f16470ff01423991a6e098bb406cce 标签: 二分, 并查集, 图, 最小生成树 --- 题意 给一张  个点  条边的无向连通带权图，你有恰好  次操作，每次可以将某条边的权值 （操作可以集中在同一条边上）。操作完成后，选出一棵生成树，使得树中边权最小的边尽量大。输出这个最大化的最小边权。 --- 思路 二分答案 对答案  进行二分：能否通过不超过  次  操作，构造出一棵所有边权  的生成树？ Check(X) 的判断 固定目标  后，对每条边 （原权值 ）而言...

11285770 小牛的作业 题目链接: https://www.nowcoder.com/practice/2003093910a142509157fa2f94088a0d 标签: 字符串, 贪心 --- 题意 给两个仅含小写英文字母的字符串  和 。对  可执行两种操作：  删除  中任意一个字符（代价 1） 将  中任意一个字符改为任意字母（代价 1）  目标：将  变为某个字符串 ，使得  与  的字符出现频率完全相同。求最小操作次数，无解输出 -1。 --- 分析 无解条件 由于只能删除或修改，不能增加字符，所以最终字符串长度 。而  的长度必须等于 （因为频率分布相同）。 因此，若...

图上染色 [题目链接](https://www.nowcoder.com/practice/93feea118678417db803ea62301ed3b1) 思路 给定一个  个节点、 条边的无向图，初始所有节点无颜色。每次操作将一个未着色节点染为某种颜色，操作后询问所有颜色相同的连通块中，最大块的大小。 关键观察 "颜色相同的连通块"是指：在原图中，若干节点两两相邻，且它们的颜色完全相同，形成的极大子图。 当我们给节点  染色  之后，只需检查  的邻居中是否也有颜色为  的节点，若有则将它们合并到同一个连通块（用并查集实现）。 算法设计 使用带权并查集（Union-F...

斐波那契 [题目链接](https://www.nowcoder.com/practice/b55722617e204b0ba9d40dd01191fb7b) 思路 给定整数  和数位 ，在前  个斐波那契数中，找出包含数位  次数最多的那个数（若有多个次数相同的，输出最小的）。 斐波那契数列定义如下： $$ \text{Fib}(n) = \begin{cases} 1 & n = 1, 2 \\ \text{Fib}(n-1) + \text{Fib}(n-2) & n \ge 3 \end{cases} $$ 解法：模拟 直接模拟：  生成斐波那契数列：从 Fib(1)=...

11285690 小O的糖果 链接: https://www.nowcoder.com/practice/c090ece039314d578e51913e758ce262 标签: 贪心, 基础数学 难度: 中等 --- 题意 小O有三盒糖果，数量分别为 a、b、c。他新获得 n 颗糖果，要恰好分到 k 个新盒子中（每盒至少 1 颗）。最终共有 3+k 盒糖果。问：无论 n 颗糖果如何分配，糖果最多的那一盒编号是否确定且唯一？ --- 分析 设原始三盒的最大值 M = max(a, b, c)，cnt_M 为原始三盒中等于 M 的盒子数。 核心观察 k 个新盒子分 n 颗糖（每盒 ≥ 1），新盒...

小O的平面画圆 [题目链接](https://www.nowcoder.com/practice/bb64967dbb2c430f8ff00e9be1c360c5) 思路 给定平面上  个圆，找出其中一个与所有其他圆都没有交点的圆。题目定义：两圆包含或相离视为没有交点（即相切也算有交点）。 两圆关系判断 设两圆圆心距为 ，半径分别为  和 。两圆的位置关系：    条件 关系 交点数      外离 0    外切 1   $\ r_1 - r_2\ < d < r_1 + r_2$ 相交 2   $d = \ r_1 - r_2\ $ 内切 1   $d < \ r_1 -...

小O的数组染色 [题目链接](https://www.nowcoder.com/practice/1e20b2f3daa14e8389c847eab1ab1f64) 题意 给定长为  的数组 ，初始全为白色。每次操作选择区间 ，要求 ，将该区间内所有元素染红。求将所有元素染红的最小操作次数。 思路 问题转化 每次操作覆盖一个区间 ，约束为 （特别地， 时  恒成立，即单个元素可以一次操作单独染色）。目标是用最少的区间覆盖 。 这是一个经典的贪心区间覆盖问题。 关键观察 对于每个位置  作为左端点，能覆盖的最远右端点是 ，即值  在数组中最后一次出现的位置。 证明：选择 ，，则 ，区间合法，覆盖...

小O的矩阵变换 [题目链接](https://www.nowcoder.com/practice/b1c40c55c4724f75a659915c6700e5ce) 思路 给定两个  的 01 矩阵  和 ，每次操作可以选择  的某一行或某一列，将该行/列所有元素翻转（0 变 1，1 变 0）。求最少操作次数使  变为 ，若不可能输出 -1。 建模 设  表示第  行是否被翻转， 表示第  列是否被翻转（翻转偶数次等价于不翻转，所以每行/列只需考虑翻转 0 或 1 次）。 对于每个位置 ，翻转后的值为 ，要求等于 ，即： $$ 令 ，问题变为：能否找到 ，使得对所有  满足 。 枚举固定  整...

小O的数位翻转 [题目链接](https://www.nowcoder.com/practice/80a2e1aa90a24841bb153d14f13aa24a) 思路 对数组中的每个数字，将其二进制表示翻转（去除前导零），如果翻转后的值严格大于原值，则计入答案。 二进制翻转 对于一个正整数 ，将其二进制从低位到高位逐位取出，依次拼到结果  的低位。具体做法：每次取  的最低位追加到 ，然后  右移一位，直到  为 0。这样自然去除了前导零。 例如 ，翻转后得 ，计入答案。 ，翻转后得 ，不计入。 判断条件 翻转后值严格大于原值，等价于二进制的最低位为 1（否则翻转后位数变少，不可能更大）且...

小O的五号倍数 题目链接: https://www.nowcoder.com/practice/f40cb14a15444609ac61bc4b4d75d3c3 题意 给定一个正整数 N（以字符串形式输入），每次可以删除其中一个数位，问最少删除多少个数位，使得剩余数字能被 5 整除。 特殊规定：全部删完后视为 0，0 也是 5 的倍数。 思路 一个整数能被 5 整除，当且仅当其最后一位是 0 或 5。 因此，策略是：  从右往左扫描，找到第一个（即最右边的）值为 0 或 5 的位置 pos。 保留 s[0..pos]，删掉 s[pos+1..n-1] 后面的所有数位。 需要删除的数位数为 n ...