高精度模板

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
define N 1e5
struct bign
{
int len;
int v[N];

// 赋值 bign=bign
bign operator = (char* s)
{
len=strlen(s);
memset(v,0,sizeof(v));
for(int i=0;i<len;i++)
v[i]=s[len-i-1]-'0';
return *this;
}
//赋值 bign=int
bign operator = (int x)
{
char s[N];
sprintf(s,"%d",x);
return *this=s;
}

// 高精加
bign operator + (const bign &b) const
{
bign c;
memset(c.v,0,sizeof(c.v));
c.len=max(len,b.len);
for(int i=0;i<c.len;i++)
c.v[i]=v[i]+b.v[i];
for(int i=0;i<c.len;i++)
{
c.v[i+1]+=c.v[i]/10;
c.v[i]%=10;
}
if(c.v[c.len]) c.len++;
return c;
}
// 高精乘
bign operator * (const bign &b) const
{
bign c;
memset(c.v,0,sizeof(c.v));
c.len=len+b.len;
for(int i=0;i<len;i++)
for(int j=0;j<b.len;j++)
c.v[i+j]+=v[i]*b.v[j];
for(int i=0;i<len;i++)
{
c.v[i+1]=c.v[i]/10;
c.v[i]%=10;
}
while(c.len>1 && c.v[c.len-1]) c.len--;
return c;
}
// 高精加等于
bign operator += (const bign &b)
{
return *this+b;
}

// 比大小
bool operator < (const bign &b) const
{
if(len<b.len) return 1;
if(len>b.len) return 0;
for(int i=len-1;i>=0;i--)
{
if(v[i]<b.v[i]) return 1;
if(v[i]>b.v[i]) return 0;
}
return 0;//两个数相等返回flase
}

bool operator > (const bign &b) const
{
return b<*this;
}

bool operator <= (const bign &b) const
{
return !(b>*this);
}

bool operator >= (const bign &b) const
{
return !(b<*this);
}

bool operator == (const bign &b) const
{
return (b>*this)^(b<*this)
}
};

随机数基本使用方法

基本公式:

要取得[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是整数的范围。
要取得a到b之间的随机整数,另一种表示:a + (int)b * rand() / (RAND_MAX + 1)。
要取得0~1之间的浮点数,可以使用rand() / double(RAND_MAX)。

STL

STL

C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。

迭代器

1
2
set<int>::iterator it_set//一个set<int>类型的迭代器
map<string,int>::iterator it_map//一个map<string,int>类型的迭代器

SET

set的各成员函数列表

  1. begin()–返回指向第一个元素的迭代器
  2. clear()–清除所有元素
  3. count()–返回某个值元素的个数
  4. empty()–如果集合为空,返回true
  5. end()–返回指向最后一个元素的迭代器
  6. equal_range()–返回集合中与给定值相等的上下限的两个迭代器
  7. erase()–删除集合中的元素
  8. find()–返回一个指向被查找到元素的迭代器
  9. get_allocator()–返回集合的分配器
  10. insert()–在集合中插入元素
  11. lower_bound()–返回指向大于(或等于)某值的第一个元素的迭代器
  12. key_comp()–返回一个用于元素间值比较的函数
  13. max_size()–返回集合能容纳的元素的最大限值
  14. rbegin()–返回指向集合中最后一个元素的反向迭代器
  15. rend()–返回指向集合中第一个元素的反向迭代器
  16. size()–集合中元素的数目
  17. swap()–交换两个集合变量
  18. upper_bound()–返回大于某个值元素的迭代器
  19. value_comp()–返回一个用于比较元素间的值的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;
set<int> s;
set<int>::iterator it_set;

int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int tmp;
scanf("%d",&tmp);
s.insert(tmp);
}
for(it_set=s.begin();it_set!=s.end();it_set++)
{
printf("%d\n",*it_set);
}
return 0;
}

链接

容器set和multiset

P1429 平面最近点对(加强版)

P1429 平面最近点对(加强版)

题目

题目描述
给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的

输入输出格式
输入格式:
第一行:n;2≤n≤200000

接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式:
仅一行,一个实数,表示最短距离,精确到小数点后面4位。

输入输出样例
输入样例#1:
3
1 1
1 2
2 2
输出样例#1:
1.0000

思路

  • 首先考虑暴力,枚举所有点对,复杂度为O(N^2)

  • 然后就是正解:

    分治算法

    • 每一次把平面分成两个部分,找出左边的最近点对,右边的最近点对以及穿越分割线的最近点对。
    • 在求穿越分割线的最近点对时,用左右已经算出的最小值作为参考,一旦大于就停止搜索