喵哈哈村的魔法考试 Round #6 (Div.3) 题解

有任何问题 直接联系QQ：475517977

喵哈哈村的代码传说 第一章 冒泡排序

第一题就是排序嘛，在ACM/OI竞赛中，我只推崇一种排序方法，就是直接调用algorithm里面的sort函数。

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n;

    while(cin>>n){

        vector<int> V;

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

            int p;

            scanf("%d",&p);

            V.push_back(p);

        }

        sort(V.begin(),V.end());

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

            cout<<V[i]<<" ";

        cout<<endl;

    }

}

喵哈哈村的代码传说 第二章 神经网络

这道题实际上就是考察你知不知道异或。

如果相同就输出0，否则输出1就好了。

#include<bits/stdc++.h>

using namespace std;

string a,b;

int n;

int main(){

    while(cin>>n){

        cin>>a>>b;

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

            if(a[i]==b[i])cout<<"0";

            else cout<<"1";

        }

        cout<<endl;

    }

}

喵哈哈村的代码传说 第三章 宽度优先搜索

BFS的裸题嘛，如果你不会代码，那就仔细研读我的代码吧。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e3+6;

int n,m,x0,yy0,x1,yy1;

int mp[maxn][maxn];

string s[maxn];

int dx[4]={1,-1,0,0};

int dy[4]={0,0,1,-1};

int check(int x,int y){

    if(x<0||x>=n)return false;

    if(y<0||y>=m)return false;

    if(mp[x][y]!=-1)return false;

    if(s[x][y]=='0')return false;

    return true;

}

void solve(){

    x0--,yy0--,x1--,yy1--;

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

        cin>>s[i];

    memset(mp,-1,sizeof(mp));

    queue<int> QX,QY;

    QX.push(x0);

    QY.push(yy0);

    mp[x0][yy0]=0;

    while(!QX.empty()){

        int nowx=QX.front();

        int nowy=QY.front();

        QX.pop(),QY.pop();

        for(int i=0;i<4;i++){

            int nex=nowx+dx[i];

            int ney=nowy+dy[i];

            if(check(nex,ney)){

                mp[nex][ney]=mp[nowx][nowy]+1;

                QX.push(nex);

                QY.push(ney);

            }

        }

    }

    printf("%d\n",mp[x1][yy1]);

    return;

}

int main(){

    while(cin>>n>>m>>x0>>yy0>>x1>>yy1)

        solve();

    return 0;

}

喵哈哈村的代码传说 第四章 并查集

这道题就是并查集的题目，就是裸的并查集。

    #include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+6;

int n,m;

int fa[maxn];

int fi(int x){

    return fa[x]==x?x:fa[x]=fi(fa[x]);

}

int uni(int x,int y){

    x = fi(x),y = fi(y);

    fa[x]=y;

}

void solve(){

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

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

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        if(a==1){

            uni(b,c);

        }else{

            if(fi(b)==fi(c)){

                cout<<"Yes"<<endl;

            }else{

                cout<<"No"<<endl;

            }

        }

    }

}

int main(){

    while(cin>>n>>m)solve();

}

喵哈哈村的代码传说 第五章 找规律

多校原题。Sg函数的裸题。

sg[0]=0

当x=8k+7时sg[x]=8k+8，

当x=8k+8时sg[x]=8k+7,

其余时候sg[x]=x；（k>=0）

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int T,n;

    scanf("%d",&T);

    while(T--)

    {

        int ans=0;

        scanf("%d",&n);

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

        {

            int x,sg;

            scanf("%d",&x);

            if(x%8!=0&&x%8!=7)

                sg=x;

            else

                if(x%8==0) sg=x-1;else sg=x+1;

            ans^=sg;

        }

        if(ans) printf("First player wins.\n");else printf("Second player wins.\n");

    }

    return 0;

}

打表找规律可得，数学归纳法可证