当前位置：首页 > news >正文

算法模拟类题目解析

news 2026/8/14 14:43:43

前言：最近开始偏系统的从简单到难一步步刷算法题，先从模拟题开始，下边附带题目与连接，感兴趣可刷刷也可看看我的思路。

一.字符串展开

链接：https://ac.nowcoder.com/acm/problem/16644
来源：牛客网
题意：

输入一个字符串（含数字、小写字母和减号），以及三个参数 p1、p2、p3。
当遇到减号“-”时，如果它两边都是小写字母或都是数字，且右边字符大于左边，就进行“展开”：

把两边之间的所有字符按顺序（或逆序）填充进去，每个字符重复 p2 次；
p1 控制填充内容（小写、大写或星号）；
p3 控制顺序（正序或逆序）。
如果两边是相邻字符（如“a-b”），则直接删掉减号；如果不满足展开条件（如“a-d-d”中的第二个减号），则保留原减号。

解析：作为模拟题目，很显然我们要做的就是跟着题目意思进行模拟，这种题目怕的主要是漏了题目所给条件，导致无法ac，这个题意已经根据原题进行精简挑出重点，但在原题目中需要好好注意提取题目主要意思进行查缺补漏。

下边为我的ac代码：

#include<iostream> #include<string> #include<ctype.h> #include<algorithm> using namespace std; int panduan(char c) { if(c>='0'&&c<='9')return 1; else if(c>='a'&&c<='z')return 2; return 0; } int main() { int p1,p2,p3; cin >> p1 >> p2 >> p3; string s,ans; cin >> s; ans=""; for(int i=0;i<s.size();i++) { if(s[i]=='-'&&s[i-1]<s[i+1]&&p1==1&&i>0&&(panduan(s[i-1])==panduan(s[i+1]))) { string sub; sub=""; for(char j=s[i-1]+1;j<s[i+1];j++) { for(int k=1;k<=p2;k++) sub+=j; } if(p3==2) reverse(sub.begin(),sub.end()); ans+=sub; continue; } else if(s[i]=='-'&&s[i-1]<s[i+1]&&p1==1&&i>0&&(panduan(s[i-1])==panduan(s[i+1]))) { string sub; sub=""; for(char j=tolower(s[i-1]+1);j<tolower(s[i+1]);j++) { for(int k=1;k<=p2;k++) sub+=j; } if(p3==2) reverse(sub.begin(),sub.end()); ans+=sub; continue; } else if(s[i]=='-'&&s[i-1]<s[i+1]&&p1==2&&i>0&&(panduan(s[i-1])==panduan(s[i+1]))) { string sub; sub=""; for(char j=toupper(s[i-1]+1);j<toupper(s[i+1]);j++) { for(int k=1;k<=p2;k++) sub+=j; } if(p3==2) reverse(sub.begin(),sub.end()); ans+=sub; continue; } else if(s[i]=='-'&&s[i-1]<s[i+1]&&p1==3&&i>0&&(panduan(s[i-1])==panduan(s[i+1]))) { for(char j=s[i-1]+1;j<s[i+1];j++) { for(int k=1;k<=p2;k++) ans+="*"; } continue; } ans+=s[i]; } cout << ans; return 0; }

一开始我没加上这个panduan函数导致我卡在70%的正确率，大部分人都是因为忘记-号前后要是同一类型a-z或者是0-9的形式，无法AC。

代码可能有点复杂了，可自行简化但思路大差不差。

二.多项式展开

链接：https://ac.nowcoder.com/acm/problem/16622
来源：牛客网
题意：

这题就是给你一个多项式从高到低每个次数的系数，让你按数学课本上的写法输出。
需要注意几个细节：第一项如果是正数不要加号；系数是 1 或 -1 时不要写那个 1，只写符号和 x；指数是 1 时不要写 ^1；指数是 0 时只输出系数；系数为 0 的项直接扔掉。

解析：
上题是题意捕捉上不要遗漏这题是模拟决策上的选择，因为负数自带符号我想着怎么调整可以运用但最后给代码搞得很乱也无法ac，最后干脆跟着题意分步骤，判断符号在输出绝对值。

下边为ac代码

#include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int>a(n+5,0); int first=0; for(int i=1;i<=n+1;i++) { cin >> a[i]; if(a[i]==0)continue; else if(a[i]>0&&first) { cout << "+"; } else if(a[i]<0) { cout << "-"; }if(i==n+1||abs(a[i])!=1) cout << abs(a[i]); if(a[i]>0||a[i]<0)first=1; if(n-i+1>1) cout << "x^" << n-i+1; else if(n-i+1==1) { cout << "x"; } } return 0; }

其实这题问题并不多主要注意的就是开头的符号判断，其他正常模拟即可。

三.机器翻译

链接：https://ac.nowcoder.com/acm/problem/16589
来源：牛客网
题意：

这题就是模拟一个固定大小的翻译缓存。
每次遇到单词时，如果缓存里有就直接用；
如果没有，就要去查词典（计数+1），然后把单词放进缓存。
如果缓存满了，就把最早放进去的那个单词挤掉。
最后输出总共查了多少次词典。

解析：这一题我第一眼觉得它是队列题但我想用桶数组试试，但很显然是我想美了，队列方式的做法简单有醒目，桶直接乱套了，所以还是老老实实的用队列，如果对队列知识不熟的可以看看我上一篇文章。

下边为ac代码

#include<bits/stdc++.h> using namespace std; int main() { int M,N,cnt=0; bool a[20000]; queue<int>q; cin >> M >> N; for(int i=1;i<=N;i++) { int t; cin >> t; if(a[t])continue; if(q.size()==M) { auto t=q.front(); a[q.front()]=0; q.pop(); } a[t]=1; q.push(t); cnt++; } cout << cnt; return 0; }