Nov 23
虽然说最后的结果没有比我预期的差,但是过程还是很囧的。鉴于这里是我自己的博客,废话就多写一点。

总之就是从10月的某个Hi消息开始的,jieyu突然告诉我,搞到了一个福州赛区的名额,和ldl同学一起,组个队伍,参加区域赛。缘由很简单,他想公费回家,顺便打个酱油。于是名叫烤馍馍(OpenKaomomo)的酱油队诞生。

真是很久没有做题了。做题的日子是很快乐的,至少可以把日子过得很简单的,其他七七八八的事情可以暂时放到一边,虽然有些不负责,但是突然觉得一切都变简单了;除了那些迫在眉睫的事情不得不分出时间来处理之外。

于是开始到机房和ldl一起做比赛,并且开始在WOJ上面刷题。大概做了四场比赛吧,WOJ的题目也刷七十多道(当然基本都是简单题),慢慢的找回了大二时的那种感觉(其实就是花大把的时间DEBUG那些BUGGY CODE)。不过之前不是搞得特别清楚的东西,在时间的积淀下,很多都豁然开朗,写起代码来也顺畅多了。

前往福州的旅程是比较曲折的。其实那一堆人里面我是最没有区域赛参赛经验了——因为这是我第一次(估计也是最后一次)参加Regional。所以在出发前两天(周三),我也还等着通知,在群里头问何时何地集合。然后发现原来大家也都在等。于是只好给董哥打电话,问。说是车票买的周五的,不是周四,要和实践办的叶主任一起去。于是给叶主任电话,约好,第二天到他办公室,谈清细节(到BBS上发集合帖),领了400块钱,下午拉上钟安原和FOUR两位同学一起到学院旁的自强去采购了320块钱的食品。真重。

周五下午3点机房集合了,把吃的东西分发,然后13个人(包括甜菜和CW)挤上一辆面包车开往武昌火车站,吃零食,看小说,看电影,睡觉(还是甜菜比较简单,从上车睡到下车),早上10点,抵达福州。真暖和。穿太多了。领着大家在公交车站等了半天308,到宾馆把房间开了,然后在天峰宾馆站等了半天91,然后在福大东门又等了好一会儿96,好不容易到福大,才跟志愿者MM碰上面。顺便说一句,志愿者MM也是福一中的,高中学妹啊。在福大食堂吃饭,jieyu和ldl随后赶到,一起吃饭去参加练习赛。进场的时候就已经迟了一点。

总算切入主题,练习赛。练习赛一共五题,ldl从后往前看,我从前往后看,jieyu看中间。A是简单的字符串处理,ldl速度上去敲,居然WA了。然后是我看的E题,素数筛法+因式分解,ldl上去敲,但是他筛法什么记不太清楚了,于是换我(正好前一阵写了好几题类似的),敲出来没有过样例,打印代码。帮ldl看A题,发现是题意没看清,100个word看成100个字符,AC。然后看自己的代码,发现有两个BUG,改了提交,AC。接着是B题,刚开始觉得最小生成树是错的,后来jieyu仔细考虑,发现如果用kruscal是可以保证正确性的。ldl敲。WA。WA。WA。看了一遍代码以后,发现是找边的循环退出条件位置不对,如果最小生成树只有1~2条边,就会出错,改之,AC。于是发现自己还是很适合搞DEBUG。这是好事还是坏事?考虑C题,SPlay有模板,不过题目的难点不在于SPlay,而在于树的输出,考虑了很久,最后放弃了。D题的图着色,写了暴力算法,不过没交。比赛结束,3题,排名78左右。练习赛的总结是,必须要给出一些极端测试数据,不能乱交。

结束后回去等车等得很痛苦,尤其是福大东门的91路……等了四五十分钟,最后还是让老妈和舅开车过来把大家接到南洋饭店吃了顿好的。晚上睡得不安稳,4点多被噩梦闹醒,然后噩梦不断,迷糊到早上7点出头,被闹钟吵醒。下楼吃了早餐(这个酒店的早餐不给力啊),然后坐车。志愿者说武大的队伍在10号车,上车坐了好一会儿说是错了,应该在14号车,结果走过去又说是13号车,上车后董哥电话问:你们上了3号车没……真是攒足了RP啊。

决赛奇葩地在9点30开始。10题,照例ldl从头,我从后,杰瑜中间。

最初是暴力的j题在100分钟AC的。首先是过不了样例,发现是忘了处理不合法的前导零。然后发现程序还有BUG,数组索引有错。然后提交,WA。jieyu检查发现是因为直接用除法,没有考虑整除。我则认为可能会溢出,改用long long进行乘法。于是AC。

第3个开的,F题是个AC自动机,就是数据量BT了一点。ldl敲完标程,过了样例,但是我出了个很弱的数据就跑错了。修改了以后提交,TLE。TLE。TLE。ldl一直比较紧张,到最后才45min的时候才静下心把问题找出来,AC。

第4个开的题目应该是B题吧。无向图最小割,被我读成了N个最大流,又是我的错-。- 总之就是TLE+TLE,在比赛最后7分钟的时候貌似还提交了一次,TLE,放弃。

H题,这题就是个大杯具,开的第2个题,AC的最后一个题。问题大概应该算在我头上吧,因为最初的时候没有把题意完全看清楚(固定的5分钟间隔),导致思考的时候出现各种偏差,提交了3次,都WA了。最后一小时我提出一个很繁琐的算法:记f[i][j]是表示在i分钟第一次选(0<=i<=4),到第i+5*j分钟可以得到的最大值,for (i = 0; i < 5; i++) f[i][j] = max{ f[i][k]+g(i+5*j) | 0<=k<j }, 其中j是选择的时间点,g(i+5*j)的值是0或1,由一个辅助的数组G[k][1..N]来导出,G[k][t]表示第t个课程在前i+5*k分钟是否被选中(且每次确定G[j][1..N]需要由G[k][1..N]更新)。此算法虽然繁琐且效率低,但是因为每一次往前都能保证最优,可以保证正确性。jieyu大致是从这里得到一点启发,想出正确的贪心算法,终于在269min,也就是最后半小时的时候AC了这题。

我们还在最后半小时的时候开了G题,在DAG上的一个简单DP,编码完全没有难度,感觉比J题还简单。这题是我去写的,思路很清晰,就是最后了比较紧张,出了两个BUG,没能在结束之前通过样例,怨念。关于这题的另一个怨念在于,开场我就看过了这题,之所以没有之前就考虑它,是因为它那OOXX的输入格式很让人纠结,跟jieyu提了一下,他说这题很有意思。然后就撂着了。杯具啊。

除了以上的题目,我们还考虑过E题(四边形费马点)、D题(XOR那题)。E题之所以没有去写,是因为杰瑜读错了题目,他问我Quadrangle这个词什么意思,我说不知道,不过Angle是角,Quadr含有4的意思,于是他认为是四面体。于是这题就废了。(字典啊字典……还是应该带上字典的,ldl同学。。)

比赛完基本上可以确定是打铁了。稍微有点失落,毕竟是第一次也是最后一次参加区域赛吧,没能拿牌还是挺遗憾的。尤其是在发挥正常的情况下至少还有2道题是确定可以出的,并且之前的题目过程太纠结。总之就是不甘+怨念。

比赛完去采购,买了很多东西。其实额外买了一瓶蜂蜜是想送给志愿者mm慰劳一下,不过出来以后才想起除了志愿者mm,还有一个志愿者gg,所以就一直没好意思拿出来~.~ 然后大家在草地上等吃饭,jieyu则干脆先跑去玩了。

大约4点50的时候,该mm说,我们有两只队伍获奖了,应该是Valor和烤馍馍,需要提前去颁奖会场做准备。过山车啊这是。。。后来在饭桌上跟大家提起,说是不对,Forward在封榜前就3题了,不应该在烤馍馍后面的。于是打电话给该mm询问,说是只确定是两支,不确定是哪两只。过山车啊这是。。。看来是确定铁牌了。5点45的时候再跟着志愿者走到颁奖会场,登记的时候神奇地发现,武大有三支队伍获奖,烤馍馍耗尽RP,排在了名单倒数第二的位置。过山车啊这是。。。

幸好过山车到站,最后顺利领到牌子……最终成绩是Valor,5题,铜牌第一;Forward,3题,铜牌30左右;烤馍馍,3题,铜牌倒二。

这里顺便提一下颁奖晚会的俩奇葩舞蹈,一个是劲舞(名字不太记得),前面两排mm,大都很漂亮,后面一排gg,大都很帅,不过最中间的那个mm明显不给力,腰围的绝对值比较大,其中一个做俯卧撑的动作,很吃力。另外一个舞蹈叫《女人花》,大多数mm都很不错,但是最核心的那个……腰围更粗,明显赘肉在颤,摆出各种S型,还叼花……我只能联想起当年那个“芙蓉姐姐 叼花”的照片,你去百度图片搜一下,第一张那个……

终于领了证书,坐上回程的车,回到宾馆,至此,福州比赛结束。最终的结果差强人意。虽然早先jieyu说应该拿个silver,但是根据现场的情况来看,正常发挥应该也就是5题,还是bronze,所以就不需要太怨念了。

----分割线----

最后是Felix021@烤馍馍的比赛总结:

· 看清题意。还是太忽视了一点。如果决定开始做一道题目,应该要有两个人看清题意,并且在细节上达成一致,这样才能保证不会出现各种糊涂问题,比如此次的E、H题。

· 每个人都应该把每题都大概看过,至少稍微思考一下,不至于漏掉G那样的简单题。

· 这次比赛对Board的关注太少了,以至于G这样的题目到最后半小时才开始考虑,实在是太过分了。

· 如果某人开了一题,条件允许的情况下,应该有人帮忙出测试数据。这次正式比赛的时候我们这个约定没被贯彻好。

· 大家都太紧张了,应该早点喝红牛的。
Nov 17
数码相机拍下来的照片普遍偏大,在很多情况下,需要保存的照片并不需要很高的分辨率和压缩质量,所以会用一些程序,比如ACDSee、QQ影像、ImageMagick之类的程序来批处理照片,将它们的尺寸缩小,并适当降低压缩比,使得照片的存储、传输更方便。

这样一来会遇到的问题是,EXIF信息的丢失。上述的这些工具在处理照片的时候都有意无意地忽略了EXIF,让人很郁闷(令人感到惊奇的是,粗糙的windows画图板在缩放、保存图片的时候EXIF信息是不会丢失的)。

最近处理WHUMSTC10周年party照片的时候就遇到这个问题。照片总共有605张,使用Canon 450D最高分辨率拍摄,一共2.4G+,一张照片平均有4MB。通过QQ影像压缩到原来的1/4,并且压缩质量调整为85%,所有照片的体积立即缩小为176M左右。但是EXIF信息的丢失,使得很有含金量的“照片拍摄时间”也随之丢失。

于是试着去解决。本来想用PHP自带的EXIF库(最熟PHP,没办法-.-),但是发现它只支持Read,不支持Write。又找了找PYTHON的,挺多,但是用起来总不对头,就没继续折腾。最后还是在Ubuntu下apt-cache search exif,发现了exiv2这个实用工具,非常赞。

对一张照片处理,执行:
引用
$ exiv2 ex xxx.jpg
(ex=extract)会将照片的exif信息保存到同文件夹下的xxx.exv文件中;
引用
exiv2 in xxx.jpg
(in=insert)则会将同文件夹下的xxx.exv信息插入到xxx.jpg中。

需要批量处理的话,完整过程是这样:

1. 使用QQ影像或者使用命令行的ImageMagick将src/*.jpg压缩转换,保存到dest/*.jpg。注意相同文件的文件名保持不变。

2. 在src下面执行
引用
~/src$ exiv2 ex *.jpg
将所有文件的exif信息导出

3. 将所有exv文件拷贝到dest文件夹
引用
~/src$ mv *.exv ~/dest

4. 恢复exif信息
引用
~/dest$ exiv2 in *.jpg


如果是windows,可以從這裡下載exiv2的可執行文件:http://www.exiv2.org/download.html ;如果有Ubuntu的話,直接apt-get install exiv2就好,當然也可以自己編譯安裝,只要身體裡兩個圓形的器官不會隱隱作痛就行。。

終り.
Nov 8

RMQ再学习笔记 不指定

felix021 @ 2010-11-8 23:54 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(12980) | Via 本站原创
2年多以前看的算法,当时基本看懂了(实际上还是有问题的),今天再翻出来,感觉基本忘了,重新实现一遍,试着自己把推导过程也写写。非常赞的算法。

RMQ: Range Minimum Query, 区间最小值查询。已知数组在区间 [0, n) 有定义,给出 i, j (0 <= i < j <=n),求 [i, j) 之间的最小值。

朴素算法非常简单,但是显然,每次查询是O(N)的,效率很低:
min = +INFINITE
FOR k = i TO j - 1
  IF min > arr[k]
    min = arr[k]
  END IF
END FOR
RETURN min

由于经常遇到需要多次查询的情况,所以朴素算法不合意。一个比较好的改进是使用线段树/树状数组,首先通过O(NlogN)预处理,让每个分支节点保存了其所有叶子节点的最小值(由底向上递推)。这样每次查询的时候,就可以在O(logN)的时间内得到结果。具体代码稍繁琐,这里不写了。

最好的方法,是用叫做sparse_table的算法,其思路和线段树很像,区别是通过O(NlogN)的预处理,可以让查询的时间复杂度降低到O(1)。其具体思路为:

预处理:
1. 记F[s][p] = min{ arr[i] | s <= i < s + 2^p} = min(arr[s..(s + 2^p - 1)])。例如, F[1][2] = min{ arr[i] | 1<= i < 5} = min(arr[1..4])。
2. 由1,易推知,F[s][0] = min { arr[i] | s <= i < s + 1} = arr[s].
3. 通过由底向上递推的预处理得到所有满足(s + 2^p <= n, 即区间[s, s + 2^p) 包含于[0..n)区间内)的F[s][p] = min(F[s][p-1], F[s+2^(p-1)][p-1])。例如, F[2][3] = min(arr[2..9]) = min(min(arr[2..5]), min(arr[6..9])) = min(F[2][2], F[6][2]) = min(F[2][3-1], F[2 + 2^(3-1)][3-1])。

查询[i, j):
1. 令 k = log2(j - i)取整,则 (j - 2^k) <= (i + 2^k),即区间 [i, i + 2^k) 和 [j - 2^k, j) 必定覆盖 [i, j)。例如,区间[3, 8),k = log2(8-3)取整 = 2,则 [3, 7), [4, 8) 覆盖 [3, 8)。
2. RMQ[i, j) = min(F[i][k], F[j - 2^k][k]).

----扩展---
LCA(树中任意两个节点的最近公共祖先)问题,是可以通过RMQ+DFS来完成的,详见LCA问题。ZOJ 1141是一道纯LCA问题。

具体实现和检验代码如下(做了一点改进,F[s][p]中存放的是[s, s + 2^p)中最小值在数组中的索引):
Nov 2
C标准中的qsort函数,可以对任意类型的数组进行快速排序,用起来也还算方便,不过行为有一点诡异。加上之前曾经看过一篇文章(沈大写的,曾经登上过ecom的双周刊,居然在这个youalab.com也等出来了-。-),说是qsort不是线程安全的,所以把glibc的代码翻出来,看看qsort的具体实现。

用Ubuntu的话,找代码就很容易了:
引用
$ apt-get source libc6
$ cd eglibc-xxxx
$ grep -r . -Hne qsort | grep void

可以看到qsort是在stdlib.h里面的,源码在msort.c 302行,调用了qsort_r函数:
void
qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
  return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);                                                     
}
其中__compar_fn_t就是 int (*)(const void *, const void *)类型的函数指针,__compar_d_fn_t则是 int (*)(const void *, const void *, void *)类型的函数指针(为什么还有个void *呢?很神奇~求解)。

qsort_r函数也在msort.c中,约164行起。为了榨干CPU的性能,写了很多代码来优化效率,其流程大致是:

1. 判断额外所需内存大小,如果很小(<1024B),在栈上分配;否则获取系统内存参数——如果比可用内存小,试图在堆上分配;如果所需内存超过物理内存(为防出现不得不使用交换分区的情况致使性能恶化,故不分配),或者分配失败(可用空间不足),使用性能较差的stdlib/qsort.c中的_quicksort函数来排序。
    1.1. _quicksort位于 stdlib/qsort.c,对快排进行了两个改进:1. 将递归转化为递推; 2. 使用插入排序来处理4个元素以内的区间。不过用于交换两个元素的宏SWAP(a, b, size)没有额外的优化,比较意外(本来以为会考虑一次多个字节拷贝,或者使用duff device来减少循环)。

2. 分配成功的情况下,使用额外分配的空间,调用 msort_with_tmp() 函数来进行排序。
    2.1. 如果单个元素的大小超过32个字节,那么使用间接排序,分配空间时就有额外的判断,如果需要间接排序,则额外分配2n个指针的空间,前n个空间用于存放原指针,后n个空间用于按照所指元素大小存放排序好的指针。最后再按照排序好的指针顺序将元素拷贝。(注释中提到了Knuth vol. 3 (2nd ed.) exercise 5.2-10.,应该是指这个算法出自Knuth的《The Art of Computer Programming》卷3吧)
    2.2. 否则使用直接排序。这里也进行了一些优化,主要是为msort_with_tmp()提供p.var参数,完成针对元素的大小进行拷贝的优化:默认是使用gcc内置的__builtin_mempcpy来拷贝。
    2.3. msort_with_tmp对典型的快排也进行了非常赞的优化。
    2.3.1. 从msort_with_tmp的函数名和代码可以看出,这个算法不是就地排序,而是使用了第一步分配的O(N)的额外空间,这样可以让排序时的拷贝效率更高(这个优化应该对CPU的cache命中率也有较大的提高)。
    2.3.2. qsort_r传进来的参数p有个属性var
    (1) 默认情况下p.var = 4,使用mempcpy来进行拷贝。
    (2) 如果单个元素大于32bytes,p.var = 3, 表示是间接排序,拷贝的是指针,不是元素
    (3) 如果数组是按uint32_t对其的,且元素的大小是uint32_t的倍数,则可以进一步优化到每次按照uint32_t/uint64_t/unsigned long来进行拷贝,一次拷贝4或者8个字节,此时p.var = 0,1,2表示按照uint32_t, uint64_t, unsigned long拷贝。

直接在里头做了些注释,有兴趣的话可以更仔细地看看。可以的话自己去下了glibc的源码阅读,更有意思:D
Nov 2
上一篇谈到:“典型的情况是某些非法内存访问,Glibc会open("/dev/tty",...),write()一些错误信息,然后open("/proc/self/maps", ...)把进程的内存映射表输出。还有一个更常见的情况,那就是用qsort。GCC的qsort实现,会主动open(/proc/meminfo),获取一些信息,通过这些信息来最优化排序时的内存管理。” 通过执行
strace ./a.out 2>&1 | grep open
可以看到进程执行的open系统调用。

对于这类情况,ptrace监控进程open系统调用,并获取文件名,检查文件名是否合法,如果合法,予以放行,这样就可以避免上述RE被误判为RF的情况了。

说起来很简单,但是具体做起来就有点麻烦。不过可以从我写woj-land的时候参考的ptrace教程《Playing with ptrace, 玩转ptrace》入手。这篇非常不错,强烈推荐有兴趣的同学学习学习:

Playing with ptrace, Part I — 玩转ptrace(一) http://www.kgdb.info/gdb/playing_with_ptrace_part_i/
Playing with ptrace, Part II — 玩转ptrace(二) http://www.kgdb.info/gdb/playing_with_ptrace_part_ii/

上篇以write系统调用为例,介绍了write系统调用的等价汇编码(当然是早期的了,现在的pc上linux貌似不用0x80了)、截获write系统调用,获取write系统调用的参数和返回值、甚至反转write系统调用的输出。具体的看原文了。

在这里,我需要peek的是read系统调用的参数。以x86为例,一个最简单的read系统调用:
read("/proc/meminfo", O_RDONLY)
,大致等同于
movl $5, %eax  ;open的系统调用编号
movl $filename, %ebx ;文件名地址(这里不一定对)
movl $0, %ecx ;open的flags: O_RDONLY
int $0x80
也就是说,可以通过获取x86 CPU寄存器的值来取得系统调用的参数,具体代码如下:
user_regs_struct regs;
ptrace(PTRACE_GETREGS, child, NULL, &regs);
syscall_id = regs.orig_eax; //因为eax也是用来填写函数返回值的,所以该struct额外增加了一个orig_eax
params[0]  = regs.ebx;
params[1]  = regs.ecx;
union u{ unsigned long val; char chars[sizeof(long)]; }data;
data.val = ptrace(PTRACE_PEEKDATA, child, params[0],  NULL);

注意:虽然ebx中存放的是地址,但是不是用户程序可以直接读取的,需要通过ptrace的PTRACE_PEEKDATA命令来获取。该命令一次可以获取sizeof(long)个字节的内容,如果要获取字符串的所有内容,就得通过循环来完成。

此外,为了保证代码能够在x86_64架构下通过编译,需要把上述代码做个小修改:
#if __WORDSIZE == 32
syscall_id = regs.orig_eax;
params[0]  = regs.ebx;
params[1]  = regs.ecx;
#else
syscall_id = regs.orig_rax;
params[0] = regs.rdi;
params[1] = regs.rsi;
#endif


通过这种方式,能够识别出open系统调用打开的文件,在保证系统安全的情况下,改善了Judge的识别能力。

更具体的代码可以参见:
http://code.google.com/p/woj-land/source/browse/trunk/code/judge/judge.h?spec=svn150&r=150#671
Nov 1
因为这两个东西占了地方,每次选盘符时总需要往下拉滚动条,很不爽。在网上搜到3篇文章,这里转载记录一下。

http://bbs.pcbeta.com/viewthread.php?tid=729301
http://bbs.pcbeta.com/viewthread.php?tid=729310
http://bbs.pcbeta.com/viewthread.php?tid=733262

“库” @  [HKEY_CLASSES_ROOT\CLSID\{031E4825-7B94-4dc3-B131-E946B44C8DD5}]
“家庭组” @  [HKEY_CLASSES_ROOT\CLSID\{B4FB3F98-C1EA-428d-A78A-D1F5659CBA93}]

修改注册表这里,需要右键->权限,给Administrators “完全控制” 的权限。

如果需要去掉这两项的显示,分别把键值 ShellFolder\Attributes 由原来的 b080010d 改为 b090010d,然后注销(其实Kill掉explorer也行)就行了。如果不想去掉显示,那么修改 SortOrderIndex 键值(默认是0x42、0x43),改到0x52或者更大,就会排到“计算机”后面了。

点击在新窗口中浏览此图片
分页: 1/1 第一页 1 最后页 [ 显示模式: 摘要 | 列表 ]