头像

普朗tong


访客:582

离线:8小时前



1:memset函数

  • 按照字节填充
  • 在头文件cstring里面

2:fill函数

  • 按照单元赋值,将一个区间的元素都赋同一个值
  • 在头文件algorithm里面

因为memset函数按照字节填充,所以一般memset只能用来填充char型数组,(因为只有char型占一个字节)如果填充int型数组,除了0和-1,其他的不能。因为只有00000000 = 0,-1同理,如果我们把每一位都填充“1”,会导致变成填充入“11111111”。

而fill函数可以赋值任何,使用起来也比较方便。

  • fill(arr, arr + n, 要填入的内容);

举例:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int arr[10];
    fill(arr, arr + 10, 2);
    return 0;
}

//output:
2 2 2 2 2 2 2 2 2 2 

赋值vector:

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main(){
    vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    fill(v.begin(), v.end(), -1);
    return 0;
}  

//output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

fill填充二维数组

#include<cstdio>
#include<iostream>
using namespace std;

int main(){
    int G[6][4];
    fill(G[0],G[0]+6*4,520);
    for(int i = 0;i < 6;i++)
    {
        for(int j = 0;j < 4;j++){
            cout <<G[i][j] <<" ";
        }cout <<"\n";
    }
}

//output
520 520 520 520 
520 520 520 520 
520 520 520 520 
520 520 520 520 
520 520 520 520 
520 520 520 520 

3:vector也可以采用以下方法初始化:

初始化二维vector,为r*c的vector,所有值为0.

  • 直接用初始化方法

vector<vector<int> > res(r, vector<int>(c, 0));

  • 用resize()来控制大小
    vector<vector<int> > res;
        res.resize(r);//r行
        for (int k = 0; k < r; ++k){
            res[k].resize(c);//每行为c列
        }



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

using namespace std;

const int N=200010;

int n,m;
int p[N];//并查集里存父亲节点

struct Edge{
    int a,b,w;

    bool operator<(const Edge& e){
        return w<e.w;
    }
}edges[N];

//查找x的父亲节点
int find(int x){
    if(x!=p[x]){
        p[x]=find(p[x]);
    }
    return p[x];
}

int main(){
    scanf("%d%d",&n,&m);

    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }

    sort(edges,edges+m);

    for(int i=1;i<=n;i++){
        p[i]=i;
    }

    int res=0;//最小生成树边权重之和
    int cnt=0;//加入到最小生成树中的边数和
    for(int i=0;i<m;i++){
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b){
            p[a]=b;
            res+=w;
            cnt++;
        }
    }

    if(cnt==n-1){
        printf("%d\n",res);
    }else{
        puts("impossible");
    }

    return 0;
}




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

using namespace std;

const int N=510,INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dis[N];
bool st[N];


int prim(){
    memset(dis,0x3f,sizeof dis);

    int res=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dis[t]>dis[j])){
                t=j;
            }
        }
        st[t]=true;


        if(i&&dis[t]==INF){
            return INF;
        }
        if(i){
            res+=dis[t];
        }

        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],g[t][j]);
        }
    }

    return res;
}

int main(){
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                g[i][j]=0;
            }else{
                g[i][j]=INF;
                g[j][i]=INF;
            }
        }
    }
    //memset(g, 0x3f, sizeof g);

    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
    }

    int res=prim();
    if(res==INF){
        puts("impossible");
    }else{
        printf("%d\n",res);
    }
}



#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],in[N],idx;


void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void topsort(){

    vector<int> res;
    queue<int> q;

    for(int i=1;i<=n;i++){
        if(!in[i]){
            q.push(i);
        }
    }

    while(q.size()){
        auto t=q.front();
        q.pop();

        res.push_back(t);

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            in[j]--;
            if(!in[j]){
                q.push(j);
            }
        }
    }

    if(res.size()==n){
        for(int i=0;i<res.size();i++){
            cout<<res[i]<<" ";
        }
    }else{
        cout<<-1;
    }
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);

    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
        in[b]++;
    }

    topsort();
    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

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

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dis[N],cnt[N];
bool st[N];//记录已经插入到队列中待更新的节点


void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool spfa(){

    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    queue<int> q;

    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }

    while(q.size()){
        auto t=q.front();
        q.pop();

        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dis[j]>dis[t]+w[i]){
                dis[j]=dis[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n){
                    return true;
                }
                if(!st[j]){
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }

    return false;
}


int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);

    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    if(spfa()){
        puts("Yes");
    }else{
        puts("No");
    }
}



活动打卡代码 AcWing 851. spfa求最短路

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

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dis[N];
bool st[N];//记录已经插入到队列中待更新的节点


void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int spfa(){

    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=true;

    while(q.size()){
        auto t=q.front();
        q.pop();

        st[t]=false;

        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dis[j]>dis[t]+w[i]){
                dis[j]=dis[t]+w[i];
                if(!st[j]){
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }

    return dis[n];
}


int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);

    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    int t=spfa();
    if(t==0x3f3f3f3f){
        puts("impossible");
    }else{
        printf("%d\n",t);
    }
}




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

using namespace std;

const int N=510,M=10010;

struct Edge{
    int a,b,c;
}edge[M];

int n,m,k;
int dis[N],backup[N];

void bellman_ford(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;

    for(int i=0;i<k;i++){
        memcpy(backup,dis,sizeof dis);
        for(int i=0;i<m;i++){
            auto t=edge[i];
            dis[t.b]=min(dis[t.b],backup[t.a]+t.c);
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&k);

    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge[i]={a,b,c};
    }

    bellman_ford();

    if(dis[n]>0x3f3f3f3f/2){
        puts("impossible");
    }else{
        printf("%d\n",dis[n]);
    }
}



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

using namespace std;
typedef pair<int,int> PII;

const int N=1e6+10;
int h[N],e[N],ne[N],w[N],idx;
int dis[N];
int n,m;
bool st[N];

void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int dijkstra(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;

    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});



    while(heap.size()){

        auto t=heap.top();
        heap.pop();

        int node=t.second,distance=t.first;

        if(st[node]) continue;
        st[node]=true;


        for(int i=h[node];i!=-1;i=ne[i]){
            int j=e[i];
            if(dis[j]>distance+w[i]){
                dis[j]=distance+w[i];
                heap.push({dis[j],j});
            }
        }
    }

    if(dis[n]==0x3f3f3f3f){
        return -1;
    }else{
        return dis[n];
    }

}

int main(){

    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);

    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    int res=dijkstra();
    printf("%d\n",res);

    return 0;
}



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

using namespace std;

const int N=510;

int n,m;
int g[N][N];
int dis[N];
bool st[N];//集合,已经确定的最短长度的点

int dijkstra(){

    memset(dis,0x3f,sizeof dis);
    dis[1]=0;

    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dis[t]>dis[j])){
                t=j;
            }
        }

        st[t]=true;

        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],dis[t]+g[t][j]);
        }
    }

    if(dis[n]==0x3f3f3f3f){
        return -1;
    }else{
        return dis[n];
    }
}


int main(){
    scanf("%d%d",&n,&m);

    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){
    //         if(i==j){
    //             g[i][j]=0;
    //         }else{
    //             g[i][j]=0x3f3f3f3f;
    //         }
    //     }
    // }

    memset(g, 0x3f, sizeof g);

    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }

    int res=dijkstra();
    printf("%d\n",res);

    return 0;
}




#include<iostream>
#include<stack>
#include<algorithm>
typedef long long LL;
using namespace std;

const int N=100010;

int n;
int h[N],l[N],r[N];


void get(int a[]){
    stack<int> s;
    h[0]=-1;
    s.push(0);
    for(int i=1;i<=n;i++){
        while(h[s.top()]>=h[i]){
            s.pop();
        }
        a[i]=s.top();
        s.push(i);
    }
}

int main(){

    while(cin>>n&&n){
        for(int i=1;i<=n;i++){
            cin>>h[i];
        }

        get(l);
        reverse(h+1,h+1+n);
        get(r);

        LL res=0;
        for(int i=1,j=n;i<=n;i++,j--){
            res=max(res,(LL)(n-l[j]-r[i])*h[i]);
        }
        cout<<res<<endl;
    }

    return 0;
}