最短路
打包:https://www.cnblogs.com/phemiku/p/11537316.html
快速幂和快速乘
首先,快速幂的目的就是做到快速求幂,假设我们要求a^b,按照朴素算法就是把a连乘b次,这样一来时间复杂度是O(b)也即是O(n)级别,快速幂能做到O(logn),快了好多好多。它的原理如下:
假设我们要求a^b,那么其实b是可以拆成二进制的,该二进制数第i位的权为2^(i-1),例如当b==11时 a11=a(2^0+2^1+2^3) 。
11的二进制是1011,11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1,因此,我们将a¹¹转化为算 a2^0*a2^1*a2^3,也就是a1*a2*a8,看出来快的多了吧原来算11次,现在算三次,但是这三项貌似不好求的样子....不急,下面会有详细解释。 由于是二进制,很自然地想到用位运算这个强大的工具:&和>>&运算通常用于二进制取位操作,例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶,x&1==1为奇。>>运算比较单纯,二进制去掉最后一位。from CXCXCXC
#include<bits/stdc++.h> using namespace std; #define int long long //这样就不用每次开long long了 const int N = 100050; inline int read() { //快读 char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } inline int qpow(int a,int b,int mod){ //快速幂 for(int c = 1; ;a = a * a % mod){ if(b & 1)c = c * a % mod; if(!(b >>= 1))return c; } } inline int qmul(int a,int b,int mod){ //快速乘 for(int c = 0; ;a = (a << 1) % mod){ if(b & 1)c = (c + a) % mod; if(!(b >>= 1))return c; } } int n,m,a,b,q,c,d,r; signed t; signed main() { t = read(); for(int i = 1;i <= t; i++){ a = read();b = read();q = read(); c = read();d = read();r = read(); cout << qpow(a,b,q) << " "<< qmul(c,d,r) << endl ; } }
二分
跳石头地址:https://www.luogu.org/problem/P2678
#include <bits/stdc++.h> const int N = 50050; int n, d[N], m, len, ans; inline bool check(int mid) { int sum = 0, now = 0; for (int i = 1; i <= n; i++) { if (d[i] - d[now] < mid) sum++; else now = i; } if (sum > m) return 0; else return 1; } int main() { std::cin >> len >> n >> m; for (int i = 1; i <= n; i++) std::cin >> d[i]; if (!n) std::cout << len; else { int l = 1, r = len; while (l < r) { int mid = l + (r - l) / 2; if (check(mid)) { l = mid + 1; ans = mid; } else r = mid; } std::cout << ans; } return 0; }
矩阵快速幂
https://www.luogu.org/problem/P3390
#include<iostream> #include<cstring> #define mod 1000000007 #define ll long long using namespace std; struct Mat{ ll m[101][101]; }; Mat a,e; ll n,p; Mat Mul(Mat x,Mat y) //矩阵乘 { Mat c; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) c.m[i][j]=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) c.m[i][j] = c.m[i][j] % mod + x.m[i][k] * y.m[k][j] % mod; return c; } Mat pow(Mat x,ll y) //矩阵快速幂 { Mat ans=e; while(y) { if(y&1) ans=Mul(ans,x); x=Mul(x,x); y>>=1; } return ans; } int main() { cin>>n>>p; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a.m[i][j]; for(int i=1;i<=n;i++) e.m[i][i]=1; //构造单位矩阵 Mat ans = pow(a,p); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout << ans.m[i][j] % mod << " "; cout << endl; } return 0; }
堆
小根堆
https://www.luogu.org/problem/P3378
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<vector> using namespace std; int main(){ priority_queue< int,vector<int>, greater<int> >q; int n,m,k,p,x,y; scanf("%d",&n); for(register int i = 1; i <= n; ++i){ scanf("%d",&x); if(x==1){ scanf("%d",&y); q.push(y); } else if(x==2){ printf("%d",q.top()); } else { q.pop(); } } return 0; }
高精度
高精度减法
#include<bits/stdc++.h> using namespace std; const int N= 10500; int na[N],nb[N],nc[N]; bool bj; string a,b; int main() { cin>>a>>b; if(a.size()<b.size()||(a.size()==b.size()&&a<b)){ //我果然年少又无知…string可以直接比较大小的…(ASCII码 bj=1; swap(a,b); } for(int i=a.size();i>=1;i--)na[i]=a[a.size()-i]-'0'; for(int i=b.size();i>=1;i--)nb[i]=b[b.size()-i]-'0'; int n=max(a.size(),b.size()); for(int i = 1; i <= n; i ++){ if(na[i] < nb[i]){ na[i + 1] --; na[i] += 10; } nc[i] = na[i] - nb[i]; } while(nc[n]==0)n--; if(bj)cout<<"-"; for(int i=n;i>0;i--)cout<<nc[i]; if(n<1)cout<<"0"; }
高精度乘法
#include<iostream> #include<cstring> #define maxn 100000+10 using namespace std; int na[maxn],nb[maxn],nc[maxn]; char a[maxn],b[maxn]; void mul() { int i,j,lena,lenb; memset(na,0,sizeof(na)); memset(nb,0,sizeof(nb)); memset(nc,0,sizeof(nc)); lena=strlen(a); lenb=strlen(b); for(i=0;i<lena;i++) na[i]=a[lena-i-1]-'0'; for(i=0;i<lenb;i++) nb[i]=b[lenb-i-1]-'0'; for(i=0;i<lena;i++) for(j=0;j<lenb;j++) nc[i+j]+=na[i]*nb[j]; int max=lena+lenb; for(i=0;i<max;i++) nc[i+1]+=nc[i]/10,nc[i]%=10; while(!nc[--max]); max++; for(i=0;i<max;i++) a[i]=nc[max-i-1]+'0'; a[max]='