题目大意：
维护一个数据结构，支持两个操作：
给一段数+/-上一个值
求最大前缀和。
哇咔咔,我是数据结构控！！这种裸的数据结构神马的最喜欢了T_T。。。
。。。首先。。看AC人数这么少。。线段树肯定不可做。。。
然后肯定要。。块状数组。
分成根号N块，
那么在每块中的最大前缀和必然是前面块的和+这块中内部的最大前缀和。
可以发现，如果一个块整体增量为a，我们需要知道Max(S[i]+a*i)
。。用凸包XX维护一个块。。可以LogN搞出这个结果。。。
然后每次增加会有一个块被重构，其余都只要增加块增量的标记。。
询问也差不多。。。
Monthly Archives: October 2010
灰色头像模拟赛正式题解
对不住大家因为时间仓促现在才写好。。真是太不好意思了。。
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存储。但是价值的和说不定就要溢出了。
题目3断桥残雪（2）
输入：
第 一行四个数N，M分别表示点数，边数
然后 M行，每行a和b和c表示有 一条从a到b的长度为c的有向 边。
结点编号从0到N-1
输出：
一 个数表示答案。如果WJMZBMR在最坏情况下无法到达1号点。输出-1
样例输 入
Sampe Input 1:
3 3
0 1 1
0 2 2
2 1 3
Sample Input 2：
4 5
0 2 1
0 3 1
2 3 1
2 1 1
3 1 1
样例输 出：
Sample Output 1:
5
Sample Output 2:
3
样例的 解释：
Sample 1 Explanation:
在WJMZBMR在0号结点的时候，让0->1的桥断掉，WJMZBMR就只能走0->2->1的路径了，长度为5.
Sample 2 Explanation:
WJMZBMR一开始可以往2号结点和3号结点走，但是如果WJMZBMR往3号结点走。那么如果3->1的桥被切断，WJMZBMR就无路可走悲剧了。所以WJMZBMR只能一开始往2号结点走，然后2->1被切断（注意，这就是最坏情况， 也是NZK神犇的决策），WJMZBMR就只能往2->3->1走了。总长度为3。
数据范围： 40%的数据 N<=20
100%的数据 N<=300 M<=1000 一些解释： 这个题目是为了对应NOIP2009 trade出的图论题，因为本身的模型涉及二人博弈有点绕，本来不想出的，但由于此题的算法比较好，还是出了。我已经尽量将题目写清楚了，如果还是有不理解的，可以去答疑贴问，不过最好自己先看两遍，我怕被问爆囧T_T。
题目3断桥残雪（1）
断桥残雪(snow.in/snow.out)
引子：
断桥是否下过雪
我望着湖面
水中寒月如雪
指尖轻点融解
断桥是否下过雪
又想起你的脸
若是无缘再见
白堤柳帘垂泪好几遍
背景：
在美丽的WJMZBMR的家乡，有很多的断桥，在冬天的时候，就会出现断桥残雪的景象。WJMZBMR不禁会哼起许嵩的《断桥残雪》。
但有时候这对交通也是一种阻碍T_T，在这里我们把位置看成节点，把连接位置之间的桥看成边。由于某些信春哥的原因，这些桥都是单向的囧。
但是由于雪大的原因，有些桥是会突然断掉的。由于WJMZBMR是信春哥的，桥不会在WJMZBMR走过的时候断掉，只会在WJMZBMR到它前面的时候突然断掉。而且春哥告诉WJMZBMR，只有一座桥由于有一次春哥在上面跑步承受了春哥的霸气有断掉的可能。
但春哥日理万机已经忘掉了是哪座桥了T_T。
WJMZBMR想从他的家去春哥那里膜拜！他的家是0号结点，春哥在1号。
WJMZBMR想知道在最坏的情况下，他最少需要多少时间能到到达春哥所在处。
数学定义：
这个是为了更加清楚的说明写的，如果您在上面已经看懂了就不用看了。如果您在上面没有看懂的话就别管上面的了。直接看数学模型吧。
这是一个二人博弈问题。假设是WJMZBMR在跟NZK神犇玩游戏。
给你一个带权有向图，每条边有一个经过的时间，有两个玩家WJMZBMR和NZK神犇在玩游戏， WJMZBMR的目标是最快的从结点0到达结点1，他可以沿着一条边走到另一条边并花去一定的时间。
NZK神犇的目标是让WJMZBMR到达结点1的时间最长，NZK神犇的能力是在一个特定的时间让一条边断掉，但只能使用一次，并且不能在WJMZBMR在一条边上的时候使用。
求两者都是最优决策的情况下，WJMZBMR到达结点1的时间。
题目2素颜
素颜(face.in/face.out)
引子：
如果再看你一眼
是否还会有感觉
最真实的喜怒哀乐全都埋葬在昨天
不掺任何的表演
轰轰烈烈那几年
我怀念 别怀念
怀念也回不到从前
背景：
WJMZBMR已经长大了，不由感觉物是人非，又听起了许嵩的素颜，感到很伤感，想起很久以前自己玩过的一个游戏。不由感觉“当年素面朝天要多纯洁就有多纯洁”
这个游戏是这样的，给你一个无穷大的棋盘，上面有一些黑棋子，WJMZBMR有无穷多的黑棋子。然后WJMZBMR如果看到三个黑棋子组成了一个两边平行于坐标轴的矩形的3个顶点，而第四个顶点上没有黑棋子，那么他就会在那个顶点上放一个黑棋子。一直到没有可以放的条件为止。
WJMZBMR想知道他能否无限放下去？如果不能，请输出棋盘上最后的棋子数量。
数学定义：
P.S 下面这段话可能比较繁琐，因为要有数学定义就写了，如果你已经看懂就忽略数学定义这一块吧T_T。。。
三个棋子(x1,y1),(x2,y2),(x3,y3)如果满足
x1,x2,x3三个数有两个是一样的，另一个不一样。
y1,y2,y3也是。
那么他们就是可以组成一个合法的平行与坐标轴矩形的3个顶点。
第四个顶点就可以放上一个棋子。
输入：
第一行N表示有N个黑棋子一开始就在棋盘上。
接下来N行，每行都表示一个棋子的坐标，其中X坐标在前，Y坐标在后。
输出：
一行，如果能无限放下去，输出-1
否则输出最后的棋子数（不保证范围）
样例输入：
3
0 0
0 1
1 0
样例输出： 4 数据范围： 对于40%的数据，N<=5000
对于100%的数据, N<=200000
x和y都在longint（Pascal）和int(C++)的范围
题目1灰色头像
灰色头像(gray.in/gray.out)
引子：
你灰色头像不会再跳动
哪怕是一句简单的问候
心贴心的交流一页页翻阅多难过
是什么 坠落 升空
又想起你曾说的陪我到最后
暖色的梦变冰凉的枷锁
如果时光倒流我们又能抓得住什么。
背景：
WJMZBMR喜欢上QQ。。但是很多人的头像已经变成灰色了。这让他压力很大。而且WJMZBMR的好友太多了，大量的灰色头像让他无法准确的找到他想找的好友。。
今天WJMZBMR决定清理一下他的QQ，找出那些不会在跳动的头像并且把它们踢掉。为此他翻出了最近一个月的聊天记录。
如果一个头像在在最近一个月中与WJMZBMR聊天次数小于等于2次，WJMZBMR就会认为这是不会再跳动的灰色头像然后把他删掉。
那么请你为WJMZBMR写个程序完成这件事情，并输出剩下的头像。
定义：
头像其实就是ID，是一个长度小于等于30的，由小写或者大写英文字母组成的字符串。
严格的数学定义：
给出一些字符串，输出其中出现次数大于等于3次的。
关于输出的顺序，出现次数多在前，如果次数一样多就按字典序从小到大，相同的ID只输出一次。
输入格式:
第一行N表示聊天记录的长度
接下来N行每行一个字符串表示与WJMZBMR聊天的ID。
输出格式:
第一行表示要输出的头像的个数M
之后M行每行一个字符串表示输出的ID(请按给定顺序输出,两个相同的ID只输出一次)
样例输入：
6
Gx
tracyhenry
seventhplus
Gx
seventhplus
Gx
样例输出:
1
Gx
数据范围：
20%的数据N<=1000
100%的数据 N<=100000