• 24程序设计难度较低，且只有2道，基础还可以的话应该都能拿满分。
• 仅22程序设计难度较大，其余21、23、24年难度都比较低。
• 程序设计不涉及数据结构，程序设计题主要考察基础语法（结构体数组排序、自定义一个新概念），偶尔涉及少量简单算法（背包、贪心、二维前缀和）

1. 相亲数

在数学中，若彼此的约数之和（除去自身）等于另一方，则二者被称为亲和数。

例如：

220的约数和为1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
284的约数和为1 + 2 + 4 + 71 + 142 = 220

则220和284为一对亲和数。

输出10000以内的亲和数。

#include <iostream>

using namespace std;

// 计算一个数的约数之和
int get(int n)  
{
    // 1是任何数的约数，所以初始值设为1
    int s = 1;  
    // 从2开始遍历到sqrt(n)，因为如果i是n的约数，那么n/i也是n的约数
    for (int i = 2; i * i <= n; i ++)  
    {
        if (n % i == 0)  
        {
            s += i;  
            if (i * i != n)
                s += n / i;  
        }
    }
    return s;  
}

int main()
{
    int n = 10000;  
    for (int i = 1; i <= n; i ++)  
    {
        int s1 = get(i);  
        int s2 = get(s1);  
        if (i < s1 && i == s2)  
            cout << i << ' ' << s1 << endl;
    }

    return 0;
}

暴力

// 思路：枚举10000以内的所有数字i，求他的约数之和j，若j的约数之和也为i，则将这一对亲和数输出

#include <iostream>

using namespace std;

// 求x的约数之和
int get(int x)
{
    int s = 0;
    for (int i = 1; i <= n / 2; i ++)
        if (n % i == 0)
            s += i;
    return s;
}

int main()
{
    for (int i = 1; i <= 10000; i ++)
    {
        int s1 = get(i); // i的约数之和为s1
        int s2 = get(s1);   // s1的约数之和为s2
        if (i < s1 && i == s2)
            cout << i << ' ' << s1 << endl;
    }

    return 0;
}

输出

284 220
1210 1184
2924 2620
5564 5020
6368 6232

2. 异位字符串

给定两个字符串 $s$ 和 $t$ ， $s$ 和 $t$ 的长度 $n$ 最大是 1000 ，判断 $s$ 和 $t$ 是否为字母异位词（相同字母的数量是否相等），大小写敏感，不含非字母字符串，且时间复杂度要求在 $O(n)$ ，除了输入输出以外不能用字符串相关的函数，如果是则输出true，不是输出false

例如：$s = “anagram”, t = “nagaram”$，则 $s$ 和 $t$ 是字母异位词

解法1：unordered_map

算法思路
1. 首先判断两个字符串的长度是否相等，如果不相等，则它们肯定不是字母异位词，直接返回false。
2. 使用unordered_map（无序映射）来记录字符串中每个字符出现的次数。
- 遍历第一个字符串s，对于其中的每个字符c，在cnt中增加c的计数（如果c不存在，则初始化为0后再加1）。
- 遍历第二个字符串t，对于其中的每个字符c，在cnt中减少c的计数。
3. 遍历unordered_map中的所有元素，检查每个字符的计数是否都为0。如果有任何字符的计数不为0，则说明两个字符串不是字母异位词，返回false。
4. 如果所有字符的计数都为0，则说明两个字符串是字母异位词，返回true。

#include <iostream>
#include <unordered_map>

using namespace std;

// 函数check用于判断两个字符串是否为字母异位词
bool check(string s, string t)
{
    // 如果两个字符串长度不同，它们肯定不是字母异位词
    if (s.length()!= t.length()) return false;

    // 创建一个无序映射，用于记录字符出现的次数
    unordered_map<char, int> cnt;
    // 遍历字符串s，统计每个字符出现的次数
    for (char c : s)
        cnt[c] ++;
    // 遍历字符串t，减少对应字符出现的次数
    for (char c : t)
        cnt[c] --;

    // 检查每个字符的计数是否都为0
    for (auto item : cnt)
        if (item.second != 0)
            return false;

    // 如果所有字符的计数都为0，说明是字母异位词
    return true;
}

int main()
{
    string s, t;
    cin >> s >> t;

    if (check(s, t))
        puts("true");
    else
        puts("false");

    return 0;
}

解法2：数组模拟

算法思路
1. 定义两个长度为26的数组，分别用于记录大小写字母出现的次数。
2. 遍历第一个字符串，统计其中大小写字母出现的次数，分别在对应的数组位置上加1。
3. 遍历第二个字符串，对其中的大小写字母在对应的数组位置上减1。
4. 检查两个数组中所有位置的值是否都为0，如果是，则两个字符串是字母异位词；如果有不为0的值，则不是字母异位词。

#include <iostream>

using namespace std;

// 用于记录小写字母出现次数的数组
int lower[26];
// 用于记录大写字母出现次数的数组
int upper[26];

// 函数check用于判断两个字符串是否为字母异位词
bool check(string s, string t)
{
    // 统计字符串s中每个字母出现的次数
    for (char c : s)
    {
        if (c >= 'a' && c <= 'z')
            lower[c - 'a']++;
        else if (c >= 'A' && c <= 'Z')
            upper[c - 'A']++;
    }

    // 统计字符串t中每个字母出现的次数，并减去之前在s中统计的次数
    for (char c : t)
    {
        if (c >= 'a' && c <= 'z')
            lower[c - 'a']--;
        else if (c >= 'A' && c <= 'Z')
            upper[c - 'A']--;
    }

    // 检查是否所有字母出现的次数都相同（即是否为字母异位词）
    for (int i = 0; i < 26; i++)
        // 如果有任何字母的出现次数不为0，则不是字母异位词
        if (lower[i] || upper[i])
            return false;

    // 如果所有字母出现次数都为0，则是字母异位词
    return true;
}

int main()
{
    string s, t;
    cin >> s >> t;

    if (check(s, t))
        puts("true");
    else
        puts("false");

    return 0;
}