《大圣归来》——儿童动画不是借口

前些日子好不容易从『悠然见南山』的世外桃源搬回了『钢铁森林』的现代文明社会,周末无聊之余和同学一起去电影院看了这个在网上被誉为『中国动画的希望』的作品。

影片放映结束之后,想起之前网络上的种种盛赞,心里很不是滋味。

《大圣归来》讲述了一个很简单的故事。父母被山妖杀害的孤儿江流儿,机缘巧合从山妖手里救下了女童,山妖夺回女童时和江流儿误入关押孙悟空的山洞,唤醒了五行山下压了500年的齐天大圣孙悟空,孙悟空被江流儿烦的受不了只好答应将其和女童护送回长安城;之后半路因为如来的封印还未解开,女童被妖怪夺回;最后孙悟空变身超级赛亚人,成功找到真物,再把女童夺回的故事。

从电影的节奏安排上来看,起承转合中规中矩,开端、发展、高潮、结局的结构也是十分典型。

然而当看完电影,回过头咂摸一下的时候,会发现这个电影的内容实在是有问题。

首先这部电影无论是全名《西游记之大圣归来》还是常用的名字简称《大圣归来》都直接或间接的表明了这是一部以《西游记》作为故事背景的电影。可剧情的内容和《西游记》并没有任何的契合点,如果说《大圣归来》中孙大圣『不服一审』,再次跑到天庭大闹一通;或是按照《西游记》中的剧情,按部就班的取经,最后归顺为『斗战胜佛』。这些都可以和《西游记》的剧情、世界观紧紧扣合在一起。

而本作中的剧情却与《西游记》的大背景没有什么关系。如果把孙大圣等人的面具摘掉,其实这个故事和《飓风营救》倒是很是契合。人质丢了去救,救回来因为种种原因在眼前又丢了,最后主角一波『爆种』成功救回人质,主线剧情完成,皆大欢喜。《西游记》中庞大的奇幻世界观,深刻的故事安排,本作中都没有吸取精华。相反只是生搬硬套的将孙大圣的面具套到了特工Bryan的头上,再生搬硬造一个江流儿出来,套到Bryan的女儿头上,再把国外人贩子黑恶势力化妆成会万象天引的山寨无脸男,就变成了《大圣归来》。照着这个套路,还可以制作出《西游记之勇救桃子公主》、《西游记之大战德古拉》等作品。说句玩笑话,《大圣归来》目前抓人贩子找孩子这个剧情,还不如交给刑警803来演。

孙悟空被压在五行山下的这500年中,他都思考了些什么;为什么500年前还是条桀骜不驯的『套马汉子』,如来都无法感化,500年后却被一个小屁孩轻松的萌成了『绿坝护航小能手』之类的问题还存在着很多,但《大圣归来》中都没有给予解释。故事和世界观的不兼容,让人感觉很是突兀。

除了和《西游记》关系不大这个问题以外,剧情上还有许多硬伤。包括大反派为什么这么执着于这个女童、孙大圣为什么不早爆种等许多问题。这些剧情上逻辑讲不通的地方将其限制在了只能糊弄小孩儿的儿童片的境界。

可同作为糊弄小孩儿的儿童片的《哆啦A梦 伴我同行》却能让大人和小孩都能看得开心。也许是《哆啦A梦》打得童年情怀牌?《西游记》就不是千万人的童年了么?儿童片并不能作为剧情不好看的理由,《大圣归来》想要感动成年观众,也许需要做的只是让孙大圣再闹一次天宫,让观众们再找到儿时的热血与回忆。

说完剧情,再看看角色。

首先角色的造型就有很大问题。除了《西游记》中出现了的孙大圣、猪八戒、白龙等人物(前略,天国的沙僧),原创角色中的几个的造型或多或少的都有些眼熟。以下几幅图是我觉得多少有些类似的角色外形。借鉴不借鉴的这个问题很难说清,只是在这里提一下。

首先是大反派混沌(不去查看完都不知道叫啥)的造型和动画角色无脸男カオナシ的造型很像。也有人在豆瓣上提到了混沌的阶段1的造型借鉴了京剧中的白脸脸谱,也算说得过去。

有人说大反派混沌阶段2的造型和怪物猎人中的电龙很像,不过豆瓣上有人说混沌这个名字的由来是山海经中叫做帝江的凶兽,google了一下帝江的样子,和大反派阶段2的样子相似度也很高。

Dune_Beast

《暗黑2》中的Baboon Demon和山妖的近似度还是很高的。银背大猩猩式的躯干四肢,背上的针刺等都十分相似。

然后是反派山妖的造型。看得时候我就觉得和《暗黑破坏神2》中的一个怪物长得有些像。查了下wiki果然很像。

而反派山妖喽喽变身后的造型就更眼熟了。看过《葫芦娃》的童鞋们肯定都认识这条蛇精。而男山妖(或者是公山妖?)的面部骨骼也是明显冲着蝎子精去的。

山神那个山岭巨人一样的外表再加上小小的vt二连一样的技能。不忍直视...

抛开造型的设计,角色的表情也明显有着明显的学习迪士尼的痕迹。倒不是说学习迪士尼不行,我还是希望看到中国动画能有自己的风骨。就像60年代的《大闹天宫》一样有自己的特色。

角色的取舍上也有问题。为什么有猪八戒有白龙就是没有沙僧?如果说八戒还有大圣和江流儿吵架时打圆场的功能,白龙完全没有任何推动剧情进展的功能为什么要留着他?江流儿的孤儿背景对于故事进展有没有用,没有用为什么要设置老爷爷这个角色?鼹鼠模样的土地除了卖萌还有啥用?

这么想下来的话,许多角色就都可有可无了。

再说一下观众们都口碑不错的动作戏。

客观来说,我认为《大圣归来》的动作戏还是可圈可点的,作为一个动画片,能将动作设计的比较有张力且连贯已经不容易了。然而令我有些不舒服的是,即使是动作戏还是有许多地方有借鉴的痕迹,比如中间有一段动作很像火影忍者中的莲华等等。可能也是我太敏感了吧。

另外,由于本片绝大部分是喜剧,所以动作戏也都是映衬着喜剧这一风格。虽然是动画片,成龙式武打片的感觉还是很强烈。动画片中虽然能把成龙电影中无法表现出来的效果,以动画作为载体夸张的表现出来,以获得更好的喜剧效果。可作为一个看多了成龙电影的中国观众,我认为这种套路已经很难逗笑观众了。

最后是画面质量的问题。

与迪士尼的一票动画对比,我认为本片的画面至少是不输太多的。虽然本片中部多次出现的水面看起来很奇怪,像是2000年左右的效果;还有本面前半部森林中的地面的贴图看起来有些粗糙等小小不严的问题以外。别的在我看电影的过程中没什么出现崩出事故的地方。

然而我认为电影虽然是通过画面讲述故事,其重点还是要落在故事上。很多人在网上挺《大圣归来》的画面与迪士尼不相上下,骂《大圣归来》是烂片就是不客观云云。这也恰好印证了我之前说的《大圣归来》是个儿童片这个事实,故事的空洞无力的前提下,制作者也只能通过相对不错的画面来得分了。不过不知道那些挺《大圣归来》画面好所以一切都好的观众,他们是不是也是《小时代》的粉丝。

总的来说,《大圣归来》算的上是一部中规中矩,但没什么亮点的合格作品。作为不是很常见的中国动画长片,由于其还处于起步阶段,到处学习也倒是可以理解,虽然观众在观看过程中可能会多处感觉眼熟。

乐观点看的话,这是一个好兆头,古时有燕昭王千金买马骨,如今投资者们看到这样的片在一番粉墨之后都可以如此捞得盆满钵满,想必会有更多的投资者向动画片中投资,动画片行业的从业者们也能挣得更多些,行业才能健康发展。而以后才能看到更多的真正的优秀的动画片作品。

而悲观点看的话,中国观众的素质也就这样了,随便一些疯子骗傻子式的炒作就能将这样的一个片炒到豆瓣8.5分的水平,也许这也恰恰验证了胖头同学几年前“看蜂蜜四叶草的人心都软,所以给分都高”的断言吧。

mkr

不知何年何月,50年前的那个中国的孙大圣才能真正的归来。

ipv6环境下openvpn的搭建

小学期如期结束,即将搬家到市里的校区,学校的网管也早早下班,ipv4的网络不再计费。趁着这几天赋闲在宿舍,搭了个用ipv6连接的openvpn。

在这里不得不赞叹下DigitalOcean的文档做的真是好,从头到尾什么都写了。虽然是ipv4环境下的,不过仍然非常有借鉴价值。搭建过程中google了下,有一篇很流行的中文指南是在CentOS下的,Ubuntu的好像不是很多。所以在这里把DigitalOcean上的那片指南翻译过来。

VPN是个什么干什么用的就不细说了。在这里只翻译下主要的步骤。

原文链接:How To Set Up an OpenVPN Server on Ubuntu 14.04

本文基本翻译自原文,另有部分修改以方便阅读。

前提

本文中使用的系统是Ubuntu 14.04,操作过程中全程使用了root账号。当然在openvpn配置完毕之后,使用一个拥有sudo权限的普通账户进行管理是一个不错的点子。


1. 安装并设置OpenVPN的服务器环境

以下步骤将完成服务器端的设置。

1.1 OpenVPN和EasyRSA的安装

首先更新Ubuntu的Repository列表,并安装OpenVPN和EasyRSA。

#apt-get update
#apt-get install openvpn easy-rsa

1.2 创建OpenVPN的配置文件server.conf

DigitalOcean的Droplet初始化之后在/usr/share/doc/openvpn/example/这个路径下有示例配置,所以将服务器端的示例配置文件拷贝到openvpn的安装路径下。

#gunzip -c /usr/share/doc/openvpn/examples/sample-config-files/server.conf.gz > /etc/openvpn/server.conf

1.3 编辑server.conf,配置OpenVPN

然后编辑解压出来的server.conf文件,可以使用自己喜欢的编辑器,DigitalOcean的指南里推荐了vim。不过nano比较简单,我还是选择了nano。

#nano /etc/openvpn/server.conf

server.conf中有几处需要改的地方,推荐用CTRL+W搜索能够比较快的找到。

如果需要修改OpenVPN的端口号的话可以修改port之后的数字。默认的端口号是1194.

# Which TCP/UDP port should OpenVPN listen on?
# If you want to run multiple OpenVPN instances
# on the same machine, use a different port
# number for each one.  You will need to
# open up this port on your firewall.
port 1194

如果使用的是ipv6进行连接的话(比如教育网),需要将下面所示的udp修改为udp6。如果使用ipv4进行连接的话,则不用修改此处。

# TCP or UDP server?
;proto tcp
proto udp

ipv6链接的配置修改之后如下所示。

# TCP or UDP server?
;proto tcp
proto udp6

之后再找到如下所示的地方。

# Diffie hellman parameters.
# Generate your own with:
#   openssl dhparam -out dh1024.pem 1024
# Substitute 2048 for 1024 if you are using
# 2048 bit keys.
dh dh1024.pem

将上文中的dh1024.pem修改为dh2048.pem,此处修改的为RSA的密钥长度,自然是长度越长加密程度越高。修改之后的如下所示。(井号之后的内容都是注释,就不再写第二遍了。)

dh dh2048.pem

之后仍旧在server.conf中找到以下这处。

# If enabled, this directive will configure
# all clients to redirect their default
# network gateway through the VPN, causing
# all IP traffic such as web browsing and
# and DNS lookups to go through the VPN
# (The OpenVPN server machine may need to NAT
# or bridge the TUN/TAP interface to the internet
# in order for this to work properly).
;push "redirect-gateway def1 bypass-dhcp"

去掉push前的分号,修改之后如下所示。之后OpenVPN的服务端才会使所有的网络流量通过VPN(如同注释所说的一样)。

push "redirect-gateway def1 bypass-dhcp"

之后仍旧在server.conf中找到以下这处。

# Certain Windows-specific network settings
# can be pushed to clients, such as DNS
# or WINS server addresses.  CAVEAT:
# http://openvpn.net/faq.html#dhcpcaveats
# The addresses below refer to the public
# DNS servers provided by opendns.com.
;push "dhcp-option DNS 208.67.222.222"
;push "dhcp-option DNS 208.67.220.220"

去掉两个push之前的两个分号,修改为以下所示。

push "dhcp-option DNS 208.67.222.222"
push "dhcp-option DNS 208.67.220.220"

修改之后OpenVPN才会通过设置的DNS进行解析。此处使用的208.67.222.222和208.67.220.220为opendns的地址,也可以使用google的8.8.8.8之类的地址。

之后修改server.conf,找到下方所示的地方。

# You can uncomment this out on
# non-Windows systems.
;user nobody
;group nogroup

去掉usergroup之前的分号,最后结果如下。

user nobody
group nogroup

此处如果不修改的话OpenVPN会以root用户的权限运行。出于安全的考虑,会将其权限限制在用户nobody和用户组nogroup的等级上,而其没有特权,所以能保证安全。

之后找到如下所示的地方。

# Select a cryptographic cipher.
# This config item must be copied to
# the client config file as well.
;cipher BF-CBC        # Blowfish (default)
;cipher AES-128-CBC   # AES
;cipher DES-EDE3-CBC  # Triple-DES

去掉第二个cipher之前的分号,选择使用AES进行加密,修改之后我们之后还会在客户端的配置文件中修改加密方式使其对应。如果不需要加密的话此处也可以不修改。

修改之后的结果为

;cipher BF-CBC        # Blowfish (default)
cipher AES-128-CBC   # AES
;cipher DES-EDE3-CBC  # Triple-DES

修改完此处之后,server.conf已经修改完毕。如果使用的是nano编辑的话,可以通过CTRL+x退出,记得保存。

1.4 设置包转发

在终端中输入

#echo 1 > /proc/sys/net/ipv4/ip_forward

这样服务器才会将客户端的网络流量转发到互联网中,否则流量只会停止在服务器这一点,无法到达用户指定的地址。

然而按照上面所示的方法,在重启之后包转发的设置会被重置为不进行转发。为了重启之后也能正常工作,编辑如下文件。(我还是使用了nano,毕竟简单。)终端中输入

#nano /etc/sysctl.conf

照旧找到以下所示一处。

# Uncomment the next line to enable packet forwarding for IPv4
#net.ipv4.ip_forward=1

net.ipv4.ip_forward前面的井号去掉,取消注释。修改之后如下所示。

# Uncomment the next line to enable packet forwarding for IPv4
net.ipv4.ip_forward=1

然而CTRL+x退出,同样要记得保存。

1.5 打开Uncomplicated Firewall(ufw)防火墙
ufw是Ubuntu 14.04自带的一个防火墙。和它的名字一样,配置这个ufw并不是很复杂。当然如果觉得不需要防火墙保护则可以直接跳过这部分。

在终端输入如下的话,可以完成ipv4的配置。首先让ufw允许ssh,否则无法ssh登录了;之后因为之前在server.conf中使用了1194端口和udp协议,所以需要允许1194端口中的udp流量。此处需要注明的是,如果使用的ipv6进行连接的话,可能需要将udp修改为udp6。而且如果同时还跑着其他的程序占用其他端口,同样需要设置对应的端口。比如我的vps中还运行着shadowsocks,一开始开了OpenVPN之后shadowsocks就不能用了,想了一会才发现是ufw的锅。所以干脆我就不用ufw了...

#ufw allow ssh
#ufw allow 1194/udp

之后修改/etc/default/ufw文件修改ufw的转发策略。终端中输入

#nano /etc/default/ufw

找到DEFAULT_FORWARD_POLICY="DROP",这里的DROP必须修改为ACCEPT。修改之后如下所示。

DEFAULT_FORWARD_POLICY="ACCEPT"

之后要为ufw添加额外的规则。终端中输入

#nano /etc/ufw/before.rules

修改before.rules文件,在文件中中间添加一部分。修改完之后样子如下(我已经看不懂在干啥了...总之照做之后能用...)

#
# rules.before
#
# Rules that should be run before the ufw command line added rules. Custom
# rules should be added to one of these chains:
#   ufw-before-input
#   ufw-before-output
#   ufw-before-forward
#

# START OPENVPN RULES
# NAT table rules
*nat
:POSTROUTING ACCEPT [0:0] 
# Allow traffic from OpenVPN client to eth0
-A POSTROUTING -s 10.8.0.0/8 -o eth0 -j MASQUERADE
COMMIT
# END OPENVPN RULES

# Don't delete these required lines, otherwise there will be errors
*filter

设置完ufw之后,我们可以开启ufw了。终端中输入来开启ufw。

#ufw enable

之后会提示

Command may disrupt existing ssh connections. Proceed with operation (y|n)?

输入y并回车,此时ufw已启动。

如果需要查看ufw的规则,终端中输入

#ufw status

如果输出结果类似如下,则配置完成。(视之前的规则设置结果会有不同。)

Status: active

To                         Action      From
--                         ------      ----
22                         ALLOW       Anywhere
1194/udp                   ALLOW       Anywhere
22 (v6)                    ALLOW       Anywhere (v6)
1194/udp (v6)              ALLOW       Anywhere (v6)

如果觉得ufw好烦没必要,也可以关闭掉ufw,终端中输入

#ufw disable

即可关闭ufw。

2. 创建证书认证和服务器端的证书和密钥

OpenVPN使用证书来加密流量。

2.1 设置并创建证书认证

这一步中将设置证书认证,并创建OpenVPN的证书和密钥。OpenVPN可以使用双向的基于证书的认证方法,也就是说在服务端和客户端建立互信关系之前,服务端和客户端需要互相验证证书。这一步中我们将要使用EasyRSA中的脚本来生成证书。

首先将EasyRSA的脚本拷贝到OpenVPN的目录下。终端中输入

#cp -r /usr/share/easy-rsa/ /etc/openvpn

之后在其下创建一个存放密钥的目录keys。终端中输入

#mkdir /etc/openvpn/easy-rsa/keys

EasyRSA有一个变量文件vars,我们可以编辑它使证书能排除掉我们希望的用户以外的人。这些变量信息会被拷贝到证书和密钥中,之后还会在识别密钥的过程中起作用。终端中输入以下内容来编辑变量文件vars

#nano /etc/openvpn/easy-rsa/vars

然后在vars文件中,以下所示的部分需要按照你的要求进行修改。

export KEY_COUNTRY="US"
export KEY_PROVINCE="TX"
export KEY_CITY="Dallas"
export KEY_ORG="My Company Name"
export KEY_EMAIL="sammy@example.com"
export KEY_OU="MYOrganizationalUnit"

之后仍然在vars这个文件中,找到并修改如下一行,修改之后如下所示。

export KEY_NAME="server"

出于简单的考虑,此处将使用『server』作为密钥的名字。如果需要使用不同的名字,还需要修改OpenVPN的配置文件中对于server.keyserver.crt的引用。

之后需要生成Diffie-Hellman参数,这个操作会需要一段时间。终端中输入

#openssl dhparam -out /etc/openvpn/dh2048.pem 2048

之后切换到工作目录,也就是之前拷贝的EasyRSA的脚本所在目录。

#cd /etc/openvpn/easy-rsa

之后进行PKI(Public Key Infrastructure)的初始化,终端中输入以下命令,需要注意两个点之间有个空格。

#. ./vars

上面那个命令会输出以下内容。不过因为我们还没在keys目录下生成任何东西,所以并不需要担心这条警告。

NOTE: If you run ./clean-all, I will be doing a rm -rf on /etc/openvpn/easy-rsa/keys

之后我们会清理当前的工作目录,防止以前的旧密钥或是示例密钥遗留下来。终端中输入

#./clean-all

之后最后一个命令将会建立证书认证,其会使用一个互动式的OpenSSL的命令(说白了就是你问我答...)。弹出的提示将会提示你确认之前vars文件中输入的那些信息(国家、省份、组织之类的)。

#./build-ca

简单一些的话,一路留空回车即可。如果需要修改哪一条的话,在这里修改也可以。

2.2 生成服务端的证书和密钥

前面说道OpenVPN的证书验证是双向的,服务端和客户端都要有证书和密钥。这一步将会生成服务端的证书和密钥。

现在仍旧在/etc/openvpn/easy-rsa这个目录下,终端中输入以下命令来创建服务端的密钥。需要注意的是,这句命令中的参数『server』需要和之前2.1部分中vars文件中export KEY_NAME后的名字相同。

#./build-key-server server

然后会输出类似于2.1部分最后一步./build-ca之后的提示。照例可以一路回车过去。不过这次会多出两个提示,如下所示。

Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:
An optional company name []:

两个提示都需要留空,所以直接回车跳过即可。

之后会又有两个询问,分别输入y再回车确认即可。

Sign the certificate? [y/n]
1 out of 1 certificate requests certified, commit? [y/n]

照着做完之后,会出现如下提示。

Write out database with 1 new entries
Data Base Updated

2.3 移动一下服务端的证书和密钥

按照之前的server.conf的设置,我们需要将证书和密钥移动到/etc/openvpn这个目录下。终端中输入

#cp /etc/openvpn/easy-rsa/keys/{server.crt,server.key,ca.crt} /etc/openvpn

这个时候OpenVPN的服务端已经可以运行了,终端中输入以下内容来启动OpenVPN的服务端并检查下运行状态。

#service openvpn start
#service openvpn status

上面第二条是查询状态的命令,其会输出如下内容。

VPN 'server' is running

3. 生成客户端的证书和密钥

到此为止,我们已经安装并配置了OpenVPN服务端,建立了证书认证,并建立了服务端的证书和密钥。在接下来,我们将使用服务端的证书认证来创建每一个客户端的证书和密钥。这些证书和密钥之后将被安装在客户端所在的设备上(比如笔记本和手机等)。

3.1 创建密钥和证书

比较理想的做法是,为每一个连接到VPN的客户端准备一个单独的证书和密钥。另外最好在创建一个通用的证书和密钥供所有的客户端使用。

需要注意的是,OpenVPN默认不允许不同的客户端通过同一个证书进行连接。(在server.confduplicate-cn部分可以查看设置)

为每个客户端创建密钥和证书,你需要为每个客户端执行一遍本部分中的命令,不过需要将本部分中的client1的名字改成另外的名字,比如client2、phone2之类的名字。由于使用了不同的证书,所以每个客户端之后都可以从客户端单独的切断连接。本部分剩余部分将使用client1作为示例的客户端名称。

现在首先为client1客户端创建一个密钥,此时你应当仍旧处于/etc/openvpn/easy-rsa这个路径下。终端中输入

#./build-key client1

像上面的一样,你会被提示要求确认vars文件中你输入的国家、省份、组织之类的一些信息,一路留空回车过去即可。同时也会像2.2部分中一样被要求多进行两相确认,提示如下。

Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:
An optional company name []:

同2.2部分中一样,上面两个分别留空并回车确认。

之后也会同之前一样有两个要求确认的地方,如下所示。

Sign the certificate? [y/n]
1 out of 1 certificate requests certified, commit? [y/n]

同样输入y并回车两次分别确认。

如果密钥成功创建了的话,终端中会有以下输出。

Write out database with 1 new entries
Data Base Updated

类似于服务端的配置文件server.conf,客户端同样在路径/usr/share/doc/openvpn/examples下有实例配置文件。我们会将其作为模板,以备下载到客户端之后进行修改。拷贝过程中我们将会把实例配置文件client.conf的扩展名conf修改为ovpn,因为客户端软件需要的文件是ovpn扩展名的。在终端中执行以下命令。

cp /usr/share/doc/openvpn/examples/sample-config-files/client.conf /etc/openvpn/easy-rsa/keys/client.ovpn

到此一个客户端的证书和密钥就配置并创建完毕了。如果需要多组密钥和证书,所需要做的就是重复本部分。当然就像前面提到的,还需要将client1的名字修改为其他的名字。

3.2 将证书和密钥拷贝到客户端设备中

这部分DigitalOcean的指南中介绍了很多方法。不过我觉得准备配置OpenVPN的人中,如果是Linux用户,那这点事情肯定难不住他;如果是windows用户,推荐使用WinSCP,特别傻瓜,全是窗口操作,没啥好说的;没用过mac,所以我也不知道该咋办(= =||)。

对于每个客户端我们需要从服务端拷贝一份该客户端对应的证书、密钥和客户端示例配置文件。

继续以上文中的client1作为例子,我们的客户端client1的证书和密钥在服务器的以下路径中。

  • /etc/openvpn/easy-rsa/keys/client1.crt
  • /etc/openvpn/easy-rsa/keys/client1.key

另外对于所有的客户端,证书认证文件和客户端的示例配置文件在如下所示的路径中。需要注意证书认证文件在openvpn的根目录下,跟剩下三个不在一个路径下面。

  • /etc/openvpn/easy-rsa/keys/client.ovpn
  • /etc/openvpn/ca.crt

本部分完成之后,你的客户端设备中将有以下四个文件。

  • client1.crt
  • client1.key
  • client.ovpn
  • ca.crt

4. 创建一个OpenVPN的客户端档案

管理客户端文件有许多方法,然而最简单的一种方法就是把所有的文件都放到一个档案文件中。我们只需要修改配置文件模板client.ovpn,使其包含服务端的证书认证、服务端的证书和密钥。修改完毕之后,所需要导入的配置文件就只有client.ovpn这一个文件了。

接下来我们将在客户端设备上修改之前下载的四个文件。之前的客户端配置文件模板client.ovpn需要被复制并重命名,叫什么名字随意。名字并不需要和客户端设备相关,客户端软件将会将这个文件的名字当作VPN连接的名字。所以client.ovpn的命名应当相同与你想要其出现在你操作系统中的名字,比如work就重命名为work.ovpn等。

在这篇指南中,我们将会想要VPN的名字为DigitalOcean,所以client.ovpn将会被复制并重命名为DigitalOcean.ovpn,之后在编辑器中打开DigitalOcean.ovpn。

首先,如果使用的是ipv6连接vpn的话,类似于server.conf中的内容,DigitalOcean中的协议同样需要被修改。找到如下的一段内容

# Are we connecting to a TCP or
# UDP server?  Use the same setting as
# on the server.
;proto tcp
proto udp

proto udp修改为proto udp6。如果使用ipv4连接的话,则不需要修改这一段。修改之后的效果为

;proto tcp
proto udp6

之后找到如下一段

# The hostname/IP and port of the server.
# You can have multiple remote entries
# to load balance between the servers.
remote my-server-1 1194

其中将my-server-1修改为你的服务器的地址。如果使用的是ipv4连接VPN,则将my-server-1修改为服务器的ipv4地址;同样如果使用ipv6连接VPN则将my-server-1修改为ipv6地址(切记看清楚不要设置成网关的,说多了都是泪)

之后找到下面一段,去掉usergroup前面的分号,作用和第1部分中说的一样。客户端如果运行在Windows系统中,那么可以忽略这一步。修改之前为

# Downgrade privileges after initialization (non-Windows only)
;user nobody
;group nogroup

修改之后为

# Downgrade privileges after initialization (non-Windows only)
user nobody
group nogroup

之后找到如下一段

# SSL/TLS parms.
# . . .
ca ca.crt
cert client.crt
key client.key

ca、cert、key前面加上井号将其注释,这样我们之后将证书认证、证书和密钥输入到ovpn文件中才会生效。修改之后的效果如下

# SSL/TLS parms.
# . . .
#ca ca.crt
#cert client.crt
#key client.key

之前如果在server.conf中设置了加密方式中(比如我们在第1部分中做的那样),那么在DigitalOcean.ovpn中找到如下一段。

# Select a cryptographic cipher.
# If the cipher option is used on the server
# then you must also specify it here.
;cipher

由于我们之前选择了AES-128-CBC的加密方法,所以我们此处的设置也与server.conf中相同。修改之后的效果如下。

# Select a cryptographic cipher.
# If the cipher option is used on the server
# then you must also specify it here.
cipher AES-128-CBC

最后在DigitalOcean.ovpn文件的末尾添加以下XML结构的内容。

<ca>
(在此处插入ca.crt的内容)
</ca>
<cert>
(在此处插入client1.crt的内容)
</cert>
<key>
(在此处插入client1.key的内容)
</key>


分别用编辑器打开这三个文件,并插入即可。需要注意的是client1.crt的内容和另外两个有些不同,不过不用管,直接加入进去就好了。修改之后的效果如下。


<ca>
-----BEGIN CERTIFICATE-----
. . .
-----END CERTIFICATE-----
</ca>

<cert>
Certificate:
. . .
-----END CERTIFICATE-----
. . .
-----END CERTIFICATE-----
</cert>

<key>
-----BEGIN PRIVATE KEY-----
. . .
-----END PRIVATE KEY-----
</key>

至此为止,我们的客户端配置文件已经创建并设置完毕。

5. 安装客户端的配置文件

我目前只在windows中设置过openvpn。所以此处只简单叙述下windows中的方法。毕竟之前的才是重头戏,后面的都已经好解决了。

首先将我们的DigitalOcean.ovpn的配置文件拷贝到OpenVPN的安装根目录下的config文件夹下。

然后管理员权限启动OpenVPN GUI。(一定要以管理员权限运行)

然后在系统托盘图标上右键,并点击connect即可。

至此OpenVPN的服务端和客户端的配置已经完全完成,享受私密网络吧!

《巫师》——大型3D音乐AVG游戏

2011年《巫师2》发售之后,迅速的在学校的pt论坛上成为热门种子,当时正在努力攒上传量的我也第一时间下载并安装了这个游戏。

然而由于电脑的配置过低,加上游戏诡异的操作方式,虽然《巫师2》的大量正面评价不绝于耳,《巫师2》还是迅速被我丢到了抛弃列表里。

前些日子《巫师3》发售,各个游戏媒体又是正面评价不断。加上小学期水课之余并无事可做,于是抓紧时间补补老游戏。看着自己的破笔记本,估量了一下之后,还是决定从2007年发售的系列第一代《巫师》开始。

说到《巫师》系列的游戏,要先从他的制作公司CDP(CD Projekt)公司开始说起。CDP公司1994年成立于波兰,公司成立之初定位于从美国进口软件进行销售。在那个洪荒年代,很长的一段时间里CDP都是波兰唯一能出版游戏光碟和教育软件的公司。

如果对于CDP公司有些陌生的话,相信许多玩家对于GOG.com这个网站并不陌生。『GOG』取义于『good old games』,其2008年建立,隶属于CDP公司,售卖很多DRM-free的游戏。

说回CDP公司,CDP在建立之初的头三年里,和许多国外的工作室建立了代理关系,其中不乏interplay(黑岛的母公司)、Blizzard、Blue Byte(《工人物语》系列和《纪元》系列)这样的知名公司;代理关系建立的同时,开始了将各个公司的作品进行本地化的工作——完整的翻译为波兰语并在游戏中附带波兰语的游戏手册。之后完成了诸如《博德之门》系列、《冰风谷》系列、《异域镇魂曲》和《暗黑破坏神2》等知名RPG的本地化工作;并继续扩大经营,与微软、Konami等公司建立了代理关系。

2002年的时候,CDP成立了自己的开发部门CDPR(CD Projekt RED),也就是本作《巫师》的制作组。然后这个制作组始终沉寂着,直到07年凭着用从Bioware买来的引擎做出来的游戏《巫师》横扫世界——GameSpy和IGN分别都给出了年度最佳游戏的评价。

《巫师》是根据系列小说《猎魔人》改编而成的RPG游戏,采用了章回体的格式,讲述了狩魔猎人Geralt在寻回狩魔猎人的秘密、向Azar Javed复仇、粉碎火蜥蜴帮的过程中的种种经历。

游戏采用了半开放世界、半章回体的模式。故事根据发生地点的不同,一共分为了七个章节。虽然游戏的整个大地图面积并不小,然而由于每个章节对于可以进入的地图有所限制,所以每个章节中玩家只能在固定的一个中等面积的地图上活动。相对比与《上古卷轴》系列和《GTA》系列的地图,活动的自由度还是小了不少。

不过这也是一种比较聪明的做法。《巫师》并不是《GTA》那样始终在一张地图上活动的游戏,随着故事的进行,Geralt会在各个地方之间旅行。如果将《巫师》的地图设置成《GTA》中那样的完全开放地图,那么玩家就需要远距离移动。此时要么像《上古卷轴》系列中一样设置快速移动,要么像《GTA》中的公路飚车一样提升跑路的乐趣。

如果像《上古卷轴》中那样可以快速移动,那么跑路过程中可以触发的支线任务就会大大减少,同时也会减少游戏的带入感——不觉得两眼一闭一睁就到任务地点的设计很像国产网游中的自动寻路么。

而《巫师》的中世纪奇幻世界观也限制了其不能像《GTA》一样搞出跑车之类的载具。《刺客信条:兄弟会》搞出过骑马快速赶路这样的设计,玩起来实际上还不如爬房子赶路有趣,只是换一种形式提高移动速度;然而到了《刺客信条:黑旗》开船打海战式的赶路就有趣的多了。

再加上《巫师》的游戏重心在于叙事,将跑路设计的很有趣不免显得有些喧宾夺主,看《水浒传》里林冲上了梁山之后也不会有人关心山神庙那里还有没有支线任务吧。

半开放式中等大小地图加上章回体式地图切换对于《巫师》的带入感营造已经是最合适的选择。即使如此,玩到一半的时候,还是会因为跑路的时间太长而感到烦躁,好在有玩家制作了mod,可以增加跑步速度,某种程度上解决了这个问题。

地图的设置从视觉上提升了游戏的带入感。对白、任务的设置和叙事方法的选择则从另一个方面提升了游戏的带入感。

《巫师》对于任务的安排并不像《上古卷轴5》那样倾向于将任务水平排列——做完一个系列再做一个系列,互相的关联程度不高;而是倾向于一个完整的有因果关系的故事链条——前期的任务选择会对后期的任务有所影响。从事件的发展来看,《巫师》的叙事手法显然比《上古卷轴5》立体了很多。

而『选择』恰好是《巫师》的一个主要卖点。游戏中的主角Geralt所属的狩魔猎人这个群体以『中立』闻名,然而当Geralt被卷入各种各样的事件之后,玩家则往往必须做出违背『中立』的选择,否则骑墙的态度会下场更惨。不同的选择会影响到和不同势力、不同人物的关系,从而影响到之后的故事进展。

然而《巫师》的精妙的叙事和选择支设置却在一定程度上起了反作用。

比较复杂的剧情互相穿插,并不是很顺畅,有的地方剧情进展会让玩家感到时间错乱的感觉。比如玩家在沼泽过早的『扶老爷爷过沼泽』就会过早的拿到Kalkstein要求玩家找的《Ain Soph Aur》这本书,当任务A Mysterious Tower开启时,玩家很可能意识不到这本书早就拿到了。

另外,前面提到了《巫师》是一个RPG游戏,而不是一个文字AVG游戏。不同于文字AVG游戏将全部重心放在通过文本展开剧情,RPG游戏要求《巫师》在叙事之外还应当有合适的游戏内容——比如常见的战斗、收集、养成等要素——来提高玩家的带入感。

让我们看看《巫师》的文本之外的内容吧。

一个简单的战斗系统。

玩家可以选择两种简单的武器——『钢剑』和『银剑』,每种武器都有三种攻击姿态。玩家每次攻击之后,在提示的时间点点击鼠标继续攻击可以获得连击效果。虽然游戏采用了动作游戏常用的第三人称越肩视角,攻击效果并没有做到动作游戏的每次攻击都『拳拳到肉』的快感。玩家攻击之余只能观赏Geralt的华丽身影和等待光标着火继续攻击。这种MUG游戏的操作方式,让感觉像是穿着全套的盔甲在跳华尔兹。

游戏并不像《博德之门》有小队指挥系统,虽然游戏提供了F1、F2、F3键所对应的三种视角,操作方式也有所区别。事实上一般人都会用第三人称越肩视角,因为并没有其他角色需要用到俯视的上帝视角。

不过制作者还是为Geralt准备了五种魔法(游戏里叫法印)。这么看来,Geralt的定位大概是孤独的『特种雇佣兵』的感觉,近战、法术、炼金术都略通一二。

一个尚可的收集系统。

玩家可以在地图上找到各种炼金材料。游戏的难度足够高的话,玩家需要各种嗑药才能获得足够的BUFF来完成任务。

然而与消耗材料对比之下,装备的收集实在是鸡肋。武器与防具之间的差别相当之少,玩家并不需要注意更换。于此相对的,强化刀剑的磨刀石和符文就显得有些多余了。

值得夸奖的是,游戏中有许多书籍和羊皮卷可以收集,大量的介绍了《巫师》的世界观。并且介绍对于完成某些任务很有作用,能够大幅度的减小任务难度。这种『探索+解密』式的任务安排相对于在地宫里一路砍砍砍的《上古卷轴5》来说还是有趣了不少。

所以说《巫师》的重点还是在于文本,即故事的叙述。多线索穿插式的叙述和还算优秀的剧情给《巫师》加分不少。

然而一条腿蹦达的游戏玩起来有很严重的不平衡感。本应当成为大型3D角色扮演游戏的《巫师》就这样沦为了一个大型3D文字冒险游戏。

 

《寂静岭2》后记——一个审视自己的机会

趁着期末考完,小学期暂时没有开始的时候,通了一直想玩的《寂静岭2》(之后简称SH2)。由于小时候电脑买的太早,很遗憾并没有赶上PS和PS2的那个家用机时代,许多经典游戏都没有玩过,包括SH2这一作品。

了解SH2这一作品,还是通过《Promise》这首曲子作为契机。第一次听到这首曲子的瞬间,立刻就被俘获了。《Promise》给人一种令人上瘾的压抑感。音乐中有大量的重复的音节,像是一波又一波黑色的浪,又像是躺在幽暗的湖底望着水面月光,让人喘不上来气。可即使听的时候会感觉内心沉闷、纠结,却仍然会不由自主的不停循环。尤其是音乐末尾,在重复之后,突然回到音乐开头的旋律,最后轻轻的消失,压抑感的突兀消失让人好奇发生了什么。

sh2_ost_jp_01_front

SH2的原声集封面。Maria侧躺在Heaven's Night夜总会的地面上,其脱衣舞女的身份暗示着James对于Mary的某些期望。

后来百度了一下,知道了《Promise》是SH2的插曲。也大概知道了SH2并不是传统意义上的『horror game』,而是『depressing game』。然而因为没有家用机,迟迟没有玩SH2。

前些天和同学聊起了SH2的电影,又想起来了这个游戏。我忽然想到如此出名的游戏,有可能有PS3的重制版。百度之后发现不仅有PS3的重制还有PC的重制,于是完成了多年前就该完成的事情。

#以下有大量剧透,通关前不推荐看

游戏的剧情围绕着男主James回到Silent Hill——这个承载了自己和妻子Mary无数美好回忆的小镇,并寻找三年前去世的Mary这一故事来展开。

James在故事的开头收到了Mary的来信,可是Mary在三年前就去世了,信中提到Mary一个人在和James的『special place』等待他。

James好奇之下,便来到了Silent Hill这个特殊的地方,开始了寻找Mary的旅程。

寂静岭的原型小镇Centralia, Pennsylvania

寂静岭的原型小镇Centralia, Pennsylvania

在寂静岭这个镇子上,James遇到了被亲生父亲性虐待的Angela、因被欺凌而杀人的Eddie、Mary生前的好朋友——天真无邪的小女孩Laura、自己脑内臆想出的Mary的化身Maria,当然也遇到了无数畸形至面目无法分辨的怪物。

在寻找Mary的过程中,James在镇子上发现了种种暗示自己的罪恶的线索。最后在湖边的旅馆中,James通过遗忘在旅馆的录像带得知了Mary病重之时被自己杀死的事实。

SH2的正常结局一共有四个。我认为的最好的结局还是『Leave结局』。James面对着病床上的Mary也终于能够诚实的说出自己因为对Mary的付出无法得到回报,产生的不平衡心理导致了自己对于Mary的憎恨。Mary也宽容的对待了James的憎恨,请求James为她做最后一件事情——『Go on with your life』。James也明白了Maria只是自己脑内的臆想,即使Maria符合自己对于Mary的期望,其终究是虚幻的,无法实际存在的。人与人的关系有双面性,不可能只令人满意,总会有或多或少令人不满的地方。

就像『Maria结局』中的一样,在Silent Hill外的停车场,Maria咳嗽也象征着其会像Mary一样重病,最终变成Mary。James眼中的完美形象Maria一旦离开寂静岭这个虚幻的世界,回到在现实中后,一样会被打回原型。

结局处,Mary给James写的信再次出现在屏幕上,不过这次是完整的信件。从最终boss前、杀死两只三角头之后的走廊处James和Mary的对话,以及Mary的信件可以看出,Mary重病中的纠结心理。

一方面知道自己将不久于人世,看待事物都会被罩上一层悲观消极的色彩。即使James对她无微不至,Mary也会因为疾病的原因对James恶言相向。

另一方面,Mary的理智告诉她,James是一个好人,自己这样对James恩将仇报是不对的。Mary对James的愧疚感和绝死之前的依赖催使Mary写下了给James的信,信中Mary也终于能够平静的、真诚的、坦白的道出自己的内心。

结尾处James与Laura一同从Toluca墓地处离开了Silent Hill,暗示着James完成了Mary信中的遗愿,收养了孤儿Laura;也暗示着James和Laura一样,成为了心智纯净的人,完成了Mary死前的最后一个请求,通过自我审视和自我救赎,得以继续自己的生活,再也不会因为自己的罪恶行径被Silent Hill召唤。

如果与同以『恐怖』作为卖点的游戏《Alan Wake》作为对比的话,可以看出SH2的几个明显不同之处。

6796002118_089c6fd94a_o

《Alan Wake》中的场景相对于SH2还是温和了很多。

首先是开头处提到的,SH2不同于以往的『horror game』,更准确的说应当是『depressing game』。虽然游戏中并不会突然出现怪物或是通过突兀的声音惊吓玩家,玩家却会很自然的融入制作者精心布置的场景中去。游戏中大量出现机械式重复的背景音,有着强烈的精神污染的作用;墙壁上的斑斑血迹与锈痕,空气中的迷茫雾气,难以用理智理解的道具布景,无时不刻的在扭曲着玩家的神志。即使是不处于腐烂恶臭的里世界中,在破败残缺的表世界中玩家也会负担着强烈的精神重压。

其次,SH2相对于许多以『恐怖』作为卖点的游戏,其『压抑』气氛的营造并不通过紧张困难的操作。SH2更多的像是一个文字冒险游戏。游戏中有着大量可探索的元素,地上散落的纸片、垃圾堆中的报纸、墙壁上的血书、房间中飘荡的密语,大量的元素都有着象征意义和暗示。玩家在探索的过程中,自然而然的因为了解到的信息感到『压抑』。

Silent_hill_wallpaper_pyramid_head

杀不死的三角头。

再其次,相比于《Alan Wake》这样的很像电影的作品,SH2更像是一部小说。SH2的字里行间为玩家提供了大量的可以仔细体会的细节。例如三角头这一形象象征着James想杀死Mary的黑暗心理。游戏的过程中James可以杀死其他所有的怪物,唯独无法杀死三角头这一怪物,这象征着游戏过程中James始终没有正视自己的罪过,只能不停的逃避三角头、逃避自己犯下的罪行。然而在故事的末尾处,在同两只三角头搏斗之后,三角头却自杀身亡,这也象征着James正视并抛弃了自己的罪行,不再为自己的罪行辩护,完成了自我救赎的James战胜了自己的黑暗心理,三角头自然消失。游戏中类似的细节还有很多,玩家可以仔细思考体会的地方也有很多。所以SH2给人的感觉比《Alan Wake》厚重了许多。

然而对于SH2,我依旧有不满意的地方。SH2仍旧没有跳脱出娱乐制品的圈子。制作者虽然有着精妙的表现手法,能够让玩家在游戏中感受到强烈的压抑和精神负重,却因为着游戏剧本天生的残疾,无法将这种压抑和精神负重延续到游戏完结之后的现实生活中去。

与一个做的比较好的例子进行对比的话,多年前在读完余华的《活着》之后,面对人生无常,心生的无力和压抑能够持续很长时间,甚至能够一定程度上的改变一个人的世界观。与《活着》相比,SH2的剧本多少还是有些『小家子气』,这个时候SH2就更像一部电影了。

把SH2看作一个电影的话,其背后也是有很多有趣的幕后故事的。比如Mary的配音演员在为结尾处Mary给James的信配音时,读完了信不禁哭了出来。之类的故事还有很多,可以从wikia上找到。

另外这次玩的因为是HD重制版,所以konami为游戏添加了高清材质,游戏的分辨率也提高了很多。不过由于SH2是一个恐怖游戏,游戏材质提高之后视觉效果反倒有些滑稽。如果玩的是HD重制版的话,不推荐使用高清材质包,分辨率也尽量降低,LOFI的味道更奇妙。

GMM的EM算法实现

GMM的全名是Gaussian Mixture Model,即高斯混合模型,这个名字挺直观。

如果给了一组数据点,假设这些数据点符合iid,那么很容就能根据数据拟合出一个最佳的高斯分布。

但是如果给了一堆数据点,而他们却不符合iid,只能做到互相独立,并不能做到同分布。相反的,数据点们有可能来自不同的高斯分布,这也就是『高斯混合』模型名字的意思。这样如何能拟合出最佳的高斯分布们呢?

EM算法提供了一种方法,这种方法的思路有些像牛拉法。先是确定一个初值,然后看看当前值距离目标还有多远,然后逐渐的缩小差距(不断修正membership weight)。

具体原理见这里

这篇小短文大概记录下这次作业的内容。作业题目是生成了2个二维高斯分布混合的数据点,共2000个,然后用这两千个点拟合出2个二维高斯分布的参数。

clear;
%产生2个二维正态数据
MU1    = [1 2];
SIGMA1 = [1 0; 0 0.5];
MU2    = [-1 -1];
SIGMA2 = [1 0; 0 1];
X      = [mvnrnd(MU1, SIGMA1, 1000);mvnrnd(MU2, SIGMA2, 1000)];
scatter(X(:,1),X(:,2),10,'.');

%initial values
h_mu1 = X(randi(2000),:);
h_sigma1 = cov(X);
h_mu2 = X(randi(2000),:);
h_sigma2 = cov(X);
h_alpha1 = 0.5;
h_alpha2 = 0.5;

%simple iteration
for iter=1:100
    %E step
    w1 = mvnpdf(X,h_mu1,h_sigma1)*h_alpha1./...
    (mvnpdf(X,h_mu1,h_sigma1)*h_alpha1 + mvnpdf(X,h_mu2,h_sigma2)*h_alpha2);
    w2 = mvnpdf(X,h_mu2,h_sigma2)*h_alpha2./...
    (mvnpdf(X,h_mu1,h_sigma1)*h_alpha1 + mvnpdf(X,h_mu2,h_sigma2)*h_alpha2);

    %M step
    h_alpha1 = sum(w1)/2000;
    h_alpha2 = sum(w2)/2000;
    
    h_mu1 = sum([w1.*X(:,1) w1.*X(:,2)])/sum(w1);
    h_mu2 = sum([w2.*X(:,2) w2.*X(:,2)])/sum(w2);

    M1 = X-ones(2000,1)*h_mu1;
    h_sigma1 = ([sum(w1.*M1(:,1).^2) 0;0 sum(w1.*M1(:,2).^2)]+...
        sum(w1.*(M1(:,1).*M1(:,2)))*[0 1;1 0])/sum(w1);
    M2 = X-ones(2000,1)*h_mu2;
    h_sigma2 = ([sum(w2.*M2(:,1).^2) 0;0 sum(w2.*M2(:,2).^2)]+...
        sum(w2.*(M2(:,1).*M2(:,2)))*[0 1;1 0])/sum(w2);
end

figure;
[x,y] = meshgrid(linspace(-5,5,75));
p1 = mvnpdf([x(:),y(:)],h_mu1,h_sigma1);
p2 = mvnpdf([x(:),y(:)],h_mu2,h_sigma2);
surf(x,y,reshape(p1,75,75));hold on
surf(x,y,reshape(p2,75,75));

options = statset('Display','final');
obj = gmdistribution.fit(X,2,'Options',options);
figure,h = ezmesh(@(x,y)pdf(obj,[x,y]),[-8 6], [-8 6]);

绝大多数时候都没有什么问题,不过由于初始点是从X里随便选的一个数据点,极偶然会跑偏。

以下分别是数据点的分布、自行拟合出的结果、利用matlab自带拟合函数拟合出的结果。

originalgmm

根据给定的均值、协方差矩阵画出的GMM的图

xscatter

数据点的散点图,保存之后可能有点糊

fitbymyself

自己写的脚本拟合出的GMM的图

fitbymatlabtoolbox

matlab提供的拟合函数拟合出的图

迭代100次之后,高斯分布1的均值分别偏差0.2776%、4.4462%,协方差分别偏差了2.4458%、5.0146%;高斯分布2的均值偏差了2.6981%、1.2911%,协方差偏差了3.8498%、1.5517%。精度凑凑活活把...

对比之下,matlab自带的拟合函数拟合出来的高斯分布1的均值偏差2.2415%、2.2415%,协方差偏差为4.02%、1.32%;高斯分布2的均值偏差了0.4165%、0.4165%,协方差偏差为2.39%、4.62%。精度也没高到哪里去...不过均值偏差一样让我很是在意...

然而看图1、图3和图4的话,明显还是自己写的代码拟合效果更好一些啊,有些不科学。

算法学习笔记(4):计数排序

在宿舍呆着无聊接着在hackerrank上刷水题。这道题由于排序的依据是一定范围内的整数,所以用计数排序效率应当不错。

说到计数排序,实际上思路也很常见。最常见的一个例子就是比赛或者是考试的时候要进行排名。

比如某班有3名同学考了100分,2名同学考了99分,5名同学考了98分。那么很明显,比99分高的同学一共有3名,所以考99分的同学只能是第4名了。

计数排序大概就是做了个数数每个元素前面有多少元素这个事情。先统计最高分多少分,然后依次统计各个分数的学生个数,然后以此叠加就可以统计出前面有多少个学生了。

而且由于不同分数段的学生是按照原顺序放置到新数组中的,所以在原数组中的顺序并不会被打乱,即这个算法是稳定的。这也是为什么这道题可以用计数排序解,因为并不会打乱文本的顺序。

顺便一提,这道题中的最大值max()的复杂度应该是,所以总运行时间应该是。因为计数排序并不涉及到不同元素之间的比较,即不是比较排序,所以的下界并不适用于计数排序。

最后附上这道题的一个无脑解。

# Enter your code here. Read input from STDIN. Print output to STDOUT
n = int(raw_input())
ar = []
idx = []
out = [None]*n
for _ in range(n):
    ar.append(raw_input().split())
    ar[-1][0] = int(ar[-1][0])
    idx.append(ar[-1][0])
    if _<n/2:
        ar[-1][1] = "-"
countlist = [0]*(max(idx)+1)
for item in ar:
    countlist[item[0]]+=1
for i in range(len(countlist)-1):
    countlist[i+1]+=countlist[i]
for item in reversed(ar):
    out[countlist[item[0]]-1]=item
    countlist[item[0]]-=1
for item in out:
    print item[1],

《Cities: Skylines》——城市建造新神作?

《Cities: Skylines》是由Colossal Order工作室(之后简称CO)开发,由Paradox Interactive(俗称的P社)在2015年3月发行的模拟类游戏。

city view

这是我之前的某一个城市,由于道路安排失败,之前封印了好久。(上reddit看到许多网友都将自己的城市命名为shitvale,这份心情真是感同身受)

CO是一个成立于2009年的芬兰工作室。其之前也只有《Cities in Motion》(之后简称《CIM》)一个系列的作品,同样由P社发行。

《Cities: Skylines》(之后简称《C:S》)的中文名翻译作《都市:天际线》,从本作的命名风格来说,和《特大城市》系列有些像,都是从名字就透露出了游戏的终极目的:打造宏伟的钢筋森林。对比其他的游戏来说,比如说近期的《纪元》系列、《模拟城市》系列、《放逐》等等,游戏的目的还是比较明确的。

Cities: Skylines is a modern take on the classic city simulation. The game introduces new game play elements to realize the thrill and hardships of creating and maintaining a real city whilst expanding on some well-established tropes of the city building experience. From the makers of the Cities in Motion franchise, the game boasts a fully realized transport system.

——摘自游戏主页上的说明;游戏会引入新的元素,并有完善的游戏体验。当然介绍的最后一句也注明了游戏的制作者是《CIM》系列的制作者,所以运输系统会是游戏的一个主要部分。

事实上,游戏预售的时候,我有些怀疑这个游戏的质量。如果将城市建设游戏的主要内容分作两块的话,我觉得可以分作『区划』——城区组成的规划、公共设施的建设和预算的维持,以及『交通』——区划之间的位置关系、道路和公共交通的规划。

『区划』的设计

从『区划』部分的来看,我认为一个比较复杂而有趣的游戏是《纪元1404》(以下简称《1404》)。本科的时候,一个偶然的机会从学校的PT论坛上下载到了这个游戏,然后不久之后就开始乐此不疲的和朋友联机玩这个游戏。

《1404》中的『区划』是比较复杂的,其其不同于《C:S》继承于《模拟城市》系列的住宅区、商业区、工业区三大块,只有居住区和工业区两大块。

然而《1404》中的工业区和住宅区并不是简单的进行面积的分配就可以了。《1404》中强调了供应链和产业的概念,住宅区升级需要供应不同种类的产品;生产不同的产品就需要安排不同的生产部门和供应链。而且奇葩的是游戏中实行供给制,税金由住宅区提供,工业是消耗税金的部门。同时游戏中又存在东西方两种建筑类型,分别分布于不同的岛屿上;玩家还要抵抗其他玩家通过海战夺岛等对供应的干扰。仔细想想的话,其实《1404》的内容设置有些类似于卡坦岛的思路,其中的供应链安排其实是十分复杂的。

capitalism 2 lab

事实上还有这样一款模拟经营类『软件』——Capitalism 2 Lab,其目的便是建造自己的企业帝国;其中不仅产业分门别类的十分详细,而且可以买卖股份,兼并公司。我认为这个已经超出了游戏的范畴了。

对比之下,在《模拟城市》中则没有怎么强调供应链的概念,只需要进行城区面积的合理分配即可。工业区中什么都有,不再需要事无巨细的安排。

《C:S》则巧妙的在『区划』的游戏内容安排上走了中间道路,其中和了《模拟城市》系列的『傻瓜』和《1404》的『繁琐』。于是《C:S》中保留了大部分《模拟城市》系列中的公共服务设施——警局、消防局、医院、水电垃圾服务等;同时简化了《1404》中的供应链,只剩下了油、铁、稻、林四种自然资源及其附属工业,以及加工自然资源生产的普通工业区。这样既避免了玩家在划分区域时遇到过大的困难,从而心生厌烦;同时也避免了游戏设置过于简单,玩家容易玩腻的情况。

city_games_zoning

自己总结的三个游戏关于『区划』的游戏内容的不同;虽然《C:S》中还有一个办公区,不过由于其无输入也无输出,所以就不再列出了。

说完分区,再说一说游戏中的公共服务设施。其大致继承了《模拟城市》中的公共服务设施种类,就是上文中提到的警局、消防局、医院、水电垃圾服务等。不过由于《C:S》有着良好的mod扩展性(这好像也是P社游戏的一贯特征),游戏发售短短没有几天,steam workshop上就出现了大量mod。其中有不少便是新的公共服务设施。

举个例子来说,官方游戏中垃圾处理设施只有垃圾填埋场和垃圾焚烧站两种。而这两种设施都会产生污染,垃圾填埋场更是只能单纯的作为容器,而没有任何『消化』能力。于是玩家制作了《模拟城市4000》中的垃圾回收中心没有污染的小规模垃圾回收站。类似的这种mod很好的补充了游戏制作者对于公共服务设施的不重视。

『交通』的设计

本文一开始就提到了,《C:S》的制作公司CO工作室拿得出手的作品在本作之前只有《CIM》一作,游戏的内容就是交通运输。而在《C:S》的官方主页上,发行商更是将《CIM》作为卖点,强调《C:S》将会带来同《CIM》一样的设计交通的体验。

既然『区划』部分举了《1404》和《模拟城市》两个例子作为陪衬,那么『交通』部分也来举一个不错的陪衬。我认为『交通』设计的不错游戏是继承于《Transport Tycoon》的开源游戏《Open Transport Tycoon Deluxe 》(以下简称《OpenTTD》)。

《OpenTTD》的中文名字应当叫做《开源运输大亨》,其游戏内容没有任何城市建造成分,只有运输内容。玩家需要将各种资源运输于各个资源点之间,将旅客和邮件运输于各个城市之间。运输的主力又以铁路为主,所以这个游戏应当是吸引了不少TMRC成员一样的玩家。

Warraweah Transport, 2131-08-30

《OpenTTD》的内容除了运输便无其他,然而这种纯粹却也吸引了不少玩家。

然而《C:S》毕竟不像《OpenTTD》一样宏观,《OpenTTD》中甚至有欧洲的地图,《C:S》只是规划一个城市的交通而已。题材注定限制了《C:S》中『交通』的玩法比较微观,更注重于城市交通中常见的塞车问题。

不过值得庆幸的是,作为一款城市建设游戏,《C:S》十分可贵的将游戏地图扩展到了100平方千米的范围,玩家在这样大小的一幅地图中虽然无法像在《OpenTTD》的最大地图中一样『挥斥方遒』,却也依旧可以尝试着搭建起一个公路、轨道运输为主,水路、空运为辅的交通网。

游戏提供了多级的公路设置,道路的容量和速度分别上升,同时也像《模拟城市》一样,提供了单行道的选项。如何在有限的空间里,搭建一个合适的立体化的交通系统,是这个游戏的一个主要玩点。

是建设成北京一样的圆环套圆环公路结构,还是巴黎一样的放射状道路;如何引导车流不通过某些区域而高速的到达指定区域;怎样在有限的道路轨道资源中,通过更多的车辆。这些问题将伴随着整个游戏过程。

好在游戏的良好的mod扩展性为许多玩家解决了问题,道路建设苦手们可以在steam workshop上下载上万种的预设模型,高质量的交通浏览、控制类mod为玩家排忧解难。

2015-03-30_00001

还是之前的那个自己的shitvale。在下了一个mod,取消了高速箍口附近的交通灯之后,图中所示的拥堵迅速的就消失了。

 

一些缺点

夸了半天这个游戏,是时候说一说这个游戏的缺点了。

内容失衡这个缺点来自于CO工作室的年轻。CO工作室之前只开发过《CIM》系列一作,之后就上马了《C:S》这个游戏,这个工作室的年轻导致了其无法很好的驾驭这个类型。

直观来看,《C:S》最明显的问题就是『区划』部分的内容过于简单。如果玩家玩过《模拟城市》系列和《特大城市》系列的话,想必对于高昂的公共服务设施开销仍然记忆犹新。

所以一开始我玩《C:S》的时候,并不敢满地放公园之类的东西。然而随着我连续开了几个shitvale的存档之后,我发现这个游戏虽然披着《模拟城市》的皮,其却和《模拟城市》完全是两个游戏。

《模拟城市》中的主要难点是收支的平衡,如何用少量的税收,使城市高效的运转。

《C:S》中的税收是十分充足的,一个4万人口左右的城市,即使将支出最大化,收入剩个4万左右的结余是很正常的事情。玩家手头握许多闲钱,自然玩起来很轻松,完全没有感受到《模拟城市》和《民主制度》中作为政策制定者的那种顾此失彼的感觉。

游戏在『区划』方面没有任何难度,剩下的难度自然就要转移到『交通』方面了,而这又是CO工作室所擅长的。一方平淡无聊,一方却惊险刺激,《C:S》更像是添加一些内容、换了一张皮的《CIM》。

游戏没有黑夜模式这种每日的循环概念,全天是白天也算个小缺点。

同时游戏还有一些小小不严的BUG,比如policy页面经常调不出来啊,调出来了又经常花屏啊之类的。相信在不久的将来都可以通过补丁解决掉。

总结

对比于《模拟城市》当初的灵气,《C:S》更多的像是一款中规中矩的仿制作。网络上对其评价不错,主要还是因为近年来类似题材的作品实在是都太水了(说的就是《特大城市》你个大水货!),少有及格作。对比之下,《C:S》虽然算不上划时代,却也是一款朴实的优秀作品。

然而,就是这样一款普通的优秀作品,玩家们已经等待了太久太久,距离03年尖峰时刻发售,已经过去了整整12个年头,无数少年少女熬成了孩儿爸孩儿妈。

说实话,刚刚上手玩这款游戏的时候,这种久违的感觉真的让我有些想哭。

眼前的不是这款游戏,而是当初我每日面对着绿黄蓝地图的年少时光。

与此同时,《Cities: Skylines》推出当日销量就达到了25万,发售一周销量达到了50万,销量不可谓不可观。这样优秀的成绩,让我见识到了城市建设类游戏这个市场绝未萎缩消亡。无数玩家心中仍然有着一个『市长梦』。

作为一个模拟经营类游戏爱好者,我希望广大游戏开发商能够在这样的证明下,相信优秀的模拟经营游戏依旧可以获得优秀的销量。希望以后能见到更多更优秀的模拟经营类游戏,让这个游戏类型不像RTS一样逐渐消亡,而是能够长青不衰。

文章结尾做一下小广告。如果真的爱这款游戏的话,国区玩家可以去杉果买打了折的《Cities: Skylines》,只要¥79,比steam上买便宜许多。

images

引用一张youtube视频的封面。P社,CO,我顶你啊!

 

如何编译tslib

前些天用qt4.8做的界面的字体渲染特别难看,所以准备用qt5.4做界面。X宝上买的mini2440并不随机赠送编译好了的qt5.4,所以还得自己从头编译一份。

先记录下编译tslib的过程吧。(具体原理完全不懂啊...

编译器使用了随机赠送的arm-linux-gcc-4.4.3,这里有的下

when-theory-met-practice

下面一段中的一堆变量我也不知道为什么这样定义,不过这样能够成功。其抄袭于这篇博客

$mkdir ~/tmp
$cd ~/tmp
$git clone https://github.com/kergoth/tslib.git tslib
$cd tslib
$export PATH=编译器的路径/bin:$PATH
$export CROSS_COMPILE=arm-none-linux-gnueabi-
$export CC=${CROSS_COMPILE}gcc
$export CFLAGS="-march=armv4t -mtune=arm920t"
$export CXX=${CROSS_COMPILE}"g++"
$export AR=${CROSS_COMPILE}"ar"
$export AS=${CROSS_COMPILE}"as"
$export RANLIB=${CROSS_COMPILE}"ranlib"
$export LD=${CROSS_COMPILE}"ld"
$export STRIP=${CROSS_COMPILE}"strip"
$export ac_cv_func_malloc_0_nonnull=yes
#./autogen.sh
#./configure --host=arm-linux --prefix=你要的安装路径 --enable-shared=yes --enable-static=yes
#make
#make install

另外关于$CFLAGS的设置,可以参考这里

简单来说这样就可以安装成功了,不过还是会碰见一些问题。以下将记录下我碰见的几个简单问题。

1. configure的时候,终端中会显示

checking for arm-linux-gcc… arm-none-linux-gnueabi-gcc
checking whether the C compiler works… no
configure: error: in `/usr/local/tslib':
configure: error: C compiler cannot create executables
See `config.log’ for more details

这个应该需要具体问题具体分析。看config.log文件中的输出信息应该能摸到头绪,我是因为有些依赖没有安装。

#apt-get install lib32stdc++6

安装完之后就没有问题了。

2.undefined macro错误

错误的提示信息是

configure.ac:25: error: possibly undefined macro: AC_DISABLE_STATIC
If this token and others are legitimate, please use m4_pattern_allow.
See the Autoconf documentation.
configure.ac:26: error: possibly undefined macro: AC_ENABLE_SHARED
configure.ac:27: error: possibly undefined macro: AC_LIBTOOL_DLOPEN
configure.ac:28: error: possibly undefined macro: AC_PROG_LIBTOOL

安装libtool即可

#apt-get install libtool

《荒野大镖客:救赎》——侠与江湖的终结

趁着开学事情不多的第一周周末,用两天的时间打通了这款《荒野大镖客:救赎》。

red-dead-2

本作的主人公——John Marston,一个迷途知返的浪子。

游戏系列的中译名叫做《荒野大镖客》,玩过游戏比较多的玩家可能会想起来上世纪80年代由Capcom制作的那款经典的纵轴射击游戏——《Gun. Smoke》(即《枪·烟》。我觉得此处的『烟』应当是一个双关,即又是指牛仔们平时抽的烟,也指开枪之后,枪口所冒出的烟)。由于那个年代大陆玩家普遍英文水平不高,所以根据游戏背景和内容,套用了著名电影的名字,意译为《荒野大镖客》。

老玩家们看着应该会很眼熟。

老玩家们看着应该会很眼熟。

本篇所介绍的游戏《Red Dead: Redemption》虽然由美国游戏公司Rockstar制作,却和20多年前的那款游戏有着千丝万缕的关系。本作所隶属的《Red Dead》系列第一部作品《Red Dead: Revolver》本是由《Gun. Smoke》的开发公司Capcom开发,其自然也借鉴了《Gun. Smoke》中的一些元素。然而由于某些原因,Capcom在2003年取消了《Red Dead: Revolver》的制作,游戏也被Rockstar买下,并于2004年制作完成和发行。

本作《Red Dead: Redemption》(之后简称RDR)是《Red Dead: Revolver》的精神续作,在现在这个年代,算得上是为数不多的西部题材的精品了。

故事背景并非典型的西部片的感觉,故事围绕着John被警探Edger Ross要求杀死旧时的犯罪团伙同伴Bill Williamson、Javier Escuella和团伙首领Dutch这一线索展开。本作是沙盒类型的游戏,地图横跨美国和墨西哥两个国家,地图是GTA4的4到5倍大小,涉及到了上百个NPC,以及前后30年左右的事件。

the-west-detailed-map-small

本作宏大的地图,跨越了2个国家、3个州。

可以说游戏的规模是非常宏大的。然而对比下同为R星制作的游戏GTA5的话,会发现游戏的内容还是有些单薄。

从游戏内容的总量来看,GTA5我清完所有的主线支线大概花了30多个小时,而RDR只花了16个小时就完成了所有的主线任务和陌生人任务。这只是一个直观的数字,能够说明游戏内容的多少。

如果看游戏的内容的话,RDR的任务多集中在『骑马枪战』、『街头决斗』、『抢劫火车』、『保护运输』等具有强烈西部色彩的内容中。玩家时而抢劫别人,时而防备别人抢劫,刚开始玩的话还是有些新鲜感;不过随着故事进行,这样的内容玩的多了,还是很容易审美疲劳。对比GTA5的话,由于载具的多样性和现代的时代背景,游戏内容上天入海、飚车抢钱,显得比RDR丰富了很多。

另外我觉得两作中都有的一个毛病就是地图的利用率太低。RDR的背景是西部荒野,所以地图中的绝大部分都是一片荒芜之地。玩家骑着马在野外到处赶任务的时候,其实地图的利用率是很低的。加上游戏在野外的背景音乐为了烘托荒凉寂寥的感觉,几乎『寡淡』的感觉不到。所以玩家在跑地图的时候会觉得很无聊。这点GTA5由于其游戏故事背景,先天就比RDR好了很多,比如开车的时候可以听听收音机里的新闻,是怎么评价玩家所犯下的『罪行』的。

值得表扬的是,游戏开发者还是预料到了RDR中在野外跑路的无聊程度。游戏中不仅准备了类似于GTA系列中的出租车系统——城镇中的马车(虽然花费相对于收入确实很高,前期几乎属于奢侈消费),玩家还可以在远离道路、水域、城镇、居住点的空地上生一把柴火,在营地里就可以直接移动到目的地或是城镇,不再需要苦苦跑路了。

另外,游戏开发者还在地图中加入了一些偶然发生的小任务,比如帮店家夺回被抢的钱财、救下被匪徒袭击的妇女等等。GTA5地图中的小蓝点和小红点的随机任务应当是从这里借鉴来的,不过并没有RDR中的任务安排的精巧。毕竟GTA5中的三个主角都是匪徒,而RDR中的主角好歹还算得上是一个侠客。

游戏的细节处理的也很好。玩家在城镇中吹口哨召唤自己的马的时候,如果旁边有狗在闲逛,它们就会跑到玩家的脚旁边,乖乖的坐下;枪战击中头部的敌人也不仅仅是出现一片血雾就倒地死亡,而会像真实的子弹击中头部一样形成一个绽开的大洞。

本作和GTA4系列以及GTA5使用了同一个引擎,不过游戏的操作手感更像是GTA4系列。尤其是在角色转身的时候,会感觉对准方向很困难。这在打开箱子的时候制造了不小的困难。算是一个小瑕疵吧。

不过游戏的射击手感还是很好的,辅助瞄准很好用。而且不是像《战地4》一样,必须当敌人在视野中时才能自动瞄准,当玩家躲在掩体后面的时候就不能自动瞄准了。敌人跑动的话,准星也会自动跟随地人移动。这在骑马枪战的时候,减小了不少的难度。

游戏故事虽然以1900年左右开垦西部的美国移民为社会背景,却没有像许多西部片中那样,将主要的笔墨都放在描写垦荒人民的英雄气概上。

游戏中的人物带有着强烈的R星作品的特征(毕竟剧本是Dan Houser写的),人物不是很像传统西部片中的人物——或是侠肝义胆,或是狡诈多端——那样好坏分明;人物更多的是想GTA系列中的人物,多多少少的有些荒诞的神经质。其中一个比较明显的例子是『Flowers for a lady』的那个任务中的老大爷,他给我的感觉和GTA5中的『疯子追星族』大爷大妈很像,荒诞的不像是这个世界中的人。

Rdr_john_marston

Clint Eastwood在镖客三部曲中的形象实在是太经典了,本作中John Marston的形象应当是有所借鉴。

主角John Marston虽然长得很像电影镖客三部曲中的Clint Eastwood,不过却只能给人留下一个『老实』的硬汉的印象,并不能算是一个『英明』的硬汉形象。

从故事开始John Marston被警探Edger Ross要求追杀Bill Williamson匪帮开始,John就被各种人利用,显示被Armadillo的Marshal利用,然后被『科学骗子』Dickens和『寻宝疯子』Seth利用,到了墨西哥之后又被当地的当权军阀Allende和反叛势力Reyes来回利用,甚至险些命丧墨西哥;在肃清了Bill Williamson、Javier Escuella之后,又被Edger Ross以妻儿安全威胁,继续肃清Dutch;甚至Dutch在死前警告John,警察为了薪水,迟早有一天会肃清John之后,John依旧天真的以为自己可以顺利洗白,过上平静的牧场生活。

John作为一个亡命徒,却并没有亡命徒的觉悟。相对比之下,带他入行的Dutch却对自己的天命有着清晰的认识。在John将他逼到悬崖边的时候,Dutch清晰的认识到了,自己纵横多年的江湖早已经不存在了,自己也不再是自己当时那个劫富济贫的侠客了。完美主义者Dutch看着这个与现代社会格格不入的自己,只能选择背身跌下悬崖自我了结。

如果我们同时把眼光转向墨西哥,会发现旧军阀Allende死了之后,原先的革命者、现在的新军阀Reyes并没有把墨西哥变得更好。在主角转换成Jack之后,如果买一期报纸,在编号为213的报纸的最右侧会发现一篇题为《PRESIDENT REYES DENIES HE IS A TYRANT, DESPITE MASSACRE》的文章。文章内容大概是Reyes命令部队射杀了对政府和平示威的上千人。从文章内容中我们也可以知道Reyes在推翻了上任军阀的统治之后,自己也变成了上任军阀的样子,修建了华丽的总统府,并准备修建音乐厅等建筑物。然而事实上,墨西哥依旧处于无政府的江湖状态,自命不凡的侠客们依旧在行走四方,普通的百姓依旧生活贫苦。

如果拿Reyes和Dutch对比的话,会发现两者之间多少有些相似,一开始都是充满热忱的理想主义者(或者说只有热忱?),成为一方豪强获得权力之后理想变质;不一样的是Reyes成功的上位了,而Dutch因为联邦政府的干预在权倾一方之前就被肃清了。

总的来说,历史总是在进步的,以豪强Allende、Reyes和侠客Dutch Gang的一伙们为代表的江湖社会总会被历史的车轮所碾碎,个人所被赋予的权力会被逐渐分散,逐渐进化成一个现代社会的样子。

red-dead-redemption-14422-1920x1200-red-dead-redemption-2-would-you-want-it-as-rockstar-s-2015-surprise-game

John叔拿着枪行走江湖几十年,却终无法逆历史潮流而行,无法像终结敌人一样,用枪终结自己被诅咒的命运。

短文末尾,推荐一下RDR的OST,为西部荒凉气氛增色不少。

算法学习笔记(3):插入排序、归并排序与逆序数

前些天在挨个做hackerrank上的题目的时候,碰到了这么一道题

题目的完成率并不高,只有百分之三十六点多,我估计了下难度,自己应该是做不出来的,最后果然没做出来。不过在Discussion下面还是看到了些有用的帮助,有人说用mergesort能做出来。于是又仔细的想了想,还是花了些力气做出来了...

题目的内容是计算插入排序一个序列的移动元素的总次数。实际上是计算的序列的逆序数

逆序数的定义上面那个wiki的链接里说的挺清楚的了,数的就是反序排列的数字对数。

比如[1,3,2]的逆序数是1,在插入排序的时候,2会向左移动一次,整个序列变成了[1,2,3]。

[2,3,1]的逆序数是2,在插入排序的时候,1会向左移动两次,整个序列变成[1,2,3]。

hackerrank在排序这一章前面也有一道题是计算插入排序移动次数的,当时按照题目的提示,使用的直接在插入排序的时候,移动一次,加一次,最后依次数出来移动的次数。当然这个的时间复杂度就是,在序列比较长的情况下很容易超时。这种比较『暴力』的方法,显然不适合本题。

mergesort是一种比较简单的方法。可以很容易的想象出,在merge过程中,如果『小序列』非空,每当『大序列』的最小元素被选出来,就意味着逆序数需要自增目前『小序列』中元素个数那么多,因为这个时候『小序列』中的所有元素都比位于他们之后的『大序列』中挑出的最小元素大。

而且mergesort的时间复杂度是,已经是比较排序的最优了,所以也理应在本题中不会超时。

知道这个关键点,代码实现就很容易了,就是增添个自增的语句而已,代码如下所示。

def merge(a,b):
    global answer
    a_flag = 0
    b_flag = 0
    result = []
    while a_flag<len(a) and b_flag<len(b):
        if a[a_flag]>b[b_flag]:
            result.append(b[b_flag])
            answer+=(len(a)-a_flag)
            b_flag+=1
        else:
            result.append(a[a_flag])
            a_flag+=1
    if a_flag==len(a):
        result.extend(b[b_flag:])
    else:
        result.extend(a[a_flag:])
    return result

def mergesort(l):
    if len(l)>1:
        mid = len(l)/2
        a = l[:mid]
        b = l[mid:]
        a = mergesort(a)
        b = mergesort(b)
        return merge(a,b)
    else:
        return l

n = input()
for iterate in range( n ):
    x = input()
    a = [ int( i ) for i in raw_input().strip().split() ]
    answer = 0
    mergesort(a)
    print answer