关于STL的一些学习，发现STL现在越来越重要了
背景：首先由于我不擅长STL运用，所以专门学习了一下，所以将的也会比较肤浅了点，期待您的批阅。
1）set (集合) ：这是微软帮助文档中对集合（set）的解释： “描述了一个控制变长元素序列的对象（注：set中的key和value是Key类型的，而map中的key和value是一个pair结构中的两个分 量）的模板类，每一个元素包含了一个排序键（sort key）和一个值(value)。对这个序列可以进行查找、插入、删除序列中的任意一个元素，而完成这些操作的时间同这个序列中元素个数的对数成比例关 系，并且当游标指向一个已删除的元素时，删除操作无效。”
而一个经过更正的和更加实际的定义应该是：一个集合（set）是一个容器，它其中所包含 的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集 合中的元素按一定的顺序排列，并被作为集合中的实例。如果你需要一个键/值对（pair）来存储数据，map是一个更好的选择。一个集合通过一个链表来组 织，在插入操作和删除操作上比向量（vector）快，但查找或添加末尾的元素时会有些慢。该集合里存放的数都已经排好序了，并且自动删除了一些重复的元素。
样例操作：
#include<iostream>
#include<set>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
set<string>s;
set<string>::iterator it;
s.insert("apple");
s.insert("appla");
s.insert("basjk");
s.insert("appje");
s.insert("apale");
s.insert("aaple");
s.insert("abple");
s.insert("akple");
it=s.begin();
while(it!=s.end()){
cout<<*it<<" "<<endl;
it++;
}
return 0;
}
输入结果是：
aaple
abple
akple
apale
appje
appla
apple
basjk
vector的介绍：
构造有四种方式：
- 无参数 - 构造一个空的vector,
- 数量(num)和值(val) - 构造一个初始放入num个值为val的元素的Vector
- vector(from) - 构造一个与vector from 相同的vector
-
迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).
任意以上一种都可以。
例如：vector<int >s( 5 ,21 ) ,这样就定义了一个包含5个21的vector；
assign函数
语法:void assign( input_iterator start, input_iterator end ); void assign( size_type num, const TYPE &val );
assign() 函数要么将区间[start, end)的元素赋到当前vector,或者赋num个值为val的元素到vector中.这个函数将会清除掉为vector赋值以前的内容.
at函数
语法:TYPE at( size_type loc );
at() 函数 返回当前Vector指定位置loc的元素的引用. at() 函数 比 [] 运算符更加安全, 因为它不会让你去访问到Vector内越界的元素. 例如, 考虑下面的代码:
vector<int> v( 5, 1 ); for( int i = 0; i < 10; i++ ) { cout << "Element " << i << " is " << v[i] << endl; }这段代码访问了vector末尾以后的元素,这将可能导致很危险的结果.以下的代码将更加安全:vector<int> v( 5, 1 ); for( int i = 0; i < 10; i++ ) { cout << "Element " << i << " is " << v.at(i) << endl; }取代试图访问内存里非法值的作法,at() 函数能够辨别出访问是否越界并在越界的时候抛出一个异常.
-
back 函数
语法:TYPE back();
back() 函数返回当前vector最末一个元素的引用.例如:
vector<int> v; for( int i = 0; i < 5; i++ ) { v.push_back(i); } cout << "The first element is " << v.front() << " and the last element is " << v.back() << endl;这段代码产生如下结果:
The first element is 0 and the last element is 4
相关内容: front().
begin 函数
语法:iterator begin();
begin()函数返回一个指向当前vector起始元素的迭代器.例如,下面这段使用了一个迭代器来显示出vector中的所有元素:
vector<int> v1( 5, 789 ); vector<int>::iterator it; for( it = v1.begin(); it != v1.end(); it++ ) cout << *it << endl;
相关内容: end().
capacity 函数
语法:size_type capacity();
capacity() 函数 返回当前vector在重新进行内存分配以前所能容纳的元素数量.
clear 函数
语法:void clear();
clear()函数删除当前vector中的所有元素.
empty 函数
语法:bool empty();
如果当前vector没有容纳任何元素,则empty()函数返回true,否则返回false.例如,以下代码清空一个vector,并按照逆序显示所有的元素:
vector<int> v; for( int i = 0; i < 5; i++ ) { v.push_back(i); } while( !v.empty() ) { cout << v.back() << endl; v.pop_back(); }相关内容: size()
end 函数
语法:iterator end();
end() 函数返回一个指向当前vector末尾元素的下一位置的迭代器.注意,如果你要访问末尾元素,需要先将此迭代器自减1.
来源：(http://blog.sina.com.cn/s/blog_66ced15f0100hu9e.html) - C++ STL Vector_老虎_晓茗_新浪博客相关内容: begin()
erase 函数
语法:iterator erase( iterator loc ); iterator erase( iterator start, iterator end );
erase函数要么删作指定位置loc的元素,要么删除区间[start, end)的所有元素.返回值是指向删除的最后一个元素的下一位置的迭代器.例如: // 创建一个vector,置入字母表的前十个字符 vector<char> alphaVector; for( int i=0; i < 10; i++ ) alphaVector.push_back( i + 65 ); int size = alphaVector.size(); vector<char>::iterator startIterator; vector<char>::iterator tempIterator; for( int i=0; i < size; i++ ) { tartIterator = alphaVector.begin(); alphaVector.erase( startIterator ); // Display the vector for( tempIterator = alphaVector.begin(); tempIterator != alphaVector.end(); tempIterator++ ) cout << *tempIterator; cout << endl; }这段代码将会显示如下输出:
BCDEFGHIJ CDEFGHIJ DEFGHIJ EFGHIJ FGHIJ GHIJ HIJ IJ J
相关内容: pop_back().
front 函数
语法:TYPE front();
front()函数返回当前vector起始元素的引用
相关内容: back().
get_allocator 函数
语法:allocator_type get_allocator();
get_allocator() 函数返回当前vector的内存分配器.
insert 函数
语法:iterator insert( iterator loc, const TYPE &val ); void insert( iterator loc, size_type num, const TYPE &val ); void insert( iterator loc, input_iterator start, input_iterator end );
insert() 函数有以下三种用法:
- 在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器,
- 在指定位置loc前插入num个值为val的元素
- 在指定位置loc前插入区间[start, end)的所有元素 .
举例:
这段代码将显示:
max_size() 函数返回当前vector所能容纳元素数量的最大值(译注:包括可重新分配内存).
pop_back()函数删除当前vector最末的一个元素,例如:
这段代码将显示以下输出:
push_back()添加值为val的元素到当前vector末尾
rbegin函数返回指向当前vector末尾的逆迭代器.(译注:实际指向末尾的下一位置,而其内容为末尾元素的值,详见逆代器相关内容)
rend()函数返回指向当前vector起始位置的逆迭代器.
reserve()函数为当前vector预留至少共容纳size个元素的空间.(译注:实际空间可能大于size)
resize() 函数改变当前vector的大小为size,且对新创建的元素赋值val
size() 函数返回当前vector所容纳元素的数目
相关内容: empty()
swap()函数交换当前vector与vector from的元素
//创建一个vector,置入字母表的前十个字符 vector<char> alphaVector; for( int i=0; i < 10; i++ ) alphaVector.push_back( i + 65 ); //插入四个C到vector中 vector<char>::iterator theIterator = alphaVector.begin(); alphaVector.insert( theIterator, 4, 'C' ); //显示vector的内容 for( theIterator = alphaVector.begin(); theIterator != alphaVector.end(); theIterator++ ) cout << *theIterator;
CCCCABCDEFGHIJ
max_size 函数
语法:
size_type max_size();
pop_back
语法:
void pop_back();
vector<char> alphaVector; for( int i=0; i < 10; i++ ) alphaVector.push_back( i + 65 ); int size = alphaVector.size(); vector<char>::iterator theIterator; for( int i=0; i < size; i++ ) { alphaVector.pop_back(); for( theIterator = alphaVector.begin(); theIterator != alphaVector.end(); theIterator++ ) cout << *theIterator; cout << endl; }
ABCDEFGHI ABCDEFGH ABCDEFG ABCDEF ABCDE ABCD ABC AB A
相关内容: erase().
push_back 函数
语法:
void push_back( const TYPE &val );
rbegin 函数
语法:
reverse_iterator rbegin();
rend 函数
语法:
reverse_iterator rend();
reserve 函数
语法:
void reserve( size_type size );
resize 函数
语法:
void resize( size_type size, TYPE val );
size 函数
语法:
size_type size();
swap 函数
语法:
void swap( vector &from );
HDU 1271（整数对 经典！）
题目大意：
所以现在小希希望你编写一个程序，来帮助她找到尽可能多的解。
例如，Gardon想的是A=31,B=3 告诉小希N=34，
小希除了回答31以外还可以回答27（27+7=34）所以小希可以因此而得到一个额外的糖果。
对于每个输入的N，输出所有符合要求的解（按照大小顺序排列）如果没有这样的解，输出"No solution."
题目分析：第一次，我的思路是从一半开始枚举，发现这样超时了
TLE代码：
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int s[1000];
inline int solve(int x){
int k,ans,i,j;
int c,sum,t,times=1;
while(c){
c/=10;
k++;
}
int xx=pow(10,k-2);
for(i=xx;i<=x;i++){
k=0; c=i;
while(c){
c/=10;
k++;
}
for(j=1;j<=k;j++){
c=i;
sum=0;
int w=(int)pow(10,k-j);
if(j==1){
sum=c%w;
}
if(j==k){
sum=c/10;
}
if(j!=k&&j!=1){
t=c%w;
int p=c/w;
p/=10;
p=p*((int)pow(10,k-j));
sum=p+t;
}
if(sum+i==x){
s[times++]=i;
}
}
}
return times-1;
}
int main(){
int x,t,i;
while(scanf("%d",&x),x){
t=solve(x);
if(t==0)
printf("No solution.\n");
else{
for(i=1;i<=t;i++)
printf("%d ",s[i]);
printf("\n");
}
}
return 0;
}
后来看了一下解题报告，后来终于理解了，现在让我来说说这题的做法跟规律吧{^_^}
首先假设X的第k位拿走，然后加上加上X的和正好等于N！
这样的话 我们可以把X 分解成：X= a+b * 10^k +c * 10^( k+1 ); 这里特别强调一下， a代表的是比第k位后面的低位数子，可能是多位，b仅仅代表一个数值，即你选择拿开的那位数，c代表的是比k位高的高位数字，例如：12345 您想拿走3的话 这时候a=45,c=12,b=3; 然后拿走之后就会组合成另一个数：Y=a + c * 10^k; 然后X+Y=2 * a + b * 10 ^k +11 * c * 10^k;
现在如果N=X+Y；他必定满足上面那种结构！所以我们考虑这种结构特征就可以了，首先上述表达式的低位是2*a 可能发生进位！
所以b的值可能是10，但是 都不影响c的值， 这个时候只需要分两种不同的b的情况，来求出a，然后验证一下 是不是等于N就可以了！
AC代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
void solve(int x,set<int> &result){
int k,high,b2,a;
int c,sum,b1;
for(k=1;k<=x;k*=10){
high=x/k;
c=high/11;
c*=k;
b1=high%11;
if((b1!=0||c!=0)&&b1<10){
b1*=k;
a=(x-b1-11*c)/2;
if(2*a+b1+11*c==x)
result.insert(a+b1+c*10);
}
b2=high%11-1;
if((b2!=0||c!=0)&&b2>=0){
b2*=k;
int a2=(x-b2-11*c)/2;
if(x==2*a2+b2+11*c)
result.insert(a2+b2+10*c);
}
}
}
int main(){
int x,i;
while(cin>>x,x){
set<int>result;
//set结构不仅可以排序，而且可以去除重复的
//下次要多多学习，总结！
solve(x,result);
if(result.empty()){
printf("No solution.\n");
}
else{
set<int>::iterator it=result.begin();
printf("%d",*it);
while(++it!=result.end())
printf(" %d",*it);
printf("\n");
}
}
return 0;
}
还有一种代码思路一样
AC代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int s[1000],times;
int cmp(int x,int y){
return x<y;
}
int solve(int x){
int k,high,b2,a;
int c,sum,b1;
times=0;
for(k=1;k<=x;k*=10){
high=x/k;
c=high/11;
c*=k;
b1=high%11;
if((b1!=0||c!=0)&&b1<10){
b1*=k;
a=(x-b1-11*c)/2;
if(2*a+b1+11*c==x)
s[++times]=a+b1+c*10;
}
b2=high%11-1;
if((b2!=0||c!=0)&&b2>=0){
b2*=k;
a=(x-b2-11*c)/2;
if(x==2*a+b2+11*c)
s[++times]=a+b2+10*c;
}
}
return 0;
}
int main(){
int x,t,i;
while(scanf("%d",&x)&&x){
solve(x);
if(times==0){
printf("No solution.\n");
}
else{
sort(s+1,s+1+times,cmp);
printf("%d",s[1]);
for(i=2;i<=times;i++){
if(s[i]!=s[i-1])
printf(" %d",s[i]);
}
printf("\n");
}
}
return 0;
}
题目总结：今后一定要大量深入学校STL函数！还有这题的去除重复不能忘记，同时要深刻认识本题的思路，太巧妙，强大了
HDU 1215（七夕节）
题目大意：您的编号N的因子和就是您的另一半的编号！数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).
题目分析：其实是水题！一开始想复杂了，后来想想看，我们只要找i :1->sqrt(N)然后用通过N/i 找到比sqrt(N)大的满足要求的因子！
这样最坏情况下也才500000*3000最多！还是不会超时的
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int solve(int x){
int i,j,sum=0;
double tempt=sqrt(x);
for(i=2;i<=tempt;i++){
if(x%i==0){
sum+=i;
int t=x/i;
if(t!=i){
sum+=t;
//是在里面判断比sqrt(N)大的因子合法与否！
}
}
}
sum+=1;
return sum;
}
int main(){
int cas,t,ans;
scanf("%d",&cas);
while(cas--){
scanf("%d",&t);
ans=solve(t);
printf("%d\n",ans);
}
return 0;
}
HDU 2504（又见GCD）
题目：
有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。
刚刚开始的时候写错了，没考虑太多，直接a/b如果不等于1 就a/b-1然后乘以b！
其实枚举就行了：
#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int x,int y){
int c;
if(x<y){
c=y;
y=x%y;
x=c;
}
while(y){
c=y;
y=x%y;
x=c;
}
return x;
}
int main(){
int a,b,c,flag,cas;
cin>>cas;
while(cas--){
scanf("%d %d",&a,&b);
for(int i=2;;i++){
if(gcd(a,i*b)==b){
flag=i;
break;
}
}
printf("%d\n",flag*b);
}
return 0;
}
总结：唉，汗颜！下次细心！UP!
HDU 1722（分蛋糕 规律性题目）
一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食.
题目分析：p+q-gcd(p+q)
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int a,int b){
int c;
if(a<b){
c=a; a=b;
b=c;
}
while(b){
c=b;
b=a%b;
a=c;
}
return a;
}
int main(){
int x,y;
while(~scanf("%d %d",&x,&y)){
printf("%d\n",x+y-gcd(x,y));
}
return 0;
}
猴子分桃（很有趣的规律题）
题目大意：老猴子辛苦了一辈子，给那群小猴子们留下了一笔巨大的财富——一大堆桃子。
老猴子决定把这些桃子分给小猴子。
第一个猴子来了，它把桃子分成五堆，五堆一样多，但还多出一个。它把剩下的一个留给老猴子，自己拿走其中的一堆。
第二个猴子来了，它把桃子分成五堆，五堆一样多，但又多出一个。它把多出的一个留给老猴子，自己拿走其中的一堆。
后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。
这里有n只小猴子，请你写个程序计算一下在开始时至少有多少个桃子，以及最后老猴子最少能得到几个桃子。
题目分析:其实题目不是很难，但是我很悲剧的是，因为学校服务器的问题，害我WA了20多次，后来都别的网站上提交，1Y就过了！
这里表示非常不淡定。。。
废话不说了让我们看题目吧：假设有X个桃子，第一次把X个桃子分成5份，恰好多了1，然后拿走一份！再这里，您应该想到借他4个不就正好5份了麽？然后每次都不是5份了麽？最后当前猴子拿走的也没多拿不是麽？举个例子说明一下吧，假设有5只猴子，第一次每份
（X-1）/5；如果我们借给他4个，每份不就是（X+4）/5吗？然后您会发现，（X+1）/5=（X-1）/5+1；每次都是如此，然后每次都能被5整除，这很显然，所以您应该懂了吧～{^_^}X=5^n-4 老猴子得到=n+（X+4）*(4/5)^n-4（您得还我的呀！对吧 嘿嘿）
代码+部分注释：
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
int main(){
long long total_num,old_num;
int n;
while(cin>>n,n){
total_num=pow(5,n)-4;
old_num = n + (total_num+4)*(pow(0.8,n))-4;
cout<<total_num<<" "<<old_num<<endl;
}
return 0;
}
HDU 1713（相遇周期）求分数的最小公倍数！
题目分析：题目输入c1/t1 c2/t2 ,也就是速度的分数形式，转换成：c1*t2/(t1*t2), c2*t1/( t1*t2 ); 这时候我们只需要求出分子的最小公倍数k,然后k/( t1*t2 )就是题目求的周期
代码+部分注释：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
__int64 gcd(__int64 a,__int64 b){
__int64 c;
if(a<b){
c=a; a=b;
b=c;
}
while(b){
c=b;
b=a%b;
a=c;
}
return a;
}
__int64 min_times(__int64 x1,__int64 x2){
__int64 c=gcd(x1,x2);
return x1*x2/c;
}
int main(){
__int64 cas,c1,c2,t1;
__int64 t2,p,k,m,n,h;
cin>>cas;
while(cas--){
scanf("%I64d/%I64d",&c1,&t1);
//在这里提醒一下，用long long型的过不了！
//因为这个WA的好多次！
scanf("%I64d/%I64dd",&c2,&t2);
k=t1*t2;
m=t2*c1;
n=t1*c2;
p=min_times(m,n);
h=gcd(p,k);
if(h==k){
printf("%I64d\n",p/h);
}
else{
printf("%I64d/%I64d\n",p/h,k/h);
}
}
return 0;
}
HDU 2138(求素数的个数，容易超时！提醒自己)
题目分析：这里不能打表，然后要用到求素数的 优化!也就是我 前面一篇文章提到的。代码直接注释一下就可以了 还是看代码吧
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
bool prime(int x){
if(x%2==0&&x!=2)
return false;
//偶数肯定不是素数！
double k=sqrt(x);
//切记这里一定要用k记录他的开方
//如果写成for(int i=3;i*i<=x;i+=2)
//就超时！
for(int i=3;i<=k;i+=2)//枚举奇数！
if(x%i==0)
return false;
return true;
}
int main(){
int cas,n,flag,ans=0;
while(~scanf("%d",&cas)){
ans=0;
while(cas--){
scanf("%d",&n);
if(prime(n))
ans++;
}
printf("%d\n",ans);
}
return 0;
}
ZOJ 3498(Javabeans)
题目分析：把每个盒子看成集合。有n个集合，分别有1…n个元素。具体每种集合有多少个是没意义的，因为我们可以把具有相同元素的集合同时操作，所以我们可以用集合的种类代替集合的个数。假设，每次选取k个集合。从这k个集合里拿东西，则这k个集合拿过之后还是k个不同的集合（有可能有一个成空集），所以至少还有(k-1)个不同的集合，而除这k个外还有(n-k)个不同的集合。所以拿完之后不同集合的个数至少变为了r=max(k-1,n-k)。考虑当n是偶数时当k=n/2时，r取最小值，max(k-1,n-k)=n/2，当n为奇数时，k=(n+1)/2时,r取最小值max(k-1,n-k)=(n-1)/2。这个最小值是剩余集合数的一个下界。
其实这个下界是可以达到的：
n是偶数时，从元素个数不少于n/2的全部集合里都拿n/2个，则，剩余集合元素个数变为了1,2……n/2，问题规模缩小了一半。
n是奇数时，从元素个数不少于(n+1)/2的集合里都拿(n+1)/2个，则剩余集合元素个数变为了1,2,…(n-1)/2，问题规模也缩小了一半。
而在c语言中，除以2是下取整的，所以无论n为奇数还是偶数，一次操作之后集合个数至少变成了n/2,并且有办法可以达到这个最小值。
于是，最少拿的次数就是每次把n不断除以2，除到0为止。即n的2进制表示
代码：
#include<iostream>
#include<cstdio>
typedef long long ll;
int main(){
ll n,ans,times;
scanf("%lld",×);
while(times--){
scanf("%lld",&n);
ans=0;
while(n){
ans++;
n/=2;
}
printf("%lld\n",ans);
}
return 0;
}
HDU 1492（求一个数的倍数）
题目大意：
首先 2，3，5，7是互质的！可以把 N 写成 (2^a)*(3^b)*(5^c)*(7^d) （a,b,c,d >= 0）!
每次从a ,b,c,d中选出一组数就是一个因数
举例说明一下：12=2^2*3
因为1也是他的倍数！2能够构成的倍数有（1，1*2,2*2） 3构成的倍数有（1，1*3）
也就是把（a+1）*(b+1)*....(n+1)就是能整除他的个数
代码+部分注释：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[5];
long long times[5];
int pricount(long long num){
pri[1]=2;
pri[2]=3;
pri[3]=5;
pri[4]=7;
memset(times,0,sizeof(times));
long long i;
for(i=1;i<=4;i++){
while(num%pri[i]==0){
times[i]++;
num/=pri[i];
}
}
return 0;
}
int main(){
long long n,sum;
long long i;
while(cin>>n,n){
sum=1;
pricount(n);
for(i=1;i<=4;i++)
sum=sum*(times[i]+1);
//注意要+1，上面已经分析了！
cout<<sum<<endl;
}
}