2008年12月20日星期六
2008年12月3日星期三
| [+/-] |
POJ 1009 Edge Detection 解题报告 |
题意
- 输入:一种叫RLE格式的图片,该格式为两列数据,第一列代表像素值,第二列代表该像素值连续出现的次数。数据不超过1000行,相邻两行的第一列不等;第二列的值可以是1G的量级。
- 输出:采用RLE格式输出,第一列是,某个点的像素值和它周围8个点的最大差值;第二列代表该值连续出现的次数。
思路
- 显然不能用矩阵把输入图片“画”出来再计算,对于1G的量级,时间和空间代价都会很大。
- 假设从左到右逐行读取图片像素:当知道某个点右下角的像素值时,该点的边缘差值就可以算出来了。假设图片宽度为n,那么从第n+1个点开始,就可以逐个计算其左上角点的边缘差值了。为该差值计数,当前差值如果不等于之前的值,那么把之前的值和计数输出,重新开始计数。
- 考虑第i个点(i>n+1,从左到右,逐行计数),其左上角的点c是i-n-1,点c从左开始,顺时针方向的8个点分别是c-n-1,c-n-1,c-n,c-n+1,c+1,c+n+1,c+n,c+n-1。只要求得这8个点的像素值,c点的边缘差值就知道了。
数据结构
- 输入数据可以保存下来,用两个数组,i_val保存像素值,i_num保存该像素值的右边界,用第二个数组,很容易从某个index开始,向前搜索点c对应的idx,从而得到c的像素值。
- 输出结果不需要存下来,逐行输出即可。
优化
- 如果逐点计算,肯定会超时。考虑两种情况:行跳跃和列跳跃。
- 行内跳跃:这是考虑n非常大的情况。假设点c的LEFTUP和RIGHTUP的idx相等,表示其上方区域是成块的;同理,如果c的上中下三行各自成块,那么c附近的点边缘差值都一致,可以不用计算,直接跳跃;注意跳跃的边界:最多跳到该行最后一个点,因为下一行的UP值位置;最多跳到该块的右数第二个点,因为右数第一个点的右列未知。
- 列间跳跃:这是考虑n比较小,但是RLE的length值非常大的情况。跳跃的条件是:块的上下方各留一行。
- 前n个点可以直接跳过,不用再循环中计算;
- y代表当前点在图片中的列标。y=1时,开始考虑列间跳跃;
- y>1时,计算其左上角点的边缘差值,同时考虑行内跳跃;
- y==n时,还需要计算其上方点的边缘差值。
- 对最后一行,逐个计算点,同时考虑行内跳跃。
心得
- 第一次做的时候,觉得时间可以再优化,因为:对于每个点,只用计算4个值即可,另外4个值可以从它相邻的点那儿得到;如果能这样优化,计算量会减少,但是:需要记录3行的点的情况,不适用于n非常大的输入。该做法以WA告终。
- 这道题思路不难,但是各种边界值非常难搞定,我反复debug了两天,最后才AC。
- 练手不错,不过解题速度太慢了,memory还是大。
| Problem: 1009 | User: chenxr | |
| Memory: 456K | Time: 0MS | |
| Language: G++ | Result: Accepted |
2008年4月28日星期一
| [+/-] |
几个趁手语句zz |
来源:4G Spaces
1. Gtalk 传递命令行程序输出信息
常常需要把程序的输出结果或者调试结果通过 IM 发给同事诊断. 而这些结果通常都在字符界面下,拷贝出来很麻烦,于是,我写了一个小程序 gpipe.py,可以把 gtalk 当作一个管道接在程序后面, 比如说, 想把程序编译结果给郝培强(tinyfool),
make 2>&1 | gpipe tinyfool
他的gtalk 客户端就被我用输出给淹没了.
有兴趣的还可以套接 gtalk, 把信息用 base64 编码, 接受方再解码, 如此一来, gtalk 就和Linux 中的管道一样, 将一个机器上的程序的输出套接到另一个机器上另一个程序的输入. 实践证明, 在跨平台的环境下这种做法比使用中间文件分别执行高效很多. 调试时间也大大减少.
2. 传送文件作为邮件附件.
使用matt 客户端,一行即可完成:
echo “Content” | mutt -s “Subject” -a file email@address.demo
这个方法对及时传输一些小文件非常有效, 特别是传送源代码. 还能起到存档备份的效果, 反正Gmail 那么大不用也浪费. 懒人还可以进一步用一个脚本包装, 比如我机器上就包装出了一个 sendboss.sh, 里面是:
echo “Hi, These are the file(s), thanks. Eric” | mutt -s “File” -a $* myboss_email@wustl.edu
这样我每次就只要 “sendboss.sh files” 就可以了. 我老板常常惊讶于我发送文件的反应速度.
3. 一行语句的HTTP文件服务器.
python -m SimpleHTTPServer
即可将当前目录开设为一个8000端口的http 服务器的根目录. 在局域网中,如果需要临时共享当前目录下的一个较大文件,这个方法简便安全,实在是居家旅行必备.
还有, 下载的时候使用 “wget -c” 可以断点续传,很多哥们好像不知道这个小花招.
4. NFS 共享文件夹
SVN 和 CVS 对于代码和文档控制得很好,可是团队中免不了有些 PDF 文档或者色戒电影需要全团队共享,又不需要送到版本控制系统里面。一个共享的文件夹很有必要. 最简单的方法是使用 NFS, 能够跨平台且性能稳定. 具体服务器设置可以参考这里,客户端只要
mount nfs_server:/dir /mnt/share
即可顺利使用此文件夹. 此法对于有电驴 bt 爱好者存在的团队来说,实在是必备良方.
2008年1月8日星期二
| [+/-] |
Fanjita和Noobz小组发布PSP电话软件 |
来源:cngba
参见:noobz
前几日,索尼官方在CES 2008上宣布,轻薄版PSP掌机将在本月底进行固件升级,支持Skype功能,用户可以实现用PSP打电话的功能。不过自制软件界的Hacker们似乎永远走在SONY的前面。今天,著名的自制软件开发者Fanjita和Noobz小组发布了他们自己开发的PSP语音通话软件,比官方更早的支持PSP语音通话功能。
有时你不得不对Fanjita和他的Noobz小组表示敬佩,他们正在从事的工作将使我们陷入疯狂。正当拥有Sony PlayStation Portable的主流人群翘首期盼更多来自官方渠道的Skype消息(著名的即时通讯软件,可以拨打电话,最近有消息称sony 官方将支持skype),Fanjita 和 Noobz小组已近走在了前面。他们正在开发一个具有相同功能的自制软件来替代官方的通话软件。
从Noobz小组最近在其官方主页上的留言可以获知,自制软件开发者们纷纷指出Sony Skype-driven系统有多种缺陷,他们罗列了一系列不足之处,同时决定开发一个大家都喜欢的自制通话软件。
Fanjita 和 Noobz小组的这个新软件叫做"Furikup".他们解释说这个名字来自于俚语中的单词"geeky",(geeky--傻瓜的,奇怪的,变态的)。虽然这个名字第一次听到时或读到时会令人感到肮脏不堪,不过不要担心,让我们来看看他的主要特点:
--首先它是免费的。
---你可以在世界上任意一个角落使用它,只要附近有可用的wifi 接入点,同时有合适的基于SIP协议的VoIP(网络电话)服务提供商就可以了。在很多国家,你很容易就可以找到完全免费或近乎免费的服务商。例如:在英国,你可以选择SIPGate提供的服务,使用固定电话或手机与psp通话,只需支付标准的本地通话费。而如果使用PSP和其它SIP电话设备(如PSP或者PC)通话则是完全免费的。
--这个软件使用的是开方的标准,最大限度的与其他通话系统兼容。
--你可以使用Go!Cam(PSP摄像头),Talkman的麦克风或耳麦进行音频输入(即使你没有这些设备,你依旧可以发送WAVE格式的文件来作为音频输入)
这个软件的作者说道:"目前这个软件仍然处于测试阶段,通话的音频质量还需要花一些功夫(这个很有用),界面还不是很漂亮,视频通话功能还无法正常工作"。
这个软件目前还不成熟,不过我们相信hacker们有实力把它做得比SONY官方的软件更好!
2008年1月6日星期日
| [+/-] |
利用隧道感受IPV6 |
讲述了如何让Win/Linux支持IPv6
read more | digg story
2008年1月4日星期五
2008年1月3日星期四
| [+/-] |
Eclipse快捷键 |
Ctrl+1: 快速重构
Ctrl+/: 注释/取消注释
Ctrl+,: 在文件中快速定位到问题(如错误、警告等)
Ctrl+D: 删除光标所在行
Ctrl+H: 打开搜索窗口
Ctrl+K: 将光标停留在变量上,按Ctrl+K键可以查找到下一个同样的变量
Ctrl+L: 定位在某行
Ctrl+M: 快速对当前视图最大化
Ctrl+O: 快速显示Outline
Ctrl+Q: 回到最后一次编辑的地方
Ctrl+T: 快速显示当前类的继承结构
Ctrl+W: 关闭当前Editer
Ctrl+/(小键盘): 折叠当前类中的所有代码
Ctrl+*(小键盘): 展开当前类中的所有代码
Ctrl+单击:可以跟踪方法和类的源码
Ctrl+鼠标停留: 可以显示类和方法的源码
Ctrl+Shift+F: 格式化当前代码
Ctrl+Shift+G: 在workspace中搜索引用
Ctrl+Shift+K: 和Ctrl+K查找的方向相反
Ctrl+Shift+M: 添加import
Ctrl+Shift+O: 快速导入import
Ctrl+Shift+P 定位到对应的匹配符(譬如{})
Ctrl+Shift+R: 打开资源(文件等)
Ctrl+Shift+S: 保存全部
Ctrl+Shift+T: 打开类型
Ctrl+Shift+X: 将所选字符转为大写
Ctrl+Shift+Y: 将所选字符转为小写
Ctrl+Alt+↓: 复制当前行到下一行(复制增加)
Ctrl+Alt+↑: 复制当前行到上一行(复制增加)
Alt+/:代码提示
Alt+↓: 当前行和下面一行交互位置
Alt+↑: 当前行和上面一行交互位置
Alt+←: 前一个编辑的页面
Alt+→: 下一个编辑的页面
Alt+Enter: 显示当前选择资源(工程,or 文件 or文件)的属性
Alt+Shift+C: 修改函数结构(比较实用,有N个函数调用了这个方法,修改一次搞定)
Alt+Shift+F: 把Class中的local变量变为field变量
Alt+Shift+I: Inline
Alt+Shift+L: 抽取本地变量(可以直接把一些魔法数字和字符串抽取成一个变量,尤其是多处调用的时候)
Alt+Shift+M: 抽取方法
Alt+Shift+R: 重命名
Alt+Shift+V: 移动函数和变量
Alt+Shift+Z: 重构Undo
Shift+Enter: 在当前行的下一行插入空行(这时鼠标可以在当前行的任一位置,不一定是最后)
Shift+Ctrl+Enter: 在当前行插入空行(原理同上条)
双击左括号(小括号、中括号、大括号),将选择括号内的所有内容。
F3:打开声明该引用的文件
F4:打开类型层次结构
F5:单步跳入
F6:单步跳过
F7:单步跳出
F8:继续,如果后面没有断点,程序将运行完
F11:调试上次启动
| [+/-] |
终于能用blogger了 |
1.什么是tor?
tor的全写是“The Onion Router”,它能提供一个分布式的、匿名的网络,以抵御流量分析。简单地说,使用tor以后,你在访问的网页内容基本不会被别人知道。为了看见别人不想让你看见的内容,你需要绕过别人的监测,使人不知道你到底在访问什么。
2.需要的软件
Vidalia套件: 集成了Tor,Tor图形前端Vidalia,以及可以把SOCK5代理转换成Http代理的软件Privoxy。
Firefox2: 推荐使用的浏览器。
FoxyProxy: Firefox的插件,可以方便的切换代理。
ScribeFire: Firefox的插件,离线Blog编辑工具,支持Wordpress,Blogger等等。
3.安装与设置
- Tor相关
- 安装Vidalia套件,Tor的洋葱图标会出现在右下角,点击运行。
- 本机就有了一个SOCK5代理服务器,地址是localhost:9050。在应用程序中设置该代理即可使用Tor强大的匿名服务。
- 如果应用程序不支持SOCK5代理,可以使用Privoxy提供的HTTP代理,地址是localhost:8118。
- Firefox相关
- 安装Firefox
- 在Firefox中,可以手动进行代理设置,工具-选项-高级-网络-设置-手动设置
- http代理填localhost,端口8118
- SSL代理同上
- SOCK5代理填localhost,端口9050
- 手动设置的不便之处在于所有网站都会通过代理来访问,而我们希望部分网页才用代理,以获得更加的浏览速度。于是可以选择FoxyProxy插件:
- 安装后,重启Firefox,有Tor的配置向导。
- 在提示是否选择Privoxy时,可以选择不用,这样就直接走Tor的SOCK5代理了。
- 在设置模板的页面,主要是设置白名单和黑名单。推荐使用Delay All,Permission Whitelist的策略。将*.wikipedia.org/*,*.blogspot.com/*等站点作为通配符加入白名单。
- 接下来就可以无限制地访问互联网了。遇到被GFW的站点,可以用Alt+F2快捷键加入到FoxyProxy的白名单中。
- 使用ScribeFire插件,可以方便地编写blog。安装后,点击Firefox右下角的撰写图标,点add,填入你的blog地址http://yourname.blogspot.com,然后就可以撰写了。方便之处在于,如果你在网上看了某篇文章,想写心得,可以在页面下方打开ScribeFire,对照着写。
Powered by ScribeFire.



