【套题】GESP C++四级认证各题详解/详细代码

0. 前言

• 按照洛谷题单上的顺序整理的

1. B3940 填幻方

B3940 [GESP样题 四级] 填幻方 - 洛谷

• 按照题目的意思模拟即可，主要是要把代码写得悠亚~

#include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 填幻方 就是模拟呀​*/​const int N=20+5;int n;int a[N][N];​signed main() {scanf("%d",&n); // n一定是奇数int cnt=1; // 已经填过的数字 == N*N时退出int i=1,j=n/2+1; a[i][j]=1; // 第一行正中央为1while(cnt!=n*n) {int nx=(i==1?n:i-1); // 向上移动一格, 如果已经在第一行, 则移到同一列的最后一行int ny=(j==n?1:j+1); // 向右移动一格, 如果已经在最右一列, 则移动至同一行的第一列//      cout<<nx<<' '<<ny<<'\n';cnt++;if(!a[nx][ny]) a[nx][ny]=cnt; // 如果没填过则填上// 如果填过了则只用向下移动一格else {nx=(i==n?1:i+1); // 向下移动一格, 如果已经在最下一行, 则移到同一列的第一行ny=j;a[nx][ny]=cnt;}i=nx,j=ny; // 更新位置}for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {cout<<a[i][j]<<' ';}   puts("");}return 0;}​/*输入样例:3输出样例:8 1 63 5 74 9 2*/

2. B3939 绝对素数

B3939 [GESP样题 四级] 绝对素数 - 洛谷

• 题目给的数字范围很小，可以用常规做法，否则欧拉筛

#include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 题目限制了数字一定是两位数 那么对换就很简单 再判断两次素数即可如果数字范围大 还是推荐使用欧拉筛​*/​const int N=1e5+5;int n,a[N],vis[N];bool p[N]; // 是否为素数​// 欧拉筛: 筛选出2~n中所有素数void Euler(int n) {for(int i=2;i<=n;i++) {if(!vis[i]) {p[i]=true; // 素数存起来// j枚举i的倍数for(int j=1;i*j<=n;j++) {vis[i*j]=true;  }}}}​// 质数判定 枚举优化bool isPrime(int x) {if(x<=1) return false;for(int i=2;i<=x/i;i++) {if(x%i==0) return false;}return true;}​signed main() {// 欧拉筛的结果//  scanf("%d",&n);//  Euler(n);//  for(int i=1;i<=idx;i++) {//      cout<<p[i]<<' ';//  }//  puts("");int a,b;cin>>a>>b;// 1. 欧拉筛做法//  Euler(b);//  for(int i=a;i<=b;i++) {//      if(p[i]) cout<<i<<'\n';//  }// 2. 常规做法for(int i=a;i<=b;i++) {int x=i; // 当前数字取出来int y=(x%10)*10+x/10; // 翻转两位数//      cout<<x<<' '<<y<<'\n';if(isPrime(x) && isPrime(y)) {cout<<i<<'\n';}}return 0;}​/*输入样例:11 20输出样例:111317*/

3. B4068 Recamán

B4068 [GESP202412 四级] Recamán - 洛谷

• 注意状态数组去重，注意long long，模拟即可

 #include<bits/stdc++.h>#define x first#define y second#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 根据题目的意思模拟即可, 注意longlong​*/​const int N=3e5+5;int n,a[N];bool vis[N]; // 状态数组​signed main() {scanf("%d",&n);// 初始化a[1]=1;vis[1]=true;// 计算前n项for(int i=2;i<=n;i++) {int t=a[i-1]-i; // 第k项=a(k-1)+-kif(t>0 && !vis[t]) a[i]=t;else a[i]=t+2*i; // 补2i变+k// 标记一下vis[a[i]]=true;}// 排序sort(a+1,a+1+n);for(int i=1;i<=n;i++) {cout<<a[i]<<' ';    }return 0;}​/*输入样例:5输出样例:1 2 3 6 7*/

4. B3959 做题

B3959 [GESP202403 四级] 做题 - 洛谷

• 一眼贪心，排序后顺序枚举，直到枚举结束后（每套题都和当前应做题目数比较后无所不用其极）输出结果

#include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 每个题单只用一次判断是否大于等于天数k即可, 因此排序后顺序枚举一遍再用cnt++​*/​const int N=1e6+5;int n,a[N];​signed main() {scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);}// 排序, 从题最少的题单开始做满足数量大的不浪费 贪心sort(a+1,a+1+n);// 枚举int cnt=0; // 目前做过的套题数量, 答案, 过了几天才偷懒int day=1; // 统计过了几天, 即现在要完成几道题for(int i=1;i<=n;i++) {if(a[i]>=day) {day++;cnt++;} }cout<<cnt;return 0;}​/*输入样例:43 1 4 1输出样例:3*/

5. B4006 宝箱

B4006 [GESP202406 四级] 宝箱 - 洛谷

• 背包容量无限，是否损坏纯看最大价值和最小价值之差，首先想到的是把排序后价值最大的作为x，则最小价值为x-k，把这部分加起来，但也有可能比x-k价值更小的物品具有极多的数量会导致把比x价值更小的物品作为价值最大的物品得到的总价值更大，所以还需要一层循环来枚举价值最大的物品是哪一个

 #include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: ​*/​const int N=1e5+5;int n,a[N];int k; // 最大价值差​signed main() {scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);}// 从大到小排序sort(a+1,a+1+n,greater<int>());int ans=INT_MIN;// 1. i-枚举价值最大的物品是谁for(int i=1;i<=n;i++) {int cnt=0;// 2. j-枚举[x-k,x]之间物品for(int j=i;j<=n;j++) {if(a[i]-a[j]<=k) {cnt+=a[j];}}if(cnt>ans) ans=cnt;}cout<<ans;return 0;}​/*输入样例:​输出样例:​*/

6. B3928 田忌赛马

B3928 [GESP202312 四级] 田忌赛马 - 洛谷

• 田忌按顺序出马并不代表在计算获胜轮次的时候不能将田忌的马排序，因为每匹马之间应该是独立的，最后排序自己的马用双指针遍历看能赢多少轮，贪心不熟不好想到思路

 #include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 田忌的马按顺序出, 其实我首先想到的是能不能每次用二分去找一个最接近的去试探但是二分没有标记数组的作用, 被使用过的值依然在二分中, 所以老老实实从贪心上做手脚再来, 虽然题目中说田忌马的顺序不变, 但其实计算“我”能赢多少次 都是在和其马的速度做对比所以做两次排序, 然后双指针遍历完我自己的马看能赢多少轮即可​*/​const int N=5e4+5;int n,a[N],b[N]; // a: 我的, b: 田忌的​signed main() {scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);}for(int i=1;i<=n;i++) {scanf("%d",&b[i]);  }// 两次排序sort(a+1,a+1+n);sort(b+1,b+1+n);// 枚举我的马匹 算出能赢多少轮int cnt=0;// i-我的马匹 j-田忌马匹for(int i=1,j=1;i<=n;i++) {// 不存在平局if(a[i]>b[j]) {cnt++;j++;}}cout<<cnt;return 0;}​/*输入样例:31 3 52 4 6输出样例:2*/

7. B4069 字符排序

B4069 [GESP202412 四级] 字符排序 - 洛谷

• 问是否存在满足每个字符非严格递增的字符串, 那就把所有字符串排序后拼接起来判断即可

#include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 问是否存在满足每个字符非严格递增的字符串, 那就把所有字符串排序后拼接起来判断即可​*/​const int N=1e5+5;int n;string s[N]; // 字符串数组​// 对字符串判断是否非严格递增bool check(string s) {// s.size和s.length在速度上没有区别都是O(1)for(int i=1;i<s.size();i++) {if(s[i]<s[i-1]) return false;}return true;}​signed main() {int T;cin>>T;while(T--) {cin>>n;for(int i=1;i<=n;i++) { // 数组是从下标1开始存cin>>s[i]; // 注意这里对每个字符串来说从下标0开始存的}// 默认按照ASCII码+长度从小到大排序sort(s+1,s+1+n);string t="";// 拼接for(int i=1;i<=n;i++) {t+=s[i];}if(check(t)) cout<<"1"<<'\n';else cout<<"0"<<'\n';}return 0;}​/*输入样例:23aaacde2aacbc输出样例:10*/

8. B3869 进制转换

B3869 [GESP202309 四级] 进制转换 - 洛谷

• 非常经典的进制转换，还是R转十，直接除R余法的逆运算（顺序遍历），或者按照R的位权展开（逆序遍历）

 #include<bits/stdc++.h>#define x first#define y second#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 任意进制数转十进制数, 要么从末尾起乘其进制数和位权要么按照除R余法的思路加回去, 个人倾向第二种 因为是顺序遍历符合逻辑思维K进制数最大位数不超过9 那么最坏情况FFFFFFFFF 包开longlong啊​*/​const int N=1e5+5;int n,a[N];​// 任意R进制数到D十进制int RtoD(int R,string s) {int ans=0;for(int i=0;i<s.size();i++) {if(s[i]>='0' && s[i]<='9') {ans=ans*R+s[i]-'0';} // 对字符进行处理else {ans=ans*R+(s[i]-'A'+10);}}return ans;}​signed main() {int T;cin>>T;while(T--) {int R; // 进制string s; // 进制数cin>>R>>s;cout<<RtoD(R,s)<<'\n';}return 0;}​/*输入样例:28 136216 3F0输出样例:7541008*/

9. B3850 幸运数

B3850 [GESP202306 四级] 幸运数 - 洛谷

• 纯模拟呀纯模拟，上代码

#include<bits/stdc++.h>#define x first#define y second#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 这道题就是模拟 纯模拟就好 ​*/​const int N=1e5+5;​// 对n数按数位拆求加和int sum(int n) {int ans=0;while(n) {ans+=n%10;n/=10;}return ans;}​// 对奇数位n变换数位int trans(int n) {n*=7;while(n>9) n=sum(n); // 直到n<=9 这个写法return n;}​signed main() {int T;cin>>T;while(T--) {int x;cin>>x;int ans=0;// 对x进行拆位(从末尾开始计算)// 带奇偶判断的拆位for(int p=1;x;x/=10,p++) {// 奇数位, 位权从10^0开始if(p&1) ans+=trans(x%10)*pow(10,p-1); // 奇数位转换// 偶数位else ans+=(x%10)*pow(10,p-1);}//      cout<<ans<<'\n';// 对得到的新数字最后做一次拆位运算ans=sum(ans);// !优先级最高, 加括号!!!if(!(ans%8)) {cout<<"T"<<'\n';} else {cout<<"F"<<'\n';}}return 0;}​/*输入样例:21634776344输出样例:TF*/

10. B4041 区间排序

B4041 [GESP202409 四级] 区间排序 - 洛谷

• 用sort函数做这道题超简单的孩子们

 #include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 用sort做区间排序​*/​const int N=1e5+5;int n,a[N];​signed main() {scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);}int t;cin>>t;while(t--) {int l,r;cin>>l>>r;sort(a+l,a+1+r); // 从下标1开始// 1~n 排序 a+1 a+1+n, l~r 排序 a+l a+1+r 套左边公式 }for(int i=1;i<=n;i++) {cout<<a[i]<<' ';    }return 0;}​/*输入样例:53 4 5 2 134 53 41 3输出样例:1 3 4 5 2*/

11. B3851 图像压缩

B3851 [GESP202306 四级] 图像压缩 - 洛谷

• 题面非常之恶心呀，翻译过来就是：给一个每行不定长的灰度图(每两个字符表示一个灰阶)，统计其中频次最高的16个灰阶，再将这个灰度图中的每个点转换成最接近这16个灰阶中的某一个(绝对值最接近)，并将原来两个字符表示一个灰阶的方式改变为用一个字符表示(这16个灰度的二进制编号)

• 每两个字符表示一个灰度，难点在于此处的灰度就用数值型去存储，不用把两个字符拼接成string，太麻烦，最后打印编号的时候再按照16进制的形式打印就好

#include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 题目有点恶心 看的题解 最烦大模拟 这里翻译一下题目    给一个每行不定长的灰度图(每两个字符表示一个灰阶), 统计其中频次最高的16个灰阶再将这个灰度图中的每个点转换成最接近这16个灰阶中的某一个(绝对值最接近)并将原来两个字符表示一个灰阶的方式改变为用一个字符表示(这16个灰度的二进制编号)​*/​const int N=25; int a[N][N]; // 保存压缩后的数据​// 不用字符存(00~FF) 而是该用16进制存struct HD{int val; // 灰度值int num; // 数量}hd[256]; // 存前16个频次最高的灰度值​// 十六进制转十进制int toInt(char c) {if(c>='A' && c<='F') return c-'A'+10;return c-'0';}​// 十进制转为十六进制void printHx(int x) {char c;if(x>9) c='A'+x-10;else c=x+'0';cout<<c;}​// 按出现的数量从小到大排序, 数量相同时灰度小的在前bool cmp(HD x,HD y) {if(x.num==y.num) return x.val<y.val;return x.num>y.num;}​signed main() {int n;string s;cin>>n;for(int i=1;i<=n;i++) {cin>>s; // 输入每一行int t; // 计算两位组合在一起的十六进制表示数for(int j=0;j<s.size();j+=2) {t=toInt(s[j])*16+toInt(s[j+1]);a[i][j/2+1]=t; // j=0 j/2+1 从下标1开始存 a[1][1]hd[t].num++; // 统计频次}}for(int i=1;i<=255;i++) hd[i].val=i; // 初始化每种灰度值sort(hd,hd+256,cmp); // 排序// 打印前16个for(int i=0;i<16;i++) {printHx(hd[i].val/16); // 第1位printHx(hd[i].val%16); // 第2位}cout<<endl;int len=s.size()/2;// 找到每个像素点的最近值for(int i=1;i<=n;i++) {for(int j=1;j<=len;j++) {int mmin=INT_MAX;int idx=0; // 记录编号// 从16种灰阶里面去找for(int k=0;k<=15;k++) {// 用绝对值比较if(abs(hd[k].val-a[i][j])<mmin) {mmin=abs(hd[k].val-a[i][j]);idx=k;}}printHx(idx); // 打印编号的十六进制表示}   puts("");}return 0;}​/*输入样例:1000FFCFAB00FFAC09071B5CCFAB7600AFCBAB11FFAB09981D34CFAF5601BFCEAB00FFAC0907F25FCFBA6510FBCBAB11FFAB09981DF4CFCA6700FFCBFB00FFAC0907A25CCFFC7600FFCBAB1CFFCB09FC1AC4CFCF6701FCCBAB00FFAC0F071A54CFBA6510EFCBAB11FFAB09981B34CFCF6701FFCBAB00FFAC0F071054CFAC761000CBAB11FFAB0A981B84CFCF66输出样例:ABCFFF00CB09AC07101198011B6776FC321032657CD10E36409205ACC16DB41032657FD16D8F409205ACF14D324F326570D1FE3240C245FC411DBF4032687CD16D8F409205ACC11DB240326878D16E83409205ACE11D*/

12. B3870 变长编码

B3870 [GESP202309 四级] 变长编码 - 洛谷

• 字符串模拟，比上一题好懂一些，读懂题目就会做

• 需要学的是字符串分割和最后的用控制流输出保证大写的同时每个十六进制数占2位且自动在高位补0

#include<bits/stdc++.h>#define x first#define y second#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 题目有点长, 读完分为以下几个步骤, 说白了 模拟1. 把输入的数字转成二进制2. 每组7bit, 不足7位高位补03. 对每组 若为最后一组高位补0 否则补14. 把每组数据转换为十六进制表示并打印​*/​const int N=1e5+5;int n,a[N];vector<int> v; // 存二进制表示形式 vector<string> bit(10); // 按组划分 2×10^18 不超过64位 最多8组​signed main() {scanf("%lld",&n);// 1. 对0特判if(n==0) v.push_back(0);// 二进制拆 倒着while(n) {v.push_back(n%2);n/=2;}//  cout<<"二进制表示如下:"<<'\n';//  for(int i=0;i<v.size();i++) cout<<v[i]<<' ';//  puts("");// 从低位到高位7位一组拆分int flag=0; // 数到7int cnt=0; // 组数string s="";for(int i=0;i<v.size();i++) {flag++;s=to_string(v[i])+s; // 不要用char, 注意拼接方向// 走到末尾也算if(flag==7 || i==v.size()-1) {bit[cnt]=s; // 不给空间的话这样访问会报错s="";flag=0;cnt++;}}//  cout<<"7个1组分组后结果如下:"<<'\n';//  for(int i=0;i<cnt;i++) {//      cout<<bit[i]<<'\n';//  }//  puts("");// 看最高位是否够7位 不够补0while(bit[cnt-1].size()<7) bit[cnt-1]="0"+bit[cnt-1];// 枚举一次 如果不是最后一组都加1否则补0for(int i=0;i<cnt;i++) {if(i!=cnt-1) bit[i]="1"+bit[i];else bit[i]="0"+bit[i];}// 每组打印出来看看//  for(int i=0;i<cnt;i++) cout<<bit[i]<<'\n';//  puts("");// 最后把每一组转换成十六进制编码即可// 1. 二→十// 2. 十进制下用hex打印for(int i=0;i<cnt;i++) {int ans=0;for(int j=0;j<bit[i].size();j++) {ans=ans*2+(bit[i][j]-'0');}// 以十六进制形式打印 大写 补0 占2位cout<<hex<<uppercase<<setw(2)<<setfill('0')<<ans<<' '; // 神奇吧 控制流输出}return 0;}​/*输入样例:987654321012345678输出样例:CE 96 C8 A6 F4 CB B6 DA 0D*/

13. B4040 黑白方块

B4040 [GESP202409 四级] 黑白方块 - 洛谷

• 在n×m的矩阵中找一个4×4满足条件的子矩阵，因为有4行，所以枚举的时候起点枚举到第n-3行就可以了，学一下找条件满足矩阵的思路，把x和y当做偏移量

 #include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: n×m的矩阵中去找4×4满足条件的子矩阵​*/​const int N=1e3+5;const int ans[][4]={{'0','0','0','0'},{'0','1','1','0'},{'0','1','1','0'},{'0','0','0','0'}};​int n,m;char g[N][N]; // 地图1​// 起点坐标(i,j)bool check(int x,int y) {for(int i=0;i<=3;i++) {for(int j=0;j<=3;j++) {// 对比地图的思路 需要学习 x和y做偏移量if(g[x+i][y+j]!=ans[i][j]) return false;}}return true;}​signed main() {int T;cin>>T;while(T--) {cin>>n>>m;// 1. 输入地图for(int i=1;i<=n;i++) {cin>>g[i]+1; // 从下标1开始存}//      for(int i=1;i<=n;i++) {//          for(int j=1;j<=m;j++) {//              cout<<g[i][j];//          }   //          puts("");//      }// 2. 枚举起点开始check 矩阵的右下角刚好覆盖到整个地图右下角时// 此时左上角的坐标为(n-3,m-3)bool flag=false;for(int i=1;i<=n-3;i++) {for(int j=1;j<=m-3;j++) {if(check(i,j)) flag=true;}}if(flag) cout<<"Yes"<<'\n';else cout<<"No"<<'\n';}return 0;}​/*输入样例:31 401105 50000001100011000000101100输出样例:NoYes*/

14. B4005 黑白方块

• 维护两个前缀和，再用四层循环枚举区间和最后去更新最大平衡矩阵的大小就好了

#include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 很明显要用两个前缀和, 一个记黑格子 一个记白格子因为n和m都非常小 所以枚举子矩阵的时候可以用四层循环(左上角坐标和右下角坐标)​*/​const int N=10+5;int n,m;int a[N][N]; // 白格子int b[N][N]; // 黑格子char g[N][N];​signed main() {cin>>n>>m;// 从[1,1]开始存for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {cin>>g[i][j];// 自行推二维前缀和计算公式if(g[i][j]=='0') {a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+1; // 白格子+1b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]; // 虽然不加但仍要计算, 递推}else {a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1];b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+1; // 黑格子+1}}}int ans=INT_MIN;// 四重循环for(int x1=1;x1<=n;x1++) {for(int y1=1;y1<=m;y1++) {for(int x2=x1;x2<=n;x2++) {for(int y2=y1;y2<=m;y2++) {// 计算区间和int s1=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]; // 白区间和int s2=b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1]; // 黑区间和if(s1==s2) {// 计算子矩阵的大小int t=(x2-x1+1)*(y2-y1+1);if(t>ans) {//                          cout<<x1<<' '<<y1<<'\n';//                          cout<<x2<<' '<<y2<<'\n';ans=t;  }}}   }}}if(ans==INT_MIN) cout<<0;else cout<<ans;return 0;}​/*输入样例:4 500000011110001100011输出样例:16*/

15. B3927 小杨的字典

• 题目很好懂，这题比较麻烦的地方在于标点符号可以上一个字符也可以是两个字符，一般来按分隔符分割字符串的方法有如下：

单个字符作为分隔符

bool check(char c) {if(c==',' || c=='.') return true;return false;}​signed main() {string s;cin>>s;s+='.'; // 末尾加标点// 双指针for(int i=0,j=0;i<s.size();i++) {// 遇到分隔符 提取单词if(check(s[i])) {string t=s.substr(j,i-j); // 从j开始长度位i-j+1cout<<t<<'\n';j=i+1; // 跳}}return 0;}

两个字符或多个字符作为分隔符，更精悍，以后可以这样写

 signed main() {string s;cin>>s;s+='.'; // 末尾加标点 使每段单词之间独立string t="";// 遍历sfor(auto c:s) {if(c>='a' && c<='z') t+=c;// 说明碰到分隔符else {// 如果已有单词 (这句很巧妙 如果t=="" 说明这个分割符由多个字符组成)// 也就是说最少遇到一个字符的时候才打印 如果t为空说明分割符有多个字符if(t!="") {cout<<t<<'\n';t="";}}}return 0;}

• 所以本道题的代码就出来了

 #include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 这道题比较恶心的地方的地方在于标点符号可以是1位 "," 也可以是2位 "()"一般来说标点符号只有一位的话就按照双指针来拆了​*/​const int N=1e5+5;int n,a[N];map<string,string> m; // 存映射关系​signed main() {cin>>n;for(int i=1;i<=n;i++) {string a,b;cin>>a>>b;m[a]=b;}string s;cin>>s;s+='.'; // 末尾加个 . 这样可以使每个单词都独立平等string t=""; // 当前拆分每个单词string ans=""; // 翻译后的结果// 对每个字符for(char c:s) {if(c>='a' && c<='z') t+=c;else {// 遇到标点符号 且目前已有单词if(t!="") {if(m.count(t)) ans+=m[t];else ans+="UNK";t="";}ans+=c; // 分隔符加上 可处理两边型 好用!!!}}ans.pop_back(); // 一开始加的 '.' 弹出cout<<ans<<'\n';return 0;}​/*输入样例:1abcdefghij klmnopqrst!()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz输出样例:!()-[]{}\|;:'",./?<>UNK*/

16. B3958 相似字符串

• 非常经典的一个题呀，也很值得学习，对两个长度不相同的字符串，若len(a)<len(b)则交换a,b，默认让a的长度比b更大，更容易处理，删除和添加都是len(a)-len(b)==1所以可以合在一起处理，用双指针遍历即可，若len(a)==len(b)则遍历，判断是否有超过两个不同的字符即可

 #include<bits/stdc++.h>#define x first#define y second//#define int long long​using namespace std;​typedef long long LL;typedef pair<int,int> PII;​/*解题思路: 是个比较经典的字符串处理的题目1. 删除或添加一起处理 都是b串长度比a串少1 若不是则交换 ab两串从头比较发现不同字符cnt++ 若cnt>2则不相似2. 若ab串字符相同 是否修改一个字符到达则二者从头比较是否有不同字符注意完全相同的字符串也是相似的​*/​const int N=1e5+5;int n,a[N];​// 判断a和b是否相似bool isSimilar(string a,string b) {int la=a.size(),lb=b.size();// 1. 长度之差大于1 肯定不能一次转变过来 if(la-lb>1) return false;// 2. 长度相同 判断是否出现2个及以上不相同的字符if(la==lb) {int cnt=0;for(int i=0;i<la;i++) {if(a[i]!=b[i]) cnt++;if(cnt>1) return false;}return true;}// 3. 长度不同 即la-lb==1// 用双指针 i指向a, j指向bif(la-lb==1) {int i=0,j=0,cnt=0;while(i<la && j<lb) {if(a[i]==b[j]) i++,j++;else {cnt++; // 出现不相同的字符if(cnt>1) return false;i++; // i跳 j不跳 下次还是会比较当前j这个字符}}return true; }}​signed main() {int T;cin>>T;while(T--) {string a,b;cin>>a>>b;if(a.size()<b.size()) swap(a,b); // 调整长度顺序 默认a比b长cout<< (isSimilar(a,b)?"similar":"not similar")<<'\n';}return 0;}​/*输入样例:5apple appleeapple appeapple bppleapplee bppleapple apple输出样例:similarsimilarsimilarnot similarsimilar*/