One month in Beijing

2015年2月28日到达北京,到现在一月有余,是时候月度总结了。 这是我第三次来北京 2014年的6月份第一次来北京,去北大计算所实习十天。感受了一下北大计算所p老师及其博士生z的冷漠。我还记得刚到的那天晚上一个人孤零零的走在北京的大街上寻找北大方正员工宿舍的场景。每天重复着朝九晚十的固定模式,每个人都像机器一样的工作,实验室只有敲击键盘的声音,偶尔看到p的时候他也是阴沉着脸,临走的时候还被z批评了。虽然p承诺说只要我通过夏令营面试就会要我,但是这明显就是废话呀;而且这段不算愉快的实习经历让我对p的实验室产生了厌恶。 回学校之后开始准备期末考试和7月份的夏令营,并于2014年7月9日到达北京,这次的行程包括北大计算所和中科院计算所的夏令营。北大计算所因为机试和综合排名不占优势,败下阵来,不过现在想想当初幸好没有进p的实验室,要不然天天对着p的臭脸,估计要疯。 中科院计算所的风格完全不像北大,中科院真正做到了海纳百川,一视同仁,不像北大看不起校外学生。来北京之前和ict的h老师沟通过很多次,发现我和h老师的性格很相似,我非常崇拜h老师严谨的处事风格,经过认真的准备,我也顺利通过了ict的夏令营,然后跑去深圳siat玩耍了。 北京的物价真是贵 这次是来ict完成我的本科毕业设计的,大概要待到5月初。一来从家里不方便带太多东西,二来想想要在北京待三年,所以准备在北京重新置办生活用品。 2月28刚到北京,去了师兄推荐的家乐福大超市。超市很大,有两层,不过里面的东西真是贵。也就买了被子、三件套、桶、盆,花了四五百,很可恨的是,很薄的春秋单人被子,居然要169,这还是最便宜的,床垫比被子还贵,要199。 没必要的用品可以不买,但是饭不能不吃。以前在学校一天也就十几块,到北京后发现,一顿饭就十多块了。早餐一个鸡蛋要2块,一个小包子要1.5块,哎,想想以前自己家做早餐的时候1块钱4个大肉包子啊,当初怎么不多吃几个呢。 餐厅里的饭菜确实贵,不过国科大食堂的饭菜既便宜又好吃,赞一个。 北京的雾霾 来北京之前对北京的雾霾也略有耳闻,觉得那是北京人的小题大做,武汉也是扬尘满天飞,我也活得好好的啊;不过真来北京之后,确实受不了,放眼望去,街道上灰蒙蒙的一片,路上的特大广告牌都看不清。也许是雾霾加干燥的原因,刚来北京那一个星期,嗓子特别不舒服,每天早晨刷牙的时候都恶心干呕,不过后来慢慢好了。 3月28那天,北京还遭遇了沙尘暴,那场景真像外星人袭击地球。所以来北京,口罩是必需品。 3月28日北京的沙尘暴[1] 北京的风景 来北京的前3个星期,忙于组内布置的任务,也是过着朝九晚十的生活,后来想想也不能天天这样,我应该出去透透气,于是选择了颐和园,3月份属于颐和园景区的淡季,加上学生证,门票不贵。颐和园不愧是皇家园林,里面的景色确实很漂亮,有万寿山、昆明湖,湖水还算干净。 我去的那天天气很好,空气质量也不错;人虽多,但不算拥挤,部分原因是颐和园真是太大了。我在游玩的过程中看到了很多外国旅游团,听到过英语、法语、日语、韩语、粤语、中文,让我默默联想起了八国联军侵略中国的场景。 在游玩的过程中遇到了一个很温馨的“外国小家庭”,妈妈是外国人,爸爸应该也是外国人,爸爸和妈妈聊天的时候是用英语,但是爸爸和儿子却是用中文,他们还有一个坐在婴儿车里的小女儿,儿子坐在湖边玩ipad,小女儿在车里哭个不停… 虽然颐和园的风景很好,但是里面居然有很多蚊子(小虫子)!期间有一个虫子撞到我的嘴巴,还有一个钻进了我的耳朵。可能是春天到了,万物复苏,加上颐和园内潮湿,植物丰富,给虫子提供了很好的环境。 下面放几张游玩时拍的照片。 谁能告诉我这是什么乐器 学太极的外国人 这也是迎春花? 这个角度的颐和园很美 长廊 准备回去的时候看到的,各种长枪大炮,据说是在抓拍一种珍稀鸟类。。。 颐和园的风景虽好,但就自然风光来说,比不上南方早已复苏的大自然。 家乡的油菜花,比颐和园的迎春花漂亮多了-:) 武大樱花已经争奇斗艳了,北方还是萧瑟一片[2] 后记 没来北京之前,我想着以后一定要在北京工作,还要争取在北京安家落户。虽然北京生活压力很大,但是机会和挑战也多,这不就是我要的生活吗;而且北京是全国的政治、经济和文化中心,可以很方便的去感受中国几千年的文化和历史。在北京生活一个月之后,我的想法变了,很重要的原因是北京的雾霾和气候。雾霾不是一个人一天两天能够解决的,你必须尽量减少不必要的出行,跑步健身什么的就更别提了;北京属于北温带季风气候,冬天很干燥,而且放眼望去看不到绿色,ict旁边种的树,光秃秃的只有树干。这种钢筋混凝土构筑起来的城市,我真的不喜欢。 和南方的一些城市相比,北京真的不适宜居住,尤其对于南方人! 参考 [1]. 新京报网:http://www.bjnews.com.cn/news/2015/03/28/358122.html [2]. 中新网:http://www.chinanews.com/tp/hd2011/2015/03-21/496005.shtml

March 30, 2015 · 1 min

从一个数字序列中取若干个数字使得和为某个数,问共有多少种取数方案?

在上一题POJ Problem 1837: Balance中,我们曾讲到,如果只有两个挂钩,问题会好办得多,就拿题目给的样例数据来说: Sample Input 2 4 -2 3 3 4 5 8 Sample Output 2 如上图所示,给定重量为3,4,5,8的砝码,放在一个左右臂长分别为2和3的天平上,要使天平平衡,问有多少种方法。 这个问题可以稍加转换,假设放在左边的重量为x,右边为y,则有如下方程组成立: $$ \begin{cases} x+y=3+4+5+8=20\\ 2x=3y \end{cases} $$马上解出x=12,y=8。这样就相当于把原问题转换为:已知序列3,4,5,8,问从中取若干个数使和为12(或8)的方案数有多少个? 因为取出数字和为8,则剩余和为12,所以和为8和12的方案数是相等的。 因为这里只有4个数字,一眼就能看出有(3,4,5),(4,8)能使和为12,即只有两种方案。如果给的数字较多较大,该怎样写代码求出呢?可以使用动态规划求解。 设dp[i][j]表示从前i个数中选若干个数使得和为j的方案数,则我们可以得到这样的状态转换方程: $$ \begin{cases} dp[i][j]=1\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\text{if}i=0\&\&j=0\\ dp[i][j]=dp[i-1][j]\qquad\qquad\qquad\qquad\qquad\qquad\text{if}w[i]>j\\ dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]]\qquad\quad\text{if}w[i]<=j \end{cases} $$ 当i=0&&j=0时,dp[i][j]=1表示从0个数中取若干个数使得和为0,当然只有1种方案,那就是什么都不取 当w[i]>j时,第i个数用不上,因为你单个数字都超过j了,怎么使和为j呢,所以直接dp[i][j]=dp[i-1][j] 当w[i]<=j时,第i个数可以用了,这个时候分两种情况,用或者不用第i个数,如果不用,则和w[i]>j时一样dp[i][j]=dp[i-1][j],如果用的话,则要从前i-1个数中取若干个数使和为j-w[i],也就是dp[i-1][j-w[i]],这样总的方案数就是用和不用第i个数的方案数之和,即dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]] 下面是针对这个例子我手算的一个图: 以上面的内容设计一个OJ题如下: 描述: 给定一个正整数数字序列,从中取出若干个数字,使得这些数字之和为某一个特定的值,求所有取法的方案数。 输入: 输入包含多个测试用例,每个测试用例的第一行有两个数N,S,N表示这个数字序列共有多少个数字;S表示取出的数字之和为S。后面一行包含N个正整数。 N,S为0程序结束 输出: 每个测试用例输出一行,表示从N个数中取若干个数使得和为S的方案总数。 样例输入: 4 8 3 4 5 8 4 12 3 4 5 8 10 10 10 9 8 7 6 5 4 3 2 1 0 0 样例输出: 2 2 10 知道了状态转换方程,我们可以很快的写出以上OJ的代码: ...

November 15, 2014 · 2 min

Git相关笔记

一、第一次使用Github的步骤: 在这个页面中填写Repo名称 不要勾选Initialize this repository with a README 点击Create repository 在本地使用Git命令行工具进入到和第1步填写Repo相同名称的文件夹中(此文件夹中已包含你要push到Github上的内容),执行以下几个命令: 1 2 3 4 5 6 git init touch README.md #optional git add . git commit -m 'your comment' git remote add origin https://github.com/UserName/RepoName git push origin master 如果你在第2步中勾选了Initialize this repository with a README,那么在第4步中省略touch README.md并且在git add .之前,执行第5行代码,然后git pull origin master将远端(remote)的内容pull到本地 关于Git命令中的fetch和pull的区别,请看这篇博文 关于Git bash和Github的连接,请看这篇博文 二、Git命令中fetch和pull的区别(转载) Git中从远程的分支获取最新的版本到本地有这样2个命令: ...

November 11, 2014 · 1 min