Review: Accepted (2006)

February 17th, 2008 No Comments »

"There are a lot of things in my life that I thought were real and ended up being fake. Why can't the opposite be true?"

- Monica, in Accepted (2006)

South Harmon Institute of Technology.

S.H.I.T.

突然觉得好笑,人们对旧体制的挑战总不免被盖上如此称号。

关于电影本身其实我没有什么想说的;片中主人公所做不过是很多人想做而不敢做之事。

但,我们真正需要的,除了一种藐视一切挑战一切奔放创造的精神,除了这青春的意义,还有什么?

一直想说的一句话。If this is how this is going to be ... then SO BE IT. 这不仅限于本文。

最感动的部分还是片尾那段Bartleby对抗Dean校长的辩论。非常激情的演讲。

Barteby:

     Nah, I'm not going to answer your question, 'cause you guys have already made up your minds.
     I'm an expert in rejection, and I can see it on your faces.
     And it's too bad that you judge us by the way we look and not by who we are.
     Just because you want us to be more like them when the truth is …
     We're not like them. And I am damn proud of that fact.

*

     Well, what about you parents?
     Did -did the system really work out for you?
     Did it teach you to follow your heart, or to just play it safe, roll over?
     What about you guys?
     Did you always want to be school administrators?
     Dr. Alexander, was that your dream?
     Or maybe no, maybe you wanted to be a poet.
     Maybe you wanted to be a magician or an artist. Maybe you just wanted to travel the world.
     Look, I - I - I - I lied to you. I lied to all of you, and I'm sorry. Dad, especially to you.
     But out of that desperation, something happened that was so amazing.
     Life was full of possibilities. A - and isn't that what you ultimately want for us? As parents, I mean, is - is that, is possibilities.

     Well, we came here today to ask for your approval, and something just occurred to me. I don't give a shit.
     Who cares about your approval?
     We don't need your approval to tell us that what we did was real.
     'Cause there are so few truths in this world, that when you see one, you know it. And I know that it is a truth that real learning took place at South Harmon. Whether you like it or not, it did.
     'Cause you don't need teachers or classrooms or - or fancy highbrow traditions or money to really learn. You just need people with a desire to better themselves, and we got that by the shitload at South Harmon.
     So you can go ahead, sign your forms, reject us and shoot us down, and do whatever you gotta do. It doesn't really matter at this point. Because we'll never stop learning, and we'll never stop growing, and we'll never forget the ideals that were instilled in us at our place.
     'Cause we are S.H.I.T. heads now, and we'll be S.H.I.T. heads forever and nothing you say can do or stamp can take that away from us!
     So go!

Problemset Analysis: Benelux Algorithm Programming Contest 2007

February 17th, 2008 3 Comments »

题外话..一会儿的TCO 显然又不能做...

哎,TC这个TCO/TCCC的年龄限制有意思么……难道仅仅参加比赛都不可以。。。还是Baidu厚道-_-

================================

BAPC 2007 题目分析

整体难度中等吧,比较适合Warmup的一套题……

题目数据请参考官方网站ZOJ 2912 - 2921.

Problem A: Average distance

描述:求一棵树上所有点对距离总和的平均值。(N <= 104)

经典题。直接DFS统计。

Problem B: Bus Pass

描述:给出一张图及公交线路(|V|<= 104)。要求选择点集S: {距点P距离不超过X的所有点}, 使给出的所有点对(<= 200组)均在以S为点集构成的新图中连通。最小化X。

简单的BFS。

Problem C: Cutting Banknotes

PKU Monthly 2008 – 01第一题简化版本。略过。

Problem D: Dice Password Security

描述:给出一些单词,求长度为K且恰好包含P个单词的组合数目。

简单DP。

Problem E: Lingo

描述:给出一个8*8的棋盘。棋盘中一些格子被染成黑色。现在需要将恰好K个格子变成白色,使得存在同行/同列/同对角线全白色格子。问随机选择K个格子成功的概率。

容斥原理(218 * 状态生成复杂度),或者状态压缩DP (一般方法:8 * 64 * 28 + 2 + 1 * 256,需要剪枝).

P.S., 在ZOJ上状态压缩DP必须写整行转移的版本,否则状态是存不下的……

Problem F: Splitting the Loot

描述:给出集合S,初始仅包含一个数X <= 105, 每次我们可以从S中删除一个数Y并插入P, Q,且Y, P, Q需要满足(P + Q) * ratio = Y (0 <= ratio < 1). 要求最后S中包含由不少于N(<= 50)个数组成的集合S’,且S’中的数分别不小于S[0] .. S[N -1]。最大化S -S’中所有数之和。

TC流的经典题目,二分+check。

P.S., 注意这里最显然的思路不能保证利润最大化。

Problem G: Pachinko

描述:小球从棋盘顶下落。碰到障碍物时有均等概率落向左边/右边。小球落到某些格子中有固定得分并中止下落。问从棋盘顶哪一列放手期望得分最大。

模拟题。

Problem H:  Hiking

描述:给出平面上等半径的N个圆 (N <= 100), 问从S到T且保证路径中每一段都在至少一个圆内的最短路长度。

易见交点个数很容易达到O(N2)级别,而判断一条线段是否在圆内的复杂度是O(NlogN), 所以总建图复杂度高达O(N5logN)。 而这个复杂度是确实可以达到的。

但是上面的分析忽略了一个事实,就是那些被圆严格包含的点其实是会在求最短路过程被忽略的。考虑我们得到的区域的特殊性,由边界构成方式知有效点个数不超过2*N个。因此直接求最短路即可,总时间复杂度是O(N3logN)。

P.S., 注意这里我们可以一边求最短路一边处理出路径长度。

Problem I: Ranking

描述:模拟ACM排名系统……具体规则看题目

唯一需要注意的问题:两个队需要通过比较它们最晚排名不同的时间来break tie。

Problem J: Stock

描述:给出N <= 105天中每天的买入股票数量,最大卖出数量和卖出价格,求最大化利润方案。

易见最大卖出价格->最后天的卖出顺序一定是最优的。那么直接模拟即可,时间复杂度为O(N).

================================

其实写了分析才发现这套题其实没什么特别值得说的……

所以以上内容仅供参考……