牛客CSP-S提高组赛前集训营2 ———

期望得分：100+20+20

实际得分：40+20+30

awa cccc

T1 :基于贪心的思路，然后开始爆搜（雾

那必然是会死的，好吧他就是死了

#include<iostream>

#include<cstdio>

#include<algorithm>

#define int long long

using namespace std;

int n,q,m;

int ans,sum=-;

int a[];

int x,y;

inline int read();

int cha() {

    int ans=-;

    for(int i=; i<=n; i++)ans=max(ans,a[i]);

    return ans;

}

signed main() {

    n=read(),m=read(),q=read();

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

        a[i]=read();

        ans+=a[i];

        sum=max(a[i],sum);

    }

    if(sum*m>=ans)cout<<sum<<"\n";

    else {

        sum=ans/m;

        if(ans%m)sum++;

        cout<<sum<<"\n";

    }

    while(q--) {

        x=read(),y=read();

        ans+=y-a[x];

        if(y<a[x]&&a[x]==sum)a[x]=y,sum=cha();

        a[x]=y;

        if(y>sum)sum=y;

        if(sum*m>=ans)cout<<sum<<"\n";

        else {

            sum=ans/m;

            if(ans%m)sum++;

            cout<<sum<<"\n";

        }

    }

    return ;

}

inline int read() {

    int s=,w=;

    char ch=getchar();

    while(ch<''||ch>'') {

        if(ch=='-')w=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

        s=(s<<)+(s<<)+(ch^),ch=getchar();

    return s*w;

}

T2:题目倒是没看明白，smg

就直接贴了个并查集求连通块个数，，，只拿了20分

20分代码(☄⊙ω⊙)☄：

//20分，k=0的情况,若k!=0,直接return 0，毫不犹豫awa

//看我对评测机多好，希望评测机可以对我好一点

#include<iostream>

#include<cstdio>

#include<cmath>

#define int long long

using namespace std;

int N,M,K,ans;

int  pre[];

int find(int a) {

    if(pre[a]!=a) pre[a]=find(pre[a]);

    return pre[a];

}

void join(int x,int y) {

    int fx=find(x),fy=find(y);

    if(fx!=fy) pre[fy]=fx;

}

inline int read() {

    int s=,w=;

    char ch=getchar();

    while(ch<''||ch>'') {

        if(ch=='-')w=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

        s=(s<<)+(s<<)+(ch^),ch=getchar();

    return s*w;

}

signed main() {

    N=read(),M=read(),K=read();

    if(K!=){

        cout<<M-K+<<endl;

        return ;

    }

    for(int i=; i<=N; i++) pre[i]=i;

    for(int i=; i<=M; i++) {

        int a,b;

        a=read(),b=read();

        join(a,b);

    }

    for(int i=; i<=N; i++) if(pre[i]==i) ans++;

    cout<<ans;

    return ;

}

T3：暴力模拟30分

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;

int n,m,f;

int t,l,r,x,y;

int ans;

int a[];

bool vis[];

void gai(int l,int r,int x) {

    memset(vis,false,sizeof vis);

    for(int i=l; i<=r; i++)a[i]=x;

    for(int i=; i<=n; i++)vis[a[i]]=true;

}

void cha(int x,int y) {

    if(!vis[x]||!vis[y]) {

        ans=-;

        return;

    }

    ans=inf;

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

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

            if((a[i]==x&&a[j]==y)||(a[i]==y&&a[j]==x)) {

                ans=min(ans,abs(i-j));

                break;

            }

    if(ans==inf)ans=-;

}

int lastans;

inline int read() {

    int s=,w=;

    char ch=getchar();

    while(ch<''||ch>'') {

        if(ch=='-')w=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

        s=(s<<)+(s<<)+(ch^),ch=getchar();

    return s*w;

}

int main() {

    n=read(),m=read(),f=read();

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

        a[i]=read(),vis[a[i]]=true;

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

        t=read();

        if(t==) {

            l=read(),r=read(),x=read();

            if(f==)l^=lastans,r^=lastans,x^=lastans;

            gai(l,r,x);

        }

        if(t==) {

            x=read(),y=read();

            if(f)x^=lastans,y^=lastans;

            cha(x,y);

            cout<<ans<<"\n";

            if(ans==-)lastans=;

            else lastans=ans;

        }

    }

    return ;

}

想要AC代码来这里

巴特西

牛客CSP-S提高组赛前集训营2 ———— 2019.10.31

最新文章

热门文章