柚子快報(bào)邀請(qǐng)碼778899分享：c++ 基礎(chǔ)算法(一)#藍(lán)橋杯

http://yzkb.51969.com/

文章目錄

1、模擬1.1、DNA序列修正1.2、無盡的石頭

2、遞歸2.1、帶備忘錄的斐波那契數(shù)列2.2、數(shù)的計(jì)算

3、進(jìn)制轉(zhuǎn)換3.1、進(jìn)制轉(zhuǎn)換模板3.2、Alice和Bob的愛恨情仇

4、前綴和4.1、前綴和模板4.2、區(qū)間次方和4.3、小鄭的藍(lán)橋平衡串4.4、大石頭的搬運(yùn)工4.5、最大數(shù)組和4.6、四元組問題**

5、差分5.1、區(qū)間更新（一維差分）5.2、肖恩的投球游戲加強(qiáng)版5.4、泡澡

6、離散化6.1、離散化舉例

7、貪心7.1、談判（優(yōu)先隊(duì)列）7.2、紀(jì)念品分組（雙指針）7.3、分糖果7.4、珠寶的最大交替和7.5、小藍(lán)的禮物7.6、四個(gè)瓷瓶的神秘游戲**7.7、雞哥的購物挑戰(zhàn)7.8、冒險(xiǎn)者公會(huì)7.9、明日方舟大作戰(zhàn)

1、模擬

1.1、DNA序列修正

#include

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int main(){

IOS;

int N;cin>>N;

string s,t;

cin>>s>>t;

for(int i=0;i

switch (s[i]) {

case 'A':

s[i]='T';

break;

case 'T':

s[i]='A';

break;

case 'C':

s[i]='G';

break;

case 'G':

s[i]='C';

break;

}

}

int ans=0;

for(int i=0;i

if(s[i]==t[i])continue;

for(int j=i+1;j

if(t[j]==s[i]&&t[i]==s[j]){

//一次操作兩個(gè)正確位置

swap(t[i],t[j]);

break;

}

}

//不能一次操作兩個(gè)的話，那么只能操作一次，直接++就可以了

//因?yàn)橹恍枰涗浗粨Q次數(shù)就行了，所以并不是必須交換的

ans++;

}

cout<

return 0;

}

1.2、無盡的石頭

#include

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1000000;

vector a(N+1,-1);

int sm(int x){

int s=0;

while(x){

s+=(x%10);

x/=10;

}

return s;

}

int main(){

IOS;

int t;cin>>t;

a[1]=0;

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

if(a[i]==-1)continue;

int x=i+sm(i);

if(x>N)break;//大于1e6的話就不再查詢了

a[x]=a[i]+1;//a[i+sm(i)]=a[i]+1

}

while(t--){

int n;cin>>n;

cout<

}

return 0;

}

2、遞歸

2.1、帶備忘錄的斐波那契數(shù)列

#include

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

using ll = long long;

const int N=1e5+9;

const ll p=1e9+7;

//備忘錄

ll dp[N];

ll fib(int n){

if(dp[n])return dp[n];

if(n<=2)return 1;

return dp[n]=(fib(n-1)+fib(n-2))%p;

}

int main(){

IOS;

int n;cin>>n;

for(int i=600;i<=n;i++)cout<

return 0;

}

2.2、數(shù)的計(jì)算

#include

using namespace std;

int a[10001];

int dfs(int dep){

int res=1;

for(int i=1;i<=a[dep-1]/2;i++){

a[dep]=i;//計(jì)算每一層的個(gè)數(shù)

res+=dfs(dep+1);//將每一層的個(gè)數(shù)累加

}

return res;//返回的是每一層的個(gè)數(shù)

}

int main()

{

int n;cin>>n;

a[1]=n;//第一層是 6

cout<

return 0;

}

3、進(jìn)制轉(zhuǎn)換

3.1、進(jìn)制轉(zhuǎn)換模板

#include

using namespace std;

char ch[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

using ll = long long;

const int N=32;

int a[N];

int main() {

int T;cin>>T;

while(T--){

int n,m;cin>>n>>m;

string s;cin>>s;

int len=s.size();

for(int i=0;i

if(s[i]>='0'&&s[i]<='9'){

a[i]=s[i]-'0';

}else{

a[i]=s[i]-'A'+10;

}

}

//any -> 10進(jìn)制

ll x=0;

for(int i=0;i

x=x*n+a[i];

}

//10進(jìn)制 -> any

string ans;

while(x){

ans+=ch[x%m];

x/=m;

}

reverse(ans.begin(),ans.end());

cout<

}

return 0;

}

3.2、Alice和Bob的愛恨情仇

#include

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

// k 是奇數(shù)，每次取 k^m, m >= 0

// 假設(shè)只有一堆小餅干，有 x 個(gè)小餅干，先手勝還是輸呢？

// k^m 是奇數(shù)，又因?yàn)?k^m 可以等于 1

// 如果 x 是奇數(shù)，無論后手怎么取，我先手永遠(yuǎn)取 1，等于說在我先手操作之后，小餅干的數(shù)量永遠(yuǎn)是偶數(shù)

// 而 0 是偶數(shù)

// 所以先手必勝

// 如果 x 是偶數(shù)，無論先手怎么取，我后手永遠(yuǎn)取 1，同理，后手必勝

// 回到原問題

// 設(shè)一共有 p 個(gè)小餅干（不管有多少堆）

// 如果 p 是奇數(shù)，先手永遠(yuǎn)取 1，先手必勝

// 如果 p 是偶數(shù)，后手永遠(yuǎn)取 1，后手必勝

int main(){

IOS;

int n,k;cin>>n>>k;

int ans=0;

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

int num;cin>>num;

ans+=num;

}

if(ans%2==0)cout<<"Bob"<<"\n";

else cout<<"Alice"<<"\n";

return 0;

}

4、前綴和

4.1、前綴和模板

#include

using namespace std;

//(前綴和)前綴和只適用于靜態(tài)數(shù)組的情況，即進(jìn)行區(qū)間查詢；

//(差分)如果實(shí)現(xiàn)先區(qū)間修改，再區(qū)間查詢就可以使用差分?jǐn)?shù)組；

//(樹狀數(shù)組和線段樹)如果需要一邊修改，一邊查詢就需要使用樹狀數(shù)組或線段樹

const int N = 10001;

int prefix[N],a[N];

int main(){

int n;cin>>n;

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

cin>>a[i];

prefix[i]=prefix[i-1]+a[i];

}

int l,r;

cin>>l>>r;

//求區(qū)間和 sum(l,r)=prefix[r]-prefix[l-1]

int sum;sum=prefix[r]-prefix[l-1];

cout<

return 0;

}

4.2、區(qū)間次方和

#include

using namespace std;

const long long N = 1e5+9;

const long long P = 1e9+7;

long long prefix[6][N],a[6][N];

int main(){

int n,m;cin>>n>>m;

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

cin>>a[1][i];

}

for(int i=2;i<=5;i++){

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

a[i][j]=a[i-1][j]*a[1][j];

}

}

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

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

prefix[i][j]=prefix[i][j-1]+a[i][j];

}

}

while(m--){

int l,r,k;cin>>l>>r>>k;

cout<<(prefix[k][r]-prefix[k][l-1])%P<<"\n";

}

return 0;

}

4.3、小鄭的藍(lán)橋平衡串

#include

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1001;

char s[N];

int prefix[N];

int main(){

IOS;

cin>>s+1;

int n=strlen(s+1);

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

prefix[i]=prefix[i-1]+(s[i]=='L'?1:-1);

}

int ans=0;

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

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

if((prefix[j]-prefix[i-1])==0){

ans=max(ans,j-i+1);

}

}

}

cout<

return 0;

}

4.4、大石頭的搬運(yùn)工

#include

using namespace std;

using Pair=pair;

using ll=long long;

//帶權(quán)中位數(shù)的計(jì)算

//|x-1| + |x-3| + |x-6| + |x-13|

//求，此時(shí)x=? 結(jié)果最小，毫無疑問的是等于中位數(shù)的時(shí)候

int main() {

int n;cin >> n;

vector a(n);

ll sw = 0;

//p初始位置，w權(quán)值

for(auto &[p,w]:a){

cin>>w>>p,sw+=w;//計(jì)算w的和

}

sort(a.begin(), a.end());//根據(jù)pair的第一個(gè)大小排序，也就是p

ll nw=0;//左側(cè)的w數(shù)據(jù)

int x=0;//中位數(shù)

for (const auto &[p, w]: a) {

//nw*2

//因?yàn)檎业阶钚〉膸?quán)中位數(shù)

if(nw*2

x=p;break;

}

nw+=w;

}

//10^5*10^5 > 10^8 所以使用long long

ll ans = 0;

for (const auto &[p, w]: a) {

ans+=(ll)w*abs(p-x);

}

cout <

return 0;

}

4.5、最大數(shù)組和

#include

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

using ll = long long;

int main(){

IOS;

int t;cin>>t;

while(t--){

int n,k;cin>>n>>k;

vector prefix(n+1,0),a(n,0);

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

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

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

prefix[i]=prefix[i-1]+a[i-1];

}

ll ans=0;

for(int i=0;i<=k;i++){

// 0 1 2 3 ... n-k-1

// 2*k ... n-1

ans=max(ans,prefix[n-(k-i)]-prefix[2*i]);

}

cout<

}

return 0;

}

4.6、四元組問題**

#include

using namespace std;

int main(){

int n;cin>>n;

if(n<4){

cout<<"No"<<"\n";return 0;

}

int k=INT_MIN,m=INT_MAX;

vector v(n+1),rmin(n+1,m);

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

// a nums[d]

//先找 c nums[d]

for(int i=n-1;i>=1;i--){

// i 位置右邊最小的值是 rmin[i] 即為nums[d]

rmin[i]=min(rmin[i+1],v[i+1]);

}

stack s;

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

//k nums[b],v[i] nums[a],rmin[i] nums[d]

//因?yàn)橛衦min[i]的存在，所以就肯定有nums[c]

if(v[i]rmin[i]){//當(dāng)前的值

cout<<"YES";return 0;

}

//單調(diào)棧

//尋找 nums[a]

while(!s.empty()&&s.top()

k=max(k,s.top());

s.pop();

}

s.push(v[i]);

}

cout<<"NO";

return 0;

}

5、差分

5.1、區(qū)間更新（一維差分）

#include

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

/*

對(duì)差分?jǐn)?shù)組做前綴和，可以得到原數(shù)組

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

diff[i]=a[i]-a[i-1];

將區(qū)間都加上x:

diff[l]+=x;

diff[r+1]-=x;

*/

const int N = 1e5+5;

int a[N],diff[N];

int main() {

IOS;

int n,m;

while(cin>>n>>m){

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

cin>>a[i];

diff[i]=a[i]-a[i-1];

}

while(m--){

int x,y,z;cin>>x>>y>>z;

diff[x]+=z;

diff[y+1]-=z;

}

for(int i=1;i<=n;i++)a[i]=a[i-1]+diff[i];

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

cout<<"\n";

}

return 0;

}

5.2、肖恩的投球游戲加強(qiáng)版

#include

using namespace std;

const int N = 2001;

long long a[N][N],d[N][N];

void solve(const int &Case) {

int n,m,q;cin>>n>>m>>q;

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

for(int j=1;j<=m;j++){

cin>>a[i][j];

d[i][j]=a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1];//差分

}

int x1,y1,x2,y2,c;

while(q--){

cin>>x1>>y1>>x2>>y2>>c;

//操作區(qū)間數(shù)據(jù)

d[x1][y1]+=c;

d[x2+1][y1]-=c;

d[x1][y2+1]-=c;

d[x2+1][y2+1]+=c;

}

//前綴和求原數(shù)組

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

for(int j=1;j<=m;j++){

a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+d[i][j];

}

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

for(int j=1;j<=m;j++)

cout<

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

int T=1;

for(int Case=1;Case<=T;Case++)solve(Case);

return 0;

}

5.4、泡澡

#include

using namespace std;

const int N = 2e5+5;

using ll = long long;

ll a[N];

void solve(const int &Case) {

int n,w;cin>>n>>w;

while(n--){

int l,r,p;cin>>l>>r>>p;

a[l]+=p;

a[r]-=p;

}

for(int i=1;i

for(int i=0;i

if(a[i]>w){

cout<<"No\n";return;

}

}

cout<<"Yes\n";

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

int T=1;

for(int Case=1;Case<=T;Case++)solve(Case);

return 0;

}

6、離散化

6.1、離散化舉例

#include

using namespace std;

vector L;//離散化數(shù)組

int getidx(int x) {

return lower_bound(L.begin(),L.end(),x)-L.begin();

}

const int N = 1e5 + 9;

int a[N];

int main() {

int n;cin>>n;

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

//將元素存入到L數(shù)組中去

for(int i=1;i<=n;i++)L.push_back(a[i]);

//排序去重

/*unique的功能是去除相鄰的重復(fù)元素(只保留一個(gè)),其實(shí)它并不真正把重復(fù)的元素刪除,

是把重復(fù)的元素移到后面去了，然后依然保存到了原數(shù)組中，

然后 返回去重后最后一個(gè)元素的地址，因?yàn)閡nique去除的是相鄰的重復(fù)元素*/

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

L.erase(unique(L.begin(),L.end()),L.end());

cout<<"離散化數(shù)組為：";

for(const auto &i:L)cout<

int v;cin>>v;

cout<

return 0;

}

7、貪心

7.1、談判（優(yōu)先隊(duì)列）

#include

using namespace std;

using ll =long long;

priority_queue,greater> pq;

void solve(const int &Case) {

int n;cin>>n;

for(int i=0;i

int t;cin>>t;

pq.push(t);

}

ll ans=0;

while(pq.size()>1){

ll x=pq.top();pq.pop();

ll y=pq.top();pq.pop();

ans+=x+y;

pq.push(x+y);

}

cout<

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

int T=1;

for(int Case=1;Case<=T;Case++)solve(Case);

return 0;

}

7.2、紀(jì)念品分組（雙指針）

#include

using namespace std;

const int N = 300001;

int a[N];

void solve(const int &Case) {

int w,n;cin>>w>>n;

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

sort(a,a+n);

int l=0,r=n-1;

int ans=0;

while(l<=r){

ans++;

if(l==r)break;

if(a[l]+a[r]<=w){

l++;r--;

}else{

r--;

}

}

cout<

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

int T=1;

for(int Case=1;Case<=T;Case++)solve(Case);

return 0;

}

7.3、分糖果

#include

using namespace std;

const int N = 1e6+9;

char s[N];

//題意：將字符串分為x個(gè)，這個(gè)x個(gè)的大小差距要求盡可能小，讓后找到里面最大的字符串

void solve(const int &Case) {

int n,x;cin>>n>>x;

cin>>s+1;

sort(s+1,s+1+n);

if(s[1]==s[n]){ // a a a a a a a 3

for(int i=1;i<=n/x+(n%x?1:0);i++)cout<

}else if(s[1]==s[x]){ // a a a b b c d d 3

for(int i=x;i<=n;i++)cout<

}else{// a a b c c d 3

cout<

}

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

int T=1;

for(int Case=1;Case<=T;Case++)solve(Case);

return 0;

}

7.4、珠寶的最大交替和

#include

using namespace std;

using ll = long long;

const int N = 1e6+5;

ll a[N];

void solve(const int &Case) {

int n;cin>>n;

for(int i=0;i

int num;cin>>num;

a[i]=abs(num);

}

ll sum=0;

for(int i=0;i

sum+=(ll)pow(-1,i)*a[i];

}

ll mx=INT_MIN,mn=INT_MAX;

for(int i=0;i

if(a[i]

}

for(int i=1;i

if(a[i]>mx)mx=a[i];

}

cout<

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

int T=1;

for(int Case=1;Case<=T;Case++)solve(Case);

return 0;

}

7.5、小藍(lán)的禮物

#include

using namespace std;

using ll = long long;

const int N = 1e6+5;

ll a[N];

void solve(const int &Case) {

int n,k;cin>>n>>k;

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

sort(a,a+n);

ll sum=0;

for(int i=0;i

if(sum+(a[i]+1)/2>k){

cout<

return;

}

sum+=a[i];

}

cout<

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

int T=1;

for(int Case=1;Case<=T;Case++)solve(Case);

return 0;

}

7.6、四個(gè)瓷瓶的神秘游戲**

#include

using namespace std;

using ll = long long;

ll num = 3;

ll func(const ll &a,const ll &b,const ll &c){

ll A=a+2*b;

ll B=0;

ll C=c-b;

ll t=C/3;

if(A==0)return 0;

C%=num;

if(C==0||C==1){

return A+3*t;

}else return A+3*t+1;

}

int main(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

vector a(4);

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

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

cout<

return 0;

}

7.7、雞哥的購物挑戰(zhàn)

#include

using namespace std;

const int N =2e5+1;

long long a[N];

void solve(const int &Case){

int n;cin>>n;

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

//加一個(gè) greater()那么就按照從大到小排序了

sort(a,a+n,greater());

long long ans=0;

for(int i=0;i

if(i==n-1)continue;

if(a[i]+a[i+1]>0)ans+=a[i]+a[i+1];

else break;

}

cout<

}

int main(){

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

int T=1;

for(int Case=1;Case<=T;Case++)solve(Case);

return 0;

}

7.8、冒險(xiǎn)者公會(huì)

#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 m,n;cin>>m>>n;//m個(gè)冒險(xiǎn)者，n個(gè)村莊

vector a(m);//每位冒險(xiǎn)者的能力值

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

vector> b(n);//每個(gè)村莊的任務(wù)量

int mxk=0;

for(auto &x:b){

int k;cin>>k;//第n個(gè)村莊的任務(wù)量 b[][]

x.resize(k);//調(diào)整第n個(gè)村莊數(shù)量

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

sort(x.begin(),x.end());//對(duì)第二維的向量排序

mxk=max(mxk,k);//mxk是所有村莊中最大的任務(wù)量

}

sort(a.begin(), a.end());//能力值

int j=n-1;

//記錄冒險(xiǎn)者完成的任務(wù)數(shù)量

vector c(m);

//初始化最大任務(wù)量為 0

ll ans=0;

for (int T = 0; T < mxk; T++) {

int mx = 0;//m個(gè)冒險(xiǎn)者，n個(gè)村莊

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

// 取 vector 元素前一定要判斷是否為空

//遍歷所有村莊，找到一個(gè)最大的難度值

if (!b[i].empty())mx=max(mx, b[i].back());

}

//尋找能夠完成當(dāng)前任務(wù)的冒險(xiǎn)者(能力值>=難度值)

while (j > 0 && a[j - 1] >= mx)j--;

if (a[j] < mx) { // 如果最難的任務(wù)不能被任何冒險(xiǎn)者完成，則輸出 -1

cout << "-1\n";return 0;

}

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

if (!b[i].empty())b[i].pop_back();

}

c[j]++;//記錄冒險(xiǎn)者完成的任務(wù)數(shù)量

}

for (int i = 0; i < m; i++) {

if (c[i] > 1) {

if (i == m - 1) { // 當(dāng)前沒有比這個(gè)冒險(xiǎn)者還強(qiáng)的了，但是仍然需要，所以輸出 -1

cout << "-1\n";return 0;

}

//一個(gè)人只能出戰(zhàn)一次

c[i + 1] += c[i] - 1, c[i] = 1;

}

if (c[i] == 1)ans += a[i];

}

cout<

return 0;

}

7.9、明日方舟大作戰(zhàn)

#include

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

using namespace std;

using ll = long long;

using Pair = pair;

int main(){

IOS;

int n,m,B;cin>>n>>m>>B;

vector a(n);

for(auto &[x,y]:a)cin>>x>>y;//攻擊力，費(fèi)用

int mx = 0;

for (int i = 0; i < m; i++) {

int x;cin >> x;

mx = max(mx, x);//敵人最大的生命值 mx

}

vector f(B + 1, INT_MIN);

f[0] = 0;

for (auto &[x, y]: a) {

//如果當(dāng)前物品的費(fèi)用大于背包容量 B，則跳過此物品

if (y > B)continue;

//將當(dāng)前狀態(tài)向量 f 復(fù)制給 g，作為備份

auto g = f;

//swap(f) 將新創(chuàng)建的向量與向量 f 進(jìn)行交換

//這樣做的目的是清空 f 中的內(nèi)容，并將其大小調(diào)整為 B + 1

//這種做法可以更有效地清空 f，

//避免了遍歷 f 來賦予初始值的過程，提高了效率

vector(B + 1, INT_MIN).swap(f);

for (int i = 0; i < y; i++) {

f[i] = g[i];

}

//更新背包容量大于等于當(dāng)前物品費(fèi)用的狀態(tài)值

for (int i = y; i <= B; i++) {

f[i] = max(g[i], g[i - y] + x);

}

}

int Mx = *max_element(f.begin(), f.end());

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

else cout << (mx + Mx - 1) / Mx << '\n';

return 0;

}

柚子快報(bào)邀請(qǐng)碼778899分享：c++ 基礎(chǔ)算法(一)#藍(lán)橋杯

http://yzkb.51969.com/

相關(guān)文章