Lunarmony’s Journal

这学期某课程的某Project源代码。。。

本来觉得没什么的，后来整理源文件的时候才发现一个很神奇的现象。。。

g++编译出来的可执行文件8.2MB... - -!!!!

好奇之下拿vc++编译了一下……然后可执行文件就只有不到0.1M了....

研究原因中……

(编译器版本: g++ 3.4.5, vc++ 15.00.21022.08)

We would not say goodbye even if we know the results beforehand.

We would not leave even if the judgments have been issued before the trials were held. 

*

Still, the result hurts.

But all those negative feelings dissipate into nothingness,

when we come to terms with the fact that we're still standing together.

Always, and ...

forever.

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

ACM/ICPC World Final 2008, Competition Day

Lunarmony's perspective

(似乎被我写成了流水账……简明版的大家还是参考FreePeter或者LynnKaye的版本比较好)

或者是空气或者是温度的原因，我觉得高海拔地区还是很适合我的。来之前还担心会有轻微的高原反应……在Banff呆了几天发现这个可以完全忽略不计。

转回话题。

一开始扫题，读到E差点被我误判成简单题，后来想了下发现判重处理还是不是太显然的。继续读了F, 没有立即反映过来I感觉是容斥+YY就可以做，跳过。然后读了G/H，H倒是反映过来了，可我实在没有兴趣写这个模块题……这个时候有点小郁闷，问了下peter / LynnKaye才发现他们也没有比较可做的题。情绪不太好直接翻过来看K, 发现是道[100][100][4][2]的最短路。。。按约定传给peter, 接着发现J也是道送分的计算几何。I么，刚开始我居然被数据范围欺骗了……感觉有点像容斥但是可做，丢到了pending set里面。

读+想完这些题的时候应该已经30分钟左右了。peter在准备写K, 跟LynnKaye交流了一下发现前面的题似乎我们要么没反映过来要么比较麻烦，有点郁闷。当然手上有两道可以写的JK, 大体规划了一下1个小时左右出掉这两道题问题应该不是很大。peter说A可能可以写但是他不确定。

这个时间我和LynnKaye在分别推不同的题。应该到50多分钟我对E有个实现的猜想，问peter发现K似乎有点小问题……然后我就有点倾向peter暂时下来检查下代码，不过经过讨论还是Peter继续调试。

到了1个小时左右(?) 场上B/F/J/K都有人过了，LynnKaye跟我交流了一下F的思路但是有个细节我没想清楚，pending……后来在peter调试的空余时间，我把键盘抢下来写了一个E我的理解版本，不过发现这样还是判不掉重复情况。这个时候场上总体情况似乎不是很乐观，第一名大概已经3题左右了。

然后就发生了peter所说的我再次抢下键盘写J的事情了。写完发现Sample #2不过，有点郁闷，直到peter 1Y K若干分钟后才发现一个p打成q的低级错误。100多分钟1Y J。

大体分配了一下题，但是我一直到这个时候还是完全失误的没有发现LynnKaye当时状态不对……直到peter拿来diet coke的时候才意识到问题……

后面一段时间还是很顺的，LynnKaye帮忙推了一下A然后是2Y F - 1Y A - 1Y B (?)，5题之后我们rank也爬到了第7。讨论了一下决定我去写D & peter想I.

写D的时候完全不敢加速，感觉这种题很容易因为某个细节挂掉。大约是在我写完框架的时候peter跟我说I是DFA, 这时我才反应过来I明明就是当时命的某题的变体-_- 马上就有抢过来的冲动。。。

后来跟LynnKaye交流了一下G的思路，发现理论上可以抖，但是由于交流失误，我们决定先把这道题pending掉。

最后一段时间只能说写的还是有些郁闷的。当时(210min ?)的大体目标就是先写完D/I 然后有时间的话交一个G, 但一些比较耗时间的细节因素耗掉了大量时间……基本是到280分钟左右过I & 285分钟编译过D。然后样例不过……静下心来看程序，但发现bug的时候已经只剩5分钟左右了。最后那个bug还是没改掉。。。

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

其实有些时候差距真的是在细节。

记得曾经读到过Jordan苦练三分线投篮，只因为对手不可能让他靠近篮板的故事。

而对于Final来说，大家不过是在拼反映，代码速度与准确率。

当然还有心态。

这点看似微不足道的差距能说明什么？

It's all about how you choose to structure your perception, how you choose your attitude toward certain things.

peter曾经跟我说过，我们有的是20%的付出所带来的80%的结果，但是我们没有做好的就是其余80%的付出。

很多时候差距不过是一念之间，不过是微小的数字上的差距。

一个人决定100%的投入而另一个人只投入98%。

看上去微不足道的事情。

但10年，20年，50年之后，这样带来的是什么样的结果呢。

很难想象。

*

We exist and fight on

for reasons beyond simple winning and losing

For results are nothing but abstractions in the equation of life

What we cherish

What we value

Is

The path which we've walked together

The tears of pain and joy we shared

The memory recorded in eternity

And ultimately

The love, support, and caring that defines Amethyst

- 12:43a.m., April 12, Vancouver, CA

You are only a whisper away
But I can’t touch your heart
If the words aren’t enough to bet your soul
I’ll give you the moon

You are always shining sun or rain
Like a violet stone
I close my eyes but you never fade
But you never disappear

I feel alone
Can’t you see me standing on the verge of blue?
I’ll be watching all the stars till they are gone
Should I know nothing could make me kiss you less?

Oh I’ll be waiting for you to tell me what is love
I don’t know how to be loved, how to be by your side
Morning lights shine in my room
I’m holding dreams of you
It may take no less than this pain
But I can’t stop loving you

Feel my heart
You have never know that you have all of me
Every time I see you I’m falling in love
I can live or I can’t live without you

Oh I’ll be waiting for you to tell me what is love
I don’t know how to be loved, how to be by your side
Morning lights shine in my room
I’m holding dreams of you
It may take no less than my life
But I can’t stop loving you

- Yoshiki, Eternal Melody II

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

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

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

BAPC 2007 题目分析

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

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

Problem A: Average distance

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

经典题。直接DFS统计。

Problem B: Bus Pass

描述：给出一张图及公交线路(|V|<= 10⁴)。要求选择点集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个格子成功的概率。

容斥原理(2¹⁸ * 状态生成复杂度)，或者状态压缩DP (一般方法：8 * 64 * 2^{8 + 2 + 1} * 256，需要剪枝).

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

Problem F: Splitting the Loot

描述：给出集合S,初始仅包含一个数X <= 10⁵, 每次我们可以从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(N²)级别，而判断一条线段是否在圆内的复杂度是O(NlogN), 所以总建图复杂度高达O(N⁵logN)。 而这个复杂度是确实可以达到的。

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

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

Problem I: Ranking

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

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

Problem J: Stock

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

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

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

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

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