ゆっくりでいいさ

nhd-seeding.user.js

這是一個用於NexusHD的Greasemonkey User Script，用於在torrents.php頁面標示出哪些種子是已在做種的。因為自己經常忘記NHD上的某個種子是否已經下載過，每次都要點開details.php頁面看看有沒有自己，所以想到了寫個腳本搞定這個問題。每次訪問userdetails.php頁面的時候，都會自動更新做種列表，然後在torrents.php里修改正在做種種子的背景色以示區別。使用這個腳本的時候請把uid改成自己的。

接上上次和上次的题解，补上这最后一部分。这次的三道题分别是我出的程序员六级阅读理解题Crack Me II；复数表达式解析计算题（误）Complex Calculator；和大自然数值积分题（大误）Bessel Function II。

ZOJ3441. Crack Me II

[cpp + indent, sorting, set_difference]

题目就是要求写一个和这段天书一样的代码(ZOJ3441txt.c)功能完全相同的程序。

这一题是程序员四级阅读理解题ZOJ1584 Crack Me的加强版。首先说说这段天书是怎么来的吧，其实最初是一段非常简单的Haskell程序(ZOJ3441hs.hs)。然后我简单的用C重写的了一遍所有函数，于是得到了下面的C语言程序(ZOJ3441c.c)，因为是按Haskell的思路来写的，所以几乎没有循环，全是递归。之后就是人肉宏替换了，其实写这段代码远比看懂它要辛苦啊。

如果你直接提交这段代码，会MLE，一看程序你就会发现，不断的malloc，完全不free。即使处理了内存泄漏，依然会TLE。有的时候可以通过只修改瓶颈代码来AC，比如ZOJ1584就可以这样做，不过这一题就行不通。

解决这道题的一种办法是通过够找各种sample，测出这段程序的功能。这是一个比较可取的办法，不过如果遗漏掉了任何一个地方都会WA，通常也会设置一些这样的陷阱，比如ZOJ1584在长度大于某个阈值的时候要数出”0″，这是很难测出来的。这段程序没有太xe的地方，不过对于负数的处理，也是要花点时间来找规律的。

另一种方法就是阅读代码了，这段代码的直接阅读难度要远远大于ZOJ1584。不过我们为什么要直接阅读呢？宏展开这种事编译器不就能做么，何必人肉？gcc -E命令就可以将宏展开，其实背后就是调用了GCC中一个叫cpp的程序，cpp是The C Preprocessor，只要

cpp ZOJ3441txt.c > ZOJ3441cpp.c

就得到了宏展开的代码，不过代码缺少良好的缩进，还是不可读，再利用代码格式化工具，比如indent，来处理一下

indent ZOJ3441cpp.c

这样代码(ZOJ3441cpp.c)的可读性就比较强了，唯一的麻烦就是变量名都没有意义，你可以在阅读的同时替换成有意义的名字。

接着上次4道比较简单的题的解题报告写。这次是Detect the Virus II和An Unusual Problem的解题报告，主要涉及如何在C, C++, Java, Perl, Python中使用正则表达式与及无损压缩算法。

ZOJ3440. Detect the Virus II

[regex, topSort]

题目简单来讲就是通过上下文无关语法(context-free grammar, CFG)描述了virus。问一个字符串是否存在virus形式的子串。题目保证描述不会有环/递归。

这题用正则表达式(Regular expressions, regex)来做是再自然不过了，比如sample就等价于下面这段perl代码：

# subparta:=fg|g
$subparta = qr(fg|g);
# parta:=a|b|c
$parta = qr{a|b|c};
# partb:=d|e[subparta]h
$partb = qr{d|e($subparta)h};
# virus:=[parta][partb][partb]
$virus = qr{($parta)($partb)($partb)};

printf 'abcdefghijklm' =~ $virus ? "YES\n" : "NO\n";
printf 'nopqrstuvwxyz' =~ $virus ? "YES\n" : "NO\n";

当然，因为代码是顺序执行的，所以我们调整了几个record的顺序。顺插一句，如果是函数式编程语言的话，那顺序就完全无关紧要了。于是问题就是给定的字符串能否匹配题目所描述的正则表达式，不过因为输入的顺序不确定，所以要麻烦一点，不过即然没有环，一个拓扑排序就搞定了(ZOJ3440watashi2.pl)。

ZOJ在建站105个月之后迎来了第一百场比赛。

办一场比赛来庆祝一下，这个想法最先是姐姐在邮件中提出的：

所谓求人不如求己，我自己的记录里是有序号的，所以知道我们目前有98场原创比赛和10场Practice了！喂，要不要庆祝一下第100场呀？？！^_^

而我们在ZOJ2.1提供了几个脚本语言的支持后，也一直想办一场“非主流”的比赛。所以便有了今天的 Let’s Celebrate the 100th Contest on ZOJ! — An Unusual Contest powered by ZOJ Staff 这场9道非同寻常的题组成的9小时9分9秒的比赛。题目的准备还是比较匆忙的，事实上除了hhanger的一道题以外，所有题都是最近几天出的。感谢参与出题和验题的navi, hhanger, quark, hsys和猛犸也钻地等童鞋，也感谢大家的捧场和支持。

下面是解题报告：

ACFUN上经常有一些考验暂停党的图集视频，内含各种哔哔和◯◯，但是对于反射弧比较长，暂停苦手的人们来说，只得反复折腾得肉牛满面。而我这种暂停四级考试完全不合格的人更是鸭梨很大。于是想到求助perl, imgseek和mplayer，把视频中的所有图片提取出来。思路很简单，就是首先用mplayer将视频内容转为一帧一帧的png或jpg图片(视频分帧)，再用Image::Seek来通过图片内容的相似度比较去除重复图片。写了一段简单的perl代码(wapauser.pl)：

#!/usr/bin/perl

use strict;
use constant SCORE => -30;
use File::Temp qw(tempfile tempdir);
use Image::Imlib2;
use Image::Seek qw(loaddb cleardb add_image query_id remove_id);
use POSIX ':sys_wait_h';

our ($id, $db, $dir);

sub init {
	$id = 0;
	$dir = tempdir('wapauserXXXX', CLEANUP => 1, DIR => '.');
	$db = tempfile('wapauserXXXX', DIE => $dir, SUFFIX => 'db');
	loaddb($db);
	cleardb();
}

sub gao {
	my $file = shift;
	my $img = Image::Imlib2->load($file);
	add_image($img, $id);
	my @result = query_id($id, 2);
	if (!$id || $result[1]->[1] > SCORE) {
		++$id;
		link $file, sprintf './output/%04d.png', $id;	# or `cp`
	} else {
		remove_id($id);	# important
	}
}

sub wapauser {
	my ($file, @args) = @_;
	init();
	if (my $pid = fork) {
		wait;
		opendir(my $dh, $dir);
		my @pngs = grep {/\.png/} readdir($dh);
		closedir($dh);
		for my $png (sort @pngs) {
			gao("$dir/$png");
		}
	} else {
		chomp(my $path = `which mplayer`);
		unshift @args, '-vo', "png:outdir=$dir", '-nosound';
		print STDERR "path = $path\nfile = $file\n", join("  ", @args), "\n";
		close STDOUT;
		close STDERR;
		exec $path, $file, @args;
	}
}

wapauser(@ARGV);

拿某个长度4min的flv视频测试了一下，第一步和第二部分别花了4min的时间，最后从6000多帧中提取了70多张不同的图片。实验表明，SCORE的阀值大概取到-25~-30比较合适，具体的值还是要反复尝试。大多数相同的图结果都在-35以上，但也有可能只有-31。不同的图通常区别都在-15以内，但是只有一些小区别的几张图（你们懂的）之间的区别可能有负的二十多。总的来说还有以下问题：

• 视频分帧结束后才开始图片去重，实际上两步可以同时进行，分步的结果就是得先消耗很大的临时空间来存储成千上万帧的图片，上面的测试就吃掉了4G的硬盘；
• 生成的图片是非常大png，这也是为什么会吃掉那么多磁盘的原因，当然这可以通过设置参数z=<0-9>改成压缩较高的png，或者用参数-vo jpeg，并设置参数quality=<0-100>改成较小的jpg；
• 这种方法只能处理完全静态的图集视频，对其它视频要么无能为力，要么作用很有限；
• 生成的图片质量取决的视频质量，所有除非是高清视频，否则图片质量不会太好；
• SCORE阀值的设置……凡是涉及到阀值的问题总是很头疼的，稍微高点低点，效果可能就差很多，这就像调试蓝田的热水一般（典故见附件）。

附件：我刚进浙大不久时的一篇文章《走进浙大—揭开蓝田浴室之谜》，想起来当时我们一看见校医院的救护车从蓝田方向开来就会说“又有人洗澡被烫伤了”……

发信人: botanyh (botany), 信区: Joke
标 题: 走进浙大—揭开蓝田浴室之谜ZZ
发信站: 缥缈水云间 (Mon Oct 30 11:33:02 2006), 站内