A、智乃办赛

1、字母部分计算：每个字母对应500个编号。将输入的n减1后除以500得到字母的索引（0对应'A'，1对应'B'，以此类推）。

2、数字部分计算：n减1后对500取余，得到余数再加1，确保数字范围为1到500。使用printf的格式控制%03d保证数字部分为三位数，不足三位时补前导零。

3、组合输出：将字母和数字部分拼接，直接输出结果。

代码实现：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 计算字母部分：每500个数一个字母
    int letter_index = (n - 1) / 500;
    char letter = 'A' + letter_index;
    // 计算数字部分：余数转换为1-500，补前导零
    int number = (n - 1) % 500 + 1;
    // 输出格式化为字母+三位数
    printf("%c%03d", letter, number);
    return 0;
}

B、智乃的Wordle

1、字符存在性判断：首先遍历 secret 单词，记录每个字符是否存在。这一步用布尔数组 exist 实现，exist[c] 表示字符 c 是否在 secret 中出现。

2、绿色标记处理：第一次遍历比较 secret 和 guess 的每一位，若字符相同则标记为 g，同时检查是否所有位置都正确。

3、黄色/红色标记处理：第二次遍历处理非绿色标记的位置。若该字符存在于 secret 中（无论是否被正确匹配过），则标记为 y；否则标记为 r。

4、结果输出：根据标记结果生成字符串，并输出是否完全正确的提示。

代码实现：

#include <iostream>
#include <string>
using namespace std;

int main() {
    string secret, guess;
    cin >> secret >> guess;

    // 记录secret中的字符是否存在
    bool exist[26] = {false};
    for (char c : secret) {
        exist[c - 'a'] = true;
    }

    string result(8, ' ');
    bool allCorrect = true;

    // 第一次遍历：处理绿色标记（g）
    for (int i = 0; i < 8; ++i) {
        if (secret[i] == guess[i]) {
            result[i] = 'g';
        } else {
            allCorrect = false; // 存在不匹配的位置
            // 暂时不处理黄/红标记，后续统一处理
        }
    }

    // 第二次遍历：处理黄色和红色标记（y/r）
    for (int i = 0; i < 8; ++i) {
        if (result[i] != 'g') { // 非绿色位置需要进一步判断
            if (exist[guess[i] - 'a']) {
                result[i] = 'y';
            } else {
                result[i] = 'r';
            }
        }
    }

    // 输出结果
    cout << result << endl;
    cout << (allCorrect ? "congratulations" : "defeat") << endl;

    return 0;
}

C、智乃的数字

（一）题目分析

我们需要找到第k大的“智数”。智数的定义是满足以下条件之一的奇数：

1. 以5结尾。
2. 各个数位之和是3的倍数（等价于该数能被3整除）。

通过分析，我们可以将问题转化为数学公式，并使用二分法快速确定第k个智数的位置。

（二）方法思路

1、数学公式推导：

1. 以5结尾的奇数：构成等差数列5, 15, 25, ...，公差为10。
2. 能被3整除的奇数：构成等差数列3, 9, 15, 21, ...，公差为6。
3. 同时满足以上两个条件的数：构成等差数列15, 45, 75, ...，公差为30。

2、容斥原理：计算到某个数N时的智数总数，需减去重复计数的部分。

3、二分查找：通过二分法确定满足条件的最小N，使得前N个数中的智数总数等于k。

代码实现：

#include <iostream>
using namespace std;

typedef long long ll;

ll compute_count(ll n) {
    if (n < 3) return 0;
    ll count1 = (n >= 5) ? ((n - 5) / 10 + 1) : 0;
    ll count2 = (n >= 3) ? ((n - 3) / 6 + 1) : 0;
    ll count3 = (n >= 15) ? ((n - 15) / 30 + 1) : 0;
    return count1 + count2 - count3;
}

ll find_kth(int k) {
    ll low = 1, high = 1e18;
    while (low <= high) {
        ll mid = (low + high) / 2;
        ll cnt = compute_count(mid);
        if (cnt < k) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int k;
        cin >> k;
        cout << find_kth(k) << "\n";
    }
    return 0;
}

D、智乃与长短期主义者博弈

（一）题目分析

两位玩家轮流从一排数字的两端取数。短期主义者（先手）每次选择较大的数，若相等则选左边；长期主义者（后手）选择全局最优策略。我们需要计算两者的最终得分。

（二）思路解析

1、动态规划（DP）状态定义：

• 表示当剩余区间为 且当前为短期主义者取数时，当前玩家的净得分（当前得分减去对方后续得分）。
• 表示当剩余区间为 且当前为长期主义者取数时，当前玩家的净得分。

2、状态转移：

• 短期主义者的选择是确定的：取左右两端较大的数，若相等则取左边。
• 长期主义者需选择使全局最优的解，即比较取左或右后的净得分，取最大值。

3、初始条件：当区间长度为1时，玩家直接取该数，净得分为该数值。

4、计算总净得分：通过动态规划填充所有区间的状态，最终得到全局净得分 S，进而计算两位玩家的具体得分。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    // 定义两个二维DP数组，分别表示当前玩家是短期（dp0）或长期（dp1）时的净得分
    vector<vector<int>> dp0(n, vector<int>(n, 0)); // 短期玩家的DP表
    vector<vector<int>> dp1(n, vector<int>(n, 0)); // 长期玩家的DP表

    // 初始化区间长度为1的情况
    for (int i = 0; i < n; ++i) {
        dp0[i][i] = a[i];
        dp1[i][i] = a[i];
    }

    // 从区间长度2开始，逐步处理更大的区间
    for (int len = 2; len <= n; ++len) {
        for (int left = 0; left <= n - len; ++left) {
            int right = left + len - 1;

            // 计算短期主义者的选择：取较大的一端，相等则左
            if (a[left] >= a[right]) {
                // 选择左端，剩余区间由长期主义者处理
                dp0[left][right] = a[left] - dp1[left + 1][right];
            } else {
                // 选择右端，剩余区间由长期主义者处理
                dp0[left][right] = a[right] - dp1[left][right - 1];
            }

            // 计算长期主义者的选择：取左右中更优的结果
            int chooseLeft = a[left] - dp0[left + 1][right]; // 选左端的净得分
            int chooseRight = a[right] - dp0[left][right - 1]; // 选右端的净得分
            dp1[left][right] = max(chooseLeft, chooseRight); // 选择最优解
        }
    }

    // 计算总净得分并得出两位玩家的最终得分
    int totalDiff = dp0[0][n - 1];
    int shortScore = (sum + totalDiff) / 2;
    int longScore = (sum - totalDiff) / 2;

    cout << shortScore << " " << longScore << endl;

    return 0;
}

E、智乃的跳跃排序

（一）题目理解

给定一个长度为N的数组，元素互不相同。我们只能交换满足以下条件的一对元素：

1. 下标差为k；
2. 元素值的差为k。

要求判断是否可以通过这样的交换将数组排序为升序。

（二）关键点分析

• 交换规则的特殊性：不能随意交换元素，必须满足下标或值的差为k。
• 分组思想：若元素值的差为k，它们可以形成一条链式结构，这样的元素可以相互交换。
• 模k余数匹配：每个元素在排序后的正确位置的模k余数必须与原位置的模k余数在对应的链中保持一致。

（三）解题思路

1. 排序数组：首先得到排序后的数组作为目标顺序。
2. 余数分组：对于每个元素，计算其在原数组中的位置模k余数，以及在排序后数组中的位置模k余数。
3. 数值链分析：遍历每个元素，找到所有与之数值差为k的元素形成的链。对于每个链中的元素，检查其原余数集合和排序后的余数集合是否相同（排序后顺序可不同，但集合元素必须相同）。
4. 判断条件：若所有链的余数集合匹配，则可以排序成功，否则失败。

（四）具体步骤

1. 排序目标数组：获得排序后的正确顺序。
2. 建立映射关系： now：记录原数组中每个元素的位置模k余数。zhen：记录排序后每个元素的位置模k余数。
3. 遍历数值链：使用哈希表标记已处理的元素。对于每个未被处理的元素，向上下延伸找到所有数值差为k的元素，形成链。
4. 比较余数集合：将链中原余数和目标余数分别收集并排序，若不一致则输出"No"。
5. 最终判断：所有链均通过检查则输出"Yes"。

代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int arr[N], brr[N];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        brr[i] = arr[i]; // 复制数组用于排序
    }
    sort(brr + 1, brr + 1 + n); // 排序得到目标数组brr

    unordered_map<int, int> r, zhen, now;
    // r记录元素是否存在，zhen记录排序后的余数，now记录原数组的余数
    for (int i = 1; i <= n; i++) {
        r[arr[i]] = 1; // 标记元素存在
        zhen[brr[i]] = i % k; // 排序后元素的位置模k余数
        now[arr[i]] = i % k; // 原数组中元素的位置模k余数
    }

    auto idx = r.begin();
    while (idx != r.end()) {
        vector<int> ans, da; // ans保存当前链的原余数，da保存目标余数
        int t = (*idx).first; // 当前处理的元素值

        // 向上扩展：t, t+k, t+2k...
        while (r[t + k] == 1) { 
            t += k;
            ans.push_back(now[t]); // 原余数加入ans
            da.push_back(zhen[t]); // 目标余数加入da
            r.erase(t); // 标记已处理
        }

        t = (*idx).first;
        // 向下扩展：t, t-k, t-2k...
        while (r[t - k] == 1) {
            t -= k;
            ans.push_back(now[t]);
            da.push_back(zhen[t]);
            r.erase(t);
        }

        t = (*idx).first;
        ans.push_back(now[t]); // 加入当前元素自身余数
        da.push_back(zhen[t]);
        r.erase(idx++); // 删除当前元素，迭代器后移

        // 排序后比较余数集合是否一致
        sort(ans.begin(), ans.end());
        sort(da.begin(), da.end());
        for (int i = 0; i < ans.size(); i++) {
            if (ans[i] != da[i]) {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    while (T--) solve();
    return 0;
}

F、智乃的数组乘积

（一）题目理解

给定一个长度为N的数组和一个质数P，要求通过最少次数的修改，使得修改后的数组满足：不存在任何子区间乘积模P等于给定值x。每次修改可将元素变为任意小于P的非负整数。

（二）关键点分析

• x=0的特殊处理：需确保数组中所有元素均不为0，否则存在单个元素为0的子区间。
• x≠0的动态维护：通过维护前缀积和危险值集合，避免后续乘积产生x的同余值。
• 打断策略：遇到可能产生危险值时，通过修改元素为0，切断前缀积链，重新开始计算，可以证明这样的修改次数一定是最少的。

（三）解题思路

1. x=0的情况：将所有0元素改为非0数（如1），保证所有子区间乘积非0。修改次数等于原数组中0的个数。
2. x≠0的情况：维护前缀积res和危险值集合book。遍历数组，计算当前前缀积与元素的乘积ans。若ans存在于book中，说明保留当前元素会导致存在危险子区间，需将其修改为0，并重置前缀积。否则，更新前缀积，并将新的危险值（）加入集合。

代码实现：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
const int INF = 1e18;
int arr[N], jc[N];
int n, p, x;
void solve() {
    cin >> n >> p >> x;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    if (x) {// 处理x≠0的情况
        int res = 1; // 维护当前前缀积
        unordered_map<int, int> book;
        book[x] = 1;// 初始危险值为x
        for (int i = 1; i <= n;) {
            int ans = res * arr[i] % p; // 计算当前前缀积与当前元素的乘积
            if (book[ans]) arr[i] = 0;// 若当前乘积可能导致后续出现x，修改当前元素为0以打断链条
            if (arr[i] == 0) {
                res = 1;// 重置前缀积
                book.clear();// 清空危险值集合
                book[x] = 1; // 重新初始化
                i++;// 处理下一个元素
            } else {
                res = res * arr[i] % p;// 更新前缀积
                book[res * x % p] = 1;// 将危险值加入集合
                i++;// 继续处理下一个元素
            }
        }
        for (int i = 1; i <= n; i++) cout << arr[i] << " ";
        cout << endl;
    } else {// 处理x=0的情况
        for (int i = 1; i <= n; i++) {
            if (arr[i] % p == 0) { // 将所有模p等于0的元素改为1
                arr[i] = 1;
            }
            cout << arr[i] << " ";
        }
        cout << endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    // cin>>T;
    while (T--) solve();
    return 0;
}