首页 > 其他分享 >蓝桥杯学习日记

蓝桥杯学习日记

时间：2024-04-09 11:15:02浏览次数：15  
标签：std 学习 const int res namespace 蓝桥 include 日记

目录

image-20231108195706138

image-20231218131823182

以空间换时间

image-20231218131909749

image-20231218131737143

const int N=110;

int n,m,s;

char q[N][N];

n,m,s这种未初始化的变量，放在要放在q[N] [N]数组的前面

int res = 0x3f3f3f3f;表示无穷大

image-20240306111145114

方法 二分+区间合并
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=100010;
int n,m;
PII w[N],q[N];

bool check(int mid){//利用区间合并判断当前时间是否满足水管被全覆盖
    int cnt=0;
    for(int i=0;i<n;i++){
        int L=w[i].x,S=w[i].y;
        if(S<=mid){
            int t=mid-S;
            int l=max(1,L-t),r=min((LL)m,(LL)L+t);
            q[cnt++]={l,r};
        }

    }
    sort(q,q+cnt);//这里是区间合并的公式，先进行排序，然后初始化st，ed等于-1，如果第一个区间的末端点小于等于ed,两个区间可以合并，ed=max(ed,第一个区间末端点)；否则 不可以合并，开一个新区间，st,ed=这个区间的起点和终点；
    int st=-1,ed=-1;
    for(int i=0;i<cnt;i++){
        if(q[i].x<=ed+1)ed=max(ed,q[i].y);
        else {st=q[i].x;ed=q[i].y;}
    }

    return st==1&&ed==m;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d%d",&w[i].x,&w[i].y);
    }
    int l=0,r=2e9;//二分满足水流全覆盖水管的时间
    while(l<r){
        int mid=(LL)l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",r);

}

image-20240308095040280

image-20240308095001208

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 100010;
int n,m;
int  a[N],b[N];

bool check(int mid){
    LL res=0;
    for(int i=0;i<n;i++){
        if(a[i]>=mid){
            res+=(a[i]-mid)/b[i]+1;
        }
    }
    return res>=m;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    int l=0,r=1e6;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    LL res=0,cnt=0;
    for(int i=0;i<n;i++){
        if(a[i]>=r){
            int c=(a[i]-r)/b[i]+1;
            cnt+=c;
            int ed=a[i]-(c-1)*b[i];
            res+=(LL)(a[i]+ed)*c/2;
        }
    }

    printf("%lld\n",res-(cnt-m)*r);
    return 0;
}

二分数值0~1e6，通过数列的性质，判断当前数值是否满足>=m的性质，当所取数值过小时，大于该数值的个数就会大

image-20240312104825588等于m,当所取

方法 差分

数值过大时，大于该数值的数值就会小于m。

差分是将对区间的操作转化成对两个数的操作
将差值数组转换成差分数组，从差值数组变成全零数组，和从差分数组变成全零数组的步骤是一样的，
但是差分数组每次只需要改两个数

#include <iostream>
using namespace std;
const int N=100010;
int n;
int p[N],t[N],d[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i]);
        d[i]=p[i]-t[i];
    }
    //差分是将对区间的操作转化成对两个数的操作
    /*将差值数组转换成差分数组，从差值数组变成全零数组，和从差分数组变成全零数组的步骤是一样的，
    但是差分数组每次只需要改两个数*/

    for(int i=n+1;i>0;i--){
        d[i]-=d[i-1];
    }
    int res=0;
    for(int i=1;i<=n+1;i++){
        if(d[i]>0)res+=d[i];
    }
    printf("%d",res);
    return 0;
}

sort(w+1;W+n;greater());//greater()采用降序排列，默认是升序排列

image-20240315151747683

image-20240315154451709

思路：先用离散化，将ai数列离散化，这样ai数列就相对来说是有序的了，然后再将bi数列按照ai数列映射一下，得到的下标是无序的，这样就只需要求一下bi序列映射后的下标逆序数就能求出最小交换次数。

如何求逆序数？

  • ​ 归并排序

    ​

  • ​ 树状数组

image-20240318215619520

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int months[]{
    0,31,30,31,30,31,30,31,31,30,31,30,31
};
//一三五七八十腊，三十一天永不差
//四六九冬三十日，平年二月二十八，闰年二月加一天
//闰年的判断条件年份
//year%4==0&&year%100!=0 或者 year%400==0
int is_leap(int year){
    if(year%4==0&&year%100!=0||year%400==0)return 1;
    else return 0;
}
int get_day(int y,int m){
    if(m==2)return 28+is_leap(y);
    else return months[m];

}
int cal(int y,int m,int d){
    int res=0;
    for(int i=1;i<y;i++)res+=365+is_leap(i);
    for(int i=1;i<m;i++)res+=get_day(y,i);
    res+=d;
    return res;
}
int main(){
    int y1,m1,d1,y2,m2,d2;
    while(~scanf("%04d%02d%02d\n%04d%02d%02d",&y1,&m1,&d1,&y2,&m2,&d2))
        printf("%d\n",abs(cal(y1,m1,d1)-cal(y2,m2,d2))+1);
    return 0;
}

搜索与图论

全排列

直接采用dfs

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N =10;
int n;
int path[N];
bool st[N];

void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++)printf("%d",path[i]);
        puts("");
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            st[i]=false;
        }

    }
}

int main(){
    cin>>n;
    dfs(0);
    return 0;

}
n皇后问题

image-20240327182515292

1.按每行进行搜索

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N =20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N];

void dfs(int u){

      if(u==n){
        for(int i=0;i<n;i++)puts(g[i]);
        puts("");
        return ;
      }

    for(int i=0;i<n;i++){
        if(!col[i]&&!dg[u+i]&&!udg[n+u-i]){
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[n+u-i]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[n+u-i]=false;
            g[u][i]='.';
        }

    }

}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            g[i][j]='.';
    }
    dfs(0);

    return 0;
}

2.每个点进行搜索

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N =20;
int n;
char g[N][N];
bool row[N],col[N],dg[N],udg[N];

void dfs(int x, int y,int s){
    if(y==n)y=0,x++;
    if(x==n){
      if(s==n){
        for(int i=0;i<n;i++)puts(g[i]);
        puts("");

      }
      return ;
    }
    dfs(x,y+1,s);

    if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[n+x-y]){
            g[x][y]='Q';
            row[x]=col[y]=dg[x+y]=udg[n+x-y]=true;
            dfs(x,y+1,s+1);
            row[x]=col[y]=dg[x+y]=udg[n+x-y]=false;
            g[x][y]='.';
    }


}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            g[i][j]='.';
    }
    dfs(0,0,0);

    return 0;
}
走迷宫

image-20240329161425179

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出：
8
*/
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
int g[N][N];
int d[N][N];
PII q[N*N];
int bfs(){
    int hh=0,tt=0;
    q[0]={0,0};
    memset(d,-1,sizeof d);
    d[0][0]=0;
    while(hh<=tt){
        auto t=q[hh++];
        int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
        for(int i=0;i<4;i++){
            int x=t.first+dx[i],y=t.second+dy[i];
            if(d[x][y]==-1&&g[x][y]==0&&x>=0&&x<n&&y>=0&&y<m){
                d[x][y]=d[t.first][t.second]+1;
                q[++tt]={x,y};
            }

        }
    }
return d[n-1][m-1];

}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>g[i][j];
        }
    }
    cout<<bfs();
    return 0;
}
树的重心

树图的深度优先遍历

image-20240329171309891

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出;
4
*/
using namespace std;

const int N=100010,M=N*2;//无向图边要翻倍
int n,m;
int h[N],e[N],ne[N],idx;
bool st[N];
int ans=N;
int dfs(int u){
    st[u]=true;
    int sum=1,res=0;//sum当前是一个节点，res存储子树中节点最多的分支节点数
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            int s=dfs(j);
            res =max(res,s);
            sum+=s;
        }
    }
    res = max(res,n-sum);//求当前节点的最大节点数，用来比较
    ans=min(ans,res);
    return sum;
}
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int main(){
    cin>>n;

    memset(h,-1,sizeof h);

    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1);
    cout<<ans;
    return 0;
}
图中点的层次

树图的宽度优先遍历

image-20240329174129775

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
1 2
2 3
3 4
1 3
1 4
输出;
1
*/
using namespace std;

const int N=100010,M=N;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];
int q[N];


void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int bfs(){
      int hh=0,tt=0;
      q[0]=1;
      memset(d,-1,sizeof d);
      d[1]=0;
      while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(d[j]==-1){
                d[j]=d[t]+1;
                q[++tt]=j;
            }

        }

      }
    return d[n];
}
int main(){
    cin>>n>>m ;

    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    cout<<bfs();
    return 0;
}
有向图的拓扑排序

image-20240329204512268

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
3 3
1 2
2 3
1 3
输出;
1 2 3
*/
using namespace std;
const int N = 100010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];
int q[N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++){
        if(!d[i])q[++tt]=i;
    }
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            d[j]--;
            if(!d[j]){
                q[++tt]=j;
            }
        }
    }
    return tt==n-1;

}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(d,0,sizeof d);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    if(topsort()){
        for(int i=0;i<n;i++){
            cout<<q[i]<<" ";
        }
        cout<<endl;
    }
    else
    cout<<"-1";
    return 0;
}

image-20240329205916190

数学知识

数论
质数：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者素数
质数判定 - 试除法

image-20240403205757764

O(n)
bool is_prime(int n){
    if(n<2)return false;
    for(int i=2;i<n;i++){
        if(n%i==0)return false;
    }
    return true;
}
O(sqrt(n))
  bool is_prime(int n){
    if(n<2)return false;
    for(int i=2;i<n/i;i++){
        if(n%i==0)return false;
    }
    return true;
}
质因数：将正整数表示为一连串的质因子相乘
分解质因数- 试除法

image-20240403210240311

O(n)
void divide(int n){
    for(int i=2;i<=n;i++){
        if(n%i==0){
            int s=0;
            while(n%i==0){
                n/=i;
                s++;
            }
            cout<<i<<' '<<s<<endl;
        }
    }
}
O(sqrt(n)) 大于sqrt(n）的质因子最多只有一个
void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int s=0;
            while(n%i==0){
                n/=i;
                s++;
            }
            cout<<i<<' '<<s<<endl;
        }
    }
    if(n>1) cout<<n<<' '<<1<<endl;
}
筛质数

image-20240403211035191

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
/*
输入：
8
输出;
4
*/
using namespace std;
const int N =1000010;
int primes[N],cnt;
bool st[N];
void get_primes(int n){//O(n*n)
    for(int i=2;i<=n;i++){
        if(!st[i])primes[++cnt]=i;
        for(int j=i+i;j<=n;j+=i)st[j]=true;
    }
}
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]){//埃式筛法，加个括号，只删质数的倍数，时间复杂度O(nloglogn)
        primes[++cnt]=i;
        for(int j=i+i;j<=n;j+=i)st[j]=true;
        }
    }
}
void get_primes(int n){//线性筛法，时间复杂度O(n)
    for(int i=2;i<=n;i++){
        if(!st[i]){
        primes[++cnt]=i;
        }
        for(int j=1;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}
int main(){
    int n;
    cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
//    for(int i=1;i<=cnt;i++){
//        cout<<primes[i]<<' ';
//    }
    return 0;
}
约数

image-20240404114344857

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
/*
输入：
2
6
8
输出;
1 2 3 6
1 2 4 8
*/
using namespace std;
const int N =110;

vector<int> get_divisor(int n){
    vector<int> res;
    for(int i=1;i<=n/i;i++){
        if(n%i==0){
            res.push_back(i);
            if(i!=n/i)res.push_back(n/i);
        }
    }
    sort(res.begin(),res.end());
    return res;

}
int main(){
    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        auto res =get_divisor(x);

        for(int t : res){
            cout<<t<<' ';
        }
        cout<<endl;
    }
    return 0;
}
约数个数

image-20240404203018204

#include <iostream>

#include <algorithm>
#include <unordered_map>
/*
输入：
3
2
6
8
输出;
12
*/
using namespace std;

typedef long long LL;

const int mod = 1e9+7;

int main(){
    int n;
    cin>>n;
    unordered_map<int,int> primes;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1)primes[x]++;
    }
    LL res=1;
    for(auto prime: primes) res=res*(prime.second+1)%mod;
    cout<<res;
    return 0;
}
约数之和

image-20240404210525754

#include <iostream>

#include <algorithm>
#include <unordered_map>
/*
输入：
3
2
6
8
输出;
12
*/
using namespace std;

typedef long long LL;

const int mod = 1e9+7;

int main(){
    int n;
    cin>>n;
    unordered_map<int,int> primes;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1)primes[x]++;
    }
    LL res=1;
    for(auto prime: primes){
        int p=prime.first,a=prime.second;
        LL t=1;
        while(a--){
            t=(t*p+1)%mod;
        }
        res=res*t%mod;
    }
    cout<<res<<endl;
    return 0;
}
最大公约数
#include <iostream>
#include <algorithm>

/*
输入：
2
3 6
4 6
输出;
3
2
*/
using namespace std;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

int main(){
    int n;
    cin>>n;
    while(n--){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    }
    return 0;
}
公约数

image-20240409082114216

#include <iostream>
#include <algorithm>

/*
输入：
9 27
3
1 5
10 11
9 11
输出;
3
-1
9
*/
using namespace std;
const int N =1350;
int cnt;
int res[N];
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
void init_divisor (int x){

    for(int i=1;i<=x/i;i++){
        if(x%i==0){
            res[cnt++]=i;
            if(i!=x/i)res[cnt++]=x/i;
        }
    }
    sort(res,res+cnt);
}

int main(){
    int a,b;
    cin>>a>>b;
    int d = gcd(a,b);
    init_divisor(d);
    int n;
    cin>>n;
    while(n--){
        int L,R;
        cin>>L>>R;
        int l=0,r=cnt-1;
        while(l<r){
            int mid=l+r+1>>1;
            if(res[mid]<=R)l=mid;
            else r=mid-1;
        }
        if(res[r]>=L&&res[r]<=R)cout<<res[r];
        else cout<<"-1";
    }
    return 0;
}
等差数列

image-20240409085415379

#include <iostream>
#include <algorithm>

/*
输入：
5
2 6 4 10 20
输出;
10
*/
using namespace std;
const int N =100010;
int q[N];
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}


int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q[i];
    }
    sort(q+1,q+1+n);
    int d=0;
    for(int i=2;i<=n;i++){
        d=gcd(d,q[i]-q[1]);
    }

    if(!d)cout<<n<<endl;
    else {
        int res=(q[n]-q[1])/d+1;
        cout<<res<<endl;
    }
    return 0;
}

快速幂

转圈游戏

image-20240409104100806

#include <iostream>
#include <algorithm>

/*
输入：
10 3 4 5
输出;
5
*/
using namespace std;
typedef long long LL;
int qmi(int a,int b,int p){
    int res=1%p;
    while(b){
        if(b&1)res=(LL)res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    return res;
}
int main(){
    int n,m,k,x;
    cin>>n>>m>>k>>x;
    cout<<(x+(LL)qmi(10,k,n)*m)%n;
    return 0;
}

动态规划

背包

  • 01背包
  • 完全背包
  • 多重背包
  • 分组背包
01背包

image-20240329212157055

image-20240330193125142

二维

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
1 2
2 4
3 4
4 5
输出;
8
*/
using namespace std;
const int N =1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);

        }
    }
    cout<<f[n][m];
    return 0;
}

一维

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
1 2
2 4
3 4
4 5
输出;
8
*/
using namespace std;
const int N =1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){

            if(j>=v[i])f[j]=max(f[j],f[j-v[i]]+w[i]);

        }
    }
    cout<<f[m];
    return 0;
}
完全背包
#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
1 2
2 4
3 4
4 5
输出;
10
*/
using namespace std;
const int N =1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
			for(int k =0;k*v[i]<=j;k++)
            f[i][j] = max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);

        }
    }
    cout<<f[n][m];
    return 0;
}

优化，二维

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
1 2
2 4
3 4
4 5
输出;
8
*/
using namespace std;
const int N =1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
             if(j>=v[i])f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);

        }
    }
    cout<<f[n][m];
    return 0;
}

优化，一维

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
1 2
2 4
3 4
4 5
输出;
10
*/
using namespace std;
const int N =1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=m;j++){
           
            f[j]=max(f[j],f[j-v[i]]+w[i]);

        }
    }
    cout<<f[n][m];
    return 0;
}
多重背包问题

直接暴力枚举每种物品的个数

image-20240331114547943

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出;
10
*/
using namespace std;
const int N =110;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>s[i];
    }
    for(int i=1;i<=n;i++){
        for(int j= 0;j<=m;j++){
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
            f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
        }
    }
    cout<<f[n][m];
    return 0;
}

image-20240331163742669

高效枚举法,用暴力枚举会超时

 #include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出;
10
*/
using namespace std;
const int N =25000,M=2010;
int n,m;
int v[N],w[N],s[N];
int f[N];
int main(){
    int n,m;
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s){
            cnt++;
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(k>s){
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    n=cnt;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}
分组背包问题

image-20240331161435733

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
3 5
2
1 2
2 4
1
3 4
1
4 5
输出;
8
*/
using namespace std;
const int N =110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            for(int k=1;k<=s[i];k++){
                if(j>=v[i][k])f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout<<f[m];
    return 0;
}

线性DP

数字三角形

image-20240331170040094

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出;
30
*/
using namespace std;
const int N = 510,INF=1e9;
int a[N][N];
int f[N][N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i+1;j++)
            f[i][j]=-INF;
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
       res=max(f[n][i],res);
    }
    cout<<res;
    return 0;
}
最长上升子序列

image-20240331182537009

o(n^2)

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
7
3 1 2 1 8 5 6
输出;
4
*/
using namespace std;
const int N=1010;
int a[N];
int f[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    
    
    for(int i=1;i<=n;i++){
        f[i]=1;
       for(int j=1;j<n;j++){
        if(a[j]<a[i])f[i]=max(f[j]+1,f[i]);
       }
    }
    int res=0;
    for(int i=1;i<=n;i++){
       res=max(res,f[i]);
    }
    cout<<res;
    return 0;
}
最长上升子序列

image-20240331165238089

最长公共子序列

image-20240331194104975

image-20240402083910611

01状态是包含在f[i-1,j]中的，但可以用f[i-1,j]的最大值代替01状态的最大值。

10状态是包含在f[i,j-1]中的，但可以用f[i,j-1]的最大值代替10状态的最大值.

允许求最大值有重叠

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4 5
acbd
abedc
10 10
nounjucfgh
irsfovyoah
输出;
3
2
*/
using namespace std;
const int N=1010;
char a[N],b[N];
int f[N][N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>b[i];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m];
    return 0;
}
编辑距离

image-20240402091502329

区间DP

石子合并

image-20240402092941041

image-20240402095025886

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
4
1 3 5 2
输出;
22
*/
using namespace std;
const int N=310;
int n;
int s[N];
int f[N][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    for(int i=2;i<=n;i++){
        s[i]+=s[i-1];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            f[l][r]=1e9;
            for(int k=l;k<r;k++){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    cout<<f[1][n];
    return 0;
}

数位统计Dp

计数问题

image-20240402111205561

状态压缩DP

蒙德里安的梦想

image-20240402152837538

贪心算法

区间选点

image-20240402165253625

image-20240402170231825

image-20240402170916180

最优解>=可行解

可行解>=最优解

可行解是最优解

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
3
-1 1
2 4
3 5
输出;
2
*/
using namespace std;
const int N =100010;

struct Range{
    int l,r;
    bool operator <(const Range &w)const{
        return r<w.r;
    }
}range[N];

bool cmp(Range a,Range b){
	return a.r < b.r;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        range[i]={a,b};
    }
    sort(range+1,range+1+n,cmp);
    int ed =-1e9,res=0;
    for(int i=1;i<=n;i++){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    }
    cout<<res;
    return 0;
}

结构体排序方法

第一种

在定义结构体时重载运算符,只有在进行自定义类型时才起作用,在进行基础类型比较时还是按照原来正常的加减法规则.

struct Edge{
	int a,b,w;
	bool operator< (const Edge &W)const{
		return w< W.w;
	}
}edges[M];

第二种

在排序的时候定义排序规则.

bool cmp(Edge a,Edge b){
	return a.w < b.w;
}
 
//利用sort进行排序
sort(edges+1,edges+m+1,cmp);
最大不相交区间数量

image-20240402173512587

#include <iostream>
#include <cstring>
#include <algorithm>
/*
输入：
3
-1 1
2 4
3 5
输出;
2
*/
using namespace std;
const int N =100010;

struct Range{
    int l,r;
    bool operator <(const Range &w)const{
        return r<w.r;
    }
}range[N];

bool cmp(Range a,Range b){
	return a.r < b.r;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        range[i]={a,b};
    }
    sort(range+1,range+1+n,cmp);
    int ed =-1e9,res=0;
    for(int i=1;i<=n;i++){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    }
    cout<<res;
    return 0;
}
区间分组

image-20240403110616405

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
/*
输入：
3
-1 1
2 4
3 5
输出;
2
*/
using namespace std;
const int N =100010;
priority_queue <int ,vector<int>, greater<int>> heap;
struct Range{
    int l,r;
    bool operator < (const Range &w)const{
    return l<w.l;
    }
}range[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    sort(range+1,range+1+n);

    for(int i=1;i<=n;i++){
        if(heap.empty()||range[i].l<=heap.top()){
                heap.push(range[i].r);
                }
        else{
            heap.pop();
            heap.push(range[i].r);
        }
    }
    cout<<heap.size();
    return 0;
}
区间覆盖

image-20240403112250910

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
/*
输入：
1 5
3
-1 3
2 4
3 5
输出;
2
*/
using namespace std;
const int N =100010;
int n,s,t;
struct Range{
    int l,r;
    bool operator < (const Range &w)const{
    return l<w.l;
    }
}range[N];
int main(){
    cin>>s>>t;
    cin>>n;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    sort(range+1,range+1+n);
    int res=0;
    bool success = false ;
    for(int i=1;i<=n;i++){
        int j=i,ed=-1e9;
        while(range[j].l<=s&&j<=n){
            ed=max(ed,range[j].r);
            j++;
        }

        if(ed<s){
            res=-1;
            break;
        }
        res++;
        if(ed>=t){
            success=true;
            break;
        }
        s=ed;
        i=j-1;

    }
    if(!success)res=-1;
    cout<<res;
    return 0;
}

标签：std,学习,const,int,res,namespace,蓝桥,include,日记
From： https://www.cnblogs.com/sxh426/p/18123441

相关文章

  • 蓝桥杯2014国A-排列序数(待续)
    [蓝桥杯2014国A]排列序数题目描述如果用abcd这\(4\)个字母组成一个串，有\(4!=24\)种，如果把它们排个序，每个串都对应一个序号：abcd0abdc1acbd2acdb3adbc4adcb5bacd6badc7bcad8bcda9bdac10bdca11cabd......
  • 文献学习-31-内窥镜摄像机运动模仿学习的深度齐次变换预测
    DeepHomographyPredictionforEndoscopicCameraMotionImitationLearningAuthors: MartinHuber,SébastienOurselin, ChristosBergeles, andTomVercauterenKeywords:Computervision·Roboticsurgery·ImitationlearningSource:  M......
  • 20240409报错修改学习
    未配置SpringBoot配置注解处理器spring:datasource:druid:driver-class-name:com.mysql.jdbc.Driverurl:jdbc:mysql://localhost:3306/mini_springmvc?serverTimezone=UTCusername:rootpassword:1234mybatis-plus:global-config:......
  • 前端学习-UI框架学习-Bootstrap5-016-卡片
    菜鸟教程链接简单的卡片<template><divclass="card"><h4class="card-title">标题</h4><imgsrc="../assets/th.jfif"alt="537"class="card-img-top"style="width:50px;......
  • 【蓝桥·算法双周赛 第 9 场 小白入门赛】字符迁移【算法赛】题解（字符串+模运算+差分）
    思路差分数组是一种特殊的数组，它的第iii个数定义为原数组的第ii......
  • 【蓝桥·算法双周赛 第 4 场 小白入门赛】自助餐【算法赛】题解（分支+字符串）
    思路首先定义一个整型变量n和一个长整型变量ans，其中n用于存放输入的字符串个数，ans则用于累计所有字符串对应的价格。在接收到n之后，进入一个循环，在循环中，每次接收一个字符串s，并根据s的首字母判断该字符串对应的餐盘种类，并将其价格累加到ans中。具体来说，如果......
  • 我的lisp学习历程
    在我大学的学习过程中，我选择了学习Lisp编程语言。我选择Lisp是因为它是一种功能强大的语言，可以用于解决各种问题，并且它的语法和思维方式与其他编程语言有很大的不同，这对我来说是一个很大的挑战。在开始学习Lisp之前，我很快意识到我需要一个良好的学习资源。我开始在互联网上搜......
  • 6本值得推荐的MySQL学习书籍（有赠书福利）
    前言在DotNetGuide技术社区交流群和微信公众号后台经常收到小伙伴们的留言，让我出一期MySQL相关学习书籍的推荐文章。因此，今天我特意为大家精选了6本值得推荐的MySQL学习书籍，希望能够为大家提供一个全面系统的学习参考，助力大家在MySQL数据库领域的学习和实践道路上更进一步（......
  • Elastic学习之旅 (8) 深入词项和全文搜索
    大家好，我是Edison。上一篇：Elastic学习之旅(7)聚合分析相信很多童鞋和我一样，有点傻傻分不清Term查询和全文查询的区别，那么今天我们就来一起梳理一下。基于Term的查询Term（词项）是ES中表达语义的最小单位，搜索和利用统计语言模型进行自然语言处理都需要处理Term。ES中TermQuery......
  • 狂神说Java Web学习笔记_Servlet
    Servlet简介Servlet是sun公司开发的动态web的一门技术。提供的其中一个接口叫Servlet。把实现了Servlet接口的Java程序叫Servlet。HelloServletServlet在Sun公司有两个默认实现类，HttpServlet，GenericServlet。importjavax.servlet.ServletException;importjavax.servlet.ht......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99