Educational Codeforces Round 55 Div. 2 翻车记

　　A：签到。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int T;

int main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

    T=read();

    while (T--)

    {

        int n=read(),x=read(),y=read(),d=read();

        if (abs(y-x)%d==) cout<<abs(y-x)/d<<endl;

        else

        {

            int ans=;

            if ((y-)%d==) ans=min(ans,(y-)/d+(x-)/d+);

            if ((n-y)%d==) ans=min(ans,(n-y)/d+(n-x-)/d+);

            if (ans==) cout<<-<<endl;

            else cout<<ans<<endl;

        }

    }

    return ;

}

　　B：讨论了好多种情况写的老长交了五发30min的时候才过心态爆炸。随便怎么做都行。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 200010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,a[N],pre[N],suf[N],ans,cnt;

int main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

    n=read();

    for (int i=;i<=n;i++) cnt+=(a[i]=getc()=='S');

    int x=;

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

    {

        pre[i]=x;

        if (a[i]) x=i;

    }

    x=n+;

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

    {

        suf[i]=x;

        if (a[i]) x=i;

    }

    int flag=;

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

    if (a[i]==)

    {

        int t=i;while (t<n&&a[t+]==a[i]) t++;

        flag++;

        i=t;

    }

    if (flag==) {cout<<;return ;}

    if (flag==)

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

    if (a[i]==)

    {

        int t=i;while (t<n&&a[t+]==a[i]) t++;

        cout<<t-i+;return ;

    }

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

    if (pre[i]!=i-&&suf[i]!=i+) ans=max(ans,suf[i]-pre[i]-);

    if (flag<=) ans--;

    if (flag>=)

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

    {

        if (pre[i]==i-) ans=max(ans,suf[i]-i);

        if (suf[i]==i+) ans=max(ans,i-pre[i]);

    }

    if (cnt==) ans=n;

    cout<<max(,ans)<<endl;

    return ;

}

　　C：对于每个科目显然应该从大到小选。枚举各科的学生人数，考虑每个科目，只要能选该科的人数足够且价值>0就应该把这些人选进去。用链表维护哪些科目是应该选的即可，只要人数不够或者价值<=0就将其从中删除。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define N 200010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,ans,cnt,tot[N],cho[N],nxt[N],pre[N];

vector<int> a[N];

int main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

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

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

    {

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

        a[x].push_back(y);tot[x]++;

    }

    for (int i=;i<=m;i++) sort(a[i].begin(),a[i].end()),reverse(a[i].begin(),a[i].end());

    for (int i=;i<=m;i++) nxt[i]=i+,pre[i+]=i;

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

    {

        int x=nxt[];

        while (x!=m+)

        {

            if (tot[x]>=)

            {

                if (tot[x]==) nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x],cnt-=cho[x],tot[x]=-;

                else

                {

                    tot[x]--,cnt+=a[x][j-],cho[x]+=a[x][j-];

                    if (cho[x]<=) nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x],cnt-=cho[x],tot[x]=-;

                }

            }

            x=nxt[x];

        }

        ans=max(ans,cnt);

    }

    cout<<ans;

    return ;

}

　　D：显然应该尽量让他形成一条链。只有度数<=1的点会对其造成影响。在链的两端至少各放一个度数<=1的点并将主链连起来然后瞎连即可。讨论一下一些特殊情况。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 510

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,a[N],b[N],cnt,t;

bool flag[N];

struct data{int x,y;

}edge[N];

int main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

    n=read();

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

    {

        a[i]=read();

        if (a[i]==) b[++cnt]=i;

        else flag[i]=;

    }

    if (cnt==)

    {

        cout<<"YES"<<' '<<n-<<endl;

        cout<<n-<<endl;

        for (int i=;i<n;i++) cout<<i<<' '<<i+<<endl;

        return ;

    }

    if (cnt==)

    {

        if (b[]==)

        {

            cout<<"YES"<<' '<<n-<<endl;

            cout<<n-<<endl;

            for (int i=;i<n;i++) cout<<i<<' '<<i+<<endl;

        }

        else

        {

            cout<<"YES"<<' '<<n-<<endl;

            cout<<n-<<endl;

            for (int i=;i<b[]-;i++) cout<<i<<' '<<i+<<endl;

            cout<<<<' '<<b[]<<endl;

            for (int i=b[];i<n;i++) cout<<i<<' '<<i+<<endl;

        }

        return ;

    }

    if (n==&&cnt==) {cout<<"YES"<<' '<<<<endl<<<<endl<<<<' '<<;return ;}

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

    if (a[i]!=) {edge[++t].x=b[],edge[t].y=i;break;}

    if (t==) {cout<<"NO";return ;}

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

    if (a[i]!=) {edge[++t].x=b[cnt],edge[t].y=i;break;}

    if (t==) {cout<<"NO";return ;}

    int x=;cnt--;

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

    while (a[i]>&&x<=cnt) edge[++t].x=b[x++],edge[t].y=i,a[i]--;

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

    if (flag[i])

        for (int j=i-;j>=;j--)

        if (flag[j]) {edge[++t].x=i,edge[t].y=j;break;}

    if (t<n-) cout<<"NO";

    else

    {

        cout<<"YES"<<' '<<n-cnt<<endl;

        cout<<n-<<endl;

        for (int i=;i<n;i++) cout<<edge[i].x<<' '<<edge[i].y<<endl;

    }

    return ;

}

　　E：先把本来就和C相同的数数出来做个前缀和。显然让所选区间的左右端点变为与C相同是不会更劣的。考虑每一种数。假设固定了左端点，右端点不断向右扩展，那么遇到与左端点相同的数就可以使答案+1，遇到本身就与C相同的数则会使答案-1。于是将对该数每一段的价值取出来，形如1 -a 1 -a 1……，做个最大子段和就可以了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 2000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,a[N],p[N],sum[N],nxt[N],b[N],t,cnt,ans;

int main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

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

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

    {

        a[i]=read()-m+;

        if (a[i]==) cnt++;

    }

    for (int i=;i<=n;i++) nxt[i]=p[a[i]],p[a[i]]=i;

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

    ans=cnt;

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

    if (i!=&&p[i])

    {

        int x=p[i];t=;b[++t]=;

        while (nxt[x])

        {

            b[++t]=sum[nxt[x]]-sum[x];

            b[++t]=;

            x=nxt[x];

        }

        int s=;

        for (int j=;j<=t;j++)

        {

            s+=b[j];

            if (s<) s=;

            ans=max(ans,cnt+s);

        }

    }

    cout<<ans<<endl;

    return ;

}

　　F：没看

　　G：最大权闭合子图裸题。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define int long long

#define N 2010

#define M 10010

#define S 0

#define T 2001

#define inf 10000000000000ll

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,p[N],a[N],t=-,d[M],cur[M],q[M],ans;

struct data{int to,nxt,cap,flow;

}edge[M<<];

void addedge(int x,int y,int z)

{

    t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].cap=z,edge[t].flow=,p[x]=t;

    t++;edge[t].to=x,edge[t].nxt=p[y],edge[t].cap=,edge[t].flow=,p[y]=t;

}

bool bfs()

{

    memset(d,,sizeof(d));d[S]=;

    int head=,tail=;q[]=S;

    do

    {

        int x=q[++head];

        for (int i=p[x];~i;i=edge[i].nxt)

        if (d[edge[i].to]==-&&edge[i].flow<edge[i].cap)

        {

            q[++tail]=edge[i].to;

            d[edge[i].to]=d[x]+;

        }

    }while (head<tail);

    return ~d[T];

}

int work(int k,int f)

{

    if (k==T) return f;

    int used=;

    for (int i=cur[k];~i;i=edge[i].nxt)

    if (d[k]+==d[edge[i].to])

    {

        int w=work(edge[i].to,min(f-used,edge[i].cap-edge[i].flow));

        edge[i].flow+=w,edge[i^].flow-=w;

        if (edge[i].flow<edge[i].cap) cur[k]=i;

        used+=w;if (used==f) return f;

    }

    if (used==) d[k]=-;

    return used;

}

void dinic()

{

    while (bfs())

    {

        memcpy(cur,p,sizeof(p));

        ans-=work(S,inf);

    }

}

signed main()

{

/*#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

#endif*/

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

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

    memset(p,,sizeof(p));

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

    {

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

        addedge(n+i,x,inf),addedge(n+i,y,inf);

        addedge(S,n+i,z);ans+=z;

    }

    for (int i=;i<=n;i++) addedge(i,T,a[i]);

    dinic();

    cout<<ans;

    return ;

}

　　

　　小号打的。result： rank 34 rating +158