@wqy 已改
oasis
@oasis
oasis 发布的帖子
-
C++ STL
1.二分查找upper_bound 和lower_bound
两函数是在一个左闭右开的有序区间里进行二分查找,upper_bound返回的是被查序列中第一个大于查找值的指针,lower_bound则是返回的是被查序列中第一个大于等于查找值的指针
例:
vector<int>::iterator it = lower_bound(v.begin(), v.end(), 3); //返回vector中第一个大于(等于)3的数的指针
int pos = lower_bound(v.begin(), v.end(), 3)-v.begin(); //得到在vector中的位置2.去重unique函数
unique的作用实质上是把重复的元素添加到容器末尾,而返回值是去重之后的尾地址
例:
int a[10]={1,1,2,2,3,3,4,4,5,5};
int ans=unique(a,a+10)-a; //此时ans为53.全排函数next_permutation和prev_permutation
例:
sort(a,a+n); //先排序得到a的最小排列 do //依次输出数组a的排序 { for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; }while(next_permutation(a,a+n)); //最后一次执行后,数组会回到最小排序
4.vector
a. reverse(v.begin(),v.end());将元素翻转,即逆序排列
b. 边遍历边删除
for(vector<int>::iterator it=v.begin(); it!=v.end();) v.erase(it);
c.删除区间 v.erase(v.begin()+i,v.end()+j);
5.map
a.构造map<int,string> m;
b.添加数据 m.insert(map<int,string>::value_type(111,"acs");
或m.insert(pair<int,string>(111,"acs");
或m[111]="acs";
在指定位置插入
map<int ,string>::iterator it=m.begin(); pair<map<int, string>::iterator, bool> p; p=m.insert(it,pair<int,string>(111,"acs"); if(p.second==true) 插入成功
c.遍历
for(map<int ,string>::iterator it = m.begin(); it != m.end(); it++) cout<<it->first<<' '<<it->second<<endl;
d.查找
m.find(1); //查找关键字1
e.删除
m.erase(1); //删除关键字为1的值
m.erase(it): //删除it所指向的位置的值
m.erase(it1,it2); //删除两指针间的值(左闭右开)
6.string
a.初始化
a) string s; //生成一个空字符串s
b) string s(str) //拷贝构造函数 生成str的复制品
c) string s(str,stridx) //将字符串str内“始于位置stridx”的部分当作字符串的初值
d) string s(str,stridx,strlen) //将字符串str内“始于stridx且长度最多strlen”的部分作为字符串的初值
e) string s(cstr) //将C字符串作为s的初值
f) string s(chars,chars_len) //将C字符串前chars_len个字符作为字符串s的初值。
g) string s(num,c) //生成一个字符串,包含num个c字符
h) string s(beg,end) //以区间beg;end(不包含end)内的字符作为字符串s的初值
i) s.~string() //销毁所有字符,释放内存b.查找
int find(char c, int pos = 0) const;//从pos开始查找字符c在当前字符串的位置
int find(const char *s, int pos = 0) const;//从pos开始查找字符串s在当前串中的位置
int find(const char *s, int pos, int n) const;//从pos开始查找字符串s中前n个字符在当前串中的位置int find(const string &s, int pos = 0) const;//从pos开始查找字符串s在当前串中的位置
c.插入
s.insert(2,"sf"); //在2下标插入sf
d.删除
s.erase(2,4); //删除从2下标开始的4个字符
s.erase(2); //删除从而下标开始的所有字符
s.erase(remove(s.begin(),s.end(),'a'),s.end); //删除给定区间内所有的a
e.提取
s.substr(pos,len); //提取从下标pos开始的长度为len的字符串
7.set
a.插入
s.insert(v.begin(),v,end()); //把vector中的元素插入集合
s.insert(a); //插入单个元素
b.查找
s.count(b); //返回b出现的次数
s.find(b); //返回b所在位置的指针
c.删除
s.erase(iterator) ,删除定位器iterator指向的值
s.erase(first,second),删除定位器first和second之间的值
s.erase(key_value),删除键值key_value的值 -
逆元
1.单位元:当他与其他元素结合时,并不会改变那些元素。若ae=a,e称为右单位元;若ea=a,e称为左单位元,若ae=ea=a,则e称为单位元
2.逆元:一个存在单位元素e的代数系统 ,如果对S内的元素a存在 ,使得 ,则称 为a对运算“ ”的左逆元素,亦称左逆元。 若有 ,则称 为a对运算“ ”的右逆元素,亦称右逆元。
3.求解公式:(a/b)%m:
设c是b的逆元,则有b*c≡1(mod m);
则(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);
逆元求法1:
aX≡1 mod n
这个方程等价于求一个X和K,满足
aX=nK+1 (其中X和K都是整数)
则可扩展欧几里得求逆元ax≡1(mod n)
ll extend_gcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return a; } else { ll r = extend_gcd(b, a % b, y, x); y -= x * (a / b); return r; } } ll inv(ll a, ll n) { ll x, y; extend_gcd(a, n, x, y); x = (x % n + n) % n; return x; }
逆元求法2:
费马小定理:假如p是质数,且gcd(a,p)=1,那么 a(p-1)≡1(mod p),即:假如a是整数,p是质数,且a,p互质,那么a的(p-1)次方除以p的余数等于1。
由上方的公式很容易推导出:a*a(p-2)≡1(mod p)对于整数a,p,a关于p的逆元就是a^(p-2)
int quick_pow(int a,int b){ int r=1,base=a; while(b){ if(b&1) r*=base; base*=base; b>>=1; } return r; }
ps: 快速幂(取模MOD):
ll pow(ll a,ll i){ if (i==0) return 1; int temp=pow(a,i>>1); temp=temp*temp%MOD; if (i&1) temp=(ll)temp*a%MOD; return temp%MOD; }