算法基础精选题单模拟 (个人题解)

前言：

从今天开始刷牛客上的这份题单，为暑假的牛客多校集训做准备，题单上一共有237道题，要想在集训开始前刷完难度还是很大的，但我一定会坚持下来，希望在这段时间内我能真正入门算法竞赛。接下来这三道题都与模拟有关，一般出现在比赛的一二题吧（比如蓝桥杯的填空），这三道题写下来我感觉虽然题目难度不是很大，但很需要时间和细心，而且基本要交上好几遍才能过。需要考虑的情况非常多，很容易就少考虑了，所以以后在面对这些题一定要多考虑情况，建议多写几个样例自己跑一下看看对不对（题干给的样例一定不会兼顾所有情况）。

正文：

题单：237题】算法基础精选题单_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网 (nowcoder.com)

A 字符串的展开：

#include<bits/stdc++.h>
using namespace std;
vector<char> v;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	string s;
	cin>>s;
    int cnt;
	for(int i=0;i<s.size();i++){
        cnt=v.size();
		if(s[i]!='-')v.push_back(s[i]);
		else{
            if(s[i-1]=='-'||s[i+1]=='-'){
                v.push_back('-');
				continue;
            }
            if(i==0||i==s.size()-1){
                v.push_back('-');
				continue;
            }
			if(s[i-1]==s[i+1]||abs(s[i+1]-s[i-1])>=40||s[i+1]<=s[i-1]){
				v.push_back('-');
				continue;
			}
			for(int k=s[i-1]+1;k<s[i+1];k++){
				//cout<<k<<endl;
				if(a==3){
					for(int j=1;j<=b;j++){
						v.push_back('*');
					}
				}
				if(a==1&&k>60){
					for(int j=1;j<=b;j++){
						v.push_back(char(k));
					}
				}
				if(a==2&&k>60){
					for(int j=1;j<=b;j++){
						v.push_back(char(k-32));
					}
				}
				if(a!=3&&k<60){
					for(int j=1;j<=b;j++){
						v.push_back(char(k));
					}
				}
			}
			if(c==2){
				reverse(v.begin()+cnt,v.end());
			}
		}
	}
	for(vector<char>::iterator it=v.begin();it!=v.end();it++){
		cout<<*it;
	}
	return 0;
}

以下情况需要重点考虑：

开头和结尾的‘-’，如“-a-d-”
连续的‘-’，如“---”
数字和字母之间的‘-’，如“1-a”
‘-’左侧的字符大于右侧的，如“d-a

剩下的慢慢写就能搞出来了。

B 多项式输出：

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

从前往后依次处理每一项，依次考虑符号、系数、x、x的次数：

如果系数是0，则直接continue；
如果不是第一个非零项，且系数是正的，则输出'+'；如果系数是负的，则无条件输出'-'；
如果系数的绝对值不是1，或者是常数项，则输出系数的绝对值；
如果次数不为0，则输出x
如果次数大于1，则输出次数

C 机器翻译：

、

#include<bits/stdc++.h>
using namespace std;
vector<int> q;
int main(){
	int n,m,ans=0;
	cin>>m>>n;
	while(n--){
		int x;
		cin>>x;
		int flag=1;
		for(vector<int>::iterator it=q.begin();it!=q.end();it++){
			if(*it==x){
				flag=0;
				break;
			}
			//cout<<flag<<endl;
		}
		if(flag){
			ans++;
			if(q.size()==m){
				q.erase(q.begin());
				q.push_back(x);
			}
			else{
				q.push_back(x);
			}
		}
	}
	cout<<ans<<endl;
}

用vector来模拟翻译过程，若vector内没有该词，且大小没到m就直接加进最后，若满了就删去vector首项（最早进入内存）再加进最后。若vector内有该词就直接continue掉。