贝壳找房 · 字符串 · 算法编程题
贝壳找房 字符串 T ≤ 1e3 时限 1 秒 / 64 MB

题目描述

牛牛拥有 r 个红球， g 个绿球， b 个黑球以及 w 个白球。
牛牛可以取红球、绿球、黑球各一个，然后将它们转变成三个白球。只要取完球，球的个数非负，那么，就可以进行任意多次该操作。
现在，牛牛想知道，经过若干次变换之后的球，在不舍弃任何一颗球的基础上，能否在一排排成回文的形态？即：从前往后和从后往前都是一样的。
例如：最终球的个数依次为 0, 0, 1, 4 ，那么可以摆成 白球白球黑球白球白球 ，这是一个回文的形态，而如果最终球的个数依次为 0, 3, 6, 9 ，那么无论如何也不能摆成一个回文形态。这里特殊规定，若最终所有球的数量均为 0 ，则可认为是个特殊的回文形态。

输入输出

输入描述
本题为多组测试数据，第一行输入一个正整数 T( 1≤ T≤ 1000) ，代表测试数据组数。
对于每组测试数据，一行输入四个整数 r, g, b, w( 0≤ r, g, b, w≤ 1000000) ，依次代表初始状态下红球、绿球、黑球、白球的个数。
输出描述
对于每组测试数据，如果经过若干次操作之后能够组成一个回文形态，那么在第一行输出 Yes ，第二行依次输出最终红球、绿球、黑球、白球的个数，如果存在多种可能，任意输出一种即可；如果无论如何都不能组成一个回文形态，那么只需要在第一行输出 No .

样例共 1 组

样例 1
输入
2
0 0 1 4
0 3 6 9
输出
Yes
0 0 1 4
No

算法解析依据一般

考点：字符串

数据规模 T ≤ 1e3 ｜ 限制 1 秒 / 64MB ｜ 标准输入输出

题目画像

  • 数据规模：T ≤ 1e3
  • 元素值域：r ≤ 1e6，g ≤ 1e6，b ≤ 1e6（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：字符串

按字符逐个处理，或利用字符串的前后缀性质加速匹配。

思路框架（字符串 通法 · 非本题专属）

  1. 明确操作对象是字符还是子串、是否需要保持原顺序。
  2. 子串问题常用双指针 / 滑动窗口；回文问题可用中心扩展或哈希。
  3. 多模式匹配考虑 Trie 或 KMP；只需计数则用哈希表统计字符频次。
  4. 注意字符集大小写敏感性与输入是否带引号。

实现要点：Python 切片 s[l:r+1] 取子串；注意字符串不可变，频繁拼接改用 list。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

  • 下标与切片边界差 1。
  • 忽略了大小写、空白字符的影响。

对照本题

  • 数据规模 T ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 1e6 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：2 / 0 0 1 4 / 0 3 6 9
  • 输出：Yes / 0 0 1 4 / No

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招测试类试卷。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解