分类存档：默认分类

随着复变考试以及我的补眠结束，终于有时间写这篇小结了。数据结构晚上快速看一下课件明天直接去考好了T.T
今年Regional，除了浙大出题的长春赛区，国内的赛区去光了，战绩是

1. 天津正式(季军 + K题FB) 小结：http://edwardmj.wpengine.com/?p=768
2. 金华打星(银牌) 小结：http://edwardmj.wpengine.com/?p=820
3. 杭州打星(银牌)
4. 成都正式(季军 + E题FB)

赛前prowindy一再强调别去北大出题的赛区，现在看来，还真是对的……
我一直说复旦出题很靠谱，虽然有点难被虐成狗，但是我觉得做起来很舒服，现在看来，也挺对的……
就像是冥冥中被克制了一样，中间两场总有万人轮的题被卡到死，然后感觉差不多要过了却死活弄不出来。
下面说说我对我们队伍的看法吧。

1. 首先必须注意到的一点是，我们每场比赛到最后一刻都还在调试程序……
   这说明了什么？
   我们根本没把自己所能做(该做)的都做出来。
   这个问题可能代表了两点，一个是我们这个团队对算法的实现能力已经圡成狗了，另一个是我们会写的太多了，真的写不完……
   其实说白了就是代码实现能力和YY能力的不匹配？
2. 我一直觉得每个人都比较全面的队伍才比较容易配合，这样无论和队友讨论什么，都能够互相理解
   讨论永远是建立在双方都对这东西有一点了解的前提下的
   但是时间短暂这个东西太难强求了，毕竟我们和THU，PKU的OIer队伍不一样，个人能力不是每个人都比较逆天那种……
   希望到final的时候，我们每个方面至少有两个人比较懂，也就是注意刷题的时候不要只刷单一方向的。
3. 我发现我们现在的策略基本是：基本题就不提了；见到物理以及数学题直接扔zYc；见到比较繁琐的蘑菇题、几何等直接给prowindy；然后数据结构、图论、字符串之类的问题都直接给我。
   而我的那一块队友比较难帮上忙，如果要帮忙看代码的话可能也要讲好久，于是一般是放我单干。
   zYc那一块大家都比较相信他。其实有时候不需要推公式，直接来点暴力的递推就足够了，而这种时候zYc很可能会去推很久的公式，这上面还是有很大配合空间的，我和prowindy对这类问题都是可以搞一搞的。
   而prowindy的那类蘑菇题几何题其实往往更需要队友参与……就我个人而言属于看到这种题就头疼的=.=，虽然用力去做可能效果也不差，但是会有种比较本能的抗拒，这是我自己心理问题了，需要做一点调整。

前面是一些主要感受，下面来说说最后一站成都的比赛过程吧。
开场prowindy告诉我A题很简单，我阅读速度比较慢，坚持看完题目以后

5min 1Y A

然后zYc说他做过K，好像是什么bfs还是百度之星原题什么的……写了一下WA了，prowindy帮他一看就发现错误了，似乎是prowindy以前被那个东西坑过，于是

52min 2Y K

在zYc弄K的期间，我看了D和I，瞬间就想到了解法，D显然是分sqrt(n)的做法，I就一个递推算数目。
然后我觉得I比较好写，就告诉prowindy递推式子，我先去写D企图抢First Blood。
D TLE了好多遍，百思不得其解。于是在我看代码的时候prowindy在TLE了一遍以后改成离线的做法过掉了I

69min 2Y I

接下来就是我继续搞D，zYc去做BCJ三个数学题了。
这时__holy__过掉了D，First Blood被抢掉了T.T。
期间B题弹了个cla，zYc看了一下就去搞了，我向prowindy讲了一遍代码，突然发现重边会导致我的算法每个询问并不是sqrt(n)的，合并重边以后WA了一遍，把一个int改成long long以后就过了。

115min 5Y D

zYc很给力地把B的组合公式推出来以后也过掉了B

117min 1Y B

这之后prowindy交了一下H，T了以后就放弃了。
于是重点变为CEGJ。
G是个很扎实的蘑菇题，但是写起来比较麻烦，于是prowindy就去写了。
zYc徘徊在C和J之间没有思路……
我看了看形势不太对，去看掉了没看过的E，F有点长挺讨厌的让zYc看掉了。看看board发现C比J过的人多多了，于是去zYc就直接攻C去了。
权衡了一下，F显然是个贪心，可能要三分一下，然后算算gcd什么的，略麻烦……
E题是个字符串的题目，想通了以后应该不会特别难写。
我就跳E了。
于是成了三开的节奏 我 E prowindy G zYc C 机器基本让prowindy和zYc占着
E我很快想到这个过程就是KMP的过程，于是企图在这上面进行一些修改。不是特别久以后得到了一下看上去有点疼的算法。然后花了好长时间找了几组觉得会挂的反例，但是发现都没挂。
于是我又花了一段时间把这个算法证明了。
然后我pia掉正在写题的队友上机写了，很快写完以后发现过不了sample，打印了一份。
对那个sample模拟了一遍感觉我自己的算法没错，于是我看了看代码，不是特别久之后就发现了手写的KMP里面写漏了一句话= =b，于是改完以后过样例了。
在我交之前prowindy跟我说如果觉得水就封board以后交……然后我说了一句，不是特别水，于是交上去就1Y了。
志愿者送来了两个同色的气球。

235min 1Y E First Blood

接下来基本还是继续之前的节奏，zYc C prowindy G，我只能帮两边看……
然后到最后G没写完，zYc C没过sample……

后来我们觉得杯应该没有了，就打算不参加颁奖典礼，免得太过奔波，直接去机场附近找个旅馆住，方便好好复习……
走到一半老朱告诉我们有杯，于是又跑回去和fancy会合……预约了早上6点的面包车以赶去机场。

颁奖的时候被黑飞这种事情还是不要说出来丢人了。
于是看DS课件去

1. 表示方法
   1. $$x + i y$$
   2. $$rcos\theta + risin\theta$$
   3. $$r^{i\theta}$$
2. 运算
   1. $$|z_1z_2| = |z_1||z_2|$$, $$Arg(z_1z_2) = Argz_1 + Argz_2$$
   2. $$z^n = r^n(cos\theta + i sin \theta)^n = r^n(cosn\theta + isinn\theta) = r^ne^{in\theta}$$
3. f(z)可导(解析)的充分必要条件为
   u(x, y), v(x, y)在在(x, y)处可微，且满足C-R条件
   $$\frac{\partial u}{\partial x} = \frac{\partial v}{\partial y}$$ 且 $$\frac{\partial v}{\partial x} = – \frac{\partial u}{\partial y}$$
   此时$$f'(z) = \frac{\partial u}{\partial x} + i \frac{\partial v}{\partial x}$$ 或 $$f'(z) = \frac{\partial v}{\partial y} – i \frac{\partial u}{\partial y}$$
4. 初等解析函数
   1. $$e^z = e^x(cosy + isiny)$$ 周期为$$2n\pi i$$
   2. $$ln z = ln|z| + iargz$$, $$Ln z = ln z + i2k\pi$$, $$ln z$$称为对数主支
   3. $$z^u = e^{uLnz}$$
   4. $$sin z = \frac{e^{iz} – e^{-iz}}{2i}$$, $$cos z = \frac{e^{iz} + e^{-iz}}{2}$$
   5. $$sh z = \frac{e^z – e^{-z}}{2}$$, $$ch z = \frac{e^z + e^{-z}}{2}$$
5. 若函数在C上连续，则f(z)在C上可积，且有
   $$\int_Cf(z)dz = \int_Cudx – vdy + i\int_Cvdx + udy$$
   该公式可以看成
   $$f = u + iv$$与$$dz = dx + idy$$相乘，得$$f(z)dz = (u + iv)(dx + idy) = udx – vdy + i(vdx + udy)$$在C上的积分
6. 上面的积分方法略复杂，于是一般使用参数方程积分。
   $$\int_Cf(z)dz = \int_\alpha^\beta = f(z(t))z'(t)dt$$
7. 柯西积分定理
   若f(z)在封闭曲线C及其包围的单连通区域D内解析，则$$\oint_Cf(z)dz = 0$$
   推论：解析函数的路径无关性
   在多连通区域则要求其在边界C(这个C包括内边界)以及D上解析
   所以对于解析函数有形变公式
   $$\oint_{C_0} f(z)dz = \oint_{C_1}f(z)dz$$
8. 若函数解析，则无限阶解析，并可积
9. 原函数定理
   上面已经提到解析函数积分的路径无关性，所以起点和终点即可定下积分值，固定起点$$z_0$$则可定义积分上限相关函数，记为$$F(z) = \int_{z_0}^z f(\zeta)d\zeta$$
   则$$F'(z) = f(z)$$
   推论1：因为起点$$z_0$$不同所得到的原函数至多差一个常数C。
   推论2：设G(z)为f(z)其中一个原函数，\int_Cf(z)dz = G(z1) – G(z0)
10. 柯西积分公式(用边界的积分确定内部单点的值)
    若f(z)在有界闭区域D+C上解析，(C为D的边界)，则$$f(z_0) = \frac{1}{2\pi i}\int_C\frac{f(z)}{z – z_0}dz$$
11. 积分平均值定理
    如果曲线C是以$$z_0$$为中心，R为半径的圆周$$C_R$$，函数f(z)在$$|z-z_0| \leq R$$上解析，则$$f(z_0) = \frac{1}{2\pi}\int_0^{2\pi}f(z_0+Re^{i\theta})d\theta$$
    亦即，函数f(z)在圆心处的值等于它在圆周上的积分平均值。
    此式可以由柯西积分公式推得。
12. 高阶导数的柯西积分公式
    若f(z)在有界闭区域D+C上解析，则$$f^n(z_0) = \frac{n!}{2\pi i}\oint_C\frac{f(z)}{(z-z_0)^{n+1}}dz$$
    可看成柯西积分公式两端对$$z_0$$求导
13. 柯西不等式
    f(z)在闭圆盘上解析，则有$$|f^n(z_0)| \leq \frac{n!}{R^n}M$$
    $$M = \max_{|z-z_0|=R} |f(z)|$$
    柳维尔定理
    有界整函数f(z)必为常数
    代数学基本定理
    n次多项式必有n个零点(可能重合)
14. 泰勒展开系数$$C_n = \frac{f^n(z_0)}{n!} = \frac{1}{2\pi i}\int_{C_r}\frac{f(s)}{(s-z_0)^{n+1}}ds$$
    其中$$C_r$$为一个半径为r的圆，$$R_1 \leq r \leq R_2$$
15. m级极点的充分必要条件
    f(z)可表示为$$f(z) = \frac{g(z)}{(z-z_0)^m}$$
    g(z)在$$z_0$$解析，且$$g(z_0) \neq 0$$
16. 留数，设$$z_0$$为孤立奇点
    泰勒展开系数中的$$C_{-1}$$，即$$\frac{1}{2\pi i}\oint_{C_p}f(z)dz$$
    当$$z_0$$为单极点的时候，$$Res[f(z);z_0] = \lim_{z\rightarrow z_0} (z – z_0)f(z)$$
17. 留数定理
    设D-{z1,z2,z3…}为多连通区域，则
    $$\oint_C f(z)dz = 2\pi i \sum_{k=1}^n Res[f(z);z_k]$$
18. $$\int_0^{2\pi}R(cos\theta, sin\theta)d\theta = 2\pi i \sum (Res[f(z),z_i]))$$
    其中$$z_i$$为单位圆内极点，$$f(z) = \frac{1}{iz} R(\frac{z^2+1}{2z}, \frac{z^2-1}{2zi})$$
19. f(z)是D到G的保角映射当且仅当f(z)是D到G的解析双射.
20. 黎曼映射定理
    设D和G是两个单连通区域，任取点$$z_0 \in D, w_0 \in G, \alpha$$则存在唯一的D到G的保角映射$$w=f(z)$$使得$$w_0 = f(z_0), arg f'(z_0) = \alpha$$
    也就是说，一个点的映射，以及这个点导数的arg，即可确定整个单连通区域的映射。

待续…

与你的 那一个 夏天 已经到了终点
你和我的 心愿 已经实现
虽然说 还有一些不舍依恋
但我们一定还会 再相见
别再流眼泪 你的笑更美

我们大家不再像 从前般
都已经朝着不同方向 渐行渐远
似乎我们之间谁都已忘记 曾经那些年

为何只有我能看见 你笑颜
你或许 只是我在夏天 一缕思念
还是你也有个心愿未完成 需要我们实现

啊 我看见你的眼泪 总是会不断完成你的各种心愿
啊 多希望你也可以 为自己多想一点

大家为了你 不断在努力 可是总不能完成你的心愿
心 在靠近 都是为你 完成那心愿

与你的那一个 夏天 已经到了终点
你和我的心愿 已经实现
虽然说 还有一些不舍依恋
但我们一定还会 再相见

突然间 我竟发现对你依恋舍不得
你的心里无尽思念 并非 全为我念
我害怕实现愿望 那一瞬间
你随着烟花消失 再不见
请别离开我 我喜欢你呐

啊 我们将不再相见 但我一定会记得你的各种心愿
啊 多希望下个夏天 我们还会再见面

大家在帮你 完成那心愿 其实是你在 帮助我们重见
心 在靠近 都因为你 多谢那心愿

突然间 我竟发现对你依恋舍不得
你的心里无尽思念 并非 全为我念
我害怕实现愿望 那一瞬间
你随着烟花消失 再不见
请别离开我 我喜欢你呐

烟花在绽放 明明很美呐 为何好空虚
突然间 花在绽放 突然间 心复跳动
风在吹 花瓣在飞 我的泪 已成线
你还在这里 却只是因为我们自私

与你的 那一个 夏天 已经到了终点
看来我们 始终是要 说一声再见
我相信 我们一定会再相见
再一次 一起度过那夏天

在最后 我们实现了那祈愿
我相信会再见
相信我们友谊会到永远
让我们 带着你真挚的祝福
微笑着 不断前进 到永远

与你的那一个 夏天 已经到了终点
你和我的心愿 已经实现
虽然说 还有一些不舍依恋
但我们一定还会 再相见

突然间 我竟发现对你依恋舍不得
你的心里无尽思念 并非 全为我念
我害怕实现愿望 那一瞬间
你随着烟花消失 再不见
我们在一起 永远记得你
我们在一起 不会再别离

From：贴吧

谢安琪 – 钟无艳
作曲：Christopher Chak 填词：林夕
其实我怕你总夸奖高估我坚忍
其实更怕你只懂得欣赏我品行
无人及我用字绝重拾了你信心
无人问我可甘心演这伟大 化身
其实我想间中崩溃脆弱如恋人
谁在你两臂中低得不需要身份
无奈被你识穿这个念头 得到好处的你
明示不想失去绝世好友
没有得你的允许 我都会爱下去
互相祝福心软之际或者准我吻下去
我痛恨成熟到 不要你望著我流泪
但漂亮笑下去 彷佛冬天饮雪水
被你一贯的赞许 却不配爱下去
在你悲伤一刻必须解慰找到我乐趣
我甘於当副车 也是快乐著唏嘘
彼此这麼了解＊
难怪注定似兄妹一对
其实我怕你的好感基於我修养
其实最怕你的私心亏准我体谅
无人问我寂寞像投何处去养伤
原来是我的心境高到变为 偶像
谁情愿照耀著别人就如 月亮
为奴婢为你备饭奉茶是残忍真相
无奈被你识穿这个念头 得到好处的你
明示不想失去绝世好友
没有得你的允许 我都会爱下去
互相祝福心软之际或者准我吻下去
我痛恨成熟到 不要你望著我流泪
但漂亮笑下去 彷佛冬天饮雪水
被你一贯的赞许 却不配爱下去
在你悲伤一刻必须解慰找到我乐趣
我甘於当副车 也是快乐著唏嘘
彼此这麼了解＊
让我决定我的快乐
那须得你的允许 我都会爱下去
互相祝福心软之际或者准我吻下去
我痛恨成熟到 不要你望著我流泪
但漂亮笑下去 彷佛冬天饮雪水
被你一贯的赞许 无须装说下去
在你悲伤一刻必须解慰找到我乐趣
我甘於当副车 却没法撞入堡垒
彼此这麼了解 难怪注定似兄妹一对
你的他怎允许 结伴观赏雪的泪
永不开封的汽水 让我抱在怀内吻下去