本周学习：1.STL简介 2.贪心算法
一
STL简介
一.string 类 表示可变长度的字符序列（比char类型的数组好用的多）
头文件：
string的使用
（1）
初始化
（可以对string类型的变量直接赋值）
string str;
str="abcd";
（2）
string 的访问
1：通过下标访问（类似于字符数组）
#include<bits/stdc++.h>
using namespace std;
int main(){
string str;cin>>str;for(int i=0;i<str.length();i++)cout<<str[i];return 0;}
输出结果
abcd
abcd
特殊：
如果要直接输入和输入整个字符串，只能用cin和cout。
（1）
用循环读取未知数量的string对象
string str；
while（cin>>str）cout<<str<<ebdl;
(2)采用getline()函数
string line;
while(getline(cin,line)cout<<line<<endl;
（2）：使用迭代器访问
（这里的迭代器我们可以当成一个指针）
1：迭代器的定义
string ::iterator it;
::是作用域运算符，A::B表示作用域A中的名称B，A可以是名字空间、类、结构
具体使用：
#include<bits/stdc++.h>
using namespace std;
int main(){
string str="abcd";for(string::iterator it = str.begin();it!=str.end();it++)cout<<*it;return 0;}
(3)
1.
empty()函数：判断string对象是否为空，返回一个布尔值
string str;
cin>>str;
if(!str.empty())//如果str不为空，就输出str。cout<<str<<endl;
size（）函数
返回string对象的长度
string str;
cin>>str;
if(str.size()==5)//如果长度等于5就输出strcout<<str<<endl;
3
比较string对象
大小关系按照字典顺序定义并区分大小写字母
string s1="hello";
string s2="hello world";//s2>s1
string s3="Hello";//s3<s1,s3<s2
4
string对象的连接
string s1="hello",s2="world,s3;
s3=s1;
s3=s1+s2;
二：
栈（Stack）
（先进后出，只能操作最顶端的元素）
1；如何定义一个栈
stack<data_type>stack_name
例如：stacks;
2:
栈的操作：
empty（） 返回bool型，表示栈内是否为空（s.empty()）
size() 返回栈内元素的个数（s.size()）
top() 返回栈顶元素值（s.top（））
pop() 移除栈顶元素（s.pop()）
push(data_type a) 向栈内压入一个元素（s.push（a））
三
队列（queue）
（先进先出）
1；如何定义一个队列
queue<data_type>queue_name
例如：queues;
2:
栈的操作：
empty（） 返回bool型，表示queue是否为空（s.empty()）
size() 返回queue元素的个数（s.size()）
front () 返回queue内的下一个元素（s.front()）
back() 返回queue内的最后一个元素（s.back()）
pop() 移除queue中的一个元素（s.pop()）
push(data_type a) 向queue压入一个元素（s.push（a））
四
动态数组 Vector
1:
vector 简单应用
定义：vector <data_type> vector_name;
如：vector v;
操作：
empty() – 返回bool型，表示vector是否为空 (v.empty() )
size() – 返回vector内元素个数 (v.size() )
push_back(data_type a) 将元素a插入最尾端
pop_back() 将最尾端元素删除
v[i] 类似数组取第i个位置的元素(v[0] )
五：
sort
头文件: #include
sort(begin, end);
sort(begin, end, cmp);
例：
int num[] = {
1,5,6,2,9};1) sort(num, num + 5);//默认从小到大排序num[] = {1,2,5,6,9};
2) bool cmp(int a, int b){
return a > b;
}
sort(num, num + 5, cmp); //num[] = {9,6,5,2,1};
提示：sort函数默认为升序排列；如果要降序排列，要定义一个函数来完成
bool cmp(int a,int b)return a>b;//降序排列
六
怎么随级产生一个数
rand函数用于产生一个随机数
头文件 : #include < cstdlib >
该算法需要一个起始值，称为种子，以生成数字。如果没有给出一个种子，那么它将在每次运行时产生相同的数字流。
（由此可见，我们需要再给出一个种子）
利用srand函数来实现
int main()
{
index c[100];srand( time(0) );//系统的时间for (int i = 0 ; i < 100 ; ++i ){
c[i].a = rand()%10 ; c[i].b = rand()%10 ;}sort( c , c+100 , cmp );for (i = 0 ; i < 100 ; ++i ){
cout<<c[i].a <<" "<<c[i].b <<endl;}return 0;
}小提示：
我们使用rand的函数该怎么控制随机的大小呢
产生一定范围随机数的通用表示公式
要取得[a，b)的随机整数，使用(rand() % (b-a))+ a;
要取得[a，b]的随机整数，使用(rand() % (b-a+1))+ a;
要取得(a，b]的随机整数，使用(rand() % (b-a))+ a + 1;
通用公式：a+ rand()%n；其中的a是起始值，n是整数的范围。
七 优先队列（priority_queue）
(依照元素的权值排列，权值最高的排在前面，但其他部分不一定是按大小排列，只保证最前面的是最大的）
头文件: #include
定义：priority_queue <data_type> priority_queue_name;
如：priority_queue q;
操作：
q.push(elem) 将元素elem置入优先队列
q.top() 返回优先队列的下一个元素
q.pop() 移除一个元素
q.size() 返回队列中元素的个数
q.empty() 返回优先队列是否为空
八 去重unique
该函数的作用是“去除”容器或者数组中相邻元素的重复出现的元素!
这里的去除并非真正意义的erase，而是将重复的元素放到容器的末尾，返回值是去重之后的尾地址。
unique针对的是相邻元素，所以对于顺序顺序错乱的数组成员，或者容器成员，需要先进行排序，sort().
int main()
{
int a[100];int t, n;scanf("%d",&n);for(int i = 0; i < n; i++){
scanf("%d",&a[i]);}t = unique(a,a+n)-a;//求出不重复元素的个数for(int i = 0; i < t; i++){
printf("%d ",a[i]);}return 0;
}九： 生成排列
头文件: #include
bool next_permutation(begin, end);
改变区间内元素的顺序，产生下一个排列。
bool prev_permutation(begin, end);
产生前一个排列。
end为最后一个元素的下一个位置。
upper_bound 和 lower_bound
upper_bound(begin, end, value);
返回>value的元素的第一个位置。
lower_bound(begin, end, value);
返回>=value的元素的第一个位置。
num[] = {1,2,2,3,4,5};
lower_bound(num, num + 6, 2)为num + 1
upper_bound(num, num + 6, 2)为num + 3
十： set与multset
set 和 multiset会根据特定的排序准则，自动将元素排序，两者的不同之处在于multiset可以允许元素重复而set不允许元素重复。
头文件: #include
定义：set <data_type> set_name;
如：set s;//默认由小到大排序
如果想按照自己的方式排序，可以重载小于号。
struct new_type{int x, y;bool operator < (const new_type &a)const{if(x != a.x) return x < a.x;return y < a.y;}
}
操作：
s.insert(elem) – 安插一个elem副本，返回新元素位置。
s.erase(elem) – 移除与elem元素相等的所有元素，返回被移除 的元素个数。
s.erase(pos) – 移除迭代器pos所指位置上的元素，无返回值。
s.clear() – 移除全部元素，将整个容器清空。
s.size() – 返回容器大小。
s.empty() – 返回容器是否为空。
s.count(elem) – 返回元素值为elem的元素的个数。
s.lower_bound(elem) – 返回 元素值>= elem的第一个元素位置。
s.upper_bound(elem) – 返回元素值 > elem的第一个元素的位置。
以上位置均为一个迭代器。
s.begin() – 返回一个双向迭代器，指向第一个元素。
s.end() – 返回一个双向迭代器，指向最后一个元素的下一 个位置
迭代器举例：
multiset :: iterator pos;
for(pos = s.begin(); pos != s.end(); pos++)
… …
十一：map与multimap
所有元素都会根据元素的键值自动排序，map的所有元素都是pair，pair的第一个元素被视为键值，第二个元素为实值。map不允许两个元素有相同的键值，但multimap可以。
头文件: #include
操作：
m.size() 返回容器大小
m.empty() 返回容器是否为空
m.count(key) 返回键值等于key的元素的个数
m.lower_bound(key) 返回键值等于key的元素的第一个可安插 的位置
m.upper_bound(key) 返回键值等于key的元素的最后一个可安 插的位置
m.begin() 返回一个双向迭代器，指向第一个元素。
m.end() 返回一个双向迭代器，指向最后一个元素的下一个 位置。
m.clear() 讲整个容器清空。
m.erase(elem) 移除键值为elem的所有元素，返回个数，对 于map来说非0即1。
m.erase(pos) 移除迭代器pos所指位置上的元素。
直接元素存取：
m[key] = value；
查找的时候如果没有键值为key的元素，则安插一个键值为key的新元素，实值为默认(一般0)。
m.insert(elem) 插入一个元素elem
a)运用value_type插入
map<string, float> m;
m.insert(map<string, float>:: value_type (“Robin”, 22.3));
b) 运用pair<>
m.insert(pair<string, float>(“Robin”, 22.3));
c) 运用make_pair()
m.insert(make_pair(“Robin”, 22.3));
十二：
一些小提示
#include<bits/stdc++.h>using namespace std;int main()
{
sync_with_stdio(false);....return 0;
}，#include<bits/stdc++.h>
包括了几乎所有要用的头文件
sync_with_stdio(false); 可以加快cin cout 的运行时间
#define 宏定义
#include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。#define pb push_back#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)#define mp make_pairusing namespace std;可读性变差，但能加快写代码的速度。
二：贪心算法
（必用到排序）
将一个大问题分成几个小问题，小问题中寻找最优解（局部最优）合到一起大问题也是最优。
1：怎么用贪心
（1）：查看这个题是否能用贪心的策略
（2） 选择贪心准则（是选用金钱，质量，大小，性价比等）
例
#include<bits/stdc++.h>
using namespace std;
struct load
{
int index;int w;
}box[10005];
bool cmp (load a,load b)
{
return a.w<b.w;
}
int main ()
{
int c,n,x[10000];cin>>c>>n;memset(box,0,sizeof(box));memset(x,0,sizeof(x));for(int i=1;i<=n;i++){
cin>>box[i].w;box[i].index=i;}stable_sort(box,box+n+1,cmp);if(box[1]>c)cout<<"no answer"<<endl;int i;for(i=1;i<=n&&box[i].w<=c;i++){
x[box[i].index]=1;c-=box[i].w;}cout<<i-1<<endl;for(int i=1;i<=n;i++)if(x[i])cout<<i;cout<<endl;return 0;
}本周学习感受
学习了很多新知识，也感受到了ACM的难度，不像我想象中的那样简单。但我依然很喜欢这一课程。虽然班里就我自己一个人选这门课，但我如果不选，我以后绝对会后悔。说下这门课吧，给我带来了不小的压力，我感觉这才是真正的大学，我也是想真正学点知识，不为别的，就为了让自己变得 更好。这门课也让我感受到绩点高不一定是真学霸，我还有很多不足等我去弥补。我现在有一种心理，就是怕自己做不了一个题，这来源于我实力的 不足。接下来，我必须拿出比其他所有科目的努力就完成ACM课。很有压力，但也有动力。努力让自己变得更好。