兩天講的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 大概形式↓
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++語言熟練度的區別，對比賽沒什么幫助(不要做太多，當然要提高，不過不要過于鉆研
新聞熱點
疑難解答
