Gym -102007 ：Benelux Algorithm Programming Contest (BAPC 18) (寒假自训第5场)

A .A Prize No One Can Win

题意：给定N，S，你要从N个数中选最多是数，使得任意两个之和不大于S。

思路：排序，然后贪心的选即可。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

ll a[maxn];

int main()

{

    int N,ans; ll M;

    scanf("%d%lld",&N,&M);

    rep(i,,N) scanf("%lld",&a[i]);

    sort(a+,a+N+);

    ans=;

    rep(i,,N){

        if(a[i]+a[i-]<=M) ans=i;

    }

    printf("%d\n",ans);

    return ;

}

B .Birthday Boy

题意：给出N个人的生日，让你选择一天，使得这一天的前一个生日距离它最远，如果有多个一样的，有点选择10月27之后的

思路：模拟即可。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int Y[]={,,,,,,,,,,,,};

int vis[],tot;

int mp[][],C[][],A[],B[];

int main()

{

    int N,y,d,ansx=,ansy=,ans=-;char c[];

    scanf("%d",&N);

    rep(i,,N){

        scanf("%s%d-%d",c+,&y,&d);

        mp[y][d]=;

    }

    rep(i,,)

     rep(j,,Y[i]){

        tot++; A[tot]=i; B[tot]=j; C[i][j]=tot;

        if(mp[i][j]) vis[tot]=;

    }

    rep(i,,tot) vis[i+tot]=vis[i],A[i+tot]=A[i],B[i+tot]=B[i];

    rep(i,tot,tot+tot-) {

        if(vis[i]) continue;

        int j=i; while(j->=i-tot+&&!vis[j-]) j--;

        if(i-j>ans){

            ans=i-j,ansx=A[i],ansy=B[i];

        }

        else if(i-j==ans&&C[ansx][ansy]<=C[][]&&C[A[i]][B[i]]>C[][]) ansx=A[i],ansy=B[i];

    }

    printf("%02d-%02d\n",ansx,ansy);

    return ;

}

C .Cardboard Container

题意: 给定N个1*1*1的盒子,让你用最小的表面积把它包起来.

思路: 枚举长和宽和高(因子)即可.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=;

const int maxn=+;

const int inf=;

int main()

{

    int v;

    cin>>v;

    ll ans=inf;

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

        if(v%i==){

            int l=v/i;

            for(int j=;j<=l;j++){

                if(l%j==){

                    int k=l/j;

                    ans=min(ans,2LL*(i*j+k*j+k*i));

                }

            }

        }

    }

    cout<<ans<<endl;

    return ;

}

E .Entirely Unsorted Sequences

https://blog.csdn.net/ccsu_cat/article/details/86754931

G .Game Night

模拟几种排列即可

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int sum[maxn][],N; char c[maxn];

int get(int A,int B,int C)

{

    int res=;

    rep(i,,N){

        int X=sum[i+sum[N][A]-][A]-sum[i-][A];

        int Y=sum[i+sum[N][A]+sum[N][B]-][B]-sum[i+sum[N][A]-][B];

        int Z=sum[i+N-][C]-sum[i+sum[N][A]+sum[N][B]-][C];

        res=max(res,X+Y+Z);

        //cout<<A<<" "<<B<<" "<<C<<" : "<<i<<" "<<res<<endl;

    }

    return N-res;

}

int main()

{

    scanf("%d%s",&N,c+);

    int ans=N;

    rep(i,,N) c[N+i]=c[i];

    rep(i,,N+N){

        rep(j,,) sum[i][j]=sum[i-][j];

        if(c[i]=='A') sum[i][]++;

        if(c[i]=='B') sum[i][]++;

        if(c[i]=='C') sum[i][]++;

    }

    rep(i,,)

     rep(j,,)

      rep(k,,)

       if(i!=j&&i!=k&&j!=k)

        ans=min(ans,get(i,j,k));

    printf("%d\n",ans);

    return ;

}

I. In Case of an Invasion, Please...

题意：给定N城市每个城市人数是Pi，M双向路，其中S个点(S<=10)是避难所，避难所容量是Ci，(N<1e5; Ci,Pi<1e9)最小化最大的转移时间，使得所有人都转移到避难所。

思路：二分+最大流。由于图比较大，此题需要一些优化才能过。

由于上限是1e14；所以二分次数是50次；我们可以把距离离散化上线变为了1e6，二分次数是20；这是一个优化。

第二个优化，对于二分到的mid，如果一个城市可以去的避难所容量之和<P[i]，那么显然不用跑网络流也知道不合法。

还有就是sap跑二分图比较慢，要用dinic。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1e5+;

ll inf=1ll<<;

struct Edge

{

    int from,to;

    ll cap,flow;

};

struct Dinic

{

    int n,m,s,t;

    vector<Edge>edges;

    vector<int>G[maxn];

    bool vis[maxn];

    int d[maxn],cur[maxn];

    void init(int n)

    {

        this->n=n;

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

        G[i].clear();

        edges.clear();

    }

    void AddEdge(int from,int to,ll cap)

    {

        edges.push_back((Edge){from,to,cap,});

        edges.push_back((Edge){to,from,,});

        m=edges.size();

        G[from].push_back(m-);

        G[to].push_back(m-);

    }

    bool bfs()

    {

        memset(vis,,sizeof(vis));

        queue<int>Q;

        Q.push(s);

        d[s]=;

        vis[s]=;

        while(!Q.empty())

        {

            int x=Q.front();Q.pop();

            for(int i=;i<G[x].size();i++)

            {

                Edge& e=edges[G[x][i]];

                if(!vis[e.to]&&e.cap>e.flow)

                {

                    vis[e.to]=;

                    d[e.to]=d[x]+;

                    Q.push(e.to);

                }

            }

        }

        return vis[t];

    }

    ll dfs(int x,ll a)

    {

        if(x==t||a==)return a;

        ll flow=,f;

        for(int& i=cur[x];i<G[x].size();i++)

        {

            Edge& e=edges[G[x][i]];

            if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>)

            {

                e.flow+=f;

                edges[G[x][i]^].flow-=f;

                flow+=f;

                a-=f;

                if(a==)break;

            }

        }

        return flow;

    }

    ll Maxflow(int s,int t)

    {

        this->s=s,this->t=t;

        ll flow=;

        while(bfs())

        {

            memset(cur,,sizeof(cur));

            flow+=dfs(s,inf);

        }

        return flow;

    }

}solve;

ll d[][maxn],sum,vis[maxn];

vector<int>G[maxn],dis[maxn];

struct node

{

    int u;

    ll w;

    node(int a,ll b)

    {

        u=a,w=b;

    }

    bool operator<(const node&t)const

    {

        return w>t.w;

    }

};

priority_queue<node>q;

void dij(int k,int s,int n)

{

    for(int i=;i<=n;i++)d[k][i]=inf,vis[i]=;

    d[k][s]=;

    q.push(node(s,));

    while(!q.empty())

    {

        node e=q.top();q.pop();

        int u=e.u; vis[u]=;

        for(int i=;i<G[u].size();i++)

        {

            int v=G[u][i];

            if(d[k][v]>d[k][u]+dis[u][i])

            {

                d[k][v]=d[k][u]+dis[u][i];

                if(!vis[v]) vis[v]=,q.push(node(v,d[k][v]));

            }

        }

    }

}

int p[maxn],s[maxn],c[maxn],tot; ll B[maxn*],fcy[maxn];

int main()

{

    int n,m,k,u,v,w;

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

    int S=,T=n+k+;

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

    {

        scanf("%d",&p[i]);

        sum+=p[i];

    }

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

    {

        scanf("%d%d%d",&u,&v,&w);

        G[u].push_back(v);

        dis[u].push_back(w);

        G[v].push_back(u);

        dis[v].push_back(w);

    }

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

    {

        scanf("%d%d",&s[i],&c[i]);

        dij(i,s[i],n);

    }

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

     for(int j=;j<=n;j++) B[++tot]=d[i][j];

    sort(B+,B+tot+);

    tot=unique(B+,B+tot+)-(B+);

    ll l=,r=tot,mid,ans;

    while(l<=r)

    {

        mid=(l+r)/;

        solve.init(T+);

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

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

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

        if(d[j][i]<=B[mid])

        solve.AddEdge(i,n+j,inf),fcy[i]+=c[j];

        bool F=true;

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

        if(fcy[i]<p[i]){ F=false; break;}

        if(!F) {l=mid+;continue;}

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

        solve.AddEdge(S,i,p[i]);

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

        solve.AddEdge(n+i,T,c[i]);

        ll res=solve.Maxflow(S,T);

        if(res==sum) r=mid-,ans=B[mid];

        else l=mid+;

    }

    printf("%lld\n",ans);

}

J .Janitor Troubles

题意：给定ABCD四条边，让你组成一个面积最大的四边形，保证有解。

思路：比赛时三分做的，1A。但是赛后拿去做hduwa掉了，还是没弄清楚。

三分：枚举相邻边的组合形式，然后对对角线进行三分。结论是当三分到对角线的对面两个角都是直角时，答案最大，此时正好有外接圆。

定理：根据上面结论，相当于四边形是圆内接四边形，我们可以至直接用海伦公式的变形；

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

double X[],ans;

double S(double x,double y,double x1,double y1,double z)

{

    double p=(x+y+z)/,p1=(x1+y1+z)/;

    return sqrt(p*(p-x)*(p-y)*(p-z))+sqrt(p1*(p1-x1)*(p1-y1)*(p1-z));;

}

double get(int i,int j,int k,int p)

{

    double Mn=max(X[j]-X[i],X[p]-X[k]),Mx=min(X[j]+X[i],X[p]+X[k]);

    if(Mn>Mx) return 0.0;

    int T=; double L=Mn,R=Mx,res=0.0;

    while(T--){

        double Mid1=L+(R-L)/,Mid2=R-(R-L)/;

        double F1=S(X[i],X[j],X[k],X[p],Mid1);

        double F2=S(X[i],X[j],X[k],X[p],Mid2);

        if(F1>=F2) res=max(F1,res),R=Mid2;

        else res=max(F2,res),L=Mid1;

    }

    return res;

}

int main()

{

    rep(i,,) scanf("%lf",&X[i]);

    sort(X+,X++);

    rep(i,,)

     rep(j,i+,)

      rep(k,,)

       rep(p,k+,)

        if(i!=k&&i!=p&&j!=k&&j!=p){

         ans=max(ans,get(i,j,k,p));

    }

    printf("%.10lf\n",ans);

    return ;

}

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

double X[],ans;

double get()

{

    double res=0.0,p=(X[]+X[]+X[]+X[])/;

    res=sqrt((p-X[])*(p-X[])*(p-X[])*(p-X[]));

    return res;

}

int main()

{

    rep(i,,) scanf("%lf",&X[i]);

    ans=get();

    printf("%.10lf\n",ans);

    return ;

}

K .Kingpin Escape

题意：给定一棵有根树，现在让你加最少的边，使得无论原图上哪条边被砍掉，从任意点出发都可以回到根节点。

思路：首先把保证至少两个点与根相邻，所以如果根只有一条边与它相邻，它需要加边。其次，所有叶子节点需要加边，因为他和父亲被砍断后就GG了。

我们按照一定顺序把这些点连边即可。假设X个点需要连边，那么最少需要加(X+1)/2条边。然后两两连边即可，但是注意至少一条新加的边连通了根的两个子树。

所以我们按照DFS序，然后q[i]+q[X/2+i]连边，这样可以保证，并不是所有新加的边都在同一个子树（这样可能合法，因为砍掉根与儿子后，子树无法到达根）里。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int Laxt[maxn],Next[maxn],To[maxn];

int sz[maxn],cnt,q[maxn],tot;

void add(int u,int v){

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;

}

void dfs(int u,int f)

{

    if(sz[u]==) q[++tot]=u-;

    for(int i=Laxt[u];i;i=Next[i])

     if(To[i]!=f) dfs(To[i],u);

}

int main()

{

    int N,M,u,v;

    scanf("%d%d",&N,&M); M++;

    rep(i,,N-){

        scanf("%d%d",&u,&v);

        u++; v++; sz[u]++; sz[v]++;

        add(u,v); add(v,u);

    }

    dfs(M,);

    int ans=(tot+)/;

    printf("%d\n",ans);

    rep(i,,tot/) printf("%d %d\n",q[i],q[i+tot/]);

    if(tot&) printf("%d %d\n",q[],q[tot]);

    return ;

}

巴特西