2016学年寒假集训STL专题

2019-11-10 16:52:22

字体：大中小

来源：转载

供稿：网友

两天讲的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++语言熟练度的区别，对比赛没什么帮助(不要做太多，当然要提高，不过不要过于钻研

上一篇：C# SortedList 键值对排序。

下一篇：UOJ 73 [WC2015]未来程序