NOI 网上同步赛。。


这个。。我表示震惊。。
恩。。就写点总结吧。。
首先我感觉我的水平比去年NOIP的时候是要强多了。。其实这个倒是其次,
重要的是心态好多了。。。。
Day1的话前两题都算是运气好。一个是刚好做过Zap。。一个是刚好会搞划分树。。
第三题的话现在想想确实不够稳重额。。实际上在网络流可以80分的情况下,偏偏
要写不熟悉的平面图最短路。。然后就悲剧掉了50分。。。甚至我直接放弃下一半
输入数据。。我觉得有脑子就应该发现这肯定是有问题的。。看样子当时是被前两题
冲昏了头脑。。以后一定要冷静啊。。
Day2的话暴露了我各种不行的地方囧。。
首先是Problem 1。。。看样子我确实是过于浮躁。。
没有多想就写了个暴力算法和一个囧囧的贪心。。实际上这题也不是非常难的。。
第二题就更悲剧了。。完全没有认真专研剪枝的心思。。写了个很垃圾的剪枝。。
第三题彻底悲剧。。我一开始看了数据。。感觉又一些是一维的,显然可以Dp。
有一些是经典的落盘子问题。。也可以Dp。。前三个都可以暴力。。
但由于我过于SB。。懒得去写Dp。。直接写了个每次去最近点的贪心。。
可能也是因为windows下Linux的check不能用吧。。我当时很慌。。
但是一估摸时间还有1个小时。。于是就强作镇定的自己写了一个check。。
然后调了半天才能用。。
我不行的地方…
复杂一点的贪心。。。剪枝的技巧。。。耐心和恒心。。考场上的判断力。。。

SRM 478 Solution。。

哎。这场极度失败的SRM。。。。看来自己不行的地方还有很多啊囧。。。
250:
注意到所有的变换都是x->2^n*x+2^n-1
设F(a,x)=2^n*x+2^n-1,
那么可以证明F(a,F(b,x))=F(a+b,x)..
然后变换只有a=2和a=3.。那么找出最小的t使得F(t,x)%1000…007为0.。。
然后把t表示成2和3的和就OK了。。
悲剧的是我忘了考虑一开始就可以的状态了。。然后果断被Cha。。0分。。
500:
也就是个状态压缩的Dp汗。。
设Ans[subset]为把subset的那些归并成一堆可以得到的钱,
Dp[subset]subset那些可以得到的最大钱
然后穷举一下啊subset的子集就可以了。。
1000:
设sum为所有的取法数,
考虑先算出p[i]=取的时候在第i个盒子里取的概率(就是这个盒子被选中了并且抽中了。。)
根据这个就可以算出全部了。。
设 Dp[total]为选total个苹果的方法总数,Dp2[total]为忽略第i个盒子这样的方法总数,
那么 with=Dp[total]-Dp2[total]就是选第i个盒子这样的方法总数,
那么with/sum*(Size[i]/total)就是这种情况下的概率。。
然后枚举total。。全部+起来就可以搞出p[i]了。。就OK了汗。。
Size[i]是第i个盒子中苹果总数
。。我就是一个傻X。。。

SRM 478

今天真是太悲剧了。。。第一题想了半天才弄出来结果被Cha掉了。。全房间唯一一个被Cha的。。然后其它题目脑缺全部不会做。。。0分。。。。

CodeForces#25

好吧这些题目也太水了囧。。。
Problem A 此题亮瞎我的狗眼
Problem B 此题再次亮瞎我的狗眼
Problem C 这题每次用输入的边更新一下每对点之间的最短路在求和就可以了。。
Problem D 每次找一条在环中的边,把它删掉,再把两个联通块连起来。。
Problem E 先把所有被包含的删掉(如果全部都一样的话特判一下。。)。。用Hash算出每对之间最大重合长度。。随便搜索一下就OK了。。

ZKW天牛的线段树。。

不得不说ZKW天牛的线段树实在是太NB了。。
我最近闲的无聊用这个改写了个ZJOI的Count。。结果刷到了Rank 1囧。。
然后去写QTREE。。刷到了第7囧。。
我又去研究了半天。。发现这样的写法子底向下也有悲剧的地方就是如果一定要需要区间标记,就没办法了。。不过也是蛮好解决的,由于每层最多两个区间,所以一遍走过把它们全部记录下来,然后对它们从上往下处理,有标记就往下推就可以了。。
这种写法的线段树实在太帅了。。几乎无常数,比递归快N多。。。。
Orz zkw天牛!!!!!!!!!!!!!!!!

NOI Day1。。。

我参加的是网上公开赛囧。。不过比赛还没结束就写这个会不会判作弊啊囧。。
Problem 1
题意就是对所有1<=i<=n,1<=j<=m算出(i,j)*2-1的和
额。。皇上,还记得大明湖畔的。。。
额。是POI的ZAP么。。
枚举(i,j)用一样的方法算出这样的对数,就OK了。。
好吧暴力可以拿80分。。汗。。
Problem 2
恩。。这题非常的猥琐啊。。
先求出前缀和。。设为S好了。。
考虑区间(l,r]固定r那么l的范围就是[r-R,r-L]。。
然后如果能对每个r用一种办法可以得出下一个最大的以r结尾的区间权值的话,就可以用类似表归并的
办法搞出前K大区间了。。
权值和等于S[r]-S[l]。。故只需要用区间K大值的办法来维护。。。
但数据范围很大啊。。。
我一开始写了个LogN^2的,手测TLE囧。。
然后在第三题毫无思路的情况下豁出去了。。写了个划分树。。自己机子上最大数据2s多一点。。测评机应该比我电脑强吧囧。。。
关键是这里所有查询区间的长度都是一样滴。。不过我不知道怎么用哎。。。
Problem 3
这题我纯属直觉,首先所有点高度在[0,1]。。然后我根据直觉强行认为所有点要么0要么1(就可以最小割了。。否则没法做啊。。)。。然后发现最小割对于最大数据会TLE。。很明显可以想到八中OJ的第二题。。考虑转化成对偶图。。我毫无根据的抛弃后一半输入数据。。然后建个图写了个Dijstra。。为此自己手写了个Vector,手写了个Heap囧。。。然后写了个网络流对拍。。发现没什么问题。。于是就交掉了。。。

Page 4 of 41234