GESP三级

一. 凯撒密码

题目描述

凯撒密码是一种替换加密技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例如，当偏移量是 $3$ 的时候，所有的字母 $A$ 将被替换成 $D$，$B$ 被替换成 $E$，$C$ 被替换成 $F$，以此类推，$W$ 被替换成 $Z$，$X$ 被替换成 $A$，$Y$ 被替换成 $B$，$Z$ 被替换成 $C$。这个加密方法是以罗马共和时期凯撒的名字命名的，据称当年凯撒曾用此方法与其将军们进行联系。

但是和所有的利用字母表进行替换的加密技术一样，凯撒密码非常容易被破解，而且在实际应用中也无法保证通信安全。

现在给你一个已破解的凯撒密码明文与密文，与一个有相同偏移量的未破解凯撒密码密文，请你帮忙破解它。

输入格式

输入共三行：

第一行包含一个字符串，表示已破解的凯撒密码明文；

第二行包含一个字符串，表示已破解的凯撒密码密文；

第三行包含一个字符串，表示待破解的凯撒密码密文。

输出格式

输出一行，包含一个字符串，表示待破解的凯撒密码对应的明文。

输入输出样例 #1

输入 #1

ABCDEFGVWXYZ
DEFGHIJYZABC
WKHTXLFNEURZQIRAMXPSVRYHUWKHODCBGRJ

输出 #1

THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG

说明/提示

样例解释

样例 1 中，通过已破解的密码得出偏移量为 'D' - 'A' = 3，因此，对未破解部分进行逆向偏移：密文中的 W 对应明文中的 T（'W' - 3 = 'T'），密文中的 K 对应明文中的 H（'K' - 3 = 'H'），以此类推。

数据范围

保证密码长度均不超过 $1000$，所有字符串由大写字母组成。

---

解：

思路如下：

1. 确定偏移规则：通过已破解的明文和密文，计算出统一的偏移量（例如第一个字符的差值）。由于转换规则一致，只需根据第一个字符确定偏移方向与大小。
2. 处理边界情况：当偏移后超出字母范围时，需要进行循环处理（如 ‘A’ 向左偏移变为 ‘Z’）。
3. 解密待破解密文：对密文中的每个字符应用逆向偏移，得到对应的明文。

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

int main(){

    string s1, s2, s;         // s1明文,s2密文，s待翻译的密文
    string ans = "";         // 转换后的字符串
    cin >> s1 >> s2 >> s;
    int n = s2[0] - s1[0];   // 找出转换规律
    for(int i = 0; i < s.size(); i++){
        char a = s[i] - n;   // 按规则进行转换
        if(a < 'A'){         // 超出字母表范围，循环回末尾
            a += 26;
        }else if(a > 'Z'){  // 超出字母表范围，循环回开头
            a -= 26;
        }
        ans += a;
    }
    cout << ans;
    return 0;
}

优化提示：也可以直接使用数学公式 (s[i] - 'A' - n + 26) % 26 + 'A' 来统一处理偏移与循环，避免分类讨论。如果赛时无法快速推导正确公式，建议使用分类讨论规则写法。

---

二. 二进制回文串

题目描述

对于一个正整数 $n$，我们将其转换为不含前导零的二进制表示，如果这个二进制序列从左向右读与从右向左读完全相同，则称该数为二进制回文数。例如，$9$ 的二进制表示为 $(1001{)}_2$，是二进制回文数；$12$ 的二进制表示为 $(1100{)}_2$，不是二进制回文数。

你的任务是：给定一个正整数 $n$，计算在 $1$ 到 $n$ 的范围内二进制回文数的数量。

输入格式

输入一行，包含一个正整数 $n$。

输出格式

输出一行，包含一个数，表示在 $1$ 到 $n$ 的范围内二进制回文数的数量。

输入输出样例 #1

输入 #1

15

输出 #1

6

说明/提示

样例解释

样例 1 中，$1$ 到 $15$ 范围内 $1$、$3$、$5$、$7$、$9$、$15$ 是二进制回文数。

数据范围

$1\le n\le 10^5$。

解法1(数字分解法)

思路：

1. 枚举 $i$ 从 $1$ 到 $n$。
2. 将 $i$ 转换为二进制数（用十进制形式存储，如 $4\to 100$）。
3. 判断该二进制数是否为回文数（反转后是否与原数相等）。

⚠️注意: 注意：$n\le 10^5$ 时，二进制表示最多 $17$ 位，需使用 long long 存储。

#include<bits/stdc++.h>
using namespace std;
bool check(int x) {
    long long x_to_2 = 0;   // 转换为二进制
    long long p = 1;        // 10的幂
    while(x) {
        x_to_2 += x % 2 * p;
        x /= 2;
        p *= 10;
    }
    long long x_to_2_tmp = x_to_2;
    long long rev = 0;     // x_to_2的反转数字
    while(x_to_2_tmp) {
        rev = rev * 10 + x_to_2_tmp % 10;
        x_to_2_tmp /= 10;
    }
    return rev == x_to_2;
}
int main(){
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        if(check(i)) ++ans;
    }
    cout << ans << endl;
    return 0;
}

解法2(数组，字符串)

思路：

1. 枚举$i$从$1-n$
2. 对$i$先转换为二进制对应的字符串s, 然后判断s是否为回文串即可。

#include<bits/stdc++.h>
using namespace std;
bool check(int x) {
    string s = "";    // 二进制字符串初始化
    while(x) {
        s += (x % 2) + '0';   //单数字 + '0' 转化为数字字符
        x /= 2;
    }
    for (int i = 0; i < s.size() / 2; i++) {  //枚举字符串(一半即可)
        //  依次判断s[0] = s[s.size() - 1]
        //         s[1] = s[s.size() - 2]
        //         ...
        if (s[i] != s[s.size() - 1 - i])
            return false;
    }
    return true;
}
int main(){
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        if(check(i)) ++ans;
    }
    cout << ans << endl;
    return 0;
}