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囧。。。然后写了个网络流对拍。。发现没什么问题。。于是就交掉了。。。

11 thoughts on “NOI Day1。。。

  1. 回复winmad:第三题悲剧了。。对拍找不到错误是因为对拍器生成的都是随机数据。。大点的数据我这个程序立马悲剧。。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>