202603-1 二进制回文串
题目描述
对于一个正整数 ,我们将其转换为不含前导零的二进制表示,如果这个二进制序列从左向右读与从右向左读完全相同,则称该数为二进制回文数。例如, 的二进制表示为 ,是二进制回文数; 的二进制表示为 ,不是二进制回文数。
你的任务是:给定一个正整数 ,计算在 到 的范围内二进制回文数的数量。 输入格式
输入一行,包含一个正整数 。
输出格式
输出一行,包含一个数,表示在 到 的范围内二进制回文数的数量。
样例输入 1
15样例输出 1
6提示
【样例解释】
样例 1 中, 到 范围内 、、、、、 是二进制回文数。
【数据范围】
。
代码解析
我们可以直接进行二进制的数位剥离,将数字的二进制表示从低到高逐位剥离出来,同时将这些位再重新组合,得到一个新的数 ,如果 与原数相等,那么这个数就是二进制回文数。
#include <bits/stdc++.h>using namespace std;int main() {
int n,cnt = 0; cin >> n; for (int i = 1; i <= n; i++) { int j = i, m = 0; while (j) { m = m *2 + j % 2; j /= 2; } if (m == i) cnt++; } cout << cnt;
return 0;}202603-2 凯撒密码
题目描述
凯撒密码是一种替换加密技术,明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。例如,当偏移量是 的时候,所有的字母 将被替换成 , 被替换成 , 被替换成 ,以此类推, 被替换成 , 被替换成 , 被替换成 , 被替换成 。这个加密方法是以罗马共和时期凯撒的名字命名的,据称当年凯撒曾用此方法与其将军们进行联系。
但是和所有的利用字母表进行替换的加密技术一样,凯撒密码非常容易被破解,而且在实际应用中也无法保证通信安全。
现在给你一个已破解的凯撒密码明文与密文,与一个有相同偏移量的未破解凯撒密码密文,请你帮忙破解它。
输入格式
输入共三行:
第一行包含一个字符串,表示已破解的凯撒密码明文;
第二行包含一个字符串,表示已破解的凯撒密码密文;
第三行包含一个字符串,表示待破解的凯撒密码密文。
输出格式
输出一行,包含一个字符串,表示待破解的凯撒密码对应的明文。
样例输入
ABCDEFGVWXYZDEFGHIJYZABCWKHTXLFNEURZQIRAMXPSVRYHWUKHODCBGRJ样例输出
THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG代码解析
我们可以先计算出已破解的凯撒密码明文与密文之间的偏移量 ,然后对待破解的凯撒密码密文进行解密,即将每个字符 加上 ,但是由于 有可能大于零也有可能小于 0,所以加个判断,如果 超过了 ,则减去 ,如果 小于 ,则加上 。
#include <bits/stdc++.h>using namespace std;int main() {
string s1, s2, s; cin >> s1 >> s2 >> s; int n = s1[0] - s2[0]; for (char i: s) { i += n; if (i > 'Z') i -= 26; else if (i < 'A') i += 26; cout << i; }
return 0;}202606-1 加密
题目描述
小杨同学有一串数字,想把它们变成另一串数字,这个过程叫做加密。
他有一本密码本,密码本告诉你:每个数字应该变成哪个数字。
数字一共有 个:、、、、、、、、、。
密码本会依次告诉你:
- 要变成什么
- 要变成什么
- 要变成什么
- ……
- 要变成什么
请你按照密码本,把原来的每个数字都换成新的数字,然后输出。
输入格式
输入共有 行。
第一行:一个整数,表示有多少个数字需要加密;
第二行:这些需要加密的数字;
第三行:密码本,一共 个数字。
这 个数字的意思是:
- 第 个数字:表示 加密后变成什么;
- 第 个数字:表示 加密后变成什么;
- 第 个数字:表示 加密后变成什么;
- ……
- 第 个数字:表示 加密后变成什么。
输出格式
输出加密后的数字。
也就是:把输入第二行里的每个数字,都按照输入第三行的密码本换掉后输出。
样例输入 1
70 2 0 3 4 1 99 0 1 2 3 4 5 6 7 8样例输出 1
9 1 9 2 3 0 8提示
第二行要加密的数字是:
第三行密码本是:
它的意思是:
- 变成
- 变成
- 变成
- 变成
- 变成
- 变成
- 变成
- 变成
- 变成
- 变成
所以:
- 变成
- 变成
- 变成
- 变成
- 变成
- 变成
- 变成
最后得到:
【数据范围】
需要加密的数字个数不超过 个,且均为 到 ;密码本中的数字不重复,且均为 到 。
代码解析
根据题目意思,需要遍历数组
s的每一个元素s[i],将s[i]作为数组a的下标,输出a[s[i]]
#include <bits/stdc++.h>using namespace std;int main() {
int n; cin >> n; int s[20005], a[10]; for (int i = 0; i < n; i++) cin >> s[i]; for (int i = 0; i < 10; i++) cin >> a[i];
for (int i = 0; i < n; i++) cout << a[s[i]] << ' ';
return 0;}202606-2 字符转换
题目描述
小杨同学有一串字符,里面可能有:
- 大写字母,比如 、、
- 小写字母,比如 、、
- 数字,比如 、、
现在小杨同学想把这串字符变一变,规则如下:
- 如果是大写字母,就变成对应的小写字母;
- 如果是小写字母,就变成对应的大写字母;
- 如果是数字,就变成
*。
请你按照这个规则,帮小杨把整串字符转换好。
输入格式
输入一共有 行。
第一行:一个整数,表示这串字符一共有多少个字符。
第二行:一串连续的字符,中间没有空格。
输出格式
输出转换后的字符。
注意:输出时字符之间不要加空格。
样例输入 1
5aBc98样例输出 1
AbC**提示
原来的字符是:
aBc98从左到右一个一个看:
- 是小写字母,所以变成 ;
- 是大写字母,所以变成 ;
- 是小写字母,所以变成 ;
- 是数字,所以变成
*; - 是数字,所以变成
*。
所以最后输出:
AbC**【数据范围】
字符个数不会超过 个。
每个字符只会是大写字母、小写字母或数字。
代码解析
这道题考察的就是对于字符类型的判断和大小写转换,遍历每一个字符,如果是大写就转小写,如果是小写就转大写,数字字符直接替换为
*
#include <bits/stdc++.h>using namespace std;int main() {
int n; string s; cin >> n >> s; for (int i = 0; i < n; i++) { // if ('a' <= s[i] && s[i] <= 'z') if (islower(s[i])) s[i] -= 32; else if (isupper(s[i])) s[i] += 32; else if (isdigit(s[i])) s[i] = '*'; } cout << s;
return 0;}202609-1 公共二进制位
题目描述
小红有 个非负整数 。她将每个整数转换为二进制后,想知道有多少个二进制位在所有整数中均为 。
二进制位从右向左编号为 。若某个整数的二进制表示中没有第 位,则认为它的第 位为 。
输入格式
- 第一行一个整数 ,表示整数的个数。
- 第二行 个非负整数 。
输出格式
输出一个整数,表示所有整数的二进制表示中均为 的二进制位数量。
样例输入 1
313 7 15样例输出 1
2提示
【样例解释 1】
三个整数的二进制表示分别为 、 和 。
其中第 位和第 位均为 ,因此答案为 。
【数据范围】
,。
代码解析
这道题需要透过现象看本质,搞清楚题目考的是什么,重点是怎么去判断某个二进制位在所有整数中均为 1,“全 1 为 1”,这就是按位
&运算。所以这道题就简单了,我们只需要让所有的数字都进行
&运算,统计最终结果中1的数量即可。
#include <bits/stdc++.h>using namespace std;int main() {
int n, m, r; cin >> n; // 第一个数字直接给 r,后续的数字都与 r 进行 & 运算 cin >> r; for (int i = 2; i <= n; i++) { cin >> m; r = r & m; } int cnt = 0; while (r) { if (r & 1 == 1) cnt++; r = r >> 1; } cout << cnt;
return 0;}202609-2 分割字符串
题目描述
小明拿到了一段字符串文本,小明希望用下面的规则分割这个字符串:
- 小明从左到右扫描字符串,遇到第一个空格后停止,并将字符串分割为左右两个部分(舍弃用于分割的这个空格);
- 对于上次分割后右侧的字符串,小明继续扫描,第一次遇到连续两个空格后停止,并将字符串分割为左右两个部分(舍弃用于分割的这两个空格);
- 对于上次分割后右侧的字符串,小明继续扫描,第一次遇到连续三个空格后停止,并将字符串分割为左右两个部分(舍弃用于分割的这三个空格);
- 以此类推,小明每分割一次,下一次分割就需要更长的连续空格;直到字符串无法再次分割。
最后输出每次分割的左侧的字符串,以及最后一次分割的右侧字符串。
如果字符串完全无法进行任何一次分割,直接输出其本身。
输入格式
输入一行,一个字符串。
输出格式
输出若干行。每行为分割后的一个字符串,注意依次输出:
第一次分割左侧的字符串,第二次分割左侧的字符串,……,最后一次分割左侧的字符串,最后一次分割右侧的字符串。
样例输入 1
sdfd 55 55 99312样例输出 1
sdfd55 55 99312样例输入 2
AbCd 999样例输出 2
AbCd
999提示
【样例解释 1】
- 第一次分割将字符串分割为
"sdfd"和"55 55 99312"; - 第二次分割将字符串分割为
"55 55"和" 99312"。
对于第二次分割,注意 "55" 和 "55" 之间虽然有空格,但是第二次分割需要连续两个空格才行;
另外,"55 55" 和 "99312" 之间有三个空格,第二次分割只需要两个,所以会分割为 "55 55" 和 " 99312",也就是右侧会留下一个空格;因为只留下了一个空格,所以不再满足第三次分割要求。
【样例解释 2】
- 第一次分割将字符串分割为
"AbCd"和" 999"; - 第二次分割将字符串分割为 空字符串 和
"999"。
由于 "AbCd" 和 "999" 之间有三个空格,第一次分割消耗掉一个,因此还能进行第二次分割,这个时候会分割出空字符串,因此输出中会输出一个空行(不能省略)。
【数据范围】
字符串长度不超过 ,字符串中只包含大写字母、小写字母,数字,或空格,且输入字符串不会以空格结尾。
特别强调:输入仅一行,但可能包含若干空格
代码解析
这道题的解法有很多,但是如果单纯使用模拟法的话,代码会非常复杂易出错,需要考虑很多细节。更高效的解法是使用 C++标准库中的字符串处理函数,效率会高很多,这里给出一种解法参考:
- 使用两个辅助变量,
n来记录当前分割的空格数,slag来记录当前分割的空格字符串;- 遍历字符串,使用
substr函数来判断接下来的n个字符是否等于slag,若等于则说明可以分割,否则继续遍历拼接下一个字符,这个过程和课堂中单词分割的过程类似。- 注意,每次分割后,需要将
n加 1,slag加一个空格,并且需要更新下一步i的位置。
#include <bits/stdc++.h>using namespace std;int main() {
string s; getline(cin, s);
int n = 1; string word, slag = " ";
for (int i = 0; i < s.size(); i++) { if (s.substr(i, n) == slag) { // 分割 cout << word << endl; word = ""; i += n-1; n++; slag += ' '; } else { word += s[i]; } } cout << word;
return 0;}
陕公网安备61010302001363号