紫薯P57 习题3-1 一、题意 有kase个OOXX串每个O的得分为目前连续出现的O的个数，X不得分。请求每个串的得分。 二、解析 每个串扫一遍即可，用cnt记录当前连续O的个数，ans记录得分。 三、代码 #include <iostream> #include <string> using namespace std; int kase; int main() { cin >> kase; while(kase --) { string str; cin >> str; int cnt = 0, ans = 0; for(char ch :...

紫薯P52 例题3-6 一、题意 有kase个循环字符串，输出每个字符串 (长度n<=100) 的最小表示。 二、解析 经典的求最小循环字符串题目，这里用来复习一下它的一种O(1)算法。 基本思想是双指针i, j，用k表示从i、j开始的子串的当前比对到的完全一样的长度，当判断出i、j的某一条子串的i+k、j+k位置有所不同时，大的那一条（比如是j）就可以往后跳k+1个字符，因为以这些字符起始的循环字符串已经不可能是最小的（比它们小的在i开始的串的子串中）。用这样的方法当i、j串中的某一个超过n时就不用再判断了（因为n个可能的起始位置都判断过了）。此时剩余的那个串就是最小的循环字符串。 三...

紫薯P52 例题3-5 一、题意 已知 y = x + sum(x的各位数字) (1 <= y <= 100000)有kase组数据，每组给出一个数字y，要求输出对应的最小x。 二、解析 由于y有大小限制，所以容易得出x最多比y小 5*9=45,因此对于每个y枚举比它小的44个数字即可. 三、代码 #include <iostream> #include <cmath> using namespace std; int kase, n; int num_sum(int x) { int res = 0; while(x) { res += x % 10; x...

紫薯P50 例题3-4 一、题意 输入有好几组。每组第一行一个数n，第二行开始，每行n个数，数字范围为1-9。每组第二行为一个参照序列ans。对于之后的每个序列行，它与ans序列相比，有A个数字位置正确，有B个数字在两个序列中都出现过但位置不对。输入(A, B)。当有一行全为0时，该组结束；当n为0时，输入结束。 二、解析 统计每个数字在ans序列中出现的次数cnt_a[10]；对于之后与之对比的序列b，统计每个数字在b序列中出现的次数cnt_b[10]；统计每个数字在两个序列中位置相同的次数cnt_same[10]。则 A 为所有数字位置正确的次数之和；B比较难想，就是每个数字在两个序列中出...

紫薯P48 例题3-3 一、题意 输入一些字符串，要求分别对每个字符串判断：是不是回文串；是不是镜像串。并输出相应的答句。 二、解析 回文串判断：reverse后是否相等镜像串判断：reverse+映射每个字符到其镜像字符后，是否和原串相等 三、代码 #include <iostream> #include <algorithm> #include <string> using namespace std; const string characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789"; const strin...

紫书P47 例题3-2 一、题意 输入一段字符串，是手在键盘向右移了一个后的输出结果，要求输出原字符串。 二、解析 用const字符串存放会输入/出的所有字符，然后边输入边找原来的字符（即前一个）进行输出 三、代码 #include <iostream> #include <string> using namespace std; const string str = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"; int main() { char ch; while((ch = getchar()) != EO...

紫书P45 例题3-1 一、题意 输入一篇文章，把左右引号" "分别替换为 ``和 ' '。 二、解析 边输入边判断，然后边输出即可。 三、代码 #include #include using namespace std; int main(){ char ch; const string q[2] = {"``", "''"}; int idx = 0; while((ch = getchar()) != EOF) { if(ch == '"') cout << q[idx], idx = (idx + 1) % 2; else cout << ch; } } /* ...