VegetableB的博客

2284 Inversion Number
第一年暑假的题目，来源于线性代数老师提出的思考题。
似乎很难用数学式子来表示，不过用计算机来计算就不难。

2572 Color ASCII Characters
来源88的qmd。简单bfs。不算好的一题，很多地方没说清楚。

2769 Get The Treasure
Polya定理。看sgu282想的。应该比原题简单吧，我感觉。

2858 A+B=C
数论题，中国剩余定理。应该算比较纯原创的一道吧。
难在几个数直接的关系处理，还有要大数比较麻烦。

2864 Catch the thief
最短路。sgu301改的。最后有个时间超出是0的trick，算是没有讲清楚的问题。

2866 Overstaffed Company
参考何林的冬令营论文《数据关系的简化》。
加了个离散化，不过不限于那种方法。

2841 Galaxy War
弦图＋色多项式，看黑书的时候想到可以把这两个东西合起来出道题。
不过后面加了提示，大大降低了难度。

2852 Deck of Cards
来源手机游戏。做法参考lrj的free candies。中等难度。

2854 Fish and Her Bowl
半空间交，主要来源lrj出过的一题和实验室项目。
不过数据都是随便手写的，有待加强-.-

2894 Arrange the Problem Set
随便拿来玩的，简单最佳匹配，除了要两个key外。

2930 The Worst Schedule
网络流。可惜不能证明方法是对的，或者是方法不对但是数据没错。
惭愧。。。对的话还是一道不错的题目。。。

2959 Obstacles
BT几何题，要用到圆的交和补，反正非常的麻烦。
也算是我觉得还可以的一道吧。

2950 Dice Matrix
搜索。处理手法和07年北京的一题差不多，要先把答案都打出来。
总的来说难的地方还是在于写出几种旋转的方法以及hash。

2976 Light Bulbs
简单题，枚举。

3203 Light Bulb
简单几何题，某天晚上在寝室夜读想到的-.-

3205 Derivative
前一年的求导和实验室做项目用到的对向量求导数结合得到的。
方法和参加过的一次网上赛的一题差不多。

3206 Disaster Area Reconstruction
目前唯一的黑点-_- 很久以前就想到的idea，但是当时想到了反例，
后来又忘了我想到了反例，于是就出出来，而且似乎验证的人都没发现问题 >_<
本来是想出连通块+dp的……

3215 Cartoon
四边形不等式dp。和之前常见的模型有些不一样的模型，
TIC09复赛有类似的模型，我用同样的方法过了。

3223 Journey to the Center of the Earth
最短路。final去玩的时候排队时想到的-.-
内部选拔的时候效果很好，几乎没人能想到。
但是三年之后似乎就变得相当简单了。:(

3292 Shuffle
05年国家队论文：潘震皓《置换群快速幂运算研究与探讨》

3301 Make Pair
毫无疑问的签名题-.-

3303 Pachinko
还是三年前的选拔题，字符串处理+dp
不算很难，但是似乎题目的长度吓倒了很多人了-.-

3312 8*8
专门给8周年赛出的一道题，dp。和TC上一题差不多，再加上表达式计算。
因为刚写过表达式的问题，所以顺手出了这么一题

3317 Murder in Restaurant
弱化过的题。专门给校赛省赛用的。

3320 Break Out
烦到死的dp。本来有一题是没有打穿的情况的，
加了这种情况以后繁琐程度翻了一番……

3325 Next Expression
比较麻烦的表达式处理和树处理。某个面试题中遇到的子问题。
主要是不能直接递归这点比较麻烦。

3326 An Awful Problem
idea来源于数学家的故事-.- 描述和内涵都很糟糕的题目，
出得比较急，也是专门给校赛省赛用的。

题目的意思是给定n个区间，要求区间[ai, bi]里面取的数不能少于ci个，问最少取多少个可以满足条件。n最大值为50000，ai, bi的取值范围也是50000。现在设ai, bi的取值范围为m。

第一种解法是贪心。先把区间按右端点排序，每次取数的时候尽量往右边取。因为后面的区间的右端点比当前区间的右端点右，所以往右取可以保证结果是最优的。每次先要查询区间里面已经被取到的数的个数，然后不足的部分逐个取出。查询部分我是用线段树来统计实现的。快速找到区间里下一个还没取到的数我是通过一个类似并查集的结构实现的，记录每个数左边第一个没被取到的数，然像并查集的路径压缩那样优化。总的时间复杂度是O(nlogn+nlogm+mlogm)，运行时间为320ms，其中读入和排序画了250ms。这是我第一个写的版本，用纯C写的，所以排序会慢一点实现较为复杂，代码量也有点大。

第二个做法是最常见的差分约束系统。这是我参考LeeMars的解题报告之后写的。以S[i]表示0到i之中取的个数，那么有S[i-1]+1>=S[i]>=S[i-1]，S[ai]-S[bi-1]>=ci。把S[i]看成点，S[i]-S[j]>=t就连一条权值为t的有向边从点j指向点i，那么从S[-1]到S[i]的最长距离就是S[i]的最小值，可以通过bellman-ford来求解。但是点有O(m)个，边有O(m+n)条，直接做，即是加了Yen氏优化也是很可能超时的。这里LeeMars的解题报告里面说到了对这种线状的图的一种特殊的优化：在更新点的时候，先把往前的边更新一次，然后再把往后的边更新一次。这样确实快了很多，在用了和上一个方法一样的排序方法时也是320ms通过的。仔细分析这样做的复杂度，松弛操作最坏情况是要迭代O(n)次以后才会结束的，所以这个做法的复杂度是O(nlogn+nm)的。但是之所以可以这么快通过，我认为是数据比较弱的原因。

第三种解法有点像是前面两种的结合。考虑上面一种做法的S[i]，S[i]是递增的，而且相邻两个之间最多相差1，所以每个约束的图像就是从S[bi-1]出发的水平线-斜线-水平线三段组成的折线，并且斜线的斜率都是一样的。S[i]就是经过这点的所有折线中的最大值，所以这种做法就是对区间按左端点排序后，从左往右扫描得到每个S[i]的值。因为只有线段左端点端点处的S[i]是需要用于更新后面的S[i]，所以只需要求这n个S[i]以及最后的答案就可以了。在查询折线最大值的时候，我是用了一个优先队列来加速的。由于进入优先队列的每段折线第一段的水平线总会不低于当前的S[i]，所以不需要记录这段的高度，为了避免这段高度的影响，我采用记录斜线在x轴上截距以及最后高度两个数来的方法来记录每个约束，这段折线在当前的S[i]个高度可以通过这两个数运算得到。最后总的时间复杂度是O(nlogn)，在ZOJ上跑了230ms，不过这个是用C++写的，STL的sort比qsort要快一些，输入和排序只要180ms。

不过，上面的时间也是仅供参考的，因为还有更多的优化还没有加上去，例如用桶排代替快排。相信应该也会有更多更好其他的做法。

寒假里面见了很多很奇怪的物品，让我不得不感叹，地球人实在太有创意了。
惟一的遗憾是我没有把这些都一一拍下来，只能文字描述一下。

1. 这件物品见于好又多超市，大家可以猜一下是用来做什么的，答案稍后公布。
一个全木制的物品。主体圆桶形，外径约4cm，高约5cm，桶壁约0.5cm厚。
一段开口，另一段封闭。桶身中部有一圆孔，孔中有一个像水龙头状的螺丝拧在上面。
螺丝约1cm粗，全部拧进去可以到达另一边的桶壁。

2. 好又多里面还有很多很奇怪又很有才的物品，譬如说很小巧的开瓶器，
一下把一个苹果分成八份的切苹果器，还有可以让人把煎蛋煎成心形的煎蛋器（？）。

3. 这是一种小饰物，跟酒楼里面吃到的小餐包没什么两样，但是不能吃 - -
软软的，连气味也是一样的，有的上面还有用“巧克力”画的笑脸图案。
据介绍，这玩意可以在用鼠标的时候垫在手腕下面防止疲劳，
也见到一些是挂在钥匙扣上面装饰用的，估计不知情人氏会想去吃了吧。15－20元。
最奇怪的是，这东西居然出现在陈家祠里面，
而且周围都是卖画、雕塑之类的艺术品，显得很格格不入。

4. 下面介绍的是玫瑰花。这是一般的玫瑰，而是用布做的玫瑰公仔。
形状跟真的玫瑰差不多，只是大小大了几倍，一枝有半米到一米高，还有各种颜色的。
情人节的时候觉得真的玫瑰贵的话，买几枝布做的相信也不错。
见于zjg lt的文具店，ms 15一枝。

最后公布一下1的答案，那个是开核桃器 - -

Digimon Savers据说是官方的第5部digimon，但是我就一直都不认同。
之前一直听说第5部应该是编年史，也有一部OVA是讲多路兽的，
所以一直觉得下一部digimon应该就是那部。
但是没想到突然冒出来这么一部，OP也不像话，
剧情也有无数的漏洞（虽然之前几部也有不少），人设也不喜欢，纯热血……
虽然画面是精美了不少，但是完全没有了以前几部的感觉。
没想到这次TVB就直接以数码暴龙5来命名了，让我不知道该怎么说好……

先讲讲配音方面吧。一开始就看过了原版，也大概了解了原来的配音和人物的性格。
大的声音热血是够了，但是就是感觉听起来像古惑仔……
托马的声音怎么听怎么不像博士，缺少了书生的气息……
知香还不够可爱，小百合缺少了那种母亲般的温柔……
其他感觉还好，萨摩的雷霆还缺一点那种管理者的气势，但还可以接受。

部分翻译看起来比较囧，水银兽（人家原来好歹是以奥林匹斯山十二神之一来命名的）、
要塞兽（直译是黄金乡兽，这么译怎么看都少了一些意味吧）等……
还有digi-soul charge那里，charge翻译成充值，我感觉很不妥，
又不是公交卡，叫什么充值？我觉得译成充入还差不多……

粤语OP基本跟以往差不多，在原版的OP1的基础上改成粤语的，据说是一个叫周柏豪的唱的。
不过我还是严重的不认同的原版的OP1，不是和田刚司唱的始终没有digimon的风格，
后来和田刚司唱了OP2，算是有回一点感觉，但始终不是OP1，没有原来那样的地位。
对于粤语的OP，认同感比原版OP1多一些，毕竟感觉词有部分还是可以的，
但是原版op1给我的印象太坏了，以致这首也不是很喜欢。
希望能听到粤语的OP2，但是估计可能性很小，TVB的片头和片尾一般制作好的都是定死的。

这次看了TVB版的。听说国内因为裸露镜头的关系，一直没有引进第五部，但是我知道TVB是引进了这部的，可惜就像其他动画一样，往往因为开学的关系而不得善终。基于这些原因，这次碰到了还是忍不住去看了一下，虽然原版的之前就看过了。

TVB的配音基本上已经很熟悉了，因为实在没有多少配音的人员，小时候看多了也基本听熟了。兔的配音感觉还好，和原版的还是有些区别，也说不出区别在哪里。chibi chibi moon的感觉不是十分的好，感觉她的可爱的不够。

似乎TVB的版本有两三的地方是剪过的，时间只有22min左右，包括片尾曲，而且OP和ED应该加速过。我感觉比较明显的有两处：一个似乎是裸露镜头的地方，另外一个是刺伤出血的地方。第一个地方感觉BGM有些明显的不连续，虽然不知道是不是我听错或者本来就是这样。因为既然可以把日语去掉重配，那么把BGM重新修饰也是没有问题的，但是如果有明显的不连续感觉是很部应该。当然部排除是工作人员偷懒的问题。第二个问题也是比较明显的。前面只有一个停下来、她们的剑交叉着的镜头，之后就都停下来，把剑打断的镜头，完全没有刺伤了加拉西亚的迹象。原版的应该有一点血出现，说明是被刺伤了的。似乎TVB一直都是这样，喜欢把带血的镜头的剪掉，像《中华一番》里面的有个拿刀自杀的镜头也是被剪掉了，大概是觉得血腥了吧。

还有就是最后一幕，似乎那对话作为结尾不是很有结束的感觉，不知道是不是有些改动了。还有就是之后放回《月光传说》的时候，应该是比较明显的被TVB卡掉了放原来的ED，似乎也更少了结束的气氛。当然，小卫说出国读书的事情也不了了之了 -_-

PS 点评一下和star lights分别的那个场面。似乎分离的场面一直都比较容易体现对人物的刻画。之前看过有人评论说，和小卫在机场分别的场面，很好的表现了小兔的成长。从以前碰到什么哭一场的小兔，到现在为了不想大家一起哭而强忍着自己的泪水，到后来还是忍不住，说了一段感人的话。到了结束，经历了更多的事情之后，我觉得小兔也变得更为成熟了。星野和她告别的时候，她就装作没听懂的样子，一来免了小卫为此吃醋，也断了星野的年头，二来在这分别感伤的时候插科打诨一下，可以适当调节一下气氛。等到他们都走了以后，小兔才轻轻的给星野说了一声谢谢，可见她是明白他的心意的，但也只能在他听不到看不见的地方默默的感谢和祝福他了。不过，这些我也就这次才看得出来。

PPS1 据说这是美战200话，好整，不知道一般以一季13话日本电视台当时是怎么安排的。

PPS2 为什么星野也叫seiya呢？-_- 翻译问题还是什么问题呢？

24周岁那天，sgu提交700，ac200……

于是专心干活和作业去，暑假再继续……

shall we talk
曲:陈辉阳词:林夕编:金培达

明月光 为何又照地堂
宁愿在公园躲藏 不想喝汤
任由目光 留在漫画一角
为何望母亲一眼就如罚留堂
孩童只盼望欢乐 大人只知道期望
为何都不大懂得努力体恤对方
大门外有蟋蟀 回响却如同幻觉
shall we talk shall we talk
就当重新手拖手去上学堂

陪我讲 陪我讲出我们最后何以生疏
谁怕讲 谁会可悲得过孤独探戈
难得可以同座 何以要忌讳赤裸
如果心声真有疗效
谁怕暴露更多 你别怕我

屏幕发光 无论什么都看
情人在分手边缘只敢喝汤
若沉默似金 还谈什么恋爱
宁愿在发声机器面前笑着忙
成人只寄望收获 情人只听见承诺
为何都不大懂得努力珍惜对方
螳螂面对蟋蟀 回响也如同幻觉
shall we talk shall we talk
就算牙关开始打震 别说谎

陪我讲 陪我讲出我们最后何以生疏
谁怕讲 谁会可悲得过孤独探戈
难得可以同座 何以要忌讳赤裸
如果心声真有疗效 谁怕暴露更多

陪我讲 陪我亲身正视眼泪谁跌得多
无法讲 除非彼此已失去了能力触摸
铃声可以宁静 难过却避不过
如果沉默太沉重 别要轻轻带过

明月光 为何未照地堂
孩儿在公司很忙 不需喝汤
shall we talk 斜阳白赶一趟
沉默令我听得见叶儿声声降

每次听到这首歌，都不免感慨，为什么人和人之间的沟通就这么难呢？“孩童只盼望欢乐 大人只知道期望”。父母希望孩子好好学习，长大才会有更好的生活。而孩子不懂这些，只在乎眼前的欢乐。乍看父母们的观点是很有道理的，只是很多父母都忘记了是为了孩子未来美好生活的目的，连孩子童年的欢乐生活都剥夺了。“成人只寄望收获 情人只听见承诺”。如果说前面说的是代沟，那么情人之间还为什么会有这么多的矛盾呢？如果情人之间失去了相互的信任，在一起只是相互应付对方，那又是为了什么谈恋爱？不禁感叹，现代科技进步，给交流带来了方便，但实际的交流机会却大大减少了，人之间反而变得更加的冷漠，就像最后说的那样，只会忙自己的工作，疏于和别人的交流。每听到此，我就感到一种淡淡的悲哀流过心头。人生难道就是这么一种轮回？小时候开始不懂得父母的想法，长大了又不知道如何和情人沟通，到老了，明白了沟通的重要性了，下一代却依然不了解你的想法。

想想以前，每次和家里通电话，一说就是一个小时。虽然都是他们再说，但是说了一个小时还兴致不减，每周都会在固定的时间打电话过来，我也一般都会在寝室的电话前等着。而现在，他们打电话过来的时候我还经常不在，还要等我慢慢回来了才会打电话回去叫他们打过来，还经常是很晚才打过去以至他们说了一会就怕影响我和室友的睡眠而不敢聊太久。昨天算是早了一点打过去，他们却怕说的时间太长影响我工作而早早的就结束了话题，才说了二十分钟。而我，只会在父亲节母亲节或者他们生日这样的节日，透过电话生硬的祝福他们节日快乐，也不会主动关心他们的生活，连即将到来的父亲生日都不能回去和他祝贺，只会一个人在听着陈奕迅的歌，每年写这么一些文字来反映自己的内疚和不安，然后，又继续着那种宅男的生活……所幸的是，我的家人基本都还很健康的生活着。只是，这不是淡薄和家人交流的借口……

——乱语于2008父亲节未眠之晨

　　D、孤魂野鬼

　　你并不会对荣华富贵的生活过于渴望，你想要的只是舒适随意就好，不喜欢忍受压力，希望自己能够活得更轻松。这样的你，不喜欢思考人际问题，遇到自己无法解决的问题或是难于应付的人时，就会想要逃避。你经常会觉得如果可以什么都不用做不用想该多好，会渴望一个只属于自己的空间。你虽然对生活有着自己的规划和设想，但是却总是无法下决心去努力做到，总是无法让自己更积极地去实行一些人生计划。这样的你，对待生活总是有着一份闲散和无所谓。因此，遇到什么样的人或是鬼对你来说都是无所谓的，你并不会去在意。

http://astro.sina.com.cn/t/2008-04-29/144650518.shtml

感觉还是有些符合的……

好吧，我果然脱离时代很久了。那么，先简单更新一篇吧。

顺便怒一下为什么会有些这么诡异的网站来引用我的，要想想办法怎么样批量xx掉他们。