基础算法(二)#蓝桥杯

文章目录

• • 8、双指针
  • • 8.1、挑选子串
    • 8.2、聪明的小羊肖恩
    • 8.3、神奇的数组
    • 9、二分
    • • 9.1、跳石头
      • 9.2、可凑成的最大花朵数
      • 9.3、最大通过数
      • 9.4、妮妮的月饼广场
      • 9.5、基德的神秘冒险
      • 9.6、体育健将
      • 10、倍增
      • • 10.1、快速幂
        • 10.2、最近公共祖先LCA查询
        • 10.3、理想之城
        • 10.4、���的变换

          8、双指针

          8.1、挑选子串

          #include#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>a[i];ll ans=0;//快慢指针for(int i=1,j=0,cnt=0;i//ij 说明区间不合法,j+1 表示向右移还有空间,cnt=kwhile(i>j||(j+1cnt+=(a[++j]=m);}if(cnt=k){//满足条件的情况下,找到这个最小区间[i,j],有n-j+1个子串ans+=n-j+1;}//a[i]>=m的话,就重新向后找到满足的cntcnt-=(a[i]>=m);}cout//return (xx=l)&&(xxIOS;// l x;sort(a.begin(),a.end());ll ans=0;//超时//for(int i=0;i//for(int j=i+1;jll 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(Lans+=R-L+1;}}coutIOS;int n;cinn;vectorif(a[i]==0)zero[i]=zero[i+1]+1;}ll ans=0;for(int l=0;lint r=l;int sum_xor=0;while(rif(a[r]==0){r=r+zero[r];}else{if(sum_xor & a[r])break;sum_xor^=a[r];r++;}}ans+=r-l;}coutint res=0;//可以看作移动的岩石数量for(int l=1,lst=0;lif(a[l]-a[lst]res++;continue;}lst=l;}if(l-a[lst]IOS;cinlnm;for(int i=1;ill mid=(L+R)/2;if(check(mid)IOS;int n,k;cinnk;vectorll 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;}coutIOS;int n,m,k;cinnm>>k;vector a(n),b(m);for(auto &x:a)cin>>x;for(auto &x:b)cin>>x;ll r=0;while(rif(k-a[r]=0){k-=a[r];r++;}else break;}ll ans=r;for(int l=0;lk-=b[l];while(r=1&&kk+=a[r-1];r--;}// k 表示的是剩余的能量,当 k 小于零时，意味着无法完成接下来的任务// 因此，当 k 小于零时，就没有必要继续循环了，可以直接跳出循环if(kIOS;int n,k;cinnk;vectorx;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(lIOS;ll n,q;cinnq;vectorpre_sum[i]=pre_sum[i-1]+((n-i)*(n-i-1))/2;//排列组合，每次都选择当前是最小的数，然后从后面取两个，所以是从n-i个里选两个}while(q--){ll k;cink;coutreturn a.first+a.secondIOS;cinnk;vector=0;i--)mn[i]=min(mn[i+1],a[i].first);for(int i=0;iif(k// mn数组已经算是从小到大的数据了cout  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;cinbpk;  coutIOS;int n;cinn;vector//n-1 条边int u,v;cinuv;graph[v].push_back(u);graph[u].push_back(v);//邻接矩阵}//倍增数组vectorfa[x][0]=f;for(int i=1;ifa[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]if(di & 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;coutll n,k;cinnk;vector a(n + 1);for(int i=1;i>a[i];auto jump = [&](int x,int p){for(int i=0;ix=a[x];}return x;};vector//!=0 说明已经经过这个传送门，就造成了一个闭环，咱们只需要找到这个环的长度，让k对它求模if(fa[now]!=0){int len=i-fa[now];int p=int(k%len);//now：当前位置；步长：pcoutfa[now]=i;//记录cur传送门的下标now=a[now];//更新now的值}if(i==k){coutIOS; ll a,b,c,q;cinabcq;// a = a/b + cif(b==1){coutfa[i][0]=i/b+c;}for(int j=1;jfor(int i=0;iif(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(qi&1){ans=fa[ans][i];}}cout