基础算法(二)#蓝桥杯

8、双指针

8.1、挑选子串

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
int a[2001];
int main(){	IOS;int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++)cin>>a[i];ll ans=0;//快慢指针for(int i=1,j=0,cnt=0;i<=n;i++){//i>j 说明区间不合法,j+1 表示向右移还有空间,cnt<k 表示不满足>=kwhile(i>j||(j+1<=n&&cnt<k)){cnt+=(a[++j]>=m);}if(cnt>=k){//满足条件的情况下,找到这个最小区间[i,j],有n-j+1个子串ans+=n-j+1;}//a[i]>=m的话,就重新向后找到满足的cntcnt-=(a[i]>=m);}cout<<ans<<"\n";return 0;
}

8.2、聪明的小羊肖恩

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
ll l,r;
//bool isT(ll xx){
//	return (xx>=l)&&(xx<=r);
//}
int main(){	IOS;// l <= ai + aj <= r// l - ai <= aj <= r - aill n;cin>>n>>l>>r;vector<ll> a(n);for(auto &x:a)cin>>x;sort(a.begin(),a.end());ll ans=0;
//	超时
//	for(int i=0;i<n;i++){
//		for(int j=i+1;j<n;j++)
//			ans+=isT(a[i]+a[j]);
//	}//很多时候双指针问题，都可以使用二分替代for(int i=0;i<n;i++){ll L = ll(lower_bound(a.begin()+i+1,a.end(),l-a[i])-a.begin());ll R = ll(upper_bound(a.begin()+i+1,a.end(),r-a[i])-a.begin()-1);if(L<=R){ans+=R-L+1;}}cout<<ans<<"\n";return 0;
}

8.3、神奇的数组

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;// 这里的 xor, and, or 都是位运算
// 1 xor 0 = 1, 1 xor 1 = 0
// 异或可以理解成不进位加法
// 区间和，区间异或和，要想到前缀和，虽然这题不太能这么做，但也得想到这一点
// x + y >= x xor y
// 如果 x + y = x xor y，意味着加法不能进位，x and y = 0
// 因为 x and y = 0，所以 x xor y 一定会多一些 1int main(){	IOS;int n;cin>>n;vector<ll> a(n),zero(n+1);for(auto &x:a)cin>>x;for(int i=n-1;i>=0;i--){if(a[i]==0)zero[i]=zero[i+1]+1;}ll ans=0;for(int l=0;l<n;l++){int r=l;int sum_xor=0;while(r<n){if(a[r]==0){r=r+zero[r];}else{if(sum_xor & a[r])break;sum_xor^=a[r];r++;}}ans+=r-l;}cout<<ans<<'\n';return 0;
}

9、二分

二分的思想是什么呢？

是不是我们可以这样想，如果我们有答案了，那么肯定是符合题意的，所以说我们可以枚举所有可能正确的答案。

9.1、跳石头

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
const int N = 1e6+5;
int l,n,m;
ll a[N];
int check(int mid){int res=0;//可以看作移动的岩石数量for(int l=1,lst=0;l<=n;l++){if(a[l]-a[lst]<mid){res++;continue;}lst=l;}if(l-a[lst]<mid)return res+1;//最后一块return res;
}
int main(){	IOS;cin>>l>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];ll L = 0,R = 1e9+5;while(L+1!=R){ll mid=(L+R)/2;if(check(mid)<=m)L=mid;else R = mid;}cout<<L<<'\n';return 0;
}

9.2、可凑成的最大花朵数

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
int main(){	IOS;int n,k;cin>>n>>k;vector<ll> a(n);for(auto &x:a)cin>>x;ll l=0,r=2e13+5;while(l+1!=r){ll mid=(l+r)>>1;ll cnt=0;for(const auto& x:a)cnt+=min(mid,ll(x));if(cnt/k>=mid)l=mid;else r=mid;}cout<<l<<'\n';return 0;
}

9.3、最大通过数

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
int main(){	IOS;int n,m,k;cin>>n>>m>>k;vector<ll> a(n),b(m);for(auto &x:a)cin>>x;for(auto &x:b)cin>>x;ll r=0;while(r<n){if(k-a[r]>=0){k-=a[r];r++;}else break;}ll ans=r;for(int l=0;l<m;l++){k-=b[l];while(r>=1&&k<0){k+=a[r-1];r--;}// k 表示的是剩余的能量,当 k 小于零时，意味着无法完成接下来的任务// 因此，当 k 小于零时，就没有必要继续循环了，可以直接跳出循环if(k<0)break;ans=max(ans,r+l+1);}cout<<ans<<'\n';return 0;
}

9.4、妮妮的月饼广场

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
int main(){	IOS;int n,k;cin>>n>>k;vector<ll> a(n);for(auto &x:a)cin>>x;ll l=0,r=1e14+5;while(l+1!=r){ll mid=(l+r)>>1;ll cnt=0;for(const auto& x:a)cnt+=x/mid;//mid当作高度(我们去找这个最高的高度mid)//那么cnt即为数量if(cnt>=k)l=mid;else r=mid;}if(l<=0)cout<<"-1"<<'\n';else cout<<l<<'\n';return 0;
}

9.5、基德的神秘冒险

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
int main(){	IOS;ll n,q;cin>>n>>q;vector<ll> a(n);for(auto &x:a)cin>>x;sort(a.begin(),a.end());vector<ll> pre_sum(n+1,0);for(int i=1;i<=n;i++){pre_sum[i]=pre_sum[i-1]+((n-i)*(n-i-1))/2;//排列组合，每次都选择当前是最小的数，然后从后面取两个，所以是从n-i个里选两个}while(q--){ll k;cin>>k;cout<<a[lower_bound(pre_sum.begin(),pre_sum.end(),k)-pre_sum.begin()-1]<<'\n';}return 0;
}

9.6、体育健将

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
ll n,k;
bool cmp(const pair<ll,ll> &a,const pair<ll,ll> &b){return a.first+a.second<b.first+b.second;
}
int main(){	IOS;cin>>n>>k;vector<pair<ll,ll>> a(n);for(int i=0;i<n;i++)cin>>a[i].first;for(int i=0;i<n;i++)cin>>a[i].second;sort(a.begin(),a.end(),cmp);vector<ll> mn(n+1,1e9);mn[n]=1e9;for(int i=n-1;i>=0;i--)mn[i]=min(mn[i+1],a[i].first);for(int i=0;i<n;i++){if(k<mn[i]){// mn数组已经算是从小到大的数据了cout<<i<<'\n';return 0;}k-=(a[i].first+a[i].second);	}cout<<n<<'\n';return 0;
}

10、倍增

10.1、快速幂

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using ll = long long;
ll ksm(ll b,ll p,ll k){ll r=1;while(p!=0){if(p&1){r=(r*b)%k;}b=(b*b)%k;p>>=1;}return r;
}
int main(){IOS;ll b,p,k;cin>>b>>p>>k;cout<<ksm(b,p,k)<<'\n';return 0;
}

10.2、最近公共祖先LCA查询

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using namespace std;
using ll = long long;
int main() {IOS;int n;cin>>n;vector<vector<int>> graph(n+1);for(int i=1;i<n;i++){//n-1 条边int u,v;cin>>u>>v;graph[v].push_back(u);graph[u].push_back(v);//邻接矩阵}//倍增数组vector<array<int,21>> fa(n+1);//array<int,21> 固定的数组大小21vector<int> dep(n+1);//深度function<void(int,int)> dfs = [&](int x,int f){fa[x][0]=f;for(int i=1;i<=20;i++){fa[x][i]=fa[fa[x][i-1]][i-1];}//遍历数组for(const auto& tox:graph[x]){if(tox==f)continue;dep[tox]=dep[x]+1;dfs(tox,x);}};dfs(1,0);auto glca = [&](int x,int y){if(dep[x]<dep[y])swap(x,y);int d=dep[x]-dep[y];for(int i=20;i>=0;i--){if(d>>i & 1)x=fa[x][i];}if(x==y)return x;for(int i=20;i>=0;i--){if(fa[x][i] != fa[y][i]){x=fa[x][i];y=fa[y][i];}}return fa[x][0];};int q;cin>>q;while(q--){int x,y;cin>>x>>y;cout<<glca(x,y)<<'\n';}return 0;
}

10.3、理想之城

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using ll = long long;
int main(){ll n,k;cin>>n>>k;vector<int> a(n + 1);for(int i=1;i<=n;i++)cin>>a[i];auto jump = [&](int x,int p){for(int i=0;i<p;i++){x=a[x];}return x;};vector<int> fa(n+1);int now=1,i=1;while(1){//!=0 说明已经经过这个传送门，就造成了一个闭环，咱们只需要找到这个环的长度，让k对它求模if(fa[now]!=0){int len=i-fa[now];int p=int(k%len);//now：当前位置；步长：pcout<<jump(now,p)<<'\n';return 0;}else{fa[now]=i;//记录cur传送门的下标now=a[now];//更新now的值}if(i==k){cout<<now<<'\n';return 0;}i++;k--;//传送的次数}return 0;
}

10.4、数的变换

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using ll = long long;
const int inf = 2000001;
int main() {IOS; ll a,b,c,q;cin>>a>>b>>c>>q;// a = a/b + cif(b==1){cout<<a+ll(c*q)<<'\n';return 0;}ll ans=0;vector<array<int,31>> fa(inf+1);for(int i=0;i<=inf;i++){fa[i][0]=i/b+c;}	for(int j=1;j<=30;j++){for(int i=0;i<=inf;i++){if(fa[i][j-1]>inf)fa[i][j]=inf;//防止数组越界	//将当前位置的值，设置为2^j步后的位置的值else fa[i][j]=fa[fa[i][j-1]][j-1];}}ans = a;for(int i=30;i>=0;i--){if(q>>i&1){ans=fa[ans][i];}}cout<<ans<<'\n';return 0;
}