分享牛客算法基礎精選題單題目打卡!!!

目錄

字符串的展開

多項式輸出

機器翻譯 :

鋪地毯 :?

[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;
}