STL函数

set

set查找前驱后继

multiset<int>::iterator iter;

S.insert(x);

iter=S.find(x);//返回迭代器

iter--;//前驱

int ans=*iter;

S.erase(find(x));

return ans;

或者可以使用\(lower\_bound\)（大于等于）、\(upper\_bound\)（严格大于）函数

multiset<int>::iterator iter;

iter=S.upper_bound(x);

需要注意的是，\(iter\)是一个类似指针的东西，当\(set\)的结构发生改变时，\(iter\)所指向的值也会变！

删除元素

S.erase(iter);//删除迭代器所指的元素（multiset只删一个元素）

S.erase(x);//删除所有的x元素（multiset就能把所有x删掉）

S.erase(find(x));//只删一个x

map

map的遍历

\(C++\)写法

map<int,int>::iterator iter;

for(iter=Map.begin();iter!=Map.end();iter++)

    int A=iter->first,B=iter.second;

\(C++11\)写法

for(auto x:Map) cout<<x.first<<" "<<x.second;//返回的是pair

map的查值

查\(x\)是否在\(Map\)中

1. if(Map[x]!=0) ...

2. if(Map.find(x)!=Map.end()) ...

一定要使用第二种方法，因为若\(x\)不在\(Map\)中，而调用\(Map[x]\)的话会自动新增一个结点\((x,0)\)，使得常数变大或者发生错误

deque

双端队列

#include<deque>

deque<int> Q;

Q.push_front(x);

Q.push_back(x);

Q.pop_front(x);

Q.pop_back(x);

Q.size();

!Q.empty();

bitset

值域在\(10^9\)左右的时候用它比Map快得多！！！（10.16被卡常教训）

空间计算：除以8（严格来说\(\lceil\frac{k}{64}\rceil×8\)）

结构体

重载运算符

小于号（堆）

struct food

{

	int id,tim;

	bool operator <  (const food &b)const

		{return tim>b.tim;}

	//表示按tim从小到大排序（因为默认是大根堆，不清楚可以试试，注意两个const）

};

高精度以及矩阵乘法

struct BigNum

{

    int a[110],w;

    BigNum () {memset(a,0,sizeof(a));w=0;}//表示一调用就会执行这个函数

    int &operator [] (int x) {return a[x];}//可以使用A[i]代替A.a[i]

    void operator = (int x)

        {

            memset(a,0,sizeof(a));w=0;

            while(x) {a[++w]=x%10,x/=10;}

            if(!w) a[++w]=0;

        }

    BigNum operator + (BigNum B)

        {

            BigNum C;C.w=max(w,B.w);

            for(int i=1;i<=C.w;i++) C[i]=a[i]+B[i];

            for(int i=1;i<=C.w;i++) C[i+1]+=C[i]/10,C[i]%=10;

            if(C[C.w+1]) C.w++;return C;

        }

}A;

struct Matrix

{

	int a[50][50];

	int* operator [] (int x) {return a[x];}//可以用A[i][j]代替A.a[i][j]

	Matrix () {memset(a,0,sizeof(a));}

	Matrix operator * (Matrix B)

		{

			Matrix C;

			for(int k=1;k<=n;k++)

				for(int i=1;i<=n;i++)

					for(int j=1;j<=n;j++)

						(C[i][j]+=1ll*a[i][k]*B[k][j]%mod)%=mod;

			return C;

		}

}Base,Ans;

淫荡的操作们

O(1)的long long相乘

ll mul(ll x,ll y,ll p)

{

	x%=p;y%=p;

	return (x*y-(ll)((long double)x/p*y+0.5)*p+p)%p;

}

奇怪的错误点

判断一个数是否为完全平方数

sqrt返回的是double！！要强制转成int才行

String等不定长数组的使用

在调用之前一定要判是否在长度范围内，否则会出现神奇的错误

考试时严格按照给定的编译命令

否则就会出现不开O2访问数组负下标还拍上了的情况

一些细节

实数有效位数

• float 8 位
• double 16 位
• long double 32 位