模拟 枚举

分享牛客算法基础精选题单题目打卡!!!

目录

字符串的展开

多项式输出

机器翻译 :

铺地毯 : 

[NOIP2016]回文日期

---

字符串的展开

原题链接 :  字符串的展开

思路 : 模拟

代码 : 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int p1,p2,p3;
string s;
string func(char a,char b,int p1,int p2,int p3){if(b-a==1) return "";if( ! ((isalpha(a) && isalpha(b) && a<b) ||(isdigit(a) && isdigit(b) && a<b))){return "-";}string ans = "";for(char c = a+1;c<b;c++){for(int i=0;i<p2;i++){ans += c;}}if(p1==2 && isalpha(a)){for(int i=0;i<ans.length();i++){ans[i] = ans[i]-'a'+'A';}}if(p1==3){for(int i=0;i<ans.length();i++){ans[i] = '*';}}if(p3==2){reverse(ans.begin(),ans.end());}return ans;
}
int main(){cin>>p1>>p2>>p3;cin>>s;int n = s.size();string ans = "";for(int i=0;i<n;i++){if(s[i] == '-' && i>0 && i+1<n) ans += func(s[i-1],s[i+1],p1,p2,p3);else{ans += s[i];}}cout<<ans<<endl;
}

多项式输出

题目链接 : 多项式输出

思路 : 模拟多项式展开的过程即可

代码 : 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n , a[110];
int main(){cin>>n;for(int i=0;i<=n;i++)  cin>>a[i];int t = n;//n+1个数string ans = "";for(int i=0;i<=n;i++){if(i==0){if(a[i]==0){t--;continue;}else if(a[i]==1) ans += "x^" + to_string(t);else if(a[i]==-1) ans += "-x^" + to_string(t);else ans += to_string(a[0]) + "x^" + to_string(t);t--;}else if(i==n){if(a[i] > 0) ans += '+'+to_string(a[i]);else if(a[i]<0) ans += to_string(a[i]);}else if(i==n-1){if(a[i] == 0){t--;continue;}else if(a[i] > 0){if(a[i]==1) ans += "+x";else ans += '+' + to_string(a[i]) + "x";}else {if(a[i]==-1) ans += "-x"; else ans += to_string(a[i])+"x";}t--;}else{if(a[i] == 0){t--;continue;}else if(a[i] > 0){if(a[i]==1) ans += "+x^"+to_string(t);else ans += '+' + to_string(a[i])+"x^"+to_string(t);}else {if(a[i]==-1) ans += "-x^"+to_string(t); else ans += to_string(a[i])+"x^"+to_string(t);}t--;}}cout<<ans<<endl;return 0;
}

机器翻译 :

原题链接 : 机器翻译

思路 : 模拟

#include <iostream>
using namespace std;
int vis[1010]; //记录已经在内存空间数字，在内存空间的数字标记为1
int temp[1010]; //每输入一个数据，则将数据放入该数组中。按顺序存放
int tempPos; //记录temp数组的位置
int m; //记录内存空间的大小
int n; //记录文章的长度；int main(void)
{cin >> m >> n;int count = 0; //记录内存空间中的数字个数int cnt = 0; //记录查找字典的次数int num; //记录输入进来的文章int i;for(i = 1; i <= n; i++){cin >> num;if(1 == vis[num]) continue;cnt++;if(count >= m){vis[temp[tempPos-m]] = 0; vis[num] = 1;temp[tempPos++] = num;}else{vis[num] = 1;temp[tempPos++] = num;count++;}}cout << cnt << endl;return 0;
}

铺地毯 : 

原题链接 : 

铺地毯


 

思路 : 直接从小到大枚举每一个可能在(x,y)上面的所有地毯，找到最大的一个即可

代码 : 

#include<iostream>
using namespace std;
int n,xn,yn;
struct st{int a,b,x,y;
}st[10100];
int main(){cin>>n;for(int i=0;i<n;i++){cin>>st[i].a>>st[i].b>>st[i].x>>st[i].y;}cin>>xn>>yn;int ans = 0;for(int i=0;i<n;i++){if(st[i].a<=xn&&st[i].b<=yn&&(st[i].a+st[i].x)>=xn&&(st[i].b+st[i].y)>=yn){ans=i+1;  }}if(ans == 0) cout<<-1<<endl;else cout<<ans<<endl;return 0;
}

[NOIP2016]回文日期

原题链接 : 登录—专业IT笔试面试备考平台_牛客网

 思路 : 枚举两个日期之间的所有日期，找到满足条件的日期，答案加一，最后返回答案即可

代码 : 

#include<iostream>
#include<bits/stdc++.h>using namespace std;
int M[20]= {0,31,0,31,30,31,30,31,31,30,31,30,31};
bool isLeapyear(int y)
{if((y%4==0&&y%100!=0)||y%400==0){return true;}return false;
}
bool check(int y)
{int m,d;m = (y%10)*10+((y/10)%10);d = ((y/100)%10)*10+((y/1000)%10);if(m==0||d==0||m>12){return false;}if(m==2){if(isLeapyear(y)){ M[2]=29;}else if(!isLeapyear(y)){M[2]=28;}}if(d<=M[m]){return true;}else{return false;}
}
int ReYear(int y)
{return (y%10)*1000+((y/10)%10)*100+((y/100)%10)*10+((y/1000)%10);
}
int main()
{int y1,md1;int y2,md2;scanf("%4d%4d",&y1,&md1);scanf("%4d%4d",&y2,&md2);int ans = 0;if(y1!=y2){bool flag;for(int i = y1+1; i<=y2-1 ; i++)//判断两个日期之间的年份{int m,d;//取出该年份对应回文日期的月和日if(check(i)){ans++;}}if(check(y1)&&md1<=ReYear(y1)){ans++;}if(check(y2)&&ReYear(y2)<=md2){ans++;}}else{//在同一年里int m1,d1;//取出y1年份对应回文日期的月和日m1 = (y1%10)*10+((y1/10)%10);d1 = ((y1/100)%10)*10+((y1/1000)%10);if(check(y1)&&ReYear(y1)>=md1&&ReYear(y1)<=md2){ans++;}}cout<<ans<<endl;return 0;
}