记这次高中同学聚会

每次假期回来,我们几个玩得好的哥们都要聚一聚,这一次来的有吕肥,老汪,鑫爷,干哥,叼男,咪,庞龙,大黄,麻神;bra是呆在南京,没回来,小李子也是没回来。

其实每次聚会就是打牌,疯打,不过我们每次还是都要出来,现在的年代都变了,我爸妈说,他们那个年代,玩得最好的都是大学同学,可以现在不一样了,现在大学有了电脑,有了网,大家都是一回寝室就玩游戏,上网,如果在以前那个年代,大家肯定一起自习,一起运动,现在不一样了,所以相反我和天天一起踢球的周桐,铁哥,韩冰等都玩得不错。其实说起来,玩得最好的还是这些高中的哥们,想起和鑫爷三年同学,一年室友,半年同桌,这关系无需多言;和老汪也是一年半的同桌,天天一起放学;和吕非那更不用说了,妈的两个喜欢无聊喜欢疯的家伙玩一起去了,那是啥都没法说的,各种变态,各种无聊,记得最开心的时候就是当年我,老汪,吕肥,凡逼坐最后面,那时真搞笑;还有咪和庞龙坐我前面的时候;现在回忆起来还是很开心。

今天还是老样子,上午去茶楼打牌,打麻将,中午吃了饭,下午直接去二中打篮球,从1点打到4点。。。热死了。不过玩得很开心。

这才是铁哥们,感谢你们,陪我度过高中,咱们的友情要一直延续下去~~~

滚动数组[转载]

利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。不过经常还是用在DP题目中,因为DP题目是一个自下而上的扩展过程,我们常常用到是连续的解,前面的解往往舍弃!所以用滚动数组可以说是很有必要的。

滚动数组 举个简单的例子:

1
2
3
4
5
6
int i, d[100];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
    d[i] = d[i - 1] + d[i - 2];
printf("%d", d[99]);

上面这个循环d[i]只依赖于前两个数据d[i – 1]和d[i – 2];
为了节约空间用滚动数组的做法:

1
2
3
4
5
6
int d[3];
d[0] = 1;
d[1] = 1;
for (i = 2; i < 100; i++)
    d[i % 3] = d[(i - 1) % 3] + d[(i - 2) % 3];
printf("%d", d[99 % 3]);

注意上面的取余运算,我们成功地只保留了需要的最后3个解,数组好象在“滚动”一样,所以叫滚动数组。

//DP
对于二维也可以用(代码可能不太正确和完善,但是可以理解例子):

1
2
3
4
int i,j,d[100][100];
for(i=1;i<100;i++)
    for(j=0;j<100;j++)
        d[i][j]=d[i-1][j]+d[i][j-1];

上面的d[i][j]只依赖于d[i-1][j],d[i][j-1];
运用滚动数组

1
2
3
4
int i,,j,d[2][100];
for(i=1;i<100;i++)
    for(j=0;j<100;j++)
        d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];

滚动数组实际是一种节省空间的办法,时间上没啥优势,多用于DP中,举个

例子吧:

一个DP,平常如果需要1000×1000的空间,其实根据DP的无后效性,可以开成2×1000,然后通过滚动,获得和1000×1000一样的效果。滚动数组常用于DP之中,在DP过程中,我们在由一个状态转向另一个状态时,很可能之前存储的某些状态信息就已经无用了,例如在01背包问题中,从理解角度讲我们应开DP[i][j]的二维数组,第一维我们存处理到第几个物品,也就是阶段了,第二维存储容量,但是我们获得DP[i],只需使用DP[i – 1]的信息,DP[i – k],k>1都成了无用空间,因此我们可以将数组开成一维就行,迭代更新数组中内容,滚动数组也是这个原理,目的也一样,不过这时候的问题常常是不可能缩成一维的了,比如一个DP[i][j]需要由DP[i – 1 ][k],DP[i – 2][k]决定,i

博客想转型了,大家支持我吗?

感觉博客有必要转型了,到现在为止,博客开了有一年多了,虽然写的博文有块500篇了,但其中大概有300篇全部是OJ的一些解题报告。

我是这么想的,博客,是用来交友,是用来记实,是用来以后回忆的,我以后肯定不会拿这些解题报告来回忆 8-O ,而且好多朋友来我博客,都说看不懂,辛苦大家了~~

呵呵,其实吧,现在想想,博客已经逐渐发展起来了,也没必要靠这些解题报告来充实博客了。

所以我准备把博客面向以下几个方面:

0.为什么第一项是0呢?学过编程的肯定知道,许多语言对于数组,第一项的下标不是1,而是0,呵呵。我的第0方面还是解题报告,只不过不是什么题都发的,我会发一些我不会,或者比较难,或者比较经典以及有意义的题目~~~

1.算法教程,我个人比较希望总结,也希望和更多的朋友分享我的学习笔记,希望大家能多多互相探讨。

2.平时一些计算机编程方面的学习状况及笔记,包括转载,这方面有Linux, 单片机,Qt,等等。

3.我也比较喜欢一些Web前端,只是时间不够,只能偶尔学一学,当然,我也会抽出时间好好学学的。

4.数学,我只能说喜欢,所以我也会找一些数学方面有意思的文章转载,我个人暂时没能力写出来~~~

5.天文,这个是我一直都很喜欢的,不过还重来没写过文章,呵呵,等毕业了自己买个天文望远镜好好学学。

6.灵修,这方面我看过的书籍还是比较多,不过没怎么思考,这样可不好,要多思考思考,记录一下。

7.足球,这个不用说,我基本天天要踢3个小时,算是比较狂热的了吧?

8.心情札记,包括身边的事,以及一人唠叨的话啊~~这个是重点,生活就是由这些组成的~~

所以说,以后我的博客里的解题报告不会多了,但是编程方面的文章肯定还是主打,毕竟这是以后我混饭的东西,但是其他类容也会增加很好。

嗯,博客转型了,庆祝一下,也希望大家多多支持!

HDU/HDOJ 1196 Lowest Bit(水题)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1196

注意<<与&的优先级。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Author: Tanky Woo
// Blog: www.WuTianQi.com
// Title: HDOJ 1196 Lowest Bit
// About: 水题
 
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
 
 
int fun(int n)
{
    int ans = 1;
    while((n & 1) == 0)
    {
        ans *= 2;
        n = n >> 1;
    }
    return ans;
}
 
int main()
{
    int n;
    while(cin >> n && n)
    {
        cout << fun(n) << endl;
    }
}