本文最后更新于 148 天前,其中的信息可能已经有所发展或是发生改变。
以前一直没有总结的习惯。
快速幂
//a的b次方
int qsmi(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans*=a //b--可写可不写
b>>=1;
a*=a;
}
return ans;
}
欧几里得
int gcd(int a, int b)
{
return b?(b,a%b):a;
}
int gcd(int a ,int b)
{
int temp;
while(b)
{
temp=a%b;
a=b;
b=temp
}
return a;
}
子矩阵前缀和
生成前缀和矩阵
a[i]为原矩阵,s[i]为子矩阵
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
}
求任意子矩阵的和
(x1,y1)为子矩阵左上角坐标,(x2,y2)为子矩阵右下角坐标
ans=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]
素数
试除法判断一个数是否为素数
bool isprime(int a)
{
if(a<2)return false;
for(int i=2;i<=a/i;i++)
{
if(a%i==0)return false;
}
return true;
}
埃氏筛法 筛选1~n之间的素数(欧拉筛不好记),实际上时间差不了超级多
bool isprime[N];//是否为素数
void sieve(){
//我们初始化都标记为素数。再筛不是素数的
for(int i=0;i<=maxn;i++)isprime[i]=true;
isprime[0]=isprime[1]=false;//1,0不是素数
for(int i=2;i<=maxn;i++){//从2开始往后筛,因为2是目前最小的素数,那么素数的倍速一定不是素数
if(isprime[i]){
for(int j=i+i;j<=maxn;j+=i){
isprime[j]=false;
}
}
}
}
整数二分模板
男左女右,所以左边要+1,而有加必有减
//查找左边界 SearchLeft 简写SL 查找满足条件的最小那个数
int SL(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
//查找右边界 SearchRight 简写SR 查找满足条件最大的那个数
int SR(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; //
if (check(mid)) l = mid; //男左,上边需要加1
else r = mid - 1; //有加必有减
}
return r;
}
floyd算法求带权图的最短路
#include <iostream>
using namespace std;
const int N = 210, M = 2e+10, INF = 1e9;
int n, m, k, x, y, z;
int d[N][N];
void floyd() {
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF;
while(m--) {
cin >> x >> y >> z;
d[x][y] = min(d[x][y], z);//x到y的权重
//注意保存最小的边
}
floyd();
while(k--) {
cin >> x >> y;
if(d[x][y] > INF/2) puts("impossible");
//由于有负权边存在所以约大过INF/2也很合理
else cout << d[x][y] << endl;
}
return 0;
}
unique函数用法
直接去重
int a[6] = {1, 3, 3, 3, 2, 7};
unique(a, a + 6);
// cout << m;
for (int x : a)
cout << x << " ";
输出
1 3 2 7 2 7
输出去重后数组的元素数量
int a[8] = {1, 3, 3, 3, 3, 2, 5, 7};
int m = unique(a, a + 8) - a;
cout << m;
输出
5
next_permutation(a,a+n) 下一个全排列、以及prev_permutation(a,a+n);
string.find()
找到字串的下标,第二个参数是从哪里开始找
string a="abcdabacde";
string f="ab";
int index=a.find(f);
while(index!=-1)
{
cout<<index<<" ";
index=a.find(f,index+1);
}
输出
0 4
rfind也是同理
stoi() 字符串转int
string s = "1234";
int a = stoi(s);
cout << a << "\n"; // 1234