林记之混沌

话说二队的神牛们在天津过了一道很少队过的题，用的是斜率DP优化,于是想学习一下DP斜率优化的我决定拿来做一下，结果很幸运的1A了，虽然想的时间比较长......

其 实就是天津的那道开心农场，题意大概是有T<=2^60的延时限制，然后要按顺序偷n<=30000棵菜，但是对方养了一条狗，每个菜都有一 个对应的愤怒值a[i]和延时值d[i],偷一次菜会增加狗的愤怒值和增加延时，如果是不刷新情况下连续偷菜，在第j次偷到第i棵菜的话延时就会增加 j * d[i],然后有m<=10次的刷新机会，每用一次清除狗的愤怒值和连续偷菜的计数，但延时会增加r<=100,然后要在不超出延时限制的情 况下使得这个过程中狗的最大愤怒值最小。其中n * sigma(d[i])<2^62

......

哎，这么多GGMM都写了总结，俺也来凑凑热闹吧。

 

首先赛前阿里巴巴挑战赛挺好玩的，但是由于作业比较多所以叫BenC在PK的前一天熬夜写了个不稳定版，

结果小车虽然能够回到家里，但却金币于前安然不动~~

 

省赛开场还是和以前一样，大家分别看题，从前面开始看题的BenC果断发现A题是水题，于是我上去Code了，接着从中间开始看题的我发现F题是经典数学...

一开始从当神处得知有这样的算法，今天又尝试了一下，重新熟悉熟悉。

这个算法一般是在树状数组中，实现寻找s[x]>=a的最前前的x这样的目的，当然寻找s[x]<=a的最后的x方法也是一样的，

首先设左值为left，右值为right

left一开始为0

right一开始为2^t，一般取2^t>=maxn

这是必须的，否则某些条件就不满足了。
...

过去只是了解了一下KM算法中的顶标的作用，遇到最大权匹配问题我都是抄例程的~~~

今天和室友一起重新研究了KM算法的整个思想，颇有收获。

...............................

根据上网下载的CJK配置UTF8环境

一开始用的很爽，但是后来发现严重了，一生成中文目录就不行了

发现\newpage可以解决问题，但是这样浪费纸啊，搞了一晚上，后来发现xlatex对中文支持很好，

但是接下来又严重了，公式显示得乱七八糟的

又搞了一早上，发现原来要更新fontspec而且要使用[no-math]选项，问题终于解决了

MS人家说中xlatex英文混排不好看...

昨晚在TC上看见一1000分的问题，简单来说，就是给出一个N*N的矩阵，其中某些位置被染成黑色，在里面如果一个矩形不包含任何黑色格子，则称之为“好矩形”，包含某个格子的“好矩形”的个数称为该格子的分数，

问题就是求若干个格子的分数之和。（N<=1500)

这一题最直观的想法就是枚举所有矩形，然后统计，发现复杂度超过N^4，就算TC的机子再快也不可能让我过。

然后什么容斥...

题意很简单，就是求覆盖所有点的最小正方形

最直接的想法就是枚举正方形旋转角度，

但是直接把[0,pi/2]分段枚举的话，1000份WA，100000份TLE，

后来在某大牛的提点下，学会了一种很有用的方法：

先粗分一次段，求出最好的那个角度，然后真正的最优值一般都在其前后两个区间，将这一区间再细分，

如此重复，精度的问题就解决了，而且速度飞快。

假设以上每条边权为1

要控制流过红点的流量最多为1，（例如控制某个物体只能选取一次之类的），显然第一幅图是错的，应该做成第二幅那样。

我SB了，怎么会犯这种错误呢。

谨记谨记~~~

 

这次的补选赛比上次有了很大的进步，虽然上次的题的确恶心很多。

这次居然爆RP上了No.1，当然这No.1来得并不是顺风顺水.....

一开始开A题，瞬间想到了是Catalan，秒之，居然是我最早交题！心中暗自得意，起码不用像上次一样吃蛋了。

然后艰辛的过程开始了....

看到B题，觉得十分简单，谁知道由于精度问题，老是WA，看到阿当他们陆续过了B，但是我已经交了好几次了，压力指数开始急剧上升，...

昨天是GDCPC 2009，

结果有点令人失望，3题 Rank 24

显然其中的一个主要原因就是实力不足了.....

而且这次省赛中居然没有一道纯正的模拟题，使得BenC强大的RP力场无用武之地。

比赛的过程也很简单

一开始瞬秒了A题，虽然赛后才发现看错题，但实在是太水了~~

BenC看了最后一题，觉得很水，于是交给我水之，
...

一开始想用线段树做，不得要领。

后来才知道是典型的差分约束系统，这是我第一次做差分约束系统的题。

总结一下：若要满足不等式V(a)<=V(b)+W(b,a),则可以从b到a连一条权为W(b,a)的边,求最短路得之。

从b到a的最短路意味着满足所有不等式的a-b之最大值。

首先向一直在保佑我们的Jambo大人回报一下：

我们的战绩是：5题

我们这次的口号是：队有Bencz，如有一宝。

虽然对于我们来说是一个很不错的战绩，但是还是要冷静地分析一下得失。

首先说一下我认为这次之所以发挥出色的原因。自然就是充分发挥我们所长，每个人的能力都得到最好的利用。

xbingo：快速看题工具+创造性参谋，准确而快速地传达题意并提出有创造性的意见。

cylixstar：水题快code工具，为保证题目数量打下基础。

bencz：模拟题之神+瞎搞之王 每次比赛都令我们惊讶赞叹，每次他AC后我们都觉得不可思议，也是我们队与其他大多数队的差距所在。

首先我们说一下比赛流程：

一开始我们三个以几乎最快的速度刷出了题目列表，三个人一起看了第一道题（那时还没发题目下来），然后发现是水题，Code之，AC，吃下了第一颗定心丸。（1000）

然后我们开始分别看题。我发现了一道字符串的水题，瞬间想出解法，Code之，RE，发现看错了数据范围，把100000看成了10000，改了数组大小，AC。（1004）

xbingo发现一模拟题（1002），根据Bencz模拟题定理，马上向Bencz解释题意，Bencz开始纸上编程......

这时我们扫描Standing，发现一道比较多人过的题（1001），我思考了一会，无果，xbingo给出了关键性的建议，我受到了触动，Code之，WA，发现想法距离答案还是有一点距离。

xbingo发现一题看上去是水题的题，Code之，WA，发现题目理解有误差。（1006）

xbingo与Bencz继续看题。我突然灵感爆发，把刚才那道水题AC了。（1001）

接下来我试着Code xbingoWA的题目，（1006）敲入例程后答案不对，换Bencz上来Code，xbingo开始看另一道比较多人过的题，然后开始推导公式（1007）。经过检查，我突然发现我的算法（1006）有问题，一看Standing没人过，于是暂时放弃。

接着Bencz Code完（1002），样例错误，开始调试，xbingo上场共同讨论之，我继续思考......

xbingo与bencz开始了联合调试，集合两人的智慧，进攻这道模拟题（1002），不久，样例通过，交之，AC！！

我们激烈拥抱，如此繁复的一道模拟题，居然一次通过！虽然早已料到这个结果，但心中依然激动难以抑制。

我与xbingo继续推最后一题的公式（1007），Bencz同时上场尝试瞎搞这一题，不知道是不是心理作用，过后回想起来，总觉得有强大的光柱投射在Bencz身上......

正当我和xbingo觉得我们与真相越来越近的时候，Bencz说了一句：“难道规律是这样的？”，我马上扭头过去，神啊，对于Bencz的瞎搞能力我是深信不移的。只见Bencz面前屏幕上的Calc闪现出一数字，我转过去那一瞬间Benc按下了了取根号的按钮，蹬蹬蹬蹬，一个美妙的整数出现了，Bencz向我解释规律，由于Bencz对这种算法的实现不太擅长，于是由我上场Code之，WA，正当我们稍觉失望的时候，我怀着姑且一试的态度把有可能超界的地方改了一改，交之，AC！！！！

我们再次激烈拥抱，Bencz激动得气喘连连，是时，距离比赛结束还有10分钟~~

于是我们坐下来，收拾东西，聊一聊天，等待着倒计时的结束。

回望比赛过程，简直就是一美妙的并行算法。

分析完客观原因，我要说一句：感谢xbingo，感谢Bencz。合作就是关键！

讲一下主观原因，当然，这纯粹是个人观点。

1、前一晚上，我

这道题的本质是求C(2n,n),2n<=200000，答案模1000003

这题一开始使用分解质因式做的，写起来繁琐不说，还很慢。

以前总认为在模的过程中不能出现除法，因为只有乘法和加法在模运算下可以分别取模。

但是我一不小心翻开了数论书又一不小心看到了欧拉定理，脑中灵光一闪：

a^E(m)==1(mod m) 当(a,m)==1时成立 E(m)为欧拉函数，看到这里我不由得一拍大腿，如果是这...

话说昨天晚上我遇到了一题我希望以后一辈子都不要遇到的题目~~~ft。

言归正传，这道题在上一次预选赛中Jambo和啊当都没作出来，貌似Jambo使用HASH，阿当是用Set~~~

今次阿当一雪前耻，把这题做了，而且还0.32S。

当然Jambo不在，于是我就上阵了，用set一次AC，2S+过了，限时3S,为了赶上阿当的记录，于是沿袭Jambo的优良传统，顺便复习了一下HASH，一开始几次超时，后来改了几下，0.3S AC，...

这是刚入学时做过但是没做出的一道题，昨天突然发现还有这样一道还没AC的题，突然发觉很简单，就顺手做了，当时不知道为什么没作出来，看着当时的代码，估计是在递推方面钻了死胡同~~看来做题还是要多转换思路啊。

想法很简单，对于一个N，存在一个无论进入的人怎么走下一步都是输的区间(不妨称之为DeathArea),很容易得到，

而对于一个DeathArea，可以推出一个新的DeathArea，在这个新的DeathArea里无论怎么走在下一步对方都可以使...

今晚做周赛，发现g++ long long 类型在移位时会出现错误，最多只能移31位，就像一个long类型一样，一旦超过结果就会不确定，后来唯有用数组一个个存起累乘的结果才过了~~。

现在还没弄清是什么原因，以后做题要注意了。

谨记谨记~~~

在网上看到某聪做了的一题，刚看完认为是DP，然后想起TC做过的一题，马上联想到了KMP，虽然情况有些不一样，但不难想到直接推广一下，由于C比较小，这是可行的，最坏情况复杂度应该是O(RC)。感觉这道题还蛮不错。

看到这题，我首先上网找了找，没找到什么特别有用的公式，于是只有自己推了一下，得出一个O(N)的递推式，再利用网上找到的一些自守数的性质改进一下，过了，而且速度很理想，不知道是不是没有极限数据，在我的机子上N=2000大约1S多才出来，限时2S，但是交上去大概是0.04S,如果采用压缩高精度可能会更快，不过那样比较麻烦。

不知道有没有O(1)递推的方法，期盼中。

想不到做着做着水题会遇上这么经典的题目，一开始误认为是公倍数的超级水题，后来才发现大错特错，分析一下之后发现是求一元一次同余方程的解，由于数据量过大，直接枚举是不可能的，翻了一下数论书，发现有一个类似辗转相除法的神妙快速算法，Code之，0MS，AC

这类的算法要不时看看，因为很容易忘记~~

PKU 1010 ~~~~的确是一道很水的水题，不过今天一晚上都栽在这里了~~~

原因竟然是~~~~~忘了c++数组下标的范围是0..n-1,郁闷死了，看来高手与菜鸟的区别就在于此，高手是不会犯低级错误D

这道题要注意的问题是：点的编号切莫与深度优先编号相混淆！

 

大意是给定一些点的坐标，X坐标严格递增，要求从第一个点走到最后一个点再走回第一个点，要经过所有的点且距离最短。

不难想到是状态为O(N^2)的DP，时间复杂度为O(N^3)，一开始过了样例和几个简单的数据，结果WA。后来在Discuss中发现一组数据，测试之，终于发现了原来我的转移过程中会出现非法情况，有些情况下的转移并不符合我定下的状态的定义！看来状态的定义一定要牢牢把握住，转移过程和状态的定义相合才是正确的DP。

一般来说状态的定义都不会出问题...

这一题不用双向链表似乎一定超时，因为双向链表的翻转操作只需要O（1）时间，而直接操作则需要O（N），当操作量巨大时差别十分明显，而双向链表不能直接访问其中内容，而需要保存前一个数，以决定下一步的方向。

 

这题例程的实现方式是直接保存某个位置的左右位置。

当需要频繁进行翻转操作而不需要频繁对其中每个数遍历时，使用双向链表是个好选择。

改变了贪食蛇的操作和运动方式，加入了吃东西的功能，终于有点像贪食蛇啦，改进了之后有点像驾驶飞机的感觉

集训过程中，大牛云集，当然我这样的菜鸟属于随机的低概率事件。偶尔看到某牛提到一个求多项式方程的好方法，唯恐忘记，便抄录之：

首先是枚举最低位非0系数的因子，因为其解必定可以整除它，然后，如果某个数代入其中得到值为0即为其解，问题是，直接代入可能会导致系数太大，可能需要高精度，某某牛直接模两个大随机数判断通过，实在是水王。

然后说说某牛保证正确的方法就是不断地用多项式除以代入的数，如果是解，最终商必定为0，过程如下

考虑类似...

想要学最小树形图，于是今天搞了PKU 3164一个晚上，发现还是弱智错误。

简述一下步骤：

1、找除了根以外的顶点的最小前导边，记录其前导顶点pre[i]。

2、检查是否有环，没有则算法结束，加上没有被标记移除的顶点的前导边权即为答案

3、由以上前导边组成的子图中，如果有环，则把环缩为一顶点new,对环中任意顶点u，若存在边(v,u),则应有一条新边(v,new)且w(v,new)=w(v,u)-...

搞定了困扰已久的一个Bug，更加深入了解Ogre的Animation是怎么起作用的。还加上了盾牌Model，准备用来当做食物，这是我目前最高艺术水准的体现哦。



图中盾牌made by Blender

临时抱佛脚的作品：



是不是比以前更像蛇了呢?没有艺术C的人就只能画出这种东西~~

受到伦仔启发，于是想做一个3D贪食蛇，于是想学Ogre，因为它很强大，而且是开源的（强烈支持）

于是从零开始学习Ogre~~~Ogre有好多全新的特性，不过网上有不少十分详尽教程，衷心感谢花时间写教程的前辈们。



3D贪食蛇 完成度:0.2%

P.S. 为了做出自己的模型，看来要学学Blender了（也是开源的，通常开源的都是跨平台的。）

就是求树的中心，一开始想DP，但是想得太简单，冲突问题没想到怎么解决，只好硬做，直接多次BFS，再加上少许剪枝，最坏情况是O(N^2)的复杂度，居然让我1.98S过了~

到nocow一看才发现原来还有这么巧妙的方法，为了显示我的懒惰与健忘，我把它Copy过来了:

 

 

 

Solution From Xcheng:
...