题目链接

九倍平方数

题目描述

给定一个由数字组成的字符串 。你可以对它进行任意次操作：选择字符串中的某一位数字 （），并将其替换为它的平方 。如果通过若干次操作，可以使 代表的数字被 整除，则称 为“好数”。

你需要判断给定的字符串 是否是“好数”。

解题思路

这道题的核心是利用数论中关于 的整除性质，并将看似复杂的操作简化为对数字和的模 计算。

1. 关键性质：整除 9 一个整数能被 整除，当且仅当它的各位数字之和能被 整除。 例如， 的数字和是 ， 能被 整除，所以 也能被 整除。

2. 分析操作

  • 操作是：选择一个数字 ，替换为 。
  • 从样例 322 -> 342 可以看出，是将一位数字 2 替换成了 4 ()。这暗示了一个隐藏的条件：操作 d -> d^2 之后，替换的结果必须仍然是一位数，否则字符串长度会改变，问题将变得异常复杂。
  • 在 的数字中，只有 和 的平方是一位数：
  • 对于其他数字（如 ），操作后会变成两位数，我们假设这种操作是不允许的。

3. 操作对数字和（模 9）的影响

  • 如果我们将一个数字 2 替换为 4，那么整个数的各位数字之和的变化是 ()。
  • 如果我们将一个数字 3 替换为 9，那么整个数的各位数字之和的变化是 ()。

4. 问题转化

  • 我们的目标是让最终的数字和能够被 整除，即数字和模 为 。
  • 设原始字符串 的数字和模 的值为 current_rem。
  • 我们需要达成的目标是，通过若干次 或 的操作，使得 (current_rem + total_change) % 9 == 0。
  • 这意味着，我们需要的总变化量 total_change 必须满足 total_change % 9 == (9 - current_rem) % 9。我们称这个值为 target_rem。

问题现在变成了：我们能否从字符串 中所有 2 和 3 提供的“变化量”（2提供变化量2，3提供变化量6）中，挑选出一个子集，使得它们的和模 等于 target_rem？

5. 动态规划求解 (子集和模 9) 这是一个典型的子集和问题，只不过是在模 的意义下。我们可以用动态规划来解决。

  • 创建一个大小为 的布尔数组 dp，其中 dp[i] 表示我们是否能够凑出和为 的总变化量。
  • 初始化 dp[0] = true（不进行任何操作，总变化量为 ），其他为 false。
  • 遍历字符串 中的每一个数字：
    • 如果遇到数字 2，它提供一个 2 的变化量。我们就用这个 2 来更新 dp 数组。
    • 如果遇到数字 3，它提供一个 6 的变化量。我们就用这个 6 来更新 dp 数组。
  • 更新方式是：对于一个变化量 c，我们遍历所有当前可达的和 j（即 dp[j] 为 true 的地方），并标记新的可达和 (j + c) % 9 也为 true。
  • 遍历完 中所有的 2 和 3 后，我们检查 dp[target_rem] 是否为 true 即可。

代码

#include <iostream>
#include <string>
#include <vector>
#include <numeric>

using namespace std;

void solve() {
    string s;
    cin >> s;

    int current_sum = 0;
    vector<int> changes;
    for (char ch : s) {
        int digit = ch - '0';
        current_sum = (current_sum + digit) % 9;
        if (digit == 2) {
            changes.push_back(2);
        } else if (digit == 3) {
            changes.push_back(6);
        }
    }

    int target_rem = (9 - current_sum) % 9;

    vector<bool> dp(9, false);
    dp[0] = true;

    for (int change : changes) {
        vector<bool> next_dp = dp;
        for (int i = 0; i < 9; ++i) {
            if (dp[i]) {
                next_dp[(i + change) % 9] = true;
            }
        }
        dp = next_dp;
    }

    if (dp[target_rem]) {
        cout << "YES" << '\n';
    } else {
        cout << "NO" << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            String s = sc.next();
            solve(s);
        }
    }

    private static void solve(String s) {
        int currentSum = 0;
        List<Integer> changes = new ArrayList<>();
        for (char ch : s.toCharArray()) {
            int digit = ch - '0';
            currentSum = (currentSum + digit) % 9;
            if (digit == 2) {
                changes.add(2);
            } else if (digit == 3) {
                changes.add(6);
            }
        }

        int targetRem = (9 - currentSum) % 9;

        boolean[] dp = new boolean[9];
        dp[0] = true;

        for (int change : changes) {
            boolean[] nextDp = dp.clone();
            for (int i = 0; i < 9; i++) {
                if (dp[i]) {
                    nextDp[(i + change) % 9] = true;
                }
            }
            dp = nextDp;
        }

        if (dp[targetRem]) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

import sys

def solve():
    s = sys.stdin.readline().strip()
    
    current_sum = 0
    changes = []
    for char in s:
        digit = int(char)
        current_sum = (current_sum + digit)
        if digit == 2:
            changes.append(2)
        elif digit == 3:
            changes.append(6)
    
    current_rem = current_sum % 9
    target_rem = (9 - current_rem) % 9

    # dp[i] is True if a total change of i (mod 9) is possible
    dp = {0}
    
    for change in changes:
        new_dp = dp.copy()
        for rem in dp:
            new_dp.add((rem + change) % 9)
        dp = new_dp

    if target_rem in dp:
        print("YES")
    else:
        print("NO")


def main():
    t_str = sys.stdin.readline()
    if not t_str:
        return
    t = int(t_str)
    for _ in range(t):
        solve()

main()

算法及复杂度

  • 算法：动态规划 (子集和问题模 9)。
  • 时间复杂度：对于每个长度为 的字符串，我们首先遍历它一次来计算初始余数和收集可用的变化量，这需要 。然后，我们进行动态规划。变化量的数量最多为 ，DP 状态的大小是常数 。因此，DP 部分的计算是 。总时间复杂度为 。由于所有测试用例的 总和有上限，因此总的运行时间是高效的。
  • 空间复杂度：我们存储了变化量列表，最坏情况下长度为 。DP 数组大小为常数 。因此空间复杂度为 。