牛客網2018年全国多校アルゴリズム冬休み訓練キャンプ練習試合(第4試合)題解

A-石油採取
テーマは海上輸送の石油漏れの問題に従って、新しい有利な業界が誕生していることを説明して、それは油抜き業界です.今、メキシコ湾に浮かぶ大量の石油は、多くの商人の目を引いている.これらの商人たちは特殊な飛行機を持っていて、海面全体を20メートル越えて10メートルの長方形に乗ることができます.(上下に隣接しているか左右に隣接している格子は、斜めにはできません)もちろん、これは1つの瓢箪に捨てられたものがすべて油であることを要求していますが、1つの瓢箪に油と水があれば、意味がなく、資源は全く利用できません.今、商人はこの地域で、彼が最も多くの瓢油を得ることができることを知りたいと思っています.地図はN×Nのネットワークは、各格子が10 mを表す×10 mの正方形の領域は、各領域に油か水かのリンクが表示されています.https://www.nowcoder.net/acm/contest/76/A問題解はすべての点を遍歴し,現在の点が周囲のある点と相殺できるかどうかを判断する.たとえば

   
###
#..
###
   
###
#..
#..
#..

ある点が消えるかどうかを判断するには、その周囲と直線的につながっている点が#であるかどうかにかかっている.サンプル2のような、常に最初から消点であることが証明される.最良の案は(0,0)(1,0)、(0,1)(0,2)、(2,0)(3,0)である.(0,0)がその周囲点と相殺できるかどうかを判断するときは,まずdfsをこの方向の先頭に進み,逆に消去する.
コード#コード#

#include 
using namespace std;
int n,ans;
char mp[55][55];
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool dfs(int x,int y)
{
    for(int i=0;i<4;i++){
        int dx=x+dir[i][0];
        int dy=y+dir[i][1];
        if(dx=0&&dy=0&&mp[dx][dy]=='#'){
            mp[x][y]='.';
            if(!dfs(dx,dy)){
                mp[dx][dy]='.';
                ans++;
                return true;
            }
            mp[x][y]='#';
        }
    }
    return false;
}
int main()
{
    int T;
    while(~scanf("%d",&T)){
    for(int cas=1;cas<=T;cas++){
        ans=0;
        scanf("%d",&n);
        for(int i=0;iscanf("%s",mp[i]);
        for(int i=0;ifor(int j=0;jif(mp[i][j]=='#'){dfs(i,j);}
            }
        }
        printf("Case %d: %d
",cas,ans);
    }}
}

B-道路建設
テーマの説明は今の社会の絶えず変化することに従って、交通問題もますます重要になって、だから市長はいくつかの道路を建設して各都市の間の貿易と取引を便利にすることを決定しました.市長の考えはいいが、一般の人もよく頭を悩ませる問題にも遭遇した.それは手元の経費が限られていることだ......計画の過程で、デザイナーたちは一部の都市間で道路を建設する経費の需要を予算した.今市長は、彼のm都市を限られた経費で道路交通を実現できるかどうかを知りたいと思っています.できればYesを出力し、そうでなければNoを出力します(両都市は直接の道路で接続する必要はなく、間接道路で到着してもいいです.)リンク:https://www.nowcoder.net/acm/contest/76/B備考:2つの都市の間に複数の線路問題解最小生成ツリーが存在する可能性があります.ここで私が使っているKruskalアルゴリズム.コード#コード#

#include 
using namespace std;
struct node
{
    int v1,v2;
    int h;
    bool operatorconst node&other)const{
        return h10005];
int main()
{
    int c,n,m;
    while(~scanf("%d%d%d",&c,&n,&m)){
        int ans=0;
        for(int i=0;i//         。
            scanf("%d%d%d",&nod[i].v1,&nod[i].v2,&nod[i].h);
        }
        sort(nod,nod+n);//         。      。
        bool vis[105]={0};
        vis[nod[0].v1]=1;//     nod[0].x    。
        int NN=1;//      
        for(int i=0;iint num=vis[nod[i].v1]+vis[nod[i].v2];
            if(NN==m) break;//          。
            if(num==1){
                ans+=nod[i].h;
                NN++;
                vis[nod[i].v1]=vis[nod[i].v2]=1;
                i=0;//              。
            }
        }
        printf("%s
",ans<=c?"Yes":"No");
    }
    return 0;
}

C-交差を求める
テーマはあなたに2つの昇順に並ぶ集合を説明して、2つの集合の交差を求めます.リンク:https://www.nowcoder.net/acm/contest/76/C問題解まず集合Aを配列Vで格納する.さらに、二分探索により、集合B中のある数が集合A中にあるか否かを判定し、すぐに出力する.コード#コード#

#include 
using namespace std;
vector<int>v;
const int inf=1000000001;
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;iint t;scanf("%d",&t);
            v.push_back(t);
        }
        int tem=inf;
        for(int i=0;iint t;scanf("%d",&t);
            if(binary_search(v.begin(),v.end(),t)==true){
                if(tem!=inf) printf("%d ",tem);
                tem=t;
            }
        }
        if(tem!=inf) printf("%d
",tem);
        else printf("empty
");
    }
    return 0;
}

E-弟に知らせる
タイトルは戦時中、A国が多くのスパイを他国に派遣して情報を収集したことを描いている.スパイは自分の身分を隠す必要があるので、彼らの間は一方的な連絡にすぎない.だから、あるスパイは一部のスパイに一方的に連絡するしかない.同時に、スパイも彼と連絡したのは誰なのか分からない.HAはスパイたちのボスだが、一部のスパイに連絡するしかない.HAは今、すべてのスパイに伝える命令があります.HAは彼が少なくとも何人の彼が連絡できるスパイにすべてのスパイに知らせることができるかを知りたいと思っています.リンク:https://www.nowcoder.net/acm/contest/76/E問題を解くという意味は、少なくとも連絡できる弟に連絡しなければならないということです.そうすると、考えが行き届かないことが起こりやすい.例えばHAはスパイAとBに連絡することができて、BもAに連絡することができて、この情況はBに連絡すればいいだけです.具体的には、私が別途提示したテストサンプルを見てください.サンプル1
3 3 1 2 3 0 2 1 3 0
サンプル2
4 2 1 2 0 1 3 1 4 1 2
コード#コード#

#include 
using namespace std;
vector<int>x;
vector<int>a[505];
bool vis[505],cst[505];
int ans=0;
void dfs(int k,int s)
{
    vis[k]=1;
    for(int i=0;iint v=a[k][i];
if(!vis[v]) dfs(v,s);
else if(v!=s &&cst[v]){
cst[v]=false;
ans--;
}
}
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) a[i].clear();
x.clear();
ans=0;
for(int i=1;i<=m;i++){
int xx;scanf("%d",&xx);
x.push_back(xx);
}
for(int i=1;i<=n;i++){
int nn;scanf("%d",&nn);
for(int j=1;j<=nn;j++){
int aa;scanf("%d",&aa);
a[i].push_back(aa);
}
}
for(int i=0;iif(!vis[x[i]]){
ans++;
cst[x[i]]=true;
dfs(x[i],x[i]);
}
}
int flag=1;
for(int i=1;i<=n;i++){
if(!vis[i]){flag=0;break;}
}
printf("%d",flag?ans:-1);
}
return 0;
}

F-Call to your teacher
テーマの説明は実験室から出てきた後、あなたは突然自分のパソコンを実験室に落としたことに気づいたが、実験室の先生はドアをロックした.さらに悪いことに、あなたはあの先生の電話番号を持っていません.あなたは知っているすべての人に電話をかけて、先生の電話があるかどうかを聞いて、もしなければ、彼らも自分の同級生に電話番号を聞いています.では、先生に連絡してパソコンを手に入れることができますか.リンク:https://www.nowcoder.net/acm/contest/76/F問題解dfs検索でいいです.注意vis[]配列を設定し、余分な操作を排除します.そうでない場合は、OJでメモリの限界超過を示すメッセージが表示されます.コード#コード#

#include 
using namespace std;
vector<vector<int> > son;
int n,m;
int flag=0;
bool vis[55];
void dfs(int k)
{
    vis[k]=1;
    if(k==n){flag=1;return;}
    for(int i=0;iif(flag==1) return;
        if(vis[son[k][i]]==0) dfs(son[k][i]);
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        flag=0;
        while(!son.empty()) son.clear();
        memset(vis,0,sizeof(vis));
        son.resize(n+1);
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            son[x].push_back(y);
        }
        dfs(1);
        printf("%s
",(flag==1?"Yes":"No"));
    }
}

H-オヤジの全配列ですね
李さんは和尚さんが自分の酒に勝ったのを見たが、自分はまだ惜しんでいたので、いたずらをして、和尚さんに「光武はだめだ.もう少し文をくれ」と言った.リンク:https://www.nowcoder.net/acm/contest/76/H問題解は主に関数next_を使用します.permutation.next_permutation関数は<<または全配列の方法で詳細に分析する.サブセット生成サンプル<<コード

#include 
using namespace std;
int main()
{
    int a[10]={1,2,3,4,5,6,7,8};
    do{
            for(int i=0;i<8;i++){
                cout<if(i==7) cout<else cout<<" ";
}
}while(next_permutation(a,a+8));
return 0;
}