9、二分9.1、跳石头9.2、可凑成的最大花朵数9.3、最大通过数9.4、妮妮的月饼广场9.5、基德的神秘冒险9.6、体育健将

10、倍增10.1、快速幂10.2、最近公共祖先LCA查询10.3、理想之城10.4、数的变换

8、双指针

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

表示不满足kwhile(ij||(j1ncntk)){cnt(a[j]m);}if(cntk){//满足条件的情况下,找到这个最小区间[i,j],有n-j1个子串ansn-j1;}//a[i]m的话,就重新向后找到满足的cntcnt-(a[i]m);}coutans\n;return

#includebits/stdc.h

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

x:a)cinx;sort(a.begin(),a.end());ll

ans0;

ll(lower_bound(a.begin()i1,a.end(),l-a[i])-a.begin());ll

ll(upper_bound(a.begin()i1,a.end(),r-a[i])-a.begin()-1);if(LR){ansR-L1;}}coutans\n;return

#includebits/stdc.h

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

区间和区间异或和要想到前缀和虽然这题不太能这么做但也得想到这一点

xor

in-1;i0;i--){if(a[i]0)zero[i]zero[i1]1;}ll

ans0;for(int

sum_xor0;while(rn){if(a[r]0){rrzero[r];}else{if(sum_xor

a[r])break;sum_xor^a[r];r;}}ansr-l;}coutans\n;return

}9、二分

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

9.1、跳石头

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

l1,lst0;ln;l){if(a[l]-a[lst]mid){res;continue;}lstl;}if(l-a[lst]mid)return

res1;//最后一块return

mid(LR)/2;if(check(mid)m)Lmid;else

mid;}coutL\n;return

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

x:a)cntmin(mid,ll(x));if(cnt/kmid)lmid;else

rmid;}coutl\n;return

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

r0;while(rn){if(k-a[r]0){k-a[r];r;}else

break;}ll

l0;lm;l){k-b[l];while(r1k0){ka[r-1];r--;}//

因此当

小于零时就没有必要继续循环了可以直接跳出循环if(k0)break;ansmax(ans,rl1);}coutans\n;return

#includebits/stdc.h

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

x:a)cntx/mid;//mid当作高度(我们去找这个最高的高度mid)//那么cnt即为数量if(cntk)lmid;else

coutl\n;return

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

x:a)cinx;sort(a.begin(),a.end());vectorll

i1;in;i){pre_sum[i]pre_sum[i-1]((n-i)*(n-i-1))/2;//排列组合每次都选择当前是最小的数然后从后面取两个所以是从n-i个里选两个}while(q--){ll

k;cink;couta[lower_bound(pre_sum.begin(),pre_sum.end(),k)-pre_sum.begin()-1]\n;}return

}9.6、体育健将

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

a.firsta.secondb.firstb.second;

int

i0;in;i)cina[i].second;sort(a.begin(),a.end(),cmp);vectorll

in-1;i0;i--)mn[i]min(mn[i1],a[i].first);for(int

}coutn\n;return

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

r1;while(p!0){if(p1){r(r*b)%k;}b(b*b)%k;p1;}return

int

b,p,k;cinbpk;coutksm(b,p,k)\n;return

}10.2、最近公共祖先LCA查询

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

u,v;cinuv;graph[v].push_back(u);graph[u].push_back(v);//邻接矩阵}//倍增数组vectorarrayint,21

fa(n1);//arrayint,21

dep(n1);//深度functionvoid(int,int)

dfs

i1;i20;i){fa[x][i]fa[fa[x][i-1]][i-1];}//遍历数组for(const

auto

tox:graph[x]){if(toxf)continue;dep[tox]dep[x]1;dfs(tox,x);}};dfs(1,0);auto

glca

y){if(dep[x]dep[y])swap(x,y);int

i20;i0;i--){if(di

fa[y][i]){xfa[x][i];yfa[y][i];}}return

fa[x][0];};int

x,y;cinxy;coutglca(x,y)\n;}return

}10.3、理想之城

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

说明已经经过这个传送门就造成了一个闭环咱们只需要找到这个环的长度让k对它求模if(fa[now]!0){int

leni-fa[now];int

pint(k%len);//now当前位置步长pcoutjump(now,p)\n;return

0;}else{fa[now]i;//记录cur传送门的下标nowa[now];//更新now的值}if(ik){coutnow\n;return

#includebits/stdc.h

ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using

i0;iinf;i){if(fa[i][j-1]inf)fa[i][j]inf;//防止数组越界

fa[i][j]fa[fa[i][j-1]][j-1];}}ans

a;for(int

i30;i0;i--){if(qi1){ansfa[ans][i];}}coutans\n;return