2016學年寒假集訓STL專題

2019-11-10 18:58:41

字體：大中小

來源：轉載

供稿：網友

兩天講的STL專題contest以及補題節選

Ugly Numbers UVA - 136 描述：包括1 在內的僅由2，3，5為因數組成的數字，稱為丑數，前11個丑數為1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 問題：求第1500個丑數

思路：

可以從/2,/3,/5最后不為0入手，顯然是效率較低的算法。

另外可以得出所有的丑數都是由2，3，5拓展而來，代碼實現 ①下一個丑數是列表中某個數乘2或3或5而來 ②每次得出丑數更新d2 d3 d4;

int main(int argc, char *argv[]){ ll a[1500]; a[0]=1,a[1]=2,a[2]=3,a[3]=5; ll end=1,d2=0,d3=0,d5=0; while(1) { while(a[d2]*2<=a[end]) d2++; while(a[d3]*3<=a[end]) d3++; while(a[d5]*5<=a[end]) d5++; ll x=min(a[d2]*2,min(a[d3]*3,a[d5]*5)); a[++end]=x; if(end==1500) break; } cout<<a[end-1]<<endl; return 0;}

H - 排列2 HDU - 1716

描述：輸入 1 2 3 4 1 1 2 3 0 1 2 3 0 0 0 0 生成全排列：這里寫圖片描述不能有任何多余的空格！思路：處理這種情況的很多次了，但還是會出錯生成全排列的函數next_permutation(start,end);//PRev_permutation 大概形式↓

int main(int argc, char *argv[]){ int a[4]={1,2,3,4}; do{ for(int i=0;i<3;i++) printf("%d ",a[i]); printf("%d/n",a[4]); }while(next_permutation(a,a+4)); for(int i=0;i<4;i++) printf("%d ",a[i]); printf("/n"); return 0;}

I - Misha and Changing Handles CodeForces - 501B

描述：更新handle（我也不知道是什么）輸出順序隨意 Input 5 Misha ILoveCodeforces Vasya Petrov Petrov VasyaPetrov123 ILoveCodeforces MikeMirzayanov Petya Ivanov Output 3 Petya Ivanov Misha MikeMirzayanov Vasya VasyaPetrov123 思路：純屬水題，本來就是拿來熟悉一下STL用的暴力遍歷 if（find） do{…}

int main(int argc, char *argv[]){ int n; string s1,s2; vector<string> f,l; cin>>n; while(n--) { cin>>s1>>s2; if(!l.empty()&&find(l.begin(),l.end(),s1)!=l.end()) { *find(l.begin(),l.end(),s1)=s2; } else { f.push_back(s1); l.push_back(s2); } } cout<<f.size()<<endl; for(int i=0;i<f.size();i++) cout<<f[i]<<" "<<l[i]<<endl; return 0;}

J - USACO ORZ HDU - 4277

描述： T組數據，n個木棍，把n個木棍分為三份，拿來做一個三角形問有多少種方法思路： DFS 這道題還是不會，搜索是弱項，需要好好吸收。注意的地方太多了，見代碼

#include <iostream>#include <cstdio>#include <sstream>#include <set>#include <bitset> #include <queue> #include <stack>#include <list>#include <vector>#include <map>#include <string>#include <cstring>#include <cmath>#include <cctype>#include <algorithm>using namespace std;typedef long long ll;typedef set<int> Set;typedef vector<int> Vec;typedef set<int>::iterator It;#define mem(s,n) memset(s,n,sizeof(s))int a[20],b[5],n;set<ll> ans;void dfs(int k){ if(k==n+1) { if(b[1]>b[2]||b[2]>b[3]||b[1]+b[2]<=b[3]) return;//剪枝，很重要，減少重復運算 for(int i=1;i<=3;i++) if(b[i]==0) return ; ll m=((ll)b[1]<<20)+b[2];//生成一個獨一無二的數，供標記自己想到的是string，不如這個 if(ans.count(m)) return ; else ans.insert(m); return; } for(int i=1;i<=3;i++) { b[i]+=a[k]; dfs(k+1); b[i]-=a[k];//回溯的過程 }}int main(int argc, char *argv[]){ int kase; cin>>kase; while(kase--) { ans.clear(); mem(b,0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); dfs(1); cout<<ans.size()<<endl; } return 0;}

K - Email Aliases CodeForces - 589A

描述第一行為T組數據，2~T+1行每行電子郵件(A@B)，現統計“等價”的郵件情況

①計算等價情況時，郵件不區分大小寫。 ②后綴為@bmail.com的比較特殊，前面的A中’+’號到@的內容全部可以忽略同時可以忽略‘.’符號如ACM.ICPC.@bmail.com and A.cmIcpc@Bmail.Com是等價的

Input 6 ICPC.@bmail.com p+con+test@BMAIL.COM P@bmail.com a@bmail.com.ru I.cpc@Bmail.Com a+b@bmail.com.ru Output 4 2 ICPC.@bmail.com I.cpc@Bmail.Com 2 p+con+test@BMAIL.COM P@bmail.com 1 a@bmail.com.ru 1 a+b@bmail.com.ru 思路: 想通了把握要點就很簡單，看成A@B 由郵件的唯一性可以找到@ 再得到A 和 B 。得到Ａ時，若有‘＋’則馬上break可以簡化運算思路清晰構造map 見代碼

#include <iostream>#include <cstdio>#include <sstream>#include <set>#include <bitset> #include <queue> #include <stack> #include <list>#include <vector>#include <map>#include <string>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define mem(s,n) memset(s,n,sizeof(s))#define SZ(v) int(v.size())string change(const string &s);int main(int argc, char *argv[]){ int n;cin>>n; string s; map<string,vector<string> > mail;//原來的string存到vector vector的size也用到了標準化的string作為下標存 mail.clear(); while(n--) { cin>>s; mail[change(s)].push_back(s); } cout<<mail.size()<<endl; for(map<string,vector<string> >::iterator it=mail.begin();it!=mail.end();it++) { cout<<it->second.size(); for(int i=0;i<it->second.size();i++) cout<<" "<<it->second[i]; cout<<endl; } return 0;}string change(const string &s){ string login,domain; int pos; for(pos = 0; pos < SZ(s); pos++){ if(s[pos] == '@'){ break; } } for(int i=pos;i<SZ(s);i++) if(isalpha(s[i])) domain+=tolower(s[i]); else domain+=s[i]; if(domain == "@bmail.com") { for(int i=0;i<pos;i++) { if(s[i]=='+') break; if(s[i]=='.') continue; login +=tolower(s[i]); } } else { for(int i=0;i<pos;i++) { if(isalpha(s[i])) login+=tolower(s[i]); else login+=s[i]; } } //cout<<login+domain; return login+domain;}

以上。專題一總結及反思： map用法不熟練 pair同理思路要清晰不能煩躁

和wdk的對話： ①clj大佬說過，水題做翻天還是弱。要做接近自己能力極限的題目。 ②水題如純模擬的題，字符串處理的題目，純考實現，與具體算法無關，這是C++語言熟練度的區別，對比賽沒什么幫助(不要做太多，當然要提高，不過不要過于鉆研

上一篇：不使用臨時變量,實現整數互換

下一篇：hashcode和equals的作用