读入数据

//在数据量足够大的时候，防止手动输入的麻烦，我可以用下面的操作
#include<cstdio>
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);

如果大家想知道为什么这个可以实现就看看下面的这个文章：
freopen(“in.text”, “r”, stdin)的用法

C++ 和STL

如果想取得一个好成绩，一个好的编程语言是必不可少的，在这里我们就用C++，其中非常重要的就是STL标准模板库了，在这里我整理一下比较常用的string、容器、经典算法的资料。

一、string

为什么要用string呢，因为他的操作确实比字符串更简单

1.字符串拼接

有了 string 类，我们可以使用+或+=运算符来直接拼接字符串，非常方便，再也不需要使用C语言中的 strcat()、strcpy()、malloc() 等函数来拼接字符串了，再也不用担心空间不够会溢出了。

//字符串拼接
   string s1 = "abcde";
   string s2 = "fgh";
   s1 = s1 + s2;

输出：abcdefg

2… 插入字符串

函数原型：string& insert (size_t pos, const string& str);
注意：第一个参数越界会出现异常

//字符串插入
    string s1 = "abcde";
	string s2 = "fgh";
	s1.insert(2, s2);
	cout << s1 << endl << s2;

s1的结果：abfghcde

3. 删除字符串

函数原型：string& erase (size_t pos = 0, size_t len = npos);
功能：从字符串第pos的位置删除len 的长度

    //删除字符串
    string s1 = "abcde";
	s1.erase(2, 4);

s1输出结果：ab
注意：删除字符串最多删除到字符串尾

4.提取子字符串

函数原型：string substr (size_t pos = 0, size_t len = npos) const;
功能：提取从pos开始len长度的字符串;

//提取子字符串
    string s1 = "abcde";
	string s2 = s1.substr(1, 3);

s2的结果为：bcd
注意：如果 pos 越界，会抛出异常；
如果 len 越界，会提取从 pos 到字符串结尾处的所有字符。

5.字符串查找

函数原型：size_t find (const string& str, size_t pos = 0) const; size_t find (const char* s, size_t pos = 0) const;
功能：从pos的位置查找str字符串，返回第一次出现str字符串的下标。

//字符串查找
    string s1 = "abcde";
	string s2 = "bcd";
	cout << s1.find(s2, 0);

输出结果：1
如果没有查找到，则返回一无穷大值：4294967295

二、STL常用算法

STL里面有很多包装好的函数可以直接实现，这样我们就省去了很多的时间，一般包含在< algorithm >这个头文件里面。

1.排序函数

sort (first, last)：头文件：< algorithm >
对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排。
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
可以看到，还有第三个参数，这个参数可以自定义排序顺序。具体操作：
代码如下（示例）：

#include <iostream>
#include <algorithm>
using namespace std;
int cmp(int a, int b) {
	return a < b;
}
int main() {
	int a[9] = { 10,1,6,5,7,8,3,4,9 };
	sort(a, a + 9);
	for (int i = 0; i < 9; i++) cout<<a[i]<<" ";
	return 0;
}

输出：1 3 4 5 6 7 8 9 10
当然,sort（）还可以对结构体数组进行排序，这个如何实现呢？举个栗子哈：

#include <iostream>
#include <algorithm>
using namespace std;
typedef struct {
	int x;
	int y;
}Stu;
int cmp(Stu a , Stu b) {
	return a.x < b.x;
}
Stu stu[10];
int main() {
	for (int i = 0; i < 10; i++)
		cin >> stu[i].x >> stu[i].y;
	sort(stu, stu + 9);
	for (int i = 0; i < 10; i++)
	    cout << stu[i].x << " " << stu[i].y;
	return 0;
}

这样就可以根据x的值对结构体进行排序啦。

2.二分查找

函数原型：//查找 [first, last) 区域内是否包含 val bool binary_search (ForwardIterator first, ForwardIterator last, const T& val); //根据 comp 指定的规则，查找 [first, last) 区域内是否包含 val bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
功能：从第first个元素到第last元素二分查找，返回值是bool类型的值，如果有返回true，如果没有返回false。
注意：第一个参数和第二个参数可以是迭代器，也可以是数组的地址;
我们可以自己写一个二分：
递归写法：

int my_search(int a[], int left, int right, int x) {
	if (left == right) {
		if (a[left] == x)
			return left + 1;
		else
			return -1;
	}
	int mid = (right + left) / 2;
	if (a[mid] >= x) my_search(a, left, mid, x);
	else            my_search(a, mid + 1, right, x);
}

非递归写法：

int my_search(int a[], int left, int right, int x) {
	int mid;
	while (left != right) {
		mid = (right + left) / 2;
		if (a[mid] >= x)
			right = mid;
		else
			left = mid + 1;
	}
	return left;
}