我某日在颓废的时候突然思索出这个傻叉的数据结构。。。可以在比O（N）小的时间内在线支持几乎一切询问（不能修改）。。。
但非常的傻叉。。。。
比如说考虑这个问题。。给出一个数列，每次询问从第l个到第r个中有几个不同的元素。。
。。。一定要在线。。
那么。。我们把这个数列分成L块，然后对每个第l块到第r块这样的子序列储存一个当前的结果。
然后计算的时候。在能使用的信息基础上，可以在O（N/L）的时间完成询问，然后再恢复。。
注意到需要的空间和预处理时间是L^2N的。。。所以L不能取很大。。比如说取个N^0.25次方。。
就能在N^1.5完成预处理，N^0.75完成询问了。。。
这。。。似乎对几乎一切的问题都适用。。。但速度可以去死了。。
囧。。尝试了下开哥的程序写法。。。
题目是这个。
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1975
裸的K短路，A*就可以了。。。
我上次由于代码风格过差被T神骂了。。所以去Orz了开哥的代码。。。感到压力非常大。。
就把我写的这个贴出来吧囧。。。
总的来说感觉还不错。。不过就是觉得把所有函数定义和主体分开来写工程的时候是很好。。但搞OI就有点囧了T_T。。
http://www.ideone.com/lDlIh
ZOJ Monthly, October 2010 题解
尽管比赛的时候还是很多题不会做。。不过上了nimendongde这个号看了lichao神犇和gaoxin神犇的程序之后。。总算全部都会了囧。。。
Orz Sro Orz gaoxin&lichao神犇
A，纯模拟题。。直接上就好了。。但是我一开始用cin TLE，然后改成C的后不知道哪里写二了WA囧。。
最后是gaoxin神犇做的。。我太弱了囧。。。
B,纯数学题，我一开始做WA，最后是lichao神犇A的囧。。
设上面切了A次，侧面切了B次，克隆了C次，
那么A+B+C=M
(A==0?1:2A)*(B+1)+C=N
若A为0，那么得到N=M+1。。显然此时答案为0。。
若N<M+1。。那么由于每次操作之后块数增加。。。显然是无解的。。。
那么现在A>0
解得：
2*A*B+A-B=N-M.
考虑配平。。
(A-1/2)(2*B+1)+1/2=N-M
(2A-1)(2B+1)=2N-2M-1…
然后就nimendongde了。。
枚举右边的因子。。。
C：
按最短路建图，可以发现求是求一个ACG中经过一个点的路径数。。
然后设in[t]为0->t的路径数，out[t]为t出发点路径数.
那么in[t]=Sum{in[i],有边i->t}
out[t]=Sum{out[i],右边t->i}+1。。
然后乘起来就OK了。。
注意10^10*10^10会超long long
a*b=2*a*(b/2)+a*(b%2)。。。
于是二分的乘法（这。。。）就可以避免爆long long了囧。。。
D：
非常恶心的计算几何，gaoxin神犇太强了。。硬是A掉了Orz Sro。。。
各种麻烦。。。
E：
首先将所有trap按Di排序，然后一个个处理，记录当前消耗时间的和now，
每次遇到一个trap，如果它加进去之后now超过了它的D。。
那么就把当前要修复的所有trap中花费时间最大的给删掉。用堆来维护就可以了。。
F:
很简单的DP。。就是要高精度。。
然后注意到要输出约化的分数，由于分母是b-a+1的n次方。。这个玩意的质因数不多。。
一个个的两边都除过去就可以了。。
我用Java强A掉了囧。。。
G：
注意对一个ai，我们的di肯定是它的因子，然后一个数的因子数一般是比较小的，所以我们可以枚举。。
然后考虑一个di，我们需要知道在x到y有多少数t
最大公约数（ai,t）=di。。
这个可以用容斥原理解决。。
具体的说就是设F(n)表示x到y之间有多少数与ai的最大公约数为n。。
那么F(n)=x到y之间n的倍数-Sum{F(m),m是n的倍数}。。。
算出这个就可以直接DP了。。
H：
这个太囧了。。
要各种分情况讨论：
设a<b
a=0 b=0:此时就是一个点，该点的情况决定一切
a=0 b>0：此时是一维的情况，就是满足条件的线段长度/线段总长度b
a>0 b>0：此时是二维的情况，画出图来可以发现是两条线去切一个矩形。。。
还有一点。。。就是当答案=0的时候。按上面这么写甚至有可能输出-0.000000
这。。。。
I：
计算几何的水题。。不多说了囧。。。
J：神犇题啊。。。gaoxin和lichao神犇的做法太强大了。。严重Orz！！！！
首先考虑O(n)的做法。。
注意到可以列期望方程F[n]=pre*F[n-1]+nxt*F[n+1]+1
pre和nxt分别是向前和向后走的概率。。
那么解方程就是n^3了。。
但这题跟上次CF的某题很像。。这个矩阵是一个Tridiagonal_matrix
http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm
所以可以O(n)求解。。
然后测试组数过多。。。O（n）TLE囧。。。。
n=2的情况很很囧。。
可以发现m=2的情况关于n成二次关系。。是一个n的二次函数。。
若m>2
设F(n,m)为答案
然后神犇们似乎是发现当n变大了之后F(n+1,m)-F(n,m)快速趋向于常数。。。
所以只需要计算很少的n。。当这个常数变的足够稳定之后。。就可以直接给答案了。。
复杂度不清楚。。但0msAC了囧。。。
ZOJ Monthly, October 2010
哇咔咔。。我们队A光了所有题目！！！！！
比赛前。。我跟高欣神犇和李超神犇组了个队。。队名就叫nimendongde嘿嘿。。。
然后去参加比赛。。
我一开始去做B。。然后各种WA。。又去写A。。还是各种WA。。然后我囧死。。
然后李超神犇去做B。。A掉了。。我连A都写错囧的要死。。后来高欣神犇去A掉了A..
不过我也造成了巨大的罚时。。。幸好没别的人AK囧。。
然后高欣神犇发现I是水题，就A掉了。。
同时高欣神犇也A掉了E。貌似是道几何题。。。接着我发现F似乎是道水题，不过需要高精度，就写了Java。。1Y了。。
然后我去做C。。发现是个图论的XX题。。于是强A。。
但我发现似乎这题有点猥琐。。因为10^10*10^10会超long long。。
幸好a*b=2*a*(b/2)+a*(b%2)。。
所以可以二分做乘法
然后J是道非常BT的题目。。我是毫无思路。。李超神犇有O（n）的做法。。但是会TLE。
一直也没有神马好点的办法。。李超神犇最后还是A掉了。。太神犇了Orz！！
接着我去作G。。。一开始没有处理好。。
导致TLE。。不过最后通过各种努力。。还是A掉了。。
gaoxin神犇则一直在写D。。一道非常XX的计算几何题。。
但是因为精度神马的问题。。一直在悲剧。。
最后换成long double。。于是A掉了。。
当时我们队8题。。有队9题。。。时间已经不多了。。
然后是J题。。。李超神犇在最后关头A掉了。。方法我也不知道囧。。
然后H题是XX的几何。。非常恶心。。有各种XX的特况。。我WA了好几次也终于A掉了。。。
然后在还剩几分钟的样子我们AK了。。
。。话说三道Special Judge的题目全是我A的囧。。是不是因为我常上SPOJ的缘故囧。。。
SPOJ UNTITLE1
题目大意：
维护一个数据结构，支持两个操作：
给一段数+/-上一个值
求最大前缀和。
哇咔咔,我是数据结构控！！这种裸的数据结构神马的最喜欢了T_T。。。
。。。首先。。看AC人数这么少。。线段树肯定不可做。。。
然后肯定要。。块状数组。
分成根号N块，
那么在每块中的最大前缀和必然是前面块的和+这块中内部的最大前缀和。
可以发现，如果一个块整体增量为a，我们需要知道Max(S[i]+a*i)
。。用凸包XX维护一个块。。可以LogN搞出这个结果。。。
然后每次增加会有一个块被重构，其余都只要增加块增量的标记。。
询问也差不多。。。
灰色头像模拟赛正式题解
对不住大家因为时间仓促现在才写好。。真是太不好意思了。。
cid-d5ca79e9c509746d.office.live.com/browse.aspx/OI
【灰色头像模拟赛】总结+简略题解
首先要道歉。。真是太对不起大家了。。第一题gray的描述有点问题。。尽管后来在空间上更新了最终版。。
可能还是导致一些童鞋0分。。太囧了。。。
而且题目的难度有点。。。囧。。。。
因为是第一次举办比赛。。不是很会控制难度。。真是太对不住了。。。
解题报告：
1.gray
此题本来是要送分的。。因为描述上SB了囧。。导致很多人丢分。。太囧了。。
题解的话直接排序。。然后统计次数。然后输出。。。
而且标程还写错导致各种SB。。。
2.face
各位童鞋那个笔随便点几个点画一下。。
可以发现结果是有很多个矩阵组成的。。
具体的说，如果两个顶点有相同的坐标，那么他们之间连一条边。。
那么对于一个连通分量。。。最后会变成一个其中不同X坐标的个数*不同Y坐标的个数的矩阵。。
然后BFS一下求连通分量就可以了。。
3.snow
这个题目有点囧的。。设Dp[i]表示WJMZBMR在i点，NZK神犇还有一次机会的答案。
那么考虑一条边i->j
NZK神犇可以有两个决策。。删 or不删
删的话:
WJMZBMR就可以走最短路了，需要 Dist[i][1]（i->j被删）。。
不删的话：
WJMZBMR就可以往j走。。就是Cost(i->j)+Dp[j]。。
NZK神犇显然要选最大值。。
用这个更新Dp[i]..然后用SPFA不断的更新。。。
Dp[0]就是答案了T_T。。
4.why
此题有点复杂和XX。。先看标程吧。。
可以证明按标程的方法，状态数是N^3的。。所以不会T
总而言之这次模拟赛办的也不是很成功。。难度过大了囧。。。
如果11月份我还有空的话我可能会再办一场。。按照我原来的想法。。
就是无限制XXX比赛了。。。
灰色头像模拟赛成绩
灰色头像模拟赛题解+测试数据发布
将在9：30准时发布。。。RT
见
cid-d5ca79e9c509746d.office.live.com/browse.aspx/OI
题目4有何不可
有何不可(why.in/why.out)
引子：
为你唱这首歌 没有什么风格它仅仅代表着 我想给你快乐为你解冻冰河 为你做一只扑火的飞蛾没有什么事情是不值得为你唱这首歌 没有什么风格它仅仅代表着 我希望你快乐为你辗转反侧 为你放弃世界有何不可夏末秋凉里带一点温热 有换季的颜色
背景：
某天，WJMZBMR在外面闲逛，看到神牛XXX在跟他的GF（你们懂的）逛街。他的GF看中了N件物品，每件物品有价格和喜爱度，可WJMZBMR知道XXX不是神马富二代。
XXX身上一分钱都没有（全被他GF花光了）。XXX非常的痛苦的时候，被春哥看到了，春哥正好心情很好，看在XXX平时信春哥的份上，给了XXX M元钱。
同时那天是伟大的数学家Fibonacci的生日，所以所有商品的价格全部是Fibonacci数。
XXX很爱他的GF，他希望在自己能及的范围内让买来的物品的喜爱度最大。
WJMZBMR在旁边表示压力很大囧。。。
数学定义：
Fibonacci数列：满足a[1]=1,a[2]=1,a[n]=a[n-1]+a[n-2]的数列。
前几项为1,1,2,3,5,8,13
Fibonacci数：Fibonacci数列中的数
N个物品，体积都是Fibonacci数，价值也给出，每个物品只有一个，放入体积为M的背包中，求最大价值。
01背包问题的扩展
输入：
第一行N和M表示物品数和钱数
接下来N行，每行两个数分别表示一个物品的价格和喜爱度
输出：
一行表示最大价值
样例输入：
3 10
1 3
5 8
8 10
样例输出：
13
样例的解释：
选择第一个和第三个物品
数据范围：
100%的数据 N<=200
40%的数据 M<=10000
100%的数据 M<=10^9
物品重量价值，可以用int和longint存储
注意：
虽然价值可以用int存储。但是价值的和说不定就要溢出了。