目錄

• 位運算
• • 90. 64位整數乘法
• 遞推與遞歸
• • 95. 費解的開關
  • 97. 約數之和【遞推】
• 前綴和與差分
• • 99. 激光炸彈
  • 100. 增減序列
• 二分
• • 102. 最佳牛圍欄
  • 113. 特殊排序
• 排序
• • 105. 七夕祭【環形平分牌】
  • 106. 動態中位數【對頂堆】
  • 107. 超快速排序【逆序對】
• RMQ
• • 1273. 天才的記憶【st表】

位運算

90. 64位整數乘法

#include<bits/stdc++.h> using namespace std; typedef long long int LL; LL a,b,p; LL quick_mi(LL a,LL b,LL p) {LL sum=0;while(b){if(b&1) sum=(sum+a)%p;b>>=1;a=(a+a)%p;}return sum%p; } int main(void) {cin>>a>>b>>p;cout<<quick_mi(a,b,p);return 0; }

遞推與遞歸

95. 費解的開關

97. 約數之和【遞推】

#include<bits/stdc++.h> using namespace std; typedef long long int LL; const int mod=9901; LL a,b; LL quick_mi(LL a,LL b) {LL sum=1;while(b){if(b&1) sum=sum*a%mod;b>>=1;a=a*a%mod;}return sum%mod; } LL sum(LL p,LL k) {if(k==1) return 1;if(k%2==0) return (1+quick_mi(p,k/2))*sum(p,k/2)%mod;return (sum(p,k-1)+quick_mi(p,k-1))%mod; } int main(void) {cin>>a>>b;LL res=1;for(int i=2;i*i<=a;i++){int s=0;while(a%i==0) a/=i,s++;if(s) res=res*sum(i,s*b+1)%mod;}if(a!=1) res=res*sum(a,1*b+1)%mod;if(a==0) cout<<0;else cout<<res;return 0; }

前綴和與差分

99. 激光炸彈

100. 增減序列

二分

102. 最佳牛圍欄

113. 特殊排序

排序

105. 七夕祭【環形平分牌】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; typedef long long int LL; LL x[N],y[N],c[N],n,m,t; LL solve(LL s[],int n) {LL avg=s[n]/n;for(int i=1;i<=n;i++) c[i]=avg*i-s[i];sort(c+1,c+n+1);LL temp=c[(n+1)/2];LL sum=0;for(int i=1;i<=n;i++) sum+=abs(temp-c[i]);return sum; } int main(void) {cin>>n>>m>>t;while(t--){int a,b; cin>>a>>b;x[a]++,y[b]++;}for(int i=1;i<=n;i++) x[i]+=x[i-1];for(int i=1;i<=m;i++) y[i]+=y[i-1];if(x[n]%n==0&&y[m]%m==0){cout<<"both "<<solve(x,n)+solve(y,m);}else if(x[n]%n==0){cout<<"row "<<solve(x,n);}else if(y[m]%m==0){cout<<"column "<<solve(y,m);}else puts("impossible");return 0; }

106. 動態中位數【對頂堆】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int x,n,t; int main(void) {cin>>t;for(int i=1;i<=t;i++){int id; cin>>id>>n;printf("%d %d\n",id,(n+1)/2);priority_queue<int>maxv;priority_queue<int,vector<int>,greater<int>>minv;int k=0;for(int j=1;j<=n;j++){cin>>x;if(maxv.empty()||(maxv.top()>=x)) maxv.push(x);else minv.push(x);if(maxv.size()>minv.size()+1){auto temp=maxv.top(); maxv.pop();minv.push(temp);}if(minv.size()>maxv.size()){auto temp=minv.top(); minv.pop();maxv.push(temp);}if(j&1){cout<<maxv.top()<<" ";k++;if(k%10==0) puts("");}}if(k%10) cout<<endl;}return 0; }

107. 超快速排序【逆序對】

#include<bits/stdc++.h> using namespace std; const int N=1e5*5+10; int a[N],b[N],n; long long int ans; void merge_sort(int l,int r) {if(l>=r) return;int mid=l+r>>1;merge_sort(l,mid),merge_sort(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(a[i]<=a[j]) b[k++]=a[i++];else {ans+=mid-i+1;b[k++]=a[j++];}}while(i<=mid) b[k++]=a[i++];while(j<=r) b[k++]=a[j++];for(int i=l,j=0;i<=r;i++,j++) a[i]=b[j]; } int main(void) {while(cin>>n,n){for(int i=0;i<n;i++) scanf("%d",&a[i]);ans=0;merge_sort(0,n-1);printf("%lld\n",ans);}return 0; }

RMQ

1273. 天才的記憶【st表】

#include<bits/stdc++.h> using namespace std; const int N=1e5*2+1; int n,m,mx[N][20],mn[N][20],a[N]; int getmx(int l,int r){//區間[l,r]內的最大值int tmp=log2(r-l+1);return max(mx[l][tmp],mx[r-(1<<tmp)+1][tmp]); } int getmn(int l,int r){//區間[l,r]內的最小值int tmp=log2(r-l+1);return min(mn[l][tmp],mn[r-(1<<tmp)+1][tmp]); } void init()//構建ST表 {for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i];for(int j=1;j<20;j++){for(int i=1;i+(1<<j)-1<=n;i++){mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);}} } int main(void) {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);init();scanf("%d",&m);while(m--){int l,r; scanf("%d%d",&l,&r);printf("%d\n",getmx(l,r));} }

總結

以上是生活随笔為你收集整理的第六章 基础算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。