算法模拟类题目解析

前言最近开始偏系统的从简单到难一步步刷算法题先从模拟题开始下边附带题目与连接感兴趣可刷刷也可看看我的思路。一.字符串展开链接https://ac.nowcoder.com/acm/problem/16644来源牛客网题意输入一个字符串含数字、小写字母和减号以及三个参数 p1、p2、p3。当遇到减号“-”时如果它两边都是小写字母或都是数字且右边字符大于左边就进行“展开”把两边之间的所有字符按顺序或逆序填充进去每个字符重复 p2 次p1 控制填充内容小写、大写或星号p3 控制顺序正序或逆序。如果两边是相邻字符如“a-b”则直接删掉减号如果不满足展开条件如“a-d-d”中的第二个减号则保留原减号。解析作为模拟题目很显然我们要做的就是跟着题目意思进行模拟这种题目怕的主要是漏了题目所给条件导致无法ac这个题意已经根据原题进行精简挑出重点但在原题目中需要好好注意提取题目主要意思进行查缺补漏。下边为我的ac代码#includeiostream #includestring #includectype.h #includealgorithm using namespace std; int panduan(char c) { if(c0c9)return 1; else if(cacz)return 2; return 0; } int main() { int p1,p2,p3; cin p1 p2 p3; string s,ans; cin s; ans; for(int i0;is.size();i) { if(s[i]-s[i-1]s[i1]p11i0(panduan(s[i-1])panduan(s[i1]))) { string sub; sub; for(char js[i-1]1;js[i1];j) { for(int k1;kp2;k) subj; } if(p32) reverse(sub.begin(),sub.end()); anssub; continue; } else if(s[i]-s[i-1]s[i1]p11i0(panduan(s[i-1])panduan(s[i1]))) { string sub; sub; for(char jtolower(s[i-1]1);jtolower(s[i1]);j) { for(int k1;kp2;k) subj; } if(p32) reverse(sub.begin(),sub.end()); anssub; continue; } else if(s[i]-s[i-1]s[i1]p12i0(panduan(s[i-1])panduan(s[i1]))) { string sub; sub; for(char jtoupper(s[i-1]1);jtoupper(s[i1]);j) { for(int k1;kp2;k) subj; } if(p32) reverse(sub.begin(),sub.end()); anssub; continue; } else if(s[i]-s[i-1]s[i1]p13i0(panduan(s[i-1])panduan(s[i1]))) { for(char js[i-1]1;js[i1];j) { for(int k1;kp2;k) ans*; } continue; } anss[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代码#includebits/stdc.h using namespace std; int main() { int n; cin n; vectorinta(n5,0); int first0; for(int i1;in1;i) { cin a[i]; if(a[i]0)continue; else if(a[i]0first) { cout ; } else if(a[i]0) { cout -; }if(in1||abs(a[i])!1) cout abs(a[i]); if(a[i]0||a[i]0)first1; if(n-i11) cout x^ n-i1; else if(n-i11) { cout x; } } return 0; }其实这题问题并不多主要注意的就是开头的符号判断其他正常模拟即可。三.机器翻译链接https://ac.nowcoder.com/acm/problem/16589来源牛客网题意这题就是模拟一个固定大小的翻译缓存。每次遇到单词时如果缓存里有就直接用如果没有就要去查词典计数1然后把单词放进缓存。如果缓存满了就把最早放进去的那个单词挤掉。最后输出总共查了多少次词典。解析这一题我第一眼觉得它是队列题但我想用桶数组试试但很显然是我想美了队列方式的做法简单有醒目桶直接乱套了所以还是老老实实的用队列如果对队列知识不熟的可以看看我上一篇文章。下边为ac代码#includebits/stdc.h using namespace std; int main() { int M,N,cnt0; bool a[20000]; queueintq; cin M N; for(int i1;iN;i) { int t; cin t; if(a[t])continue; if(q.size()M) { auto tq.front(); a[q.front()]0; q.pop(); } a[t]1; q.push(t); cnt; } cout cnt; return 0; }这边注意点不多也没有队列是否为空的判断用队列直接模拟即可