金华赛区网络赛解题报告。。

这次还是我跟AC跟JZP。。。连续两次#1了!!!!

1001:

如果我们有个一个数据结构,能过支持两个操作:

1。返回某给定矩形中的点

2。删除某个点。

那么对于每个操作,我们只要维护一个队列。

每次找出队列中的第一个点,然后把它能影响的点全部删除并且加入队列。

类似bfs的搞就可以了。

这个数据结构我直接使用了线段树套线段树(先离散化),勉强卡过了。

1002:

让我们只考虑上午的情况(下午一样)。

对每个柱子i分别考虑,容易发现在特定角度区间遮挡它的是特定柱子。

这个可以通过一次扫描实现,方法类似于凸包,画个图脑补一下就行了。

然后对于特定的区间,可以发现遮挡的长度是a+b*cot(t)的三角函数,

根据它跟0和H[i]的大小关系分一下段然后分别积分算答案。

(a+b*cot(t))*sin(t) = a*sin(t)+b*cos(t)。。。这个积分是比较好算的。。。

由于细节很多我跟JZP写了很久都没调出来。。。

1003:

就一坑爹题吧。。。直接爆搜,考虑一个度数剪枝。

令每个未经过点的度数为与他相邻的未经过点数。

显然除了最后一个终点,得至少有2度才能组成路径。

也就是说不能有0度点,1度点最多一个。

这样剪一下就能过了。

1004:

纱布题,不用讲吧。。。

1005:

说白了就是求一个圆跟一个多边形的并。

我们把多边形三角剖分,就能转化成圆跟很多个三角形的并(根据方向是有正负之分的)。

为了方便我们可以以圆心为坐标原点。

这样三角形的一个点就必然是圆心,求圆跟三角形的并就方便多了。

1006:

挺简单的dp呢。。令dp[i]表示从i点到终点的期望时间。。。然后dp[i]的话如果有flight就做flight做到不能做,否则就投个骰子。

1007:

比较简单的费用流问题。。。

对day和科目分别建点。。

然后从天向科目连边。。。

注意到虽然有的边费用是一个二次函数,但是由于这个函数的f[1],f[2],f[3]中,f[1]-f[0],f[2]-f[1],f[3]-f[1]是单调的。。。所以我们可以把它拆成多条边使用费用流算法。

1008:

我们可以发现一开始是1..n。这个条件很重要,因为s[i]!=i的i最多只有会O(m)个。

那样的话我们可以使用容斥原理计算出l..r这几个数跟p互质的数的和。

然后处理一下那些s[i]!=i的位置。

很多同学问如何算l..r这几个数中跟p互质的数的和.

首先不妨令p的质因子是p1,p2,p3..,pn..

同时令rec(r,i)表示1到r中跟pi,…,pn互质的数的和.

那么我们可以发现rec(r,i)=rec(r,i+1)-rec(r/pi,i+1)*pi

因为1到r中跟pi,…,pn互质的数的和=

1到r中跟pi+1,..,pn互质的数的和

-1到r中跟pi+1,…,pn互质的数,同时是pi的倍数的的数的和.

那么rec(r,0)-rec(l-1,0)就是答案了.

1009:

可以说是老原老原的题了吧。。。。

就不说了。。。

SPOJ MSTS

其它题目我不清楚。。。等下再补。。。

13 thoughts on “金华赛区网络赛解题报告。。

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>