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.
