爱普生ME-30的Linux驱动, Using Epson ME-30 in Linux (Driver!)

每次想把这破玩意用起来都老费事了
Ubuntu下自动找到的驱动没用, 一切运行行云流水, 提示”processing”有模有样, 打印机也动, 灯还闪, 但是就是不进纸 -_,-

搜了一下在这里下到驱动, 有For Ubuntu 8.04的, 我目前是10.10测试OK, 唯一要注意的是安装结束提示是否设置成默认打印机, 勾选也没用, 自己手动设置一下

Every time I want to use this stupid thing it causes so much trouble
Ubuntu can find driver for it automatically which doesn’t work. Everything went fine, I was notified printing is “Processing”, and the printer also made sounds with its LED blinking, except that the paper wouldn’t go in XD

So I googled and found driver HERE. Have one for Ubuntu 8.04 (I’m 10.10 and it works fine to me). The only thing you should notice is that when the installing ends it asks whether to set ME30 to be default printer, which doesn’t work even you check it. So set it manually.

Update:
Okay… There is an issue when I tried to print images.
1. Can’t print photo, maybe too complex to render…
2. simple image can be printed, like THIS, but the color is.. not only distorted, also like toxic..

我打印图片的时候有问题..
1. 照片打印不能, 可能对于这个驱动来说渲染这么复杂的东西让它不堪重负..
2. 简单的图片可以印出来, 比如这个,  但是颜色不仅失真了而且像中毒了一样..花里糊哨的

GRE意识鲨, The Big Shark Is Watching You

The Greeyeshark 是一种生活在红宝书里以背词者意念为食的鲨鱼,这是一种非常邪恶的鲨鱼。成年Greeyeshark的身体拥有非常可观且固定的长度,为436.46米(这恰好能从头到尾覆盖50个list),这样的长度主要由它的尾巴所支持。

Greeyeshark布满全身的触须使其得以将敏锐的嗅觉深入到每个单词的字根,这种意识鲨尾部长有一只过度进化的眼睛,相对的,鲨鱼头部的双眼因其无用已经在进化树的某个节点后消失,只留下一对深深的眼窝。之所以称这只眼睛“过度进化”是因为,Greeyeshark对它的依赖使其在进化的长河中具有了初步的自我意识。虽然这种进化过程中“最近”才产生的自我意识在个体进行决策时具有的优先度较Greeyeshark自身要低,但由于其在智商上的绝对优势,鲨鱼在大多数情况(尤其是在狩猎时)下不得不依赖于尾眼进行决策。所以与其说尾眼是Greeyeshark的一部分,不如说他们是寄生与被寄生的关系。

Greeyeshark在狩猎时的反应相当迅速,当背词者出现烦躁、焦虑、沮丧或绝望等脆弱的情绪时, Read More

Happy Viaxl Day!

我的函数白送你们~(破裂光环!)

– (x/(R*2)-1.2)^2 * (y/R-1)^3 + [ (x/(2*R)-1.2)^2 + (y/R-1)^-1 ]^3
R是大致半径, 这里是13..

这破烂代码有人要么, 在自习室学用VIM写的, 好恶心啊.. 还是没Emacs舒服
纯用iPad完成, 关于如果用iPad GCC, 点我的这篇文章

Read More

在iPad上写代码并用GCC编译

对于不想折腾就像体验一下用iPad敲敲代码的同学来说, 蓝牙键盘 + 一个叫textastic的带语法高亮的文本编辑器app就能满足你的需求

iPad十几个小时的续航和轻薄的体型, 再加上才买了蓝牙键盘, 实在是让我不能不想用它来写代码. 下面介绍我在iPad上最终成功运行Vim和编译运行代码的经验.

想要运行代码肯定首先要破解.. 苹果的销售策略里, app是不能运行脚本的, 就是说不能运行任何自定义的程序.

Apple is acting as a gatekeeper for what is and isn’t allowed on your device. I heard that Apple would never allow a scripting language to be installed on your iPad because it would allow end users to run code that they hadn’t verified.

摘自 http://jjinux.blogspot.com/2010/05/apple-ipad-and-emacs.html

越狱我就不多嘴了, 假设你已经越狱, 并且假设你的iPad是免费的 >=P

我的系统是3.2.2, 3系列的应该不会有问题, 4往上可能需要不同的fake-libgcc(我下面有提, 我觉得就是把系统环境伪装成2.0的系统从而让针对2.0系统开发的iphone-gcc可以工作)

获取终端

在cydia首页可以找到openSSH的下载链接, 下载&安装后, iPad就启动了SSH service.  装一个叫iSSH的app, 在iPad上运行Terminal的原理就是连接本地的SSH, 并不是底层破解 🙂 root的密码默认为alpine.

安装GNU GCC

根据 这篇文章, 但是此文是针对2.0系统的, 我3.0系统就纠结了很久, 最终整理如下: Read More

给自己做的名片, 矢量图

设计是网上看的, 我从21点改到3点, 从0开始个学习矢量图设计, 用的CorelDraw, 挺好用的, 矢量就是完美啊~

可惜因为创意不是我的在折腾那么久以后竟然不好意思写上Designed by Viaxl, 一方面说明以后再有类似的能直接自己动手做就不要导入别人的文件, 另一方面说明我的人格太闪光了, 欺人可以有, 自欺是傻逼

矢量图画质一损耗就很容易变色, 我上传的这个画质是挺高的, 1.2M, 但是Chrome好像对太高画质的图像浏览的时候有优化, 看上去还是有损耗, 保存到电脑上再看就好

了.

beta版啦~ 做这个的原因是个猫腻. 源文件就先不传了, 第一次做难免小气 >=P

Update:  印出来啦, 好好玩儿啊~~

Java + MySQL 实现的图书馆管理系统

我实在想在标题后面加两个点.. 这个是课程设计..是课程设计.. 都用的C#, C#做Windows程序貌似很方便, 不过我实在不待见M$, 比较爱开源, 所以就花了一晚上整了这么一个Java + MySQL的东西出来, 之前没怎么用Java写过东西

以我的浅薄之见JDBC(就是Java得以与SQL通信的库, 与怎样的SQL通信就装一个怎样的Driver)其实是没啥大用. Linux下做MySQL应用还是以web形式好吧, 要图形界面干嘛, 反正用不到Java, Windows用.Net也比Java快, 而且也不需要跨平台..

但是反正课程设计还指望它能有什么实际用处.. 我正好练习下Java
而且虽然没用.. 但是哥确确实实是实现了跨平台.. Linux下编好compile打包成jar, 放到windows下直接运行的感觉还是不错的 嘿嘿

八百多行好像, 一小半是图形界面的代码, 用NetBeans做的图形界面, 据yzhw牛说有个叫JBuilder的做界面很不错, 不过是收费的. NetBeans我用起来也没什么问题, 就是设计的时候界面很好看, Compile出来就傻眼了..降了一个等级

总之, 这么个东西我网上没找到适合课设的源码, JDBC的实现是我Google一点一点摸索出来的, 还有点参考价值, 放出下载吧..
有BUG哟~~ 并且下面的TAB就TAB1是真的, TAB2和3都是我随便搞出来撑场子的.. 老师查的松
不过基本的数据库操作都搞出来了, 那些墨墨迹迹的功能还不是小菜

下载见下载页

[ACM] POJ 1205, 简单DP

DP就是每次在原序列右边加一个city的时候 (此时n个city) 只要看前一个状态 (n-1个city) 最右边的city的情况
也就是记录n个city时的三个状态 xxxV xxx> xxx<
xxxV 和 xxx< 的数量和就是要求的结果, xxx>是记录一下如果允许向右流水那么方案的数量
状态转移即为右图
然后dp[100]结果超过long long, 于是用BigInteger, 写这个报告的原因也是第一次用Java交OJ..

代码:


import java.math.*;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		BigInteger dp[][]=new BigInteger[101][2];
		dp[1][0]=BigInteger.ONE;
		dp[1][1]=BigInteger.ZERO;
		for(int i=2;i<=100;i++) {
			dp[i][0]=dp[i-1][0].add(dp[i-1][0]).add(dp[i-1][1]);
			dp[i][1]=dp[i-1][0].add(dp[i-1][1]);
		}
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()) {
			int a=sc.nextInt();
			System.out.println(dp[a][0].add(dp[a][1]));
		}
	}
}

[ACM] POJ 1173 解题报告, DP, 逐位确定

我表示是跟着黄伟牛混的.. 他写的报告难以称作报告.. 题目一抄写两句话代码一贴万事, 自己琢磨了好久, 记录一下, 我记性不好喜欢写的详细一点以后自己可以查.. (拓展阅读: 刘未鹏牛的<为什么你应该(从现在开始就)写博客> )

快放假了, ACM + GRE 加油, 不拼命的下场只有一个, 平庸.. 哞

第一问 total number of symbols in BC(n,k,m) 比较容易, 简单DP

dp[n][k][m]=∑dp[n-i][k-1][m]     , i∈[1,m]

第二问 yzhw口口声声“经典的逐位确定方法”..

也就是说, 我们来看 “1111010”(从0位到6位), 简单的讲从高位(0)到低位(6)每一位如果有1, 那么就看, 如果这一位是0, (继承前面的高位后) 低位能形成多少种组合, 把这个组合数加到rank中.
流程是 1[0xxxxx]能有多少组合 即求0xxxxx符合k-1和m的组合(直接用前面求出的dp数组即可, 虽然前面求的是1xxxxx, 但是和0xxxxx数量是一样的), 然后11[0xxxx]能有多少种, 遇到0跳过, 最后看11110[0x]

但是这样并不完全缜密, 我们考虑”10011000″的情况, 按上面的算法进行到第3位的时候, 100[0xxxx], 这个0xxxx是可能产生00011这种组合的, 而放入原文就变成了10000011, 0的长度就超过了. 所以我们想出来的办法是把 0-1 (不包括1到0) 交界处的那个1单独考虑, 看前面有多少位0然后详细说明. 比如100[0xxxx], xxxx只能是以1开头的, 10[0xxx], xxx只能是1xx或者01x, (11x到哪去了? 11x不是在这里的 [特殊情况] 内考虑的, 好好想一下.. 没法讲的太清楚)

代码如下, 写的时候很有自己的想法, 多推敲推敲最后的产品和yzhw的也八九不离十了.. 这个代码还是很精简很漂亮的


#include <stdio.h>
#include <string.h>
#include <algorithm>

int main() {
	int dp[34][34][34];
	memset(dp,0,sizeof(dp));
	//DP
	for(int m=1;m<=33;m++) {
		for(int i=1;i<=m;i++)
			dp[i][1][m]=1;
		for(int k=1;k<33;k++)
			for(int n=k;n<33;n++) {
				if(!dp[n][k][m])
					break;
				for(int i=1;i<=m;i++) {
					if(n+i>33)
						break;
					dp[n+i][k+1][m]+=dp[n][k][m];
				}
			}
	}

	int n,k,m;
	scanf("%d%d%d",&n,&k,&m);
	printf("%d\n",dp[n][k][m]);

	int N;
	scanf("%d",&N);
	while(N--) {
		char a[34];
		scanf("%s",a);
		char color='1';
		int rank=0;
		int kRemain=k;
		int head=0;
		for(int p=0;a[p]!='\0';p++) {
			if(color==a[p])
				continue;
			if(color=='1') {
				color='0';
				kRemain--;
				for(int i=head+1;i<p;i++)
					rank+=dp[n-i][kRemain][m];
			}
			else {
				color='1';
				kRemain--;
				for(int i=std::min(n-1,head+m);i>p;i--)
					rank+=dp[n-i][kRemain][m];
			}
			head=p;
		}
		printf("%d\n",rank);
	}

	return 0;
}

[烹饪] 20101228煎Filet牛排实验报告

器材: 普通平底锅, 木质铲子, 菜夹子..
原料: 略微腌制的Filet牛排 (以下简称单元) (大误..), 厚度目测薄处1cm 厚处1.2~1.3cm, 两块, 分两次记录数据
黑椒蘑菇汁, 总统牌黄油
目的: 对加热时间与熟度关系的数据记录
预备: 色拉油(橄榄油已耗尽..)抹锅底防止粘锅, 黄油10克每份共两份,
条件: 煎肉油温一直保持130度

第一次实验:

放入牛排, 加热20秒翻面, 目的是锁住肉汁.
继续加热20秒, 放入一份黄油, 牛排盖住黄油加速融化.
黄油融化后加热40秒, 其间保持一定频率的搅动, 使牛排始终能与黄油有充分的接触 (否则会焦..)
翻面加热20秒取出, 放入黑椒汁与肉汁搅动加热, 温度100度, 达到温度后立即取出浇上去防止水分流失

牛排情况: 切面两边靠边部分褐色, 中间为深桃红, 引用wiki百科(Steak)

Raw — Uncooked. Used in dishes like steak tartare, Carpaccio, gored gored, tiger meat and kitfo.
Seared, Blue rare or very rare — Cooked very quickly; the outside is seared, but the inside is usually cool and barely cooked. The steak will be red on the inside and barely warmed. Sometimes asked for as “blood rare” or “bloody as hell”. In the United States, this is also sometimes referred to as ‘Black and Blue’ or ‘Pittsburgh Rare’. It is common for chefs to place the steak in an oven to warm the inside of the steak. This method generally means ‘blue’ steaks take longer to cook than any other degrees.
Rare — (52 °C [125 °F] core temperature) The outside is gray-brown, and the middle of the steak is red and slightly warm.
Medium rare — (55 °C [130 °F] core temperature) The steak will have a fully red, warm center. This is the standard degree of cooking at most steakhouses, unless specified otherwise.
Medium — (60 °C [140 °F] core temperature) The middle of the steak is hot and red with pink surrounding the center. The outside is gray-brown.
Medium well done — (65 °C [150 °F] core temperature) The meat is light pink surrounding the center.
Well done — (71 °C [160 °F] and above core temperature) The meat is gray-brown throughout and slightly charred.
Overcook — (much more than 71 °C [160 °F] core temperature) The meat is dark throughout and slightly bitter.
无法准确判定, 可能是牛排太薄的原因. 不准确判定牛排薄处为3分熟(Medium rare),  厚处低于3分熟, 因为牛排太薄所以厚薄处差距较大.
厚处嚼不动又将剩下部分放进锅里加热, 40秒后翻面加热20秒, 判定为5分熟(Medium)左右. (手机没电了缺乏图片记录并且我也忘了可以留点样品下来抱歉.. 全吃了)

第二次实验

放入牛排加热20秒翻面加热20秒, 放黄油 (与第一次相同)
加热70秒翻面, 发现边上微焦并且翘起, 推测是中心比两边温度高引起的变形, 也有可能牛排不够厚没法稳住, 解决方法猜测 1. 用厚点的牛排试试 2. 用刀划一些网格阻断表面拉力的传播
看情况决定继续加热30秒(已翻面)

牛排情况: 大概七分熟(Medium Well down)或略低, 薄处接近全熟(Well down), 感觉还是”因为牛排太薄所以厚薄处差距较大”

结论

太薄了不行, 下次买3cm的试试, 我看youtube人家弄都有一块Filet简直就是长方体的.. 口感来说3分到7分都不错, 太熟完全不好吃..再往下嚼不动了

In the world

What in the world / on earth .. ? 平时说的世界和地球两个词语,指的都是地球,我们一般人所理解的世界,也只是地球而已。然而,你说宇宙,可是宇宙有多大呢,宇宙如果在膨胀,那这所谓的边界另一头是什么?那属于另一个世界的不知道什么东西与我们的世界是否具有可比性?我觉得不可能。所谓宇宙是无限的,我们对于无限这个词也一无所知,就像热锅上的蚂蚁对脚下电磁炉使用的交流电实际是电子的高频往返运动一无所知一样,我们以为宇宙是有4%的可见物质23%的暗物质和73%的暗能量组成,我们知道个屁,宇宙不可能具有一个完整的结构体系,时间都是它的玩物,你无法想象我们所在的世界之外有什么。我不是不可知论者,但我认为知识是无限的,宇宙是无限的规律就是无限的。任何认知系统都不可能具有其中“一部分”的信息,因为假设我们对于宇宙具有“一部分”的了解,那么因为宇宙是无穷的,我们的认知也是无穷的,而人类是不具有无穷的认知能力的,并且人类是宇宙的一部分,我们增加的认知也会增加我们需要认知的量,这是一个死循环。

坐在电脑前面的我们的想象力,与宇宙比起来是0,人类能够认知的,只是与宇宙相比大小等于0的一个世界。

那这个0是多大?要先知道无穷是多大。∞只是一个看上去我们能够理解的数值,但是我们知道∞和∞是不一样的。两个函数f1=x^2,f2=2^x,在x==+∞时,f2比f1大上∞倍(虽然数学中说它们不可比较),它们的区别就是∞与∞的区别,我们选出一个最大的∞,设为a,那a*a是多大?a^a是多大? 【【【我们不断的循环使a=a^a, 操作∞次】,然后再把这整个操作进行∞次】,然后再把前面的整个操作进行∞次】…循环进行∞次,然后这样的行为后得到一个a,这时候的a已经大于∞很多很多..很多,再把a替代上面括号里的∞操作a次,这整个行为再重复a次,所有的所有.. 连这样嵌套的次数都重复a次… 我没法表达出我的想法,但你或许已经明白我说的“无穷”是我们不能表达也无法理解的无穷,就连我现在这样对它的设想,都是可笑之极的。

再说平衡,我们知道微观世界粒子什么是无规则随机运动的,为什么?不知道,它们平衡吗?在我们看来挺平衡的,什么强相互作用力弱相互作用力让它们保持稳定,但是同时它们又是一团糟的,毫无平衡可言,到底为什么那样动啊?实际上它们又是接近光速运动的,这就更迷雾了,又要扯到时间啊什么的… 也许它们根本不平衡,一直在下落马上就坠毁,只是因为它们的一瞬间在我们看来已是永远,所以我们才觉得它们平衡了,稳定了。

也许我们也一样,生态圈的平衡什么都是人类的幻觉,生态圈早晚会进化出一个类似人类这样的物种然后凶残的剥削大自然最后导致一个星球的毁灭,我们现在觉得啊地球还是挺平衡的虽然生态被破坏的不轻但是以后会好的,我们这样自以为“平衡”的幻觉只是宇宙看来的一瞬间,时间间隔timeInterval=0过去之后地球就没了,银河系也消失了,而这一切对宇宙来说毫无影响,只是质量==0的一块不翼而飞了而已,甚至都完全没有区别。

[ACM] POJ 2594 求有向图(允许路径重叠的)最小路径覆盖, Floyd + 匈牙利算法

大飞同学问我这一题, 图论的东西我是一点都没看过, 直接看了discuss
做这题用了得有十个小时.. 我可是连二分图都不知道是什么..
然后什么是二分图匹配

最小覆盖数 == 节点数 – 最大匹配数

为什么呢, 数学归纳一下, 匹配数为0时显然 最小覆盖数 == 节点数, 然后有一个二分图匹配就能把两个覆盖路径合二为一, 很简单. 具体的在ufo008ahw这里有所说明
扩展阅读: Matrix67牛有一篇文章介绍了二分图最大匹配的König定理及其证明

求二分图最大匹配匈牙利算法或者最大流(这个我还没看- -).
有向图转化成二分图很简单, 把每个节点变成两个节点(在二分图两边)一个负责入一个负责出即可

至此我们已经可以解决有向图的最小路径覆盖问题. 允许路径重叠的情况怎么办呢, 明显是要转化成不允许路径重叠的情况来依葫芦画瓢, 想要在求二分图最大匹配的过程中考虑允许重叠的情况我想过.. 没想出来, 难度吹牛逼一样.

怎样转化: 用Floyd求一下传递闭包即可, 这个我想了好久才明白, 我来说明一下
比如有向图G: 1->2->3 4->2->5
解释是: 对于任何的有重复节点的路径, 比如这里的2, 求了传递闭包以后的图就会包含1->3和4->5这两个路径, 实现”跳过去”的走法

Floyd没什么好说的, 关于匈牙利算法(初次接触)的一些细节:

1. 下面这个代码的我是看的这里, 这个数据结构和递归太牛了..做完我整个人都犀利了. 它是只记y指向x不记x指向y, 每次对x搜索可用的y, 而不是记录它们, 整个操作都简单了好多. 原文的注释写的很好
2. 代码中的visited[] 这个验证我列举了各种情况, 是正确的, 有点难度
3. 算法的原理我很清楚了. 但是代码里x和y双重循环, 为什么x和y各循环一遍就ok了我还是没有理解太透彻, 这也是匈牙利算法的精髓吧

代码点下面:
Read More

恢复被覆盖的MBR实现多系统引导 (在linux之后安装windows)

Windows的安装会覆盖linux的MBR, 看了看关于Grub2(linux使用的引导系统)的文档后发现Grub2可以非常方便的生成启动菜单

首先我们要进到Linux, 弄个LiveCD或者U盘引导的Linux系统盘引导进Linux(不是硬盘上的Linux).
接着执行以下步骤来恢复原Linux的MBR+Grub2 (需要root权限)

1. fdisk -l 查看本硬盘上的分区, 根据大小和文件系统大概可以判断原来的根目录/在哪个分区. 设为/dev/sdXY

2. mount /dev/sdXY /mnt

3. grub-install –root-directory=/mnt/ /dev/sdX    这样就写入Grub2和MBR了 , (注意root前面是两条扛, 我这版式有问题)

更详细点这里

重启进原Linux, sudo update-grub, 如果有”Found Windows 7 (loader) on /dev/sdxx” 就ok了.

如果不行需要自己加入Windows的引导. 我update-grub后就直接找到了win7系统, 但是下面的方法我试过且成功了.

先记一下Grub2的文件结构:

/boot/grub/grub.cfg
取代Grub1的/boot/grub/menu.lst, 最大区别是grub.cfg不应该被修改(虽然你可以), 防止出错. 这个文件是由update-grub生成的

/etc/default/grub
配置文件, 原来menu.lst里改的 现在在这里改

/etc/grub.d/
update-grub所使用的脚本, 包括菜单的外观, 以及在各个分区上寻找各种系统自动加入update-grub的脚本等等.
目录下有文件00_header 05_debian_theme 10_hurd 10_linux 20_memtest86+ 30_os-prober 40_custom, 更详细的说明点这里

其中40_custom是我们需要的, 往文件末端加入

menuentry "Windows" {
set root=(hd0,3)
chainloader +1
}

其中hd0就是sda, 如果你是sdb那就是hd1以此类推, 3是sda3的3. 这个sda3要说明一下, 用fdisk -l列出分区表, 我们要找的不是windows的安装分区, 而是它上面一个100M的分区, 这是windows单独分出来用来引导的. 我的sda3是100M, 所以这里填(hd0,3). 如果没有100M的分区那就按windows分区算吧, 至少win7默认安装是100M这样.

保存后别忘update-grub, OK

[ACM] POJ 1727 解题报告, 二分+贪心

思路和yzhw牛一样

1. 每一个event它对应的可能的cause是这个event点下面的三角形区域(这个区域是无穷大的)
2. 问 “the latest time at which the earliest cause could have occurred” 就相当于用一条平行于x轴的直线 t=t0 把这些三角形区域拦腰切断(当然, 此线必须在所有event下面), 只准在腰以上的三角形里放cause. 然后用二分求到一个恰好不能再往上移了的直线, 就成了.
3. 可行性判断, 用贪心. 三角形们和直线相交的那个区间就可以代表这个三角形, 因为放在直线以上的cause都可以垂直投影到直线上, 效果更佳.
4. 在这些所有的区间中, 要找出最少的cause个数n, 使得每个区间内都能包含至少一个的cause. 如果这个n<=m, 那么这条直线ok, 否则不ok.
5. 怎么判断呢, 引用yzhw “以区间右端点为第一关键字,左端点为第二关键字进行排序,然后每次贪心的选择当前区间的右端点作为子区间,统计要导出全部区间需要子区间的个数num。” (其实第二关键字是不用排序的, 无所谓).
6. 对应5, 举个例子

---------(A)
   ------
  -------
     --------
        -------
    ------------
                 -----(B)
.....           ......

按照右边界升序排序, 123行显然要放一个点在他们区间里, 放哪呢, “不妨”(这个词表达能力太强了)放在最右边, 即点A处. 然后我们下面所有的左边界< =A的都可以ban掉了, 因为右边界是升序排序的. 这个操作后得到的问题是最优子结构的. 然后到了第7行, A不给力了, "不妨"取一个B. 这些操作整合一下就是维护一个变量rightEdge, 一旦rightEdge不给力就取一个当前区间最右边的点, 同时更新rightEdge至这个点. 之前的错误: 对应6的例子, 我以前是按左边界优先于右边界升序排序的, 那样虽然也对但是无法处理一个区间包含另一个区间的情况, 需要filter一下, filter的过程能写成O(n), 我比较愚钝写的n^2一个case要算2分钟 - -.. 总之这个贪心记住了, 求最小覆盖数 代码点下面: Read More

[ACM] POJ 1887 2533 解题报告, LIS的nlogn算法..

记录到当前位置combo数为k的尾巴的最小值, 比如 1 3 2 6, 则 dp[combo]=tail 罗列为 dp[1]=1, dp[2]=2 (1,2的尾巴比1,3等小), dp[3]=6, combo最大为6. 然后再多加一位就看能不能更新前面combo数对应的tail, 让tail更小; 当然还看combo数能不能+1. 比如1 3 2 6再加个5, dp[3]就=5 (1,2,5的tail比1,2,6的tail小), 不加5加7就多一个dp[4]=7. 因为dp[combo]值相对于combo数是递增的, 所以可以二分查找实现nlogn.

这两个是买一送一的题目.. 1887的二分写的有点蛋疼.. 2533要求不能相等, 就加了个标记每次对二分的两个指针p0,p1, 和中点(p0+p1)/2看一下, 重复就continue, 不重复一样做, 省得麻烦.. 想了一下还可以前面严格<, 后面可以>=, 这样更新tail的时候就不会重复产生影响.

代码点下面:
Read More

[ACM] POJ 2430 解题报告, 状态压缩DP, 奶牛你太懒了..

从左到右DP, 存储哪里有奶牛以后排序, 同一个x坐标的上下奶牛合并.. 0没有 1上 2下 3都有
随着奶牛的位置x从左到右DP, 需要记录的状态是dp[i][p][k], p是在x处的奶牛圈起来的方式, 我记的是 0没圈(这就初始状态可能) 1圈上 2圈下 3两个一起圈 4两个分开圈, 记录每个可能的k和对应的面积最小值
状态转移比较麻烦.. 我是又分两个状态之间的圈圈怎样互相结合来枚举,  0不结合 1上边延伸出去 2下边 3两边一起延伸 4两边分开延伸. 应该还有更巧妙的方法.. 不想再碰这题了
172ms 直接大数组20M内存..代码点下面
Read More

[ACM] POJ 1230 贪心, 数据结构

挺简单的算法我没想出来..

考虑最左边的需要移除墙的列。这列是必定要移除一些墙的。
不妨移除右边界较大的那些墙。
实现的时候,可以用基数排序的方式来找到右边界较大的墙。
开两个数组如下:
map[i][j] = { 第i列中,从该列开始向右延伸,长度为j的墙的数目}
cnt[i] = {第i列中墙的数目}
这样代码比较方便,速度也快。          ——荣誉属于糯米

糯米的这个数据结构非常棒, 我做了一点改进: 糯米记录了右边还有多长的墙, 实际上只要记录右边墙的边界就可以了, 省掉一些计算和思维复杂度
所以我的代码精简一点, 看我的吧 🙂

这种题一眼看上去像DP, 我看了点东西说DP和贪心有很多相似之处, 比如都是找最优子结构. 区别在于贪心从最优子结构里选出一个或几个就行. 具体有什么区别也没太搞清楚, 感觉DP有一个图的延伸, 每个状态都可能被多次使用, 而贪心不会.

代码点下面:
Read More

[ACM] POJ 1065 POJ 3636 解题报告, 数论, 贪心, 偏序集, Dilworth定理

这两道题用的理论都是一样的, 贪心算法很简单, 关键是怎么证明:

理论基础

首先需要了解的是..
序理论(中文) http://zh.wikipedia.org/zh-sg/%E5%BA%8F%E7%90%86%E8%AE%BA
偏序集(中文) http://zh.wikipedia.org/zh-sg/%E5%81%8F%E5%BA%8F%E5%85%B3%E7%B3%BB
Dilworth’s Theorem(wiki没中文) http://en.wikipedia.org/wiki/Dilworth’s_theorem

Dilworth的对偶定理的证明我看的lambda2fei牛这里写的, 英文太长实在是没法看..
Dilworth本身的证明我还没有看.. TODO. 但是lamb牛写的chain(链)和antichain(反链)的转换我一看就明了, 通过这种转换可以很容易的使用Dilworth定理, 同样也可以证明Dilworth定理, 我还没看原本怎么证明的..(稍后update) 这种方法已经很牛逼了感觉

为了文章完整性引用一下他的证明

Dilworth定理说的是:对于一个偏序集,其最少链划分数等于其最长反链的长度。
Dilworth定理的对偶定理说的是:对于一个偏序集,其最少反链划分数等于其最长链的长度。
Dilworth定理先不证,有空再不上来,其对偶定理证明如下:

设一个偏序集S的最少反链划分数是p,最长链长度是r。
1.先证p≥r。这是显然的,因为最长链长度是r,r个元素中的任意两个都可以比较,因此它们必定两两属于不同的反链,因此反链个数≥r,即p≥r。
2.再证r≥p。设X1=S。找出X1的所有极小元组成集合Z1,将其从X1删之,得到X2,再找出X2的所有极小元组成集合Z2(特别注意Z2中的任何元素a2,在X1中必然存在一个元素a1使得a1≤a2,否则a2可以放到X1中,这与X1的选取矛盾),再将Z2从X2中删除,得到X3,……这样一直下去,总存在一个k使得XK不空但X(K+1)为空。这样便得到一条链a1,a2,a3,……,ak,其中ai属于Xi。由于r是最长链长度,因此r≥k。另一方面,我们也得到了一个反链划分,即X1,X2,X3,……,XK。由于p是最少反链划分,因此k≥p。因此有r≥p。证毕。

1065详解

要求的就是集合的chain的划分最小数目.
对于题目中给出的关系P={l <= l’ and w <= w’}, 我们定义关系P’={l < l’ and w > w’} (并不是l<=l’), 那么对于原来关于 P 可比较的两个元素, 关于 P’ 则不能比较, 原来不能比较关于 P’ 就可比较. 相应的 P 的 chain/antichain 就成为 P’ 的 antichain/chain .
这样定义后, 就可以放下原题, 题目变成找一堆元素中的最少antichain数目, 根据Dilworth定理对偶定理的证明过程(如上), 每次剥离出 Xi 中的所有极小元, 直到 Xi 为空, 剥离的次数就是答案 .

剥离的次数 == k== 关于 P’ 的最长chain的长度(对偶定理) == 关于P的最长antichain的长度(chain转换) == 关于P的chain的最少划分数(Dilworth)

有点绕.. 但比看上去简单

实例:
考虑元素集 (1,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,5) (4,1) (5,2) (6,1) (6,7) (7,1)
每次取出关于 P’ 的极小元, 过程如下

(1,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,5) (4,1) (5,2) (6,1) (6,7) (7,1)
                  (3,1) (3,2) (3,3)       (4,1) (5,2) (6,1)       (7,1)
                                          (4,1) (5,2) (6,1)       (7,1)
                                                      (6,1)       (7,1)

因为P’是严格的偏序关系, 每次取出的最小元 x 就要满足找不到 y 使 y P’ x (如果是不严格的偏序就要考虑自反的情况)
怎样取极小元呢, P’ 的极小元是 “在 l 比它小的元素中, 找不到 w 比它大的元素”, 按照代码中的 comp() 排序以后(先l后w), 以这个条件找极小元的集合, 等价于从第一个元素开始找, 后一个元素的w’>=前一个元素的w, 的元素集合. 比如(1,2) (2,3) (2,4) (3,5) (6,7), 满足2<=3<=4<=5<=7, 这样贪心就很简单了

3636详解

和1065基本一样, 有了上面的理论就很好做了. 关键在于 P => P’ 的转换

P={w1<w2 && h1<h2} (大于小于无所谓)
所以 P的”可比较”关系 Pc = {w<w2 && h1<h2 || w1>w2 && h1>h2}
所以 P’c= {w1<w2 && w1>=h2 || w1>w2 && h1<=h2 || w1==w2}
所以 P’= {w1<=w2 && h1>=h2}

这里 P’ 是具有自反性和反对称性的非严格偏序关系.
这里就有一个问题: 集合内元素具有互异性, 但是题目中的元素有可能存在两两相同的, 怎么办?
我们可以想像我们上面讨论的集合是题目中的元素”只保留相同元素中的一个”后的集合, 这个集合中的元素a包含了n个题目中的相同元素, 就有两种处理的方法:

方法一: 把这n个元素看作一个a来”剥离”(取最小元), 1065就是这样, (1,2)(1,2)(1,2)在一起剥离是可以的, 因为1<=1,2<=2, 符合P的比较条件
方法二: 剥离a后a还存在于后来的Xi中, 并且n-=1, 直到n==0 a消失, 3636就要这么干, (1,2)(1,2)是不能放在一起的, 不符题意(P), 可以证明这样干是最优的(如果不取这个最小元, 这次执行后得到的Xi要比取的元素多一个, 不取白不取)

经过思考, 这道题最终要做的贪心是: 先按照w排序, w的互异值从小到大为w1,w2..wk, 然后在w==w1的元素里找到h最大的元素取出, 再在w2中找h最大的元素取出, 并且这些h需要满足条件:比前一个取出的元素的h大, 取完一次result++, 直到取空

代码点下面:
Read More

<算法导论>作者给我回信了..

我自以为发现了书上的一个bug.. 然后email过去.. 然后上帝给我回邮件说这是不对的…
第一封email后20分钟我就发现自己错了又mail过去说明了一下, 但显然上帝没看到..
在短暂的羞愧难当后感觉如沐春风, 体验了下大师风范阿, 严谨&&谦虚&&友善

Bug report <Introduce to Algorithms>
2 messages


Xiaodi Zhu <x@axlarts.com> Sun, Sep 26, 2010 at 4:51 AM

To: clrs-bugs@mit.edu

I’m using 2nd edition but I can’t check if this exist in 3rd(not in bug list of 3rd) so anyway..

page 631

inside Π(5), the first line

NIL 3 4 5 1

has “3” updated from “1” in Π(4), which should have been done in Π(3)


Thomas H. Cormen <thc@cs.dartmouth.edu> Sun, Sep 26, 2010 at 10:47 AM

To: Xiaodi Zhu <x@axlarts.com>
Cc: clrs-bugs@mit.edu

[Quoted text hidden]

Thank you for your bug report, but it is incorrect.  You claim that pi^{(3)}_{12} should be 3.  We have that d^{(2)}_{12} = 3, d^{(2)}_{13} = 8, and d^{(2)}_{32} = 4.  Therefore, d^{(2)}_{12} < d^{(2)}_{13} + d^{(2)}_{32}, and so pi^{(3)}_{12} should equal pi^{(2)}_{12}, which is 1.

I just coded this algorithm up myself, and I ran it on the inputs in Figure 25.4.  The output agrees entirely with the values in the figure.

Tom Cormen
Professor and Chair
Dartmouth College Department of Computer Science
http://www.cs.dartmouth.edu/~thc/


该邮件已被我打印两份, 贴墙上&&拿出去炫耀