集训中学到的方法

学习就该如贪心!!一直向前~!

记录一些会用到并且好用的函数
或者是容易混淆的知识点
持续更新

有关acm中精度的问题:
https://www.cnblogs.com/crazyacking/p/4668471.html

STL的定义方式:

set/stack/queue/vector <int/string> 定义名称;
set有自动排序的功能(从小到大)

set里面用的是平衡二叉搜索树(也就是红黑树)维护

string 字符串名称;
map<string/int, int/string> 名称;

set的迭代器:

set:: iterator it;
这个it是为指针用法
eg:
it = st.begin();
cout << it;
it ++;
for(; it != st.end(); it ++)
{
cout << “ “ <<
it;
}

map的迭代器:

map<string, int> :: iterator mp;
这个mp用法要用mp -> first 或者mp -> second 来表示
eg:
map<string, int> :: iterator it1;
map<string, node> :: iterator it2;
for(it2 = mp.begin(); it2 != mp.end(); it2 ++)
{
cout << it2 -> first << endl;
for(it1 = mp[it2 -> first].count.begin(); it1 != mp[it2 -> first].count.end(); it1 ++)
{
cout << “|—-“ << it1 -> first << “(“ << it1 -> second << “)” << endl;
}
}

嵌套map用法可以为

struct node{
map<string, int> count;
};

map<string, node> mp;

用的时候为:mp[string].count[string] ++;或者一些操作

二分查找–binary_search的用法

头文件 #include <algorithm>

使用方法:

1
2
3
4
5
6
a.函数模板:binary_search(arr[],arr[]+size ,  indx)
b.参数说明:
arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值
c.函数功能: 在数组中以二分法检索的方式查找,若在数组(要求数组元素非递减)中查找到indx元素则真,若查找不到则返回值为假。

lower_bound

查找第一个大于或等于某个元素的位置
使用方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
a.函数模板:lower_bound(arr[],arr[]+size ,  indx):
b.参数说明:
arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值
c.函数功能:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置(注意是地址)。如果所有元素都小于val,则返回last的位置
d.举例如下:
  一个数组number序列为:4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标,则
  /*注意因为返回值是一个指针,所以减去数组的指针就是int变量了*/
  pos = lower_bound( number, number + 8, 3) - number,pos = 0.即number数组的下标为0的位置。
  pos = lower_bound( number, number + 8, 9) - number, pos = 1,即number数组的下标为1的位置(即10所在的位置)。
  pos = lower_bound( number, number + 8, 111) - number, pos = 8,即number数组的下标为8的位置(但下标上限为7,所以返回最后一个元素的下一个元素)。
e.注意:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置,且last的位置是越界的!

upper_bound: 查找第一个大于某个位置的元素的位置

使用方法:

1
2
3
4
5
6
7
8
a.函数模板:upper_bound(arr[],arr[]+size ,  indx):
b.参数说明:
arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值
c.函数功能:函数upper_bound()返回的在前闭后开区间查找的关键字的上界,返回大于val的第一个元素位置
  例如:一个数组number序列1,2,2,4.upper_bound(2)后,返回的位置是3(下标)也就是4所在的位置,同样,如果插入元素大于数组中全部元素,返回的是last。(注意:数组下标越界)
  返回查找元素的最后一个可安插位置,也就是“元素值>查找值”的第一个元素的位置 。

unique函数

类属性算法unique的作用是从输入序列中“删除”所有相邻的重复元素。

该算法删除相邻的重复元素,然后重新排列输入范围内的元素,并且返回一个迭代器(容器的长度没变,只是元素顺序改变了),表示无重复的值范围得结束。

1
2
3
4
// sort words alphabetically so we can find the duplicates
sort(words.begin(), words.end());
vector<string>::iterator end_unique = unique(words.begin(), words.end());
words.erase(end_unique, words.end());

在STL中unique函数是一个去重函数, unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除,是把重复的元素移到后面去了,然后依然保存到了原数组中,然后 返回去重后最后一个元素的地址,因为unique去除的是相邻的重复元素,所以一般用之前都会要排一下序。
若调用sort后,vector的对象的元素按次序排列如下:
sort jumps over quick red red slow the the turtle
下载.png
注意,words的大小并没有改变,依然保存着10个元素;只是这些元素的顺序改变了。调用unique“删除”了相邻的重复值。给“删除”加上引号是因为unique实际上并没有删除任何元素,而是将无重复的元素复制到序列的前段,从而覆盖相邻的重复元素。unique返回的迭代器指向超出无重复的元素范围末端的下一个位置。

注意:算法不直接修改容器的大小。如果需要添加或删除元素,则必须使用容器操作。
Eg:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#include <string>
#include <iterator>
using namespace std;

int main()
{
//cout<<"Illustrating the generic unique algorithm."<<endl;
const int N=11;
int array1[N]={1,2,0,3,3,0,7,7,7,0,8};
vector<int> vector1;
for (int i=0;i<N;++i)
vector1.push_back(array1[i]);

vector<int>::iterator new_end;
new_end=unique(vector1.begin(),vector1.end()); //"删除"相邻的重复元素
assert(vector1.size()==N);

vector1.erase(new_end,vector1.end()); //删除(真正的删除)重复的元素
copy(vector1.begin(),vector1.end(),ostream_iterator<int>(cout," "));
cout<<endl;

return 0;
}

gcd的前缀后缀维护

说到gcd,就不得不提一下
C++11中子代有内置gcd函数,用法是 __gcd(a, b);

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6025

持续更新
PS:暂时不会讲解,先看代码吧,等以后理解透了在讲解
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int gcd(int a,int b){
if(a<b){
int t=a;
a=b;b=t;
}
return b==0?a:gcd(b,a%b);
}
int a[1000005],q[1000005],h[1000005];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
memset(q,0,sizeof(q));
memset(h,0,sizeof(h));
int i;
for(i=0;i<n;i++){
cin>>a[i];
}
q[0]=a[0];
for(i=1;i<n-1;i++){
q[i]=gcd(q[i-1],a[i]);
}
h[n-1]=a[n-1];
for(i=n-2;i>0;i--){
h[i]=gcd(h[i+1],a[i]);
}
int ans=max(q[n-2],h[1]);
for(i=1;i<n-1;i++){
ans=max(ans,gcd(q[i-1],h[i+1]));
}
cout<<ans<<endl;
}
return 0;
}

C++中auto的用法

C++98 auto

早在C++98标准中就存在了auto关键字,那时的auto用于声明变量为自动变量,自动变量意为拥有自动的生命期,这是多余的,因为就算不使用auto声明,变量依旧拥有自动的生命期:

1
2
3
int a =10 ;  //拥有自动生命期
auto int b = 20 ;//拥有自动生命期
static int c = 30 ;//延长了生命期

C++98中的auto多余且极少使用,C++11已经删除了这一用法,取而代之的是全新的auto:变量的自动类型推断。

C++11 auto

auto可以在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型,类似的关键字还有decltype。举个例子:

1
2
3
int a = 10;
auto au_a = a;//自动类型推断,au_a为int类型
cout << typeid(au_a).name() << endl;

typeid运算符可以输出变量的类型。程序的运行结果输出了
int
这种用法就类似于C#中的var关键字。auto的自动类型推断发生在编译期,所以使用auto并不会造成程序运行时效率的降低。而是否会造成编译期的时间消耗,我认为是不会的,在未使用auto时,编译器也需要得知右操作数的类型,再与左操作数的类型进行比较,检查是否可以发生相应的转化,是否需要进行隐式类型转换。

为什么用auto:

用于代替冗长复杂、变量使用范围专一的变量声明。
想象一下在没有auto的时候,我们操作标准库时经常需要这样:

1
2
3
4
5
6
7
8
9
10
11
#include<string>
#include<vector>
using namespace std;
int main()
{
vector<string> vs;
for (vector<string>::iterator i = vs.begin(); i != vs.end(); i++)
{
//...
}
}

使用auto 可以简化代码:

1
2
3
4
5
6
7
8
9
10
#include<string>
#include<vector>
int main()
{
vector<string> vs;
for (auto i = vs.begin(); i != vs.end(); i++)
{
//..
}
}

pair的用法

pair的应用

pair是将2个数据组合成一组数据,当需要这样的需求时就可以使用pair,如stl中的map就是将key和value放在一起来保存。
另一个应用是,当一个函数需要返回2个数据的时候,可以选择pair。 pair的实现是一个结构体,主要的两个成员变量是first second 因为是使用struct不是class,所以可以直接使用pair的成员变量。

1
2
3
4
5
6
7
pair<T1, T2> p1;            //创建一个空的pair对象(使用默认构造),它的两个元素分别是T1和T2类型,采用值初始化。
pair<T1, T2> p1(v1, v2); //创建一个pair对象,它的两个元素分别是T1和T2类型,其中first成员初始化为v1,second成员初始化为v2。
make_pair(v1, v2); // 以v1和v2的值创建一个新的pair对象,其元素类型分别是v1和v2的类型。
p1 < p2; // 两个pair对象间的小于运算,其定义遵循字典次序:如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2; // 如果两个对象的first和second依次相等,则这两个对象相等;该运算使用元素的==操作符。
p1.first; // 返回对象p1中名为first的公有数据成员
p1.second; // 返回对象p1中名为second的公有数据成员

pair的创建和初始化

1
2
3
4
5
6
7
8
9
10
11
pair包含两个数值,与容器一样,pair也是一种模板类型。但是又与之前介绍的容器不同;
在创建pair对象时,必须提供两个类型名,两个对应的类型名的类型不必相同

pair<string, string> anon; // 创建一个空对象anon,两个元素类型都是string
pair<string, int> word_count; // 创建一个空对象 word_count, 两个元素类型分别是string和int类型
pair<string, vector<int> > line; // 创建一个空对象line,两个元素类型分别是string和vector类型

当然也可以在定义时进行成员初始化:
pair<string, string> author("James","Joy"); // 创建一个author对象,两个元素类型分别为string类型,并默认初始值为James和Joy。
pair<string, int> name_age("Tom", "18");
pair<string, int> name_age2(name_age); // 拷贝构造初始化
1
2
3
4
5
6
7
8
pair类型的使用相当的繁琐,如果定义多个相同的pair类型对象,可以使用typedef简化声明:
typedef pair<string,string> Author;
Author proust("March","Proust");
Author Joy("James","Joy");

变量间赋值:
pair<int, double> p1(1, 1.2);
pair<int, double> p2 = p1; //operator =

pair对象的操作

1
2
3
4
5
6
7
8
9
10
11
pair<int ,double> p1;
p1.first = 1;
p1.second = 2.5;

cout<<p1.first<<' '<<p1.second<<endl;

//输出结果:1 2.5

string firstBook;
if(author.first=="James" && author.second=="Joy")
firstBook="Stephen Hero";

生成新的pair对象

还可以利用make_pair创建新的pair对象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pair<int, double> p1;
p1 = make_pair(1, 1.2);

cout << p1.first << p1.second << endl;

//output: 1 1.2

int a = 8;
string m = "James";
pair<int, string> newone;

newone = make_pair(a, m);

cout << newone.first << newone.second << endl;

//output: 8 James

通过tie获取pair元素值

在某些清况函数会以pair对象作为返回值时,可以直接通过std::tie进行接收。比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::pair<std::string, int> getPreson() {
return std::make_pair("Sven", 25);
}

int main(int argc, char **argv) {
std::string name;
int ages;

std::tie(name, ages) = getPreson();

std::cout << "name: " << name << ", ages: " << ages << std::endl;

return 0;
}

有关字符串的一些用法

1.isalpha(c) ~判断是否为英文字符
2.tolower(c) ~将字符转换成小写
3.字符串输入sstream
4.将字符串分割成单词:
stringstream temp(str); //分割成一个个单词
5.将字符串插入进set中,自动排序~

string的用法

提到字符串就必须提一句string,这个是真的好用!!!!

简洁明了string 的用法和 int 基本上没啥差别,也就是定义的类型不同,string功能多一点罢了(string毕竟是字符串嘛)

定义:

1
2
3
4
5
string str;
string str[100];
str = "aaa";//直接赋值
for(int i = 1; i <= n; i ++)
cin >> str[i];//输入赋值

比较

说起来比较就更令人发指了!!!
不知道比起来某个char方便多少呢。

1
2
3
4
str1 = "abc";
str2 = "abb";
if(str1 > str2) puts("1");
//输出结果 1

没错,你没看错!!就是直接比较大小。。
持续更新string 功能

stringstream的用法:

stringstream是 C++ 提供的另一个字串型的串流(stream)物件,和之前学过的iostream、fstream有类似的操作方式。要使用stringstream, 必须先加入这一行:

#include
stringstream主要是用在將一个字符串分割,可以先用.clear( )以及.str( )將指定字串设定成一开始的內容,再用>>把个別的资料输出。

Eg:
題目:输入的第一行有一个数字 N 代表接下來有 N 行资料,每一行资料里有不固定个数的整数(最多20个,每行最大200个字元),编程將每行的总和打印出來。
输入:
3
1 2 3
20 17 23 54 77 60
111 222 333 444 555 666 777 888 999
输出:
6
251
4995

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int main()
{
string s;
stringstream ss;
int n;
cin >> n;
getline(cin, s); //读取换行
for (int i = 0; i < n; i++)
{
getline(cin, s);
ss.clear();
ss.str(s);
int sum = 0;
while (1)
{
int a;
ss >> a;
if(ss.fail())
break;
sum += a;
}
cout << sum << endl;
}
return 0;
}

使用stringstream简化类型转换
C++标准库中的提供了比ANSI C的<stdio.h>更高级的一些功能,即单纯性、类型安全和可扩展性。接下来,我将举例说明怎样使用这些库来实现安全和自动的类型转换。
Eg:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

int main()
{
int n = 10000;
char s[10];

sprintf(s, "%d", n);
//s中的内容为“10000”

//到目前为止看起来还不错。但是,对上面代码的一个微小的改变就会使程序发生错误

printf("%s\n", s);
sprintf(s, "%f", n);

//错误的格式化符
printf("%s\n", s);
return 0;
}

详细学习链接
http://blog.csdn.net/zhang_xueping/article/details/47846807
http://blog.csdn.net/u014097230/article/details/52089530

优先队列—自动排序!!!

说道优先队列就必须提一句
优先队列别有back()操作,并且第一个元素不是用front()而是top(),,,front()是队列的
优先队列是一种特殊的队列,在学习堆排序的时候就有所了解。
堆排序

奇偶剪枝

点这里

---------------- The End ----------------
0%