尊敬的用户:当前博客数据库正进行升级,后台暂时无法访问,前台的评论功能暂时也不能使用,敬请谅解。对此带来的不便深表歉意~
信息加载中...
首页 | 生活点滴 | 生活感悟 | 个人日记 | 育儿心经 | 精彩转载 | 生活万花筒 | 法律资料 | 快乐成长 | 牛儿作品

牛儿的变化


  晚上9:26,我的电话响了。一接,是牛儿打的。

  “妈妈,你们今天是没来学校呀?”

   我猛然想起与牛儿约好今晚去看他的,结果因为我与老公都忙而耽搁

了,忘了请牛儿班主任转告牛儿了。

   “不好意思,牛儿,我与爸爸今天都太忙了。”

   “哦,原来这样。”牛儿明显有丝失望。

   “对不起,牛儿!

   “没关系的。那你们明晚来吧。”

    “好。今天忘了请周老师转告你了。”

    “没事呢!妈妈晚安!”

    “晚安!”

    牛儿愉快地挂了电话。

    本以为牛儿会埋怨一下,没想到小朋友竟然能理解我们,没有一句

抱怨的话。这个学期以来,牛儿的变化很明显:学习更加主动了,学习

态度也更加谦虚了,性格也更加阔达了……加油,牛儿!

发布于2019年03月01日 13:57 | 评论数(0) 阅读数(92) 快乐成长

新学期的意外惊喜


    牛儿在开学的那天,提前接到班主任的通知,家长与孩子咱不到原班级报到,先去阶梯教室开会。

     由于学校班级的学生超编,牛儿与部分同学都被抽调到一起,组成一个新的班级。在新的班级,牛儿有很多好朋友,孩子们都很优秀,老师们也很优秀,家长们也很优秀。牛儿很兴奋,他告诉我:“有压力更有动力。”

     昨晚去学校看牛儿,牛儿状态非常好。新的起点,新的希望,愿牛儿在新的环境中茁壮地成长!

发布于2019年02月27日 16:03 | 评论数(0) 阅读数(189) 生活点滴

多虑?


    牛儿寒假的第一天信息学培训。

   清晨,牛儿起床清理东西。

   “牛儿,手表带了吗?”

    “带了。”

    “眼镜呢?”

    “带了。”

    “水杯?”

    “带了。都带了。”

     牛儿下楼时,我突然想起餐卡。

    “牛儿,你的餐卡!”

    “带了呢!”

    牛儿的餐卡,我昨天洗衣服时从他的口袋掏出来的,放在大餐桌上,还没来得及告诉牛儿。

    “你在哪儿拿的?”我有点不相信,因为牛儿找东西的本领与奶奶爸爸差不多,东西就摆在眼前还到找不着。

   “大餐桌。”牛儿边跑边大声回答。

   好吧,是我多虑了。

   结果,晚上回到家,牛爸爸告诉我,牛儿没带餐卡,借了同学的卡。

   我诧异了:“牛儿,你不是带了餐卡吗?”

   “我后来放在床上,忘了拿。”牛儿拿着餐卡,尴尬地从他的卧室里走出来。

    我憋住笑,静静地看着他。

   “我以后再也不会这样了。”牛儿不好意思地笑了。

   

发布于2019年01月28日 08:53 | 评论数(1) 阅读数(213) 快乐成长

作文风波——青春期之快言快语


    语文老师布置一篇作文《我的语文学习榜样》,然后班主任老师将比较优秀的作文拍照上传到家长群。

    牛儿的文章是第一篇,他写的是另一学习小组的组长兼语文课代表。在文中,牛儿运用了对比的手法,不仅写了该同学对语文的真正热爱及对语文课代表工作的认真负,还夸张地与另一个同学对比,最后的语言有些偏激了,他说别人不是真正热爱语文,只是运用一些技巧、公式,将语文作为获取分数的一个工具,还说什么“这样的人注定走不远”。其实那个孩子是牛儿的一个朋友,虽然牛儿有时候是不赞同朋友的很多做法的;我与孩子的家长呢,都相互熟悉。文章一发出,孩子的家长先看到,我是后来才看到的,当时那个尴尬呀,别提了。群里道歉后,我决定当天去学校找牛儿谈谈。

   我是下午就餐时,在食堂找到牛儿的,牛儿与同学们一起在吃晚饭。

   我委婉地提出文章事情,然后指出牛儿言语的不对,结果其他同学马上反对“某某本来就是这样的,而且他根本不会帮我们,我们问问题时,他从来不会像小牛一样帮我们解答,除非是长得漂亮的女孩子。”牛儿也很委屈地说:“看吧,我真的没夸张呢。”

   小朋友们情绪很激动,叽叽喳喳地给我讲述他们之间的众多故事,我插不上话,只能安静地听着。最后,小朋友们总结:“我们同学之间根本不会为这些小事去计较,你们大人太大惊小怪了!”

   看到小朋友们的样子,我知道我是多此一举了,因为他们有自己的判断力和自控力,他们知道如何相处。

    后来我又仔细翻看了小朋友们的作文和挑战书,发现确实是我多虑了。他们的言语都很犀利,直接指向个人。再后来,班主任发班级图文时,都会提醒一句:这是孩子们的事情,请家长们不要过多介意和干涉。确实,我们家长只要旁观即可。

  想起初中时候的我,也是如此,嘴下不饶人。当班长的我看到不公平或者违纪的现象,批评同学和处理事情,从来不知道手下留情。我们其他班委也是如此风格。就这样,后来我们班成为学校的第一个重点班。多年以后,遇到老同学,感慨当年的鲁莽和敢作敢为,现在再也没有那种激情了。

    有点羡慕小朋友们了

    

   

发布于2019年01月09日 12:23 | 评论数(1) 阅读数(227) 快乐成长

叛逆期


   这几天,几位朋友在朋友圈讨论小孩的叛逆期,我们的孩子都差不多大,叛逆,这个词已经成为大家讨论的热点了。

   牛儿的第一次“叛逆期应该是从小学三年级开始,其实准确地来说,那应该不叫叛逆期,那是小孩开始独立的时候。记得那个时候,牛儿总是觉得自己长大了,什么事情都可以独立行动了。于是,就是在暴雨的天气中,牛儿也坚持自己撑伞走路去上学和放学回家,不需要我们开车接送;奥数,牛儿也不愿再去培训班了,他觉得自己可以自学;周末,他约上几个同学去公园玩耍,不想让大人随行;他们还建立了自己的QQ群,讨论一些班级活动事情……那个时候的我,在“放手的同时还在默默关注,担心他的主见会走偏方向。

   牛儿的第二次叛逆期是从初一开始,这个应该是真正的叛逆了。

   从穿衣开始,在十月份的时候,我们都还穿着短袖和裙子,他们一帮小孩子就开始穿着秋季校服了,一边头上冒汗,一边用书当扇子。我们几个家长怎么劝都没效果,我至今也没明白他们这么穿的原因。所幸的是,今年的夏天和秋天,牛儿没这么做了。

    另外一个明显的变化就是注重外表了。天气好的时候,牛儿天天洗澡洗头发,大冬天则是两三天一洗。于是,我给他买了一堆的换洗衣裤。牛儿也特别注重鞋子了。连361、特步、李宁这些鞋子都全部被抛弃,耐克和阿迪达斯开始受到他的青睐。将我之前好不容易才培养出来的节俭习惯一下子“毁掉”了。他老爸竟然支持他还好的是,这个习惯也会像其他事情一样,很快就会过去的。

    半月假和月假,回来一两天,基本上是这种状态:不谈学习和游戏的时候,我们是母慈子孝,一片和谐;一涉及到学习和游戏,立马鸡飞狗跳,狼烟四起。一到这个时候,就是牛儿爸爸出面的时候了。牛儿爸爸一般采取这种办法。久而久之,我就撒手不管了,乐得个逍遥自在。一般情况下,我只负责后勤工作,任由他们父子俩去“折腾”。一个好处就是,牛儿从他老爸那里学到了很多,这是妈妈们无法教给的。

   记得牛儿曾在作文中写到:“有一次我半夜醒来,发现书房还有灯,推门一看,爸爸还在伏案工作。爸爸为了我们生活得更好,他那么辛苦地工作。我突然一下子懂事了,于是,我的叛逆期提前结束了。”我当时看到最后一句话时,偷偷地笑了半天,什么结束呀,现在不正处于这个时期吗?

   尽管这个叛逆期有点长,但我们有耐心陪着他慢慢度过。我的原则是:家长适当放手,管大事,小事则由小孩自己负责。关键在于引导。虽然在叛逆期,但是我们的亲子关系还是很和谐,牛儿会经常打电话回来说说学校的趣事,我们也会隔三差五地去学校看他。我们会像朋友一样地聊天、谈心。希望牛儿天天开心!

   

   

发布于2019年01月04日 11:40 | 评论数(0) 阅读数(98) 快乐成长

(好友可见)


该文章仅对作者的好友开放

发布于2019年01月01日 12:16 | 评论数(0) 阅读数(283) 快乐成长

大丈夫说(牛儿的月考作文)


    

大丈夫说

自古以来,群雄征战,最终获得胜利的人,才能左右诸侯。他们所做的一切,不过是为了争一个流芳百世的大丈夫称号罢了。争名逐利者都认为胜利者、当权者,才是大丈夫可在我看来,并非如此。
    何为大丈夫?她丈夫一词指的是有大志、有作为、有气节的男子那些心怀天下有才干忠贞不渝精神的人他们也许默默无闻,也许在战斗中成为了失败者,但他们用自己的行动,来阐释了大丈夫这个词的含义。

何为有大志?那些口口声声说自己称霸天下,最终没付诸行动的人算吗?答案显而易见。而那些为自己的志向,卧薪尝胆,寒窗苦读的人,才称得上有大志大鹏鸟有着自己翱翔九天的志向,日复做准备、练习,只为自己的志向而奋斗而那些冷嘲热讽之人,就如小小的苍蝇一般,只顾安逸享乐,又怎能知道鹏鸟的志向呢?有大志者,方为大丈夫哉
    何为有作为只会吃喝的人又能做出什么事呢?就如同一棵榕树一般,就能活千年,却不成材,有什么用呢反而看那些栎树、杨树,即使们只能短短几年,却可以成为房屋的栋梁,为人顶住厚厚的屋顶,这算是有用。做一个默默无闻的国家栋梁,总那些不努力空耗国家资源的人,要好得多有作为者,方为大丈夫哉

何为有气节当初日本侵华时,做日本走狗的人有气节吗?没有他们为了自己的利益,放弃自己和民族的原则这种人是天下都应给予鄙视的!秦末西楚霸王项羽,一夫当关,万夫莫开即使被包围,即使是四面楚歌,他都要拼一把,坚决不屈服在刘邦手下哪怕到了乌江口,明明有退路,可以东山再起,却自刎于乌江他那一正气充斥整个天地之间,纵是鬼神也然失色。生当作人杰,死亦为鬼雄,就是对他这个大丈夫一生最完美的诠释有气节者,方为大丈夫哉

是的,只有像鹏鸟、栎树、项羽这样有大志有作为有气节的人,才配得上大丈夫这个称号而我们,就应该像他们一样,做国家的栋梁,在有限年华中,为国家,为民族,为社会绽放出一朵复兴的花。

有鹏鸟之志栎木之作为,霸王之节气,为中华民族复兴而努力的人,才称得上大丈夫


发布于2018年12月22日 20:14 | 评论数(1) 阅读数(170) 牛儿作品

小月考教训


   牛儿学校的月考结束了。

   因为前段时间为了信息学的竞赛,牛儿他们几个参加竞赛的孩子停课集训,所以也没能参加期中考试。牛儿本想通过努力,在这次月考中考好,结果却粗心地闹了个乌龙。英语的答题卡客观题,牛儿没看序号,结果填涂错了,白白丢了二十多分,最后的英语成绩,牛儿形容是“惨不忍睹”,只有95分(总分120),成了班上的一个笑话。牛儿也跌出全校前五十,排在了第六十四。

   这样的情景已经不是第一次发生了。去年的英语竞赛中,牛儿也犯了类似的错误,竞赛结束时,牛儿将试卷交给英语老师对答案(牛儿学校的考试和竞赛,都只要交答题卡,试卷留给学生),欣喜地发现考了个满分。结果成绩出来是99分,牛儿这才猛然想起自己在检查时改正了一个答案,但是只在试卷上改了,本想全部检查完了再统一改答题卡,最后检查完了却忘了改答题卡

   成绩出来后,牛儿在苦恼中给我打了一个电话,我与他一起分析了这次月考的情况。首先是很多习惯不好,比如不仔细检查答题卡,书写潦草马虎,随意涂改,这是考试失分的重要原因,也是急需要改正的地方。其次,过于骄傲。月考前的生地模拟测试,牛儿考得很好,同学们都夸他,以他为学习榜样。结果导致了牛儿的飘飘然(牛儿语,所以牛儿要求我以后尽量不表扬他)。再次,对考试的认识不正确,考试只是检测自己对知识的掌握程度,而不是其他。他们普遍有点急功近利了。

   客观分析加适当鼓励,牛儿的情绪好多了。希望小朋友自己能慢慢明白学习的真正意义。

发布于2018年12月13日 18:47 | 评论数(0) 阅读数(166) 快乐成长

牛儿的考前总结


   刚才借用牛儿的U盘时,无意中发现他在信息学奥赛集训后写的一篇总结,很惊讶,小朋友的成长速度快得我跟不上了。

NOIP考前总结

目录

1. 排序

2. 递归与递推

3. 二分

4. 贪心

5. 搜索与回溯

6. (附)常用模板

7. 总结

排序算法

首先,本人简单介绍一下排序算法

排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列。

常见排序有很多种,例如快速排序、冒泡排序、插入排序、选择排序等。

快速排序

这里给大家介绍一个好东西,是一个可以实现快速排序的函数——sort(在头文件algorithm里)。

Sort中一般有两个参数aa+n,表示将数组的各个元素中从a[0]a[n-1]进行一个排序。当你使用第三个参数时,需要定义一个bool类型的函数,常规形式如右图:

其中 ab表示参与排序的两个参数return的返回值将决定排序是升序排列还是降序排列,>表示是从大到小排列,<与前者相反。同时,a,b的类型是由数组的元素类型决定的。(还有,现在联赛也可以用了哦~

冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。具体如下:

冒泡排序的时间复杂度为O(n2),和快速排序的平均时间复杂度来比(O(nlog(n))),效率就很低了,这里不做推荐。

 

插入排序

 

有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序

时间复杂度:O(n2)

上图:

插入排序在遇到特殊的题目时,可能会发挥出比其他排序更好的效果,建议掌握。

桶排序

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)

时间复杂度:O(n)

缺点:使用内存大

例:

桶排序的思想是我们应该掌握的,在许多题目中都出现过它的身影,推荐例题:明明的随机数

 

 

 

 

 

 

 

 

 

递归与递推

 

递归

1. 介绍

一说起递归,我想每个人都不陌生。举个从小就听过的例子:从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山...是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。

 

2. 示例

也许之前你在网络上看到过这张图片:

实际上这张图就很形象地表达出了递归,这句吓得我抱起了抱着抱着抱着我的小鲤鱼的我的我的我如果从字面意义上看可能看不出是什么意思,那么我们可以通过代码来实现同样的效果:

例如斐波拉契数列

斐波拉契数列就是一个经典的递归题目

如上就是它的递归式,但是我们会发现,当你求大数据时,系统迟迟给不出答案,这可怎么解决呢?于是就有了我们的新算法:递推。

递推

斐波拉契数列在递归时会大量访问重复的节点,因此会超时,但递推不会,因为它是一步一步向后递进的,因此有时对空间要求也很大。

递推式和递归式类似


这样,我们就可以完美地写出一个新的解法

如上,递推就是一步一步向后推,最后输出要求

分治算法(二分)

 

分治,字面上的解释是"分而治之",就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。在计算机科学中,分治就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)等等。

例题:

纪念品分组group

【题目描述】 元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。

你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。

【输入】 输入文件group.in包含n+2: 1行包括一个整数w,为每组纪念品价格之和的上眼 2行为一个整数n,表示购来的纪念品的总件数G 3~n+2行每行包含一个正整数Pi (5 <= Pi <= w)表示对应纪念品的价格。

【输出】 输出文件group.out行,包含一个整数, 最少的分组数目合

【输入输出样例】 

100                                6

9     

90     

20     

20     

30     

50     

60     

70     

80     

90

这是一个典型的二分加贪心(后面我们会讲)的题目,解法也很容易

题解如下:

#include<iostream>

#include<cstdio>

#include<algorithm>//快速排序需要此头文件

using namespace std;

int a[30001];//储存所有的纪念品价格

int main() {

int w,n,i,head=1,tail,ans=0;//head表示头,tail表示尾。ans表示结果。

cin>>w>>n;//输入对应的2个数

for(i=1; i<=n; i++)//循环输入对应的n个纪念品

scanf("%d",&a[i]);//cin效率高的输入

sort(a+1,a+n+1);//n<=3万,用冒泡需要循环4.5亿次,超时。只能用快速排序

tail=n;// 指向当前最大一个礼品

while(head<=tail) {//当前最小的礼品不能超过当前最大的礼品

if(a[head]+a[tail]<=w) {

head++;//如果在放了最大的那个礼品后还能再放一个小的,最小的就放进去,排序队伍里当前最小的就需要变成第二小的了

tail--;//把最大的那个去掉后,第二大的就变成了当前最大的了

ans++;//放了一个当前最大的礼品后,组数+1

} else {

tail--;

ans++;

}

cout<<ans;//输出结果

}

}

 进击的奶牛

题目描述

Farmer John建造了一个有N(2<=N<=100,000)个隔间的牛棚,这些隔间分布在一条直线上,坐标是x1,...,xN (0<=xi<=1,000,000,000)。

他的C(2<=C<=N)头牛不满于隔间的位置分布,它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗,Farmer John想把这些牛安置在指定的隔间,所有牛中相邻两头的最近距离越大越好。那么,这个最大的最近距离是多少呢?

输入输出格式

输入格式:

1行:两个用空格隔开的数字N和C。

2~N+1行:每行一个整数,表示每个隔间的坐标。

输出格式:

输出只有一行,即相邻两头牛最大的最近距离。

通过上面的两道题目可以看出,分治算法是个比较常用的算法,当它求大数据时会有意想不到的结果,是个联赛常考的算法,需要我们掌握。

贪心算法

算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。

基本思想:

建立数学模型来描述问题。

把求解的问题分成若干个子问题。

对每一子问题求解,得到子问题的局部最优解。

把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程:

从问题的某一初始解出发;

while 能朝给定总目标前进一步 do

求出可行解的一个解元素;

下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。

 

例题:[0-1背包问题]有一个背包,背包容量是M=150。有7个物品,物品不可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。

物品 A B C D E F G

重量 35 30 60 50 40 10 25

价值 10 40 30 50 35 40 30

分析:

目标函数:∑pi最大

约束条件是装入的物品总重量不超过背包容量:∑wi<=M(M=150)

根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?

每次挑选所占重量最小的物品装入是否能得到最优解?

每次选取单位重量价值最大的物品,成为解本题的策略。

值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。

贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。

可惜的是,它需要证明后才能真正运用到题目的算法中。

一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。

对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:

贪心策略:选取价值最大者。

反例:

W=30

物品:A B C

重量:28 12 12

价值:30 20 20

根据策略,首先选取物品A,接下来就无法再选取了,可是,选取BC则更好。

贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。

贪心策略:选取单位重量价值最大的物品。

反例:

W=30

物品:A B C

重量:28 20 10

价值:28 20 10

根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。

【注意:如果物品可以分割为任意大小,那么策略3可得最优解】

对于选取单位重量价值最大的物品这个策略,可以再加一条优化的规则:对于单位重量价值一样的,则优先选择重量小的!这样,上面的反例就解决了。

但是,如果题目是如下所示,这个策略就也不行了。

W=40

物品:A B C

重量:25 20 15

价值:25 20 15

:本题是个DP(动态规划)问题,用贪心法并不一定可以求得最优解,以后了解了动态规划算法后本题就有了新的解法。

贪心策略是近年以来常考的一种算法(其实也算不上算法,应该是一种思想),只看当前最优解,然后再由部分最优解得到全局最优解,这就是贪心策略的大体应用。

搜索

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况,从而求出问题的解的一种方法。

 

深度优先搜索

事实上,深度优先搜索属于图算法的一种,英文缩写为DFSDepth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次

所以,深度优先搜索常与回溯算法相结合,当我们发现这种方法行不通时,就要返回上一步,这就是我们常说的:“不撞南墙不回头”。

当然,深度优先搜索有时也被我们称为“暴搜”,因为有时它并不能拿满分,几乎是以一种暴力的手段来解题的,即使是非常难的难题,也能有二三十分。

下面上一段深搜的拆分问题题解:

#include<iostream> 

#include<cstdio>

 #include<algorithm> 

using namespace std;

 int b[1001],n;

 void dfs(int step,int start,int s) 

{

if(s>n)return;

 if(s==n)

 {

for(int i=1;i<step;i++)

{

 if(i==1&&b[i]!=n)

 cout<<b[i]; 

else

 {

 if(b[i]!=n)

 cout<<"+"<<b[i];

 }

}

cout<<endl;

 return;

}

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

 {

b[step]=i;//储存

 dfs(step+1,i,s+i);

}

 }

int main() {

cin>>n;

dfs(1,1,0);//搜索

 return 0;

}

广度优先搜索

宽度优先搜索(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

但是这有一个好处,比如说最短路径问题,如果它找到了目标节点,就可以直接输出,无需回溯,也无需遍历整张图,这就是它比深度优先搜索要更优化的原因。

经典题目——湖计数Lake Counting

由于近期的降雨,雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水('W') 或是旱地('.')。一个网格与其周围的八个网格相连,而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图,确定当中有多少水坑。

输入输出格式

输入格式:

1行:两个空格隔开的整数:N 和 M 第2行到第N+1行:每行M个字符,每个字符是'W'或'.',它们表示网格图中的一排。字符之间没有空格。

输出格式:

一行:水坑的数量

输入输出样例

输入样例#1

10 12

W........WW.

.WWW.....WWW

....WW...WW.

.........WW.

.........W..

..W......W..

.W.W.....WW.

W.W.W.....W.

.W.W......W.

..W.......W.

输出样例#1

3

题解:

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

struct node {

int x,y;

} map[10001]; //结构体队列,x表示队列的x坐标,y表示队列的y坐标,记得数组开大点

char a[101][101];

int ans=0,m,n,head,tail,next[8][2]= {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; //八个方向

void bfs(int p,int q) {

ans++;

head=0;

tail=1;

a[p][q]='.';

map[1].x=p;

map[1].y=q;

do {

head++;

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

int xx=map[head].x+next[i][0];

int yy=map[head].y+next[i][1];

if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='W') { //符合条件

a[xx][yy]='.';

tail++;

map[tail].x=xx;

map[tail].y=yy;//入队

}

}

} while(head<tail);

}

int main() {

cin>>n>>m;

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

for(int j=1; j<=m; j++) {

cin>>a[i][j];

}

}

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

for(int j=1; j<=m; j++) {

if(a[i][j]=='W') {

bfs(i,j);//开始搜索咯~

}

}

}

cout<<ans;//输出

return 0;//完美('')

}

看完上面的题目和题解,相信你已经对广度优先搜索有一点了解了,注意上面的map数组,这是一个结构体队列,其中的x表示当前节点的x坐标,y也一样。

同时,我也将水洼的八个方向用next数组储存了起来,可以模拟八个方向,另外,要将找到的水洼覆盖,防止走回起点,这就是本题的大体思路。

(附)常用模板

 

快读模板

快速幂模板

(PS:因为作者水平不够,只看得懂这两个模板)

 

 

 

 

总结

1. 在考试时,先将第12题的分拿稳,再去写第三题的暴力方法。

2. 第三四题只写部分分(除非能保证满分)

3. 考试最后十分钟,停止作答,检查文件输入输出,程序运行结果,确认无误后,方可交卷。

4. 考试时不要紧张,不要兴奋,心态最重要。

祝我自己2018拿国一!加油加油加油!

 

以上是牛儿的考前总结。

信息学,牛儿是从初中才开始学的,学习时间刚好一年,今年参加全国青少年信息学奥林匹克联赛,虽然与一等奖擦肩而过,但是得了个二等奖,我觉得已经不错了,起初牛儿去参加培训时,都是抱着打酱油的心态,去开拓思维的。





发布于2018年12月09日 13:07 | 评论数(1) 阅读数(172) 牛儿作品

感恩节的故事


  上周一,不小心感冒了,当时没注意采取措施,结果到星期四的时候,嗓子无法正常发声了。星期四是我们专业一二班的税法课,哑着嗓子给一班上了两节课,第三四节课是二班的课,第三节上到一半,嗓子完全无法出声了,只能在黑板上板书。第三节课后,我到办公室去喝水休息,等到第四节课再次回到教室时,我发现讲台上放了两盒药。原来是学生利用课间的休息时间飞奔到后街的药店买的,好感动!

  下午开会时,又收到一班学生的信息。

虽然后来因为工作的原因,没能喝上学生亲手熬的川贝雪梨膏,但是心里暖暖的。

晚上,五班的学生因为补课的事情给我电话,听出我的嗓子不舒服,简单说了两句就挂了电话,然后立马发来了一则消息。

   这几年,一直有老师在感慨学生的冷漠。但今天的事情,彻底推翻了老师们的成见。我跟教研室的教师们说了后,同事们都很惊讶,甚至有老师觉得不可思议。其实,我遇到令我感动的事情很多,比如学生毕业时给我写长长的感谢信,毕业后,有很多同学会给我打电话与发信息问候与交流学习工作和生活近况、会专程跑来看我,会给我寄惊喜的小礼物……

  那天晚上回到家翻看朋友圈时,才发现上星期四是感恩节,因为第二天去外地学习了,昨天晚上才回来,今晚趁着有空,赶紧补记一下,等儿子回来后讲给他听,让他也了解了解他的这些哥哥姐姐们。



发布于2018年11月26日 23:05 | 评论数(2) 阅读数(219) 生活点滴

    1 2 3 4 5 6  >>    尾页  页码:1/29


版权所有 © 2019 Ci123.com 育儿博客 向育儿网举报 网络110报警服务