✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线160+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

OPPO-08.31

题目一：小兰的神秘宝藏

1️⃣：理解咒语公式的数学本质，转化为

2️⃣：利用质数只能分解为 的性质求解

3️⃣：特判 的特殊情况

难度：简单

这道题目的关键在于理解 的数学本质，并利用质数的分解性质。由于质数只能分解为 ，我们可以直接计算出 ，。需要特别注意当 时无整数解的情况。

题目二：小基的魔法数字密码

1️⃣：识别为动态规划问题，定义状态为数字和

2️⃣：建立状态转移方程，考虑每位可选择1-9

3️⃣：预处理所有可能值，特判 的情况

难度：中等

这道题目结合了动态规划思想，需要理解如何用DP计算满足条件的数字个数。通过预处理所有可能的状态值，可以实现 的查询效率。关键是正确处理边界情况和模运算。

题目三：小柯的魔法阵修复

1️⃣：分析行回文和列回文的约束条件

2️⃣：将格子分组为等价类，每类中格子必须相同

3️⃣：利用异或运算的按位独立性，分位计算最优值

难度：中等偏难

这道题目需要深入理解回文约束带来的等价关系，并巧妙利用异或运算的位运算性质。通过将问题分解为按位独立的子问题，可以高效计算每个等价类的最优修改方案，实现 的时间复杂度。

01. 小兰的神秘宝藏

问题描述

在一个古老的遗迹中，考古学家 小兰 发现了一块神秘的石板。石板上刻着一个特殊的咒语公式：。

传说中，如果能找到合适的神力值和魔法值，就能解开宝藏的封印。小兰 通过研究发现，宝藏的价值总是一个神秘的质数。

现在 小兰 需要你帮助她计算：给定宝藏的价值（一个质数），是否存在正整数的神力值 和魔法值 （），使得上述咒语公式成立？

输入格式

第一行包含一个正整数 （），表示测试用例数。

接下来 行，每行包含一个质数 （），表示宝藏的价值。

输出格式

对于每组测试数据，输出一行：

• 如果存在满足条件的神力值 和魔法值 ，输出两个整数 和 。

• 如果不存在，输出 。

样例输入

2
2
3

样例输出

-1
2 1

样例	解释说明
样例1	当宝藏价值为2时，无法找到合适的神力值和魔法值
样例2	当宝藏价值为3时，神力值2，魔法值1可以满足公式

数据范围

• 
• 
• 为质数

题解

这道题的关键在于理解咒语公式的数学本质。

设 ，这其实就是 。

由于 是质数，它只能被分解为 的形式（不考虑负数）。

因此我们有：

• 
• 

解这个方程组：

• 
• 

但是我们需要 和 都是正整数。当 时，，，都不是整数，所以无解。

对于其他奇质数，由于 是奇数， 和 都是偶数，所以 和 都是正整数。

算法步骤：

1. 读入质数
2. 如果 ，输出
3. 否则输出 和

时间复杂度：，空间复杂度：。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

t = int(input())
for _ in range(t):
    n = int(input())
    # 处理特殊情况：n=2 时无整数解
    if n == 2:
        print(-1)
    else:
        # 对于奇质数，计算神力值和魔法值
        a = (n + 1) // 2  # 神力值
        b = (n - 1) // 2  # 魔法值
        print(a, b)

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        long long n;
        cin >> n;
        
        // 特殊情况：n=2 时无整数解
        if (n == 2) {
            cout << -1 << "\n";
        } else {
            // 对于奇质数，计算神力值和魔法值
            long long a = (n + 1) / 2;  // 神力值
            long long b = (n - 1) / 2;  // 魔法值
            cout << a << " " << b << "\n";
        }
    }
    
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            long n = Long.parseLong(br.readLine());
            
            // 特殊情况：n=2 时无整数解
            if (n == 2) {
                System.out.println(-1);
            } else {
                // 对于奇质数，计算神力值和魔法值
                long godPwr = (n + 1) / 2;  // 神力值
                long magPwr = (n - 1) / 2;  // 魔法值
                System.out.println(godPwr + " " + magPwr);
            }
        }
    }
}

02. 小基的魔法数字密码

问题描述

魔法师 小基 最近在研究一种特殊的数字密码。她发现，某些正整数具有神奇的魔法属性，这些数字被称为"魔法密码"。

一个正整数被称为魔法密码，当且仅当它满足以下条件：

1. 这个数字只能由数字 到 组成（不能包含数字 ）

2. 这个数字的各位数字之和恰好等于给定的魔法值

例如，当魔法值 时，满足条件的魔法密码有：（数字和为3）、（数字和为1+2=3）、（数字和为2+1=3）、（数字和为1+1+1=3），共4个。

现在 小基 想知道，对于给定的魔法值 ，一共有多少个不同的魔法密码？由于答案可能很大，请将结果对 取模。

输入格式

第一行包含一个正整数 （），表示测试用例数。

接下来 行，每行包含一个非负整数 （），表示魔法值。

输出格式

对于每组测试数据，输出一个整数，表示满足条件的魔法密码数量对 取模的结果。

样例输入

3
0
1
3

样例输出

0
1
4

样例	解释说明
样例1	魔法值为0时，不存在满足条件的正整数
样例2	魔法值为1时，只有数字"1"满足条件
样例3	魔法值为3时，有"3"、"12"、"21"、"111"四个魔法密码

数据范围

• 
• 

题解

这是一个典型的动态规划问题。

设 表示各位数字之和恰好为 的魔法密码数量。

状态转移方程：对于每个位置，我们可以选择放置数字 到 中的任意一个，因此：

初始状态：（表示空序列，虽然它不是正整数，但作为递推的基础）

特殊处理：当 时，由于题目要求的是正整数，答案应该是 而不是 。

算法步骤：

1. 预处理所有可能的 值到
2. 对于每个查询，如果 输出 ，否则输出

时间复杂度：预处理 ，单次查询 空间复杂度：

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

MOD = 10**9 + 7
MAXS = 200000

# 预处理 dp 数组
dp = [0] * (MAXS + 1)
dp[0] = 1  # 空序列作为基础状态

for i in range(1, MAXS + 1):
    total = 0
    # 尝试在当前位置放置数字 1-9
    for digit in range(1, 10):
        if digit <= i:
            total = (total + dp[i - digit]) % MOD
    dp[i] = total

t = int(input())
for _ in range(t):
    s = int(input())
    # 特殊处理：s=0 时不存在正整数
    if s == 0:
        print(0)
    else:
        print(dp[s])

• Cpp

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
const int MAXS = 200000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 预处理 dp 数组
    vector<long long> dp(MAXS + 1, 0);
    dp[0] = 1;  // 空序列作为基础状态
    
    for (int i = 1; i <= MAXS; i++) {
        long long sum = 0;
        // 尝试在当前位置放置数字 1-9
        for (int d = 1; d <= 9 && d <= i; d++) {
            sum = (sum + dp[i - d]) % MOD;
        }
        dp[i] = sum;
    }
    
    int t;
    cin >> t;
    
    while (t--) {
        int s;
        cin >> s;
        
        // 特殊处理：s=0 时不存在正整数
        if (s == 0) {
            cout << 0 << "\n";
        } else {
            cout << dp[s] << "\n";
        }
    }
    
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    private static final int MOD = 1000000007;
    private