柚子快報激活碼778899分享：c++ 基礎(chǔ)算法(二)#藍橋杯

http://yzkb.51969.com/

文章目錄

8、雙指針8.1、挑選子串8.2、聰明的小羊肖恩8.3、神奇的數(shù)組

9、二分9.1、跳石頭9.2、可湊成的最大花朵數(shù)9.3、最大通過數(shù)9.4、妮妮的月餅廣場9.5、基德的神秘冒險9.6、體育健將

10、倍增10.1、快速冪10.2、最近公共祖先LCA查詢10.3、理想之城10.4、數(shù)的變換

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<=n;i++)cin>>a[i];

ll ans=0;

//快慢指針

for(int i=1,j=0,cnt=0;i<=n;i++){

//i>j 說明區(qū)間不合法,j+1 表示向右移還有空間,cnt=k

while(i>j||(j+1<=n&&cnt

cnt+=(a[++j]>=m);

}

if(cnt>=k){

//滿足條件的情況下,找到這個最小區(qū)間[i,j],有n-j+1個子串

ans+=n-j+1;

}

//a[i]>=m的話,就重新向后找到滿足的cnt

cnt-=(a[i]>=m);

}

cout<

return 0;

}

8.2、聰明的小羊肖恩

#include

#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 - ai

ll n;cin>>n>>l>>r;

vector a(n);

for(auto &x:a)cin>>x;

sort(a.begin(),a.end());

ll ans=0;

// 超時

// for(int i=0;i

// for(int j=i+1;j

// ans+=isT(a[i]+a[j]);

// }

//很多時候雙指針問題，都可以使用二分替代

for(int i=0;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<

return 0;

}

8.3、神奇的數(shù)組

#include

#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

// 異或可以理解成不進位加法

// 區(qū)間和，區(qū)間異或和，要想到前綴和，雖然這題不太能這么做，但也得想到這一點

// x + y >= x xor y

// 如果 x + y = x xor y，意味著加法不能進位，x and y = 0

// 因為 x and y = 0，所以 x xor y 一定會多一些 1

int main(){

IOS;

int n;cin>>n;

vector 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

int r=l;

int sum_xor=0;

while(r

if(a[r]==0){

r=r+zero[r];

}else{

if(sum_xor & a[r])break;

sum_xor^=a[r];

r++;

}

}

ans+=r-l;

}

cout<

return 0;

}

9、二分

二分的思想是什么呢？

是不是我們可以這樣想，如果我們有答案了，那么肯定是符合題意的，所以說我們可以枚舉所有可能正確的答案。

9.1、跳石頭

#include

#include

#define ll long long

using namespace std;

const int N = 1e6+10;

ll a[N],n,m,l1;

int check(int mid){

int res=0,last=0;

for(int i=1;i<=n;i++){

// 這里我一直以為的是最短跳躍距離是mid

// 其實還是沒有讀懂題意

// 題意是：移走m塊巖石，此時所有巖石之間的最短距離要求是最長的

// 所以我們只需要移走最短距離的m塊巖石即可

if(a[i]-a[last]

res++;continue;

}

last=i;

}

if(l1-a[last]

return res;

}

int main(){

ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

cin>>l1>>n>>m;

for(int i=1;i<=n;i++)cin>>a[i];

ll left=0,right=1e9+1;

while(left+1!=right){

ll mid=(left+right)>>1;

if(check(mid)<=m)left=mid;//比較的是巖石移動的數(shù)量

else right=mid;

}

cout<

return 0;

}

9.2、可湊成的最大花朵數(shù)

#include

#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 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<

return 0;

}

9.3、最大通過數(shù)

#include

#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 a(n),b(m);

for(auto &x:a)cin>>x;

for(auto &x:b)cin>>x;

ll r=0;

while(r

if(k-a[r]>=0){

k-=a[r];

r++;

}else break;

}

ll ans=r;

for(int l=0;l

k-=b[l];

while(r>=1&&k<0){

k+=a[r-1];

r--;

}

// k 表示的是剩余的能量,當 k 小于零時，意味著無法完成接下來的任務

// 因此，當 k 小于零時，就沒有必要繼續(xù)循環(huán)了，可以直接跳出循環(huán)

if(k<0)break;

ans=max(ans,r+l+1);

}

cout<

return 0;

}

9.4、妮妮的月餅廣場

#include

#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 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當作高度(我們?nèi)フ疫@個最高的高度mid)

//那么cnt即為數(shù)量

if(cnt>=k)l=mid;

else r=mid;

}

if(l<=0)cout<<"-1"<<'\n';

else cout<

return 0;

}

9.5、基德的神秘冒險

#include

#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 a(n);

for(auto &x:a)cin>>x;

sort(a.begin(),a.end());

vector 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;//排列組合，每次都選擇當前是最小的數(shù)，然后從后面取兩個，所以是從n-i個里選兩個

}

while(q--){

ll k;cin>>k;

cout<

}

return 0;

}

9.6、體育健將

#include

#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 &a,const pair &b){

return a.first+a.second

}

int main(){

IOS;

cin>>n>>k;

vector> a(n);

for(int i=0;i>a[i].first;

for(int i=0;i>a[i].second;

sort(a.begin(),a.end(),cmp);

vector 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

if(k

cout<

}

k-=(a[i].first+a[i].second);

}

cout<

return 0;

}

10、倍增

10.1、快速冪

#include

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<

return 0;

}

10.2、最近公共祖先LCA查詢

#include

#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> graph(n+1);

for(int i=1;i

int u,v;cin>>u>>v;

graph[v].push_back(u);graph[u].push_back(v);//鄰接矩陣

}

//倍增數(shù)組

vector> fa(n+1);//array 固定的數(shù)組大小21

vector dep(n+1);//深度

function 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];

}

//遍歷數(shù)組

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]

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<

}

return 0;

}

10.3、理想之城

#include

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 a(n + 1);

for(int i=1;i<=n;i++)cin>>a[i];

auto jump = [&](int x,int p){

for(int i=0;i

x=a[x];

}

return x;

};

vector fa(n+1);

int now=1,i=1;

while(1){

//!=0 說明已經(jīng)經(jīng)過這個傳送門，就造成了一個閉環(huán)，咱們只需要找到這個環(huán)的長度，讓k對它求模

if(fa[now]!=0){

int len=i-fa[now];

int p=int(k%len);

//now：當前位置；步長：p

cout<

return 0;

}else{

fa[now]=i;//記錄cur傳送門的下標

now=a[now];//更新now的值

}

if(i==k){

cout<

return 0;

}

i++;

k--;//傳送的次數(shù)

}

return 0;

}

10.4、數(shù)的變換

#include

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 + c

if(b==1){

cout<

}

ll ans=0;

vector> 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;//防止數(shù)組越界

//將當前位置的值，設(shè)置為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<

return 0;

}

柚子快報激活碼778899分享：c++ 基礎(chǔ)算法(二)#藍橋杯

http://yzkb.51969.com/

文章來源