首页 > 代码库 > 喵哈哈村的代码传说 1——4

喵哈哈村的代码传说 1——4

链接:http://qscoj.cn/problem/35/

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

发布时间: 2017年3月11日 11:35   最后更新: 2017年3月11日 11:36   时间限制: 1000ms   内存限制: 128M

“敢问这位兄台,为何这喵哈哈广场围了这么多人?”,一位年轻人模样的人问着旁边的卖报小哥。

卖报小哥一听,噗嗤一下,“这位兄弟,从你这问题来看,你可不是本地人。你可知今儿是什么日子?今天可是一年一度的挑战大会!”

“不不不,此言差矣,我是本地人,只不过离开的日子太久了罢了。”,这位年轻人仿佛叹了一口气,“罢了罢了,待我去看看这村子究竟变成了什么模样。”

卖报小哥哈哈大笑,明明一年轻人,装什么老头。卖报小哥接着吆喝起自己的报纸来。

说罢,这位年轻人便走进围观人群,开始观看起来。

---

台上打的正烈!

两个人影不停的在台上移动,互相出招、应对。

“看我一招冒泡排序!”,只见沈宝宝从怀中掏出自己的键盘,噼里啪啦的迅速敲了起来。

冒泡排序虽是黄阶低级的斗技,但是沈宝宝这一手冒泡排序似乎和平时的冒泡排序并不一样。

一般人的冒泡排序可能需要在键盘上敲击五行以上的代码,可这一手!居然只用了四行,威力大增。这一手冒泡排序没有一两年的功夫,怕是练就不成的。

只见空气中的斗气凝练在沈宝宝的键盘之上,形成一个玄色尖刺,甚是骇人。不过沈宝宝的身体仿佛也不好受,他当前的身体,根本承受不了这么强的斗气之力。不过为了胜利,他只好掏出自己这压箱底的宝贝。

只见沈宝宝一下朝着对方的正面击打了过去!

--

“这下王晔就要遭重啦,这个冒泡排序,从这威力来看,估计炼体四阶以下无解。炼体三阶的王晔怕是要遭重啦。”

“王晔肯定输了。”

“不过沈宝宝使完这一招,估计也得回家躺个几天吧。”

“……”

围观人都指指点点道。

王晔却邪魅一笑,居然也不闪躲,直直的朝着尖刺迎了上去。

“王晔怎么回事儿!居然不躲!”沈宝宝心中诧异,但也不容多想,还是一招打了上去。

“嘣”,只听一声闷响。

--

沈宝宝一下子被击飞,跌在地上一动不动,而王晔却只是往后退了一小步。

赢了,王晔居然赢了。

“承让。”说完这句,王晔便走下了挑战台。

全场鸦雀无声,静谧的针落可闻,一个个全都震惊地望着躺在地上的沈宝宝,满眼的匪夷所思。

刚刚发生了什么,怎么一瞬间就被击败了。

---

“王晔居然一瞬间从怀中掏出了100000个数,直接打在了沈宝宝的键盘之上。”那一开始问路的年轻人惊讶了一下,“这王晔居然是一个造数师。”

冒泡排序虽说被沈宝宝用的极为娴熟,但是毕竟冒泡只是一个n^2的黄阶低级算法,处理大量数据的时候,会非常慢,以至于沈宝宝一下子被王晔击败。

如果沈宝宝不用冒泡排序的话,估计能够稳稳的胜下这一场,可惜可惜,遇上了天敌。

“有趣,有趣,这个挑战大会有意思。”年轻人笑了笑。

---

现在,假设你就是沈宝宝,你会怎么应对这100000个数的排序问题呢?

本题包含若干组测试数据。
第一行一个n,表示有n个数。
第二行n个整数a[i]。

保证 1<=n<=100000,1<=a[i]<=100000

对于每组测试数据,输出从小到大排序后的结果。
注意,每一行的末尾都得多加一个空格哦。
比如样例“1 2 3 4 5 \n1 2 3 \n”

 
5
1 3 2 4 5
3
3 2 1
1 2 3 4 5 
1 2 3 
题解:sort排序,可以不用写cmp
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
    return a<b;
}
int main(){
    int n;
    while(cin>>n){
        int num[100005]={0};
        for(int i=0;i<n;i++)cin>>num[i];
        sort(num,num+n,cmp);
        for(int i=0;i<n;i++)cout<<num[i]<<" ";
        cout<<endl;
    }
}

 

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

发布时间: 2017年3月11日 14:45   最后更新: 2017年3月11日 14:48   时间限制: 1000ms   内存限制: 128M

(不想读废话的,可以直接跳到最后。)

造数师,是天玄大陆五大职业中的一种。该职业往往需要凡人不可拥有的强大精神力,因为造数师需要看破对手的斗技,然后迅速用自己的精神力凝结出数字,攻击到敌方的斗技弱点上。

相传强大的造数师,会瞬间创造出以PB记数量级的数据,这些数据就算毫无控制的直接扔下去,就足以暴力破坏掉他所能看见的任何事物,山崩地裂。而还有另外一些强大造数师,利用数据能创造出另一方世界,也许这个世界,便是某个强大的造数师所创造的。

而王晔,便是一名造数师,只不过他现在实在是太弱了。

王晔的上一场战斗,虽说一下子掏出了100000个元素,但是他自己也知道,其实那100000个元素全是0,他的精神力根本造不出那么多自定义的数字。

如果沈宝宝的斗技预先检查一遍的话,输的恐怕就是王晔了。

---

之后过了四五天,王晔虽然斗技不精,但也凭着自己低阶造数师的身份,辅佐强大的精神力,打入了八强。

他的造数师身份,也被大家熟知。

---

接下来这一场八强之战,将会是他面对的一场恶战,因为对手,叫做徐告。

徐告,天玄徐家之后,虽说只有十四五岁的年纪,但是他已通过了天玄大陆第一门派谷歌派的招生筛选,成为了谷歌派的实习弟子,今年七月,他便要去谷歌派修习。

虽说还未去修习,但是就凭他能通过那0.1%不到的招生筛选,就知道徐告的实力不容小觑。

---

“八强第三场战斗,徐告对阵王晔,现在开始!”,只听裁判一声吆喝,就宣布了这对于王晔异常凶险的一场比赛开始了!

那徐告一身白衣,手握静电容键盘,站在挑战台的一端,望着蓝天,仿佛根本没有注意到这场比赛开始了一般。

王晔也不敢乱动,他知道,徐告的实力肯定在他之上,硬拼斗技的话,肯定是他输。

他在等,等徐告的出手。

两人就这样,站着。

一个望着天,一个望着他。

---

“你我差距太大,一招,如果身为造数师的你,能看破这一招,便算你赢。”徐告仿佛回过了神,淡淡的说道。

“在下实力虽然……”王晔这句话还未说完,徐告就拿出键盘攻了过来。

仿佛徐告根本不在乎王晔的回复,他说的话只是一种宣告罢了,根本不在乎你的回复,这或许就是徐家的高傲吧。

徐告的纤细手指飞舞在静电容键盘上,带着“嗒嗒”的声音。

一个光影,从静电容键盘中飞了出来。光影瞬间变得很大,笼罩了王晔的全身。

---

这个光影好像并无伤害能力,只是一个控制斗技,牢牢的困住了王晔。

王晔也不慌张,随手一招天玄大陆人人都会的A与B问题就朝着光影扔了上去。

那光影仿佛根本不会A与B一样,被打了个闷响,被打散了少许。

王晔一看这一招A与B居然有效果,于是迅速凭着自己的精神力,又造了一堆A与B的数据击打过去。

这光影被连连击退,但是击退的部分却越来越小。

王晔感觉渐渐掌握了节奏,又迅速的造了一些数据,击打了过去。

但是第三波数据之后,光影就纹丝不动了。

“这是?”,王晔感到一丝诧异。

“正是”,徐告拿着键盘站在光影之外,静静地说道,“这是神经网络斗技,玄阶中级斗技,是隶属于机器学习的一种,具有学习能力,可谓你越强,这光影就会越强。这斗技虽然只是玄阶中级,但是练就深处,恐怕地阶的一些斗技也挡不住此招。”

王晔一听,仿佛听出了什么。王晔大声问道,“这神经网络的隐含层有几层?”

“只有一层,告诉你也无妨。”徐告淡淡答道。

---

只见王晔的精神力,迅速凝结成几个组数据就扔了过去。

光影挣扎了几下,便被打散了。

神经网络便消失在空中。

徐告仿佛知道这一切的样子,淡淡说道,“看来你看破了。”

“不敢当,不敢当,在下只是恰好在书中看过罢了。神经网络的感知机只会由输出神经元进行激活函数的处理,即只拥有一层功能神经元,实际上该神经网络的学习能力很有限。感知机的学习过程一定是会收敛的,所以感知机能够处理大部分问题。比如A与B,就是一个线性可分的问题,他存在一个线性超平面能够将他们分开。”

徐告说道,“但是,他不能处理非线性可分问题。”

王晔点了点头,“没错,所以只要造出非线性可分问题的数据便能击破神经网络,比如A异或B问题。”

“胜利者,王晔,晋级四强!”

---

现在,假设你就是徐告,你会怎么应对这异或问题呢?

如果不知道异或是什么,那就百度吧。

本题包含若干组测试数据。
第一行一个整数n,表示王晔所制造的数据位数。
第二行两个n位二进制数a,b,保证只含有0或者1.

满足 1<=n<=1000

输出n位数,表示异或之后的答案。

 
3
000 111
5
01010 01010
111
00000
题解:字符串手动比较
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        char a[1005]={0},b[1005]={0};
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<n;i++)cin>>b[i];
        for(int i=0;i<n;i++){
            if(a[i]==b[i]) printf("0");
            else printf("1");
        }
        cout<<endl;
    }
}

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

发布时间: 2017年3月12日 16:00   最后更新: 2017年3月12日 16:01   时间限制: 1000ms   内存限制: 128M

描述

给你一个由0和1构成的矩阵,其中0是墙面,1是道路,现在给你起点的位置(x0,y0),终点的位置(x1,y1),问你从起点到终点最近的路是多少。

如果不能到达输出-1。

保证起点和终点位置都是1。

输入

本题包含若干组测试数据。
第一行六个整数n,m,x0,y0,x1,y1表示这个地图的大小,起点位置,终点。
接下来n行,每行m个数,表示这个地图的样子。

满足1<=n,m<=100

输出

对于每组测试数据,输出最近的路,否则输出-1.

样例输入1
3 3 1 1 3 3
100
100
111
3 3 1 1 3 3
100
000
111

样例输出1
4
-1

 题解:利用队列找最小距离,保存可走的位置,用后pop掉,开mp记录最短距离,从第一个位置开始,之后的(new)等于上一个位置(now)距离+1。check判断是否符合条件

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+6;
int n,m,x0,yy0,x1,yy1;
string s[maxn];//map
int mp[maxn][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 newx=nowx+dx[i];
            int newy=nowy+dy[i];
            if(check(newx,newy)){
                mp[newx][newy]=mp[nowx][nowy]+1;
                qx.push(newx);qy.push(newy);
            }
            
        }
        
    }
    printf("%d\n",mp[x1][yy1]);
    return;
    
}
int main(){
    while(cin>>n>>m>>x0>>yy0>>x1>>yy1){
        solve();
    }
}

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

发布时间: 2017年3月12日 16:00   最后更新: 2017年3月12日 16:01   时间限制: 1000ms   内存限制: 128M

有一个非常大的村子,叫做喵哈哈村,一开始他们都互相不认识,但是渐渐地,他们就会相互来往,所以就会有以下问题的产生:

1 x y,x家与y家成为朋友

2 x y,提问x家和y家是否为朋友,间接成为朋友也算。

本题包含若干组测试数据。
第一行两个整数n,m,表示这个村子有n户家庭,一开始他们都不认识。含有m个问题。
接下来m行:
1 x y
2 x y
分别表示操作和询问。
满足1<=n,m<=100000,注意x

是朋友输出Yes,否则输出N


3 4
2 1 2
2 1 1
1 1 2
2 1 2
No
Yes
Yes
题解
并查集,注意uni中要找祖先
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int fa[maxn];
int fi(int x){
    return fa[x]==x?x:fa[x]=fi(fa[x]);
}
void uni(int x,int y){
    x = fi(x),y = fi(y);
    fa[x]=y;
}
int main(){
    int n,m;
    while(cin>>n>>m){
        for(int i=1;i<=n;i++)fa[i]=i;
        for(int i=0;i<m;i++){
            int op,a,b;
            cin>>op>>a>>b;
            if(op==1) uni(a,b);
            if(op==2){
                if(fi(a)==fi(b))cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
            }
        }
    }
}

 

喵哈哈村的代码传说 1——4