C++ ACM基础

一、c++结构体

#include <iostream>
using namespace std;
struct point{
    int x;
    int y;
    point(int x=0,int y=0):x(x),y(y){}
};
point operator +(const point &a,const point &b){
    return point(a.x+b.x,a.y+b.y);
}
ostream& operator <<(ostream &out,const point a){
    out<<'('<<a.x<<','<<a.y<<')'<<endl;
}
int main()
{
    point a(1,2);
    point b(2,3);
    cout<<a+b<<endl;
}

注意

1. 在c++中定义struct类型，可以直接用，可以不再用typedef取别名
2. 对结构体编写重构函数参考实例如上
3. 结构体可以有成员函数，而且有它独有的初始化方式，
4. c++中的函数参数可以拥有默认值
5. c++结构体可以有多个构造函数

6. 以上，同样在class中适用

   二、模板

#include <iostream>
using namespace std;
struct point{
    int x;
    int y;
    point(int x=0,int y=0):x(x),y(y){}
};
point operator +(const point &a,const point &b){
    return point(a.x+b.x,a.y+b.y);
}
ostream& operator <<(ostream &out,const point a){
    out<<'('<<a.x<<','<<a.y<<')'<<endl;
}
// template sum
template<typename t>
t sum(t *p,t *q){
    t result=0;//initiate 0*****
    while(p!=q){
        result=result+*p;
        p++;
    }
    return result;
}
int main()
{
    point points[4]={point(0,0),point(1,1),point(2,2),point(3,3)};
    cout<<sum(points,points+4)<<endl;
}

三、stl

3.1排序与检索

例题1

现有n个大理石，每个大理石上写了一个非负整数、首先把各数从小到大排序；然后回答q个问题。每个问题问是否有一个大理石写着某个整数x，如果是，还要回答哪个大理石上写着x。排序后的大理石从左到右编号为1~n。
(在样例中，为了节约篇幅，所有大理石的数合并到一行，所有问题也合并到一行。)
样例输入：

4 1
2 3 5 1
5
5 2
1 3 3 3 1
2 3

样例输出：

case# 1：
5 found at 4
case# 2：
2 not found
3 found at 3

#define local
#include<cstdio>
#include<algorithm>
using namespace std;
const int max=100;
int main()
{

    #ifdef local
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    #endif // local
    int n,q;
    int object;
    int time=0;
    int array[max];
    while(scanf("%d%d",&n,&q)==2 && n){

        printf("case# %d:\n",++time);
        //input n numbers
        int i=n;
        while(i--)scanf("%d",&array[i]);
        sort(array,array+n);//use sort c++ gives

        while(q--){
            scanf("%d",&object);
            //find
            int p=lower_bound(array,array+n,object)-array;//to find the index of the object in array
            if(array[p] == object) printf("%d found at %d\n",object,p+1);
            else printf("%d not found\n",object);
        }
    }
    return 0;
}

以上注意：

1. 重定向操作，在本地可以这么做，放到oj上要改变写法，所以用ifdef的预定义方式。
2. sort是一个模板函数，可以接收任何有<运算的类型
3. 可以对普通数组array进行排序，也可以对vector进行排序，vector的排序方式为sort(v.begin(),v.end());
4. lower_bound()函数接受三个参数，一二两个是数组的起始位置，第三个是待查找的元素，表示在数组中寻找第一次大于或者等于待查元素的位置。
5. scanf()的返回值：正确输入的变量个数，注意正确包括类型正确，个数正确。

3.2 vector

vector的使用方法请参见此链接