您的位置: 首页  >  IT文章  >  【2018年全国多校算法寒假训练营练习比赛（第四场）】

【2018年全国多校算法寒假训练营练习比赛（第四场）】

分类: IT文章 • 2024-03-29 19:26:43

上一场自己状态爆表；这一场队友爆表，自己捡表了；题目呢，总的来说不难，相比于前面几场比赛来说，关键在于如何建图。

像D题，在我的上一个博客里面就是一道同理的题，只需要求入度为0和出度为0的点最大数，然后特判已经强连通（比如只有一个点）的情况。

 可以看看我上一个博客，可能会对此比赛有帮助。

【A 石油采集】

   题解：二分匹配之匈牙利。

【B 道路建设】

   题解：并查集。

【C 求交集】

    题解：双指针扫一遍即可。

【D 小明的挖矿之旅】  

    题解：求度为0的点数量。

【E 通知小弟】

     题解：处理入度为0的新点；

【F Call to your teacher】

    题解：水

【G 老子的意大利炮呢】

    题解：分层+优先队列SPFA。

【H 老子的全排列呢】

    题解：STL之permutation或者试一试康拓展开。

-------------------------------代码-----------------------------

【A】  

12月份刚好看过队友做过此题，当然那个题我还懵b了，所以记得。

可以先去看看POJ 2446 ，POJ3020。附上队友博客：LZH 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}
const int ws_[4]={0,1,0,-1},ad_[4]={1,0,-1,0};
int N,cas=0;
char mp[55][55];
inline int id(int x,int y)
{return (x-1)*N+y;}
int lin[3100],len;
struct edge{
    int y,next;
}e[100010];
inline void insert(int xx,int yy){
    e[++len].next=lin[xx];
    lin[xx]=len;
    e[len].y=yy;
}
inline void ins(int xx,int yy)
{insert(xx,yy),insert(yy,xx);}
bool vis[3100];
int match[3100];
bool hun(int x){
    for(int i=lin[x];i;i=e[i].next)
        if(!vis[e[i].y]){
            vis[e[i].y]=1;
            if(match[e[i].y]==0||hun(match[e[i].y])){
                match[e[i].y]=x;
                match[x]=e[i].y;
                return 1;
            }
        }
    return 0;
}
int main(){
    //freopen("in","r",stdin);
    for(int T=read();T;T--){
        printf("Case %d: ",++cas);
        char ch;
        N=read();
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++){
                ch=getchar();
                while(ch==' '||ch=='
')
                    ch=getchar();
                mp[i][j]=ch;
            }
        memset(lin,0,sizeof(lin));len=0;
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                if(mp[i][j]=='#')
                    for(int k=0;k<=3;k++){
                        int tx=i+ws_[k],ty=j+ad_[k];
                        if(tx<=0||ty<=0||tx>N||ty>N)
                            continue;
                        if(mp[tx][ty]=='#')
                            ins(id(i,j),id(tx,ty));
                    }
        memset(match,0,sizeof(match));
        int ans=0;
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                if(mp[i][j]=='#'){
                    if(!match[id(i,j)]){
                        memset(vis,0,sizeof(vis));
                        if(hun(id(i,j)))
                            ans++;
                    }
                }
        printf("%d
",ans);
    }
}
View Code

【B】

 并查集

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}
int C,N,M;
struct edge{
    int x,y,v;
    bool friend operator<(const edge&A,const edge&B)
    {return A.v<B.v;}
}e[10010];
int father[110];
int getfather(int x){
    if(father[x]==x)
        return x;
    return father[x]=getfather(father[x]);
}
int main(){
    //freopen("in","r",stdin);
    while(scanf("%d",&C)!=EOF){
        N=read(),M=read();
        for(int i=1;i<=N;i++)
            e[i].x=read(),e[i].y=read(),e[i].v=read();
        sort(e+1,e+1+N);
        for(int i=1;i<=M;i++)
            father[i]=i;
        int cnt=0;
        long long ans=0;
        for(int i=1;i<=N;i++){
            int f1=getfather(e[i].x),f2=getfather(e[i].y);
            if(f1==f2)
                continue;
            cnt++;
            ans+=e[i].v;
            father[f2]=f1;
            if(cnt==M-1)
                break;
        }
        if(ans<=C)
            printf("Yes
");
        else
            printf("No
");
    }
    return 0;
}
View Code

【C】

由于已经有序，而且集合具有互异性，可以用双指针。

假设两个队伍，每次比较队首，小的一方后移队首。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}
const int maxn=1000010;
int a[maxn],b[maxn],N,M;
int ans[maxn],tp;
int main(){
    while(scanf("%d %d",&N,&M)!=EOF){
        for(int i=1;i<=N;i++)
            a[i]=read();
        for(int i=1;i<=M;i++)
            b[i]=read();
        int i=1,j=1,tp=0;
        while(i<=N&&j<=M){
            if(a[i]==b[j])
                ans[++tp]=a[i],i++,j++;
            else if(a[i]>b[j])
                j++;
            else
                i++;
        }
        if(tp==0) printf("empty
");
        else {
        for(int k=1;k<tp;k++)
            printf("%d ",ans[k]);
        printf("%d
",ans[tp]);
        }
    }
    return 0;
}
View Code

【D】

就是问有向图至少加几条有向边使得图成为强连通，结论是：当已经强连通时，答案为0（此情况就是所谓的特判）；否则，答案=max(出度为0数，入度为0数)。

对于上面的结论，我以前证明过。但是找了下没找到对应的博客。

Tarjan缩点建图，求度为0的点数。我的代码如下，但可能数据有点大，只通过了87%。

//有向图缩点 ,注意scc_cnt=1时。
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int Laxt[maxn],Next[maxn<<1],To[maxn<<1],cnt,n,m;
int dfn[maxn],low[maxn],times,scc_cnt,scc[maxn];
int instc[maxn],stc[maxn],top,ans1,ans2;
int ind[maxn],oud[maxn];
char chr[1010][1010];
void update()
{
    cnt=times=scc_cnt=top=ans1=ans2=0;
    memset(Laxt,0,sizeof(Laxt));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(scc,0,sizeof(scc));
    memset(instc,0,sizeof(instc));
    memset(stc,0,sizeof(stc));
    memset(ind,0,sizeof(ind));
    memset(oud,0,sizeof(oud));
}
void add(int u,int v)
{
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
}
void dfs(int u)
{
    dfn[u]=low[u]=++times;
    stc[++top]=u; instc[u]=1;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instc[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        scc_cnt++;
        while(true){
            int x=stc[top--];
            scc[x]=scc_cnt;
            instc[x]=0;
            if(x==u) break;
        }
    }
}
void tarjan()
{
   for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++){
            if(chr[i][j]=='.'&&!dfn[(i-1)*m+j]) dfs((i-1)*m+j);
       }
    for(int i=1;i<=n*m;i++)
      for(int j=Laxt[i];j;j=Next[j]){
        if(scc[i]!=scc[To[j]]) {
            ind[scc[To[j]]]++;
            oud[scc[i]]++;
        }
    }
         
    for(int i=1;i<=scc_cnt;i++){
        if(ind[i]==0) ans1++;
        if(oud[i]==0) ans2++;
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        update();
        for(int i=1;i<=n;i++) scanf("%s",chr[i]+1);
        for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++){
            if(chr[i][j]=='.'){
                if(j+1<=m&&chr[i][j+1]=='.') add((i-1)*m+j,(i-1)*m+j+1);
                if(i+1<=n&&chr[i+1][j]=='.') add((i-1)*m+j,i*m+j);
            }
         }
        tarjan();
        if(scc_cnt==1) printf("0
");
        else printf("%d
",max(ans1,ans2));
    } return 0;
}
View Code

利用方向只能像东南这个条件，直接检查是是不是入度为0的点，或者出度为0的点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}
const int ws_[4]={0,1,0,-1},ad_[4]={1,0,-1,0};
int N,M;
char mp[1010][1010];
bool vis[1010][1010];
int tp1,tp2,cnt;
bool check(int xx,int yy){
    if(xx<=0||yy<=0||xx>N||yy>M)
        return 0;
    return 1;
}
void dfs(int xx,int yy){
    vis[xx][yy]=1;
    if((!check(xx+ws_[2],yy+ad_[2]))||mp[xx+ws_[2]][yy+ad_[2]]=='#')
        if((!check(xx+ws_[3],yy+ad_[3]))||mp[xx+ws_[3]][yy+ad_[3]]=='#')
            tp1++;
    if((!check(xx+ws_[0],yy+ad_[0]))||mp[xx+ws_[0]][yy+ad_[0]]=='#')
        if((!check(xx+ws_[1],yy+ad_[1]))||mp[xx+ws_[1]][yy+ad_[1]]=='#')
            tp2++;
    int tx,ty;
    for(int k=0;k<=3;k++){
        tx=xx+ws_[k],ty=yy+ad_[k];
        if(!check(tx,ty))
            continue;
        if((!vis[tx][ty])&&mp[tx][ty]=='.')
            dfs(tx,ty);
    }
}
int main(){
    //freopen("in","r",stdin);
    while(scanf("%d %d",&N,&M)!=EOF){
        cnt=0;
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++){
                char ch=getchar();
                while(ch==' '||ch=='
')
                    ch=getchar();
                mp[i][j]=ch;
                if(mp[i][j]=='.')
                    cnt++;
            }
        int ans,ans1=0,ans2=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++)
                if(mp[i][j]=='.'&&(!vis[i][j])){
                    tp1=tp2=0;
                    dfs(i,j);
                    ans1+=tp1,ans2+=tp2;
                }
        ans=max(ans1,ans2);
        if(cnt==1)
            ans=0;
        printf("%d
",ans);
    }
    return 0;
}
View Code

【E】

显然，缩点，重新建图，只有入度为0的点（缩点之后的）是需要考虑的，如果入度为0的点（缩点之后，其实是个集合）里面如果没有可以通知到的，那么“-1”；

如果入度为0的点大于m，那么“-1”；    

现在看来，只需求入度为0的有哪些，然后验证每个点（集合）是否存在可以通知的人即可，而不需重新构图。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1010;
int Laxt[maxn],Next[maxn*250],To[maxn*250],cnt,n,m;
int dfn[maxn],low[maxn],times,scc_cnt,scc[maxn];
int instc[maxn],stc[maxn],top;
int ind[maxn],ans,p[maxn],ok[maxn];
void update()
{
    cnt=times=scc_cnt=top=ans=0;
    memset(Laxt,0,sizeof(Laxt));
    memset(dfn,0,sizeof(dfn));
    memset(scc,0,sizeof(scc));
    memset(instc,0,sizeof(instc));
    memset(stc,0,sizeof(stc));
    memset(ind,0,sizeof(ind));
    memset(p,0,sizeof(p));
    memset(ok,0,sizeof(ok));
}
void add(int u,int v)
{
    Next[++cnt]=Laxt[u];
    Laxt[u]=cnt;
    To[cnt]=v;
}
void dfs(int u)
{
    dfn[u]=low[u]=++times;
    stc[++top]=u; instc[u]=1;
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(!dfn[v]){
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instc[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        scc_cnt++;
        while(true){
            int x=stc[top--];
            scc[x]=scc_cnt;
            instc[x]=0;
            if(x==u) break;
        }
    }
}
void tarjan()
{
    for(int i=1;i<=n;i++)
        if(!dfn[i]) dfs(i);
    for(int i=1;i<=n;i++)
      for(int j=Laxt[i];j;j=Next[j]){
        if(scc[i]!=scc[To[j]]) {
            ind[scc[To[j]]]++;
        }
    }
         
    for(int i=1;i<=scc_cnt;i++){
        if(ind[i]==0) ans++;
    }
    if(ans>m){
       printf("-1
");
       return ;
    }
    for(int i=1;i<=n;i++){
        if(ind[scc[i]]==0&&p[i]==1) ok[scc[i]]=1;
    }
    for(int i=1;i<=scc_cnt;i++)
     if(ind[i]==0&&!ok[i]) {
            printf("-1
");
            return ;
     }
    printf("%d
",ans);
    return ;
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        update(); int x,y;
        for(int i=1;i<=m;i++) scanf("%d",&x),p[x]=1;
        for(int i=1;i<=n;i++) {
            scanf("%d",&y);
            for(int j=1;j<=y;j++){
                scanf("%d",&x);
                add(i,x);
            }
        }
        tarjan();
    } return 0;
}
View Code

【F】

水题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}
const int maxn=60,maxm=2010;
int N,M;
int lin[maxn],len;
struct edge{
    int y,next;
}e[maxm<<1];
inline void insert(int xx,int yy){
    e[++len].next=lin[xx];
    lin[xx]=len;
    e[len].y=yy;
}
bool vis[maxn];
void dfs(int x){
    vis[x]=1;
    for(int i=lin[x];i;i=e[i].next)
        if(!vis[e[i].y])
            dfs(e[i].y);
}
int main(){
    //freopen("in","r",stdin);
    while(scanf("%d %d",&N,&M)!=EOF){
        int t1,t2;
        memset(lin,0,sizeof(lin));len=0;
        for(int i=1;i<=M;i++){
            t1=read(),t2=read();
            insert(t1,t2);
        }
        memset(vis,0,sizeof(vis));
        dfs(1);
        if(vis[N])
            cout<<"Yes
";
        else
            cout<<"No
";
    }
    return 0;
}
View Code

【G】

大家应该会感觉是最短路算法，或者搜索？因为记忆化后节点数也不多。

0代表什么都不拿....7代表1+1+1，拿了三样，这样就是分层处理。

然后每次4个方向。。。我tm居然列举出来，而不是for语句合并。。。。导致代码太丑了。。。

这里用的分层+SPFA，然后用BFS的方法（优先单调队列+STL结构体 实现）搜索的。

由于后面复制的时候排版乱了，将就吧。。。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
char chr[110][110];
int dis[8][110][110],times[10],n,m;
int sx,sy,xx[4],yy[4],ex,ey,t1,t2,t3;
const int inf=0x7fffffff;
struct In
{
    int opt1;
    int x1;
    int y1;
    int stp1;
    In(int i, int j,int k,int t):opt1(i), x1(j), y1(k), stp1(t){}
};
bool operator < (const In& x, const In& y)
{
    return x.stp1 > y.stp1;
}
priority_queue<In>q;
 
void dfs()
{
    while(!q.empty())
    {
        In tmp=q.top();q.pop();
        int opt=tmp.opt1,x=tmp.x1,y=tmp.y1,stp=tmp.stp1;
        if(opt==7&&x==ex&&y==ey) return ;
        if(opt<7){//可以*
        if(x+1<=n) {
            In temp(opt,x+1,y,stp+times[opt]);
            if(dis[opt][x+1][y]>stp+times[opt])  dis[opt][x+1][y]=stp+times[opt],q.push(temp);
            for(int i=1;i<=3;i++){
                if(x==xx[i]&&y==yy[i]&&!((opt>>(i-1))&1)) {
                    In temp(opt+(1<<(i-1)),x+1,y,stp+times[opt+(1<<(i-1))]);
                    if(dis[opt+(1<<(i-1))][x+1][y]>stp+times[opt+(1<<(i-1))])  dis[opt+(1<<(i-1))][x+1][y]=stp+times[opt+(1<<(i-1))],q.push(temp);
                }
            }
        }
        if(x-1>=1){
            In temp(opt,x-1,y,stp+times[opt]);
            if(dis[opt][x-1][y]>stp+times[opt])  dis[opt][x-1][y]=stp+times[opt],q.push(temp);
            for(int i=1;i<=3;i++){
                if(x==xx[i]&&y==yy[i]&&!((opt>>(i-1))&1)) {
                    In temp(opt+(1<<(i-1)),x-1,y,stp+times[opt+(1<<(i-1))]);
                    if(dis[opt+(1<<(i-1))][x-1][y]>stp+times[opt+(1<<(i-1))])  dis[opt+(1<<(i-1))][x-1][y]=stp+times[opt+(1<<(i-1))],q.push(temp);
                }
            }
        }
        if(y-1>=1){
            In temp(opt,x,y-1,stp+times[opt]);
            if(dis[opt][x][y-1]>stp+times[opt])  dis[opt][x][y-1]=stp+times[opt],q.push(temp);
            for(int i=1;i<=3;i++){
                if(x==xx[i]&&y==yy[i]&&!((opt>>(i-1))&1)) {
                    In temp(opt+(1<<(i-1)),x,y-1,stp+times[opt+(1<<(i-1))]);
                    if(dis[opt+(1<<(i-1))][x][y-1]>stp+times[opt+(1<<(i-1))])  dis[opt+(1<<(i-1))][x][y-1]=stp+times[opt+(1<<(i-1))],q.push(temp);
                }
            }
        }
        if(y+1<=m){
            In temp(opt,x,y+1,stp+times[opt]);
            if(dis[opt][x][y+1]>stp+times[opt])  dis[opt][x][y+1]=stp+times[opt],q.push(temp);
            for(int i=1;i<=3;i++){
                if(x==xx[i]&&y==yy[i]&&!((opt>>(i-1))&1)) {
                    In temp(opt+(1<<(i-1)),x,y+1,stp+times[opt+(1<<(i-1))]);
                    if(dis[opt+(1<<(i-1))][x][y+1]>stp+times[opt+(1<<(i-1))])  dis[opt+(1<<(i-1))][x][y+1]=stp+times[opt+(1<<(i-1))],q.push(temp);
                }
            }
        }
       }
        else {//走路
           if(x+1<=n&&chr[x+1][y]=='.') {
              In temp(opt,x+1,y,stp+times[opt]);
              if(dis[opt][x+1][y]>stp+times[opt])  dis[opt][x+1][y]=stp+times[opt],q.push(temp);
           }
           if(x-1>=1&&chr[x-1][y]=='.'){
             In temp(opt,x-1,y,stp+times[opt]);
             if(dis[opt][x-1][y]>stp+times[opt])  dis[opt][x-1][y]=stp+times[opt],q.push(temp);
           }
           if(y-1>=1&&chr[x][y-1]=='.'){
             In temp(opt,x,y-1,stp+times[opt]);
             if(dis[opt][x][y-1]>stp+times[opt])  dis[opt][x][y-1]=stp+times[opt],q.push(temp);
           }
           if(y+1<=m&&chr[x][y+1]=='.'){
              In temp(opt,x,y+1,stp+times[opt]);
              if(dis[opt][x][y+1]>stp+times[opt])  dis[opt][x][y+1]=stp+times[opt],q.push(temp);
           }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%s",chr[i]+1);
        for(int i=0;i<=7;i++)
         for(int j=1;j<=n;j++)
          for(int k=1;k<=m;k++)
           dis[i][j][k]=inf;
        scanf("%d%d%d%d%d%d%d%d%d%d",&sx,&sy,&xx[1],&yy[1],&xx[2],&yy[2],&xx[3],&yy[3],&ex,&ey);
        scanf("%d%d%d",&t1,&t2,&t3);
        times[0]=1; times[1]=1+t1;times[2]=1+t2;times[3]=1+t1+t2;
        times[4]=1+t3;times[5]=1+t1+t3;times[6]=1+t2+t3;times[7]=1+t1+t2+t3;
        In tmp(0,sx,sy,0);
        q.push(tmp);
        dfs();
        printf("%d
",dis[7][ex][ey]);
    return 0;
}
View Code

【H】

STL里面有个permutation，不过要自己手动写展开也不难。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}
int main(){
    int num[8]={1,2,3,4,5,6,7,8};
    do{
        for(int i=0;i<7;i++)
            printf("%d ",num[i]);
        printf("%d",num[7]);
        puts("");
    }while(next_permutation(num,num+8));
    return 0;
}
View Code

相关推荐