IOI 2012 。。。酱油的解题报告。。。

我今天下午看了一下题目。。。。大致上感觉都是可以做的。。。随便写的解题报告。。。有错误请轻喷T_T。。。

Day1:

problem 1:40分还是比较好拿的。。。但是接下来2个task略恶心。。。我有几个思路不知道能拿几分。。。。。。

problem 2:我觉得这题挺简单的吧。。。让我们考虑什么情况下一个图全是链条。。。

条件1:所有点度数<=2(废话)

条件2: 没有环。

那么大致分几种情况讨论和维护一下就行了。。。

problem 3:rope秒杀。。。不用rope的话也可以用类似树的结构。。总之是sb题。。。

Day2:

problem 1:

我们不妨考虑一个简单的情况,如何解决凸多边形的问题?

由于凸多边形比较优美,两点间距离就是曼哈顿。。所以直接算即可。

那么如何解决复杂的情况呢。

不妨以格子为点,相邻点间连边。

给每个格子加权,a和b之间的距离要乘上a和b的权。。
首先处理一个情况,就是桥,显然桥被经过的次数是确定的,同时从其它方向来的点,直接当成权加在桥的两端上就行了。。。

那么现在没有桥了。。。

一开始权都是1。。。

那么如果有度数是1的格子,显然他必须要往它的唯一相邻格走一步,那么就把它的权加到它的相邻格上去然后删掉他,同时这可以看成他走了一步,故答案要加上他的权乘上所有格子的权和。

如果没有度数是1的格子,那么我们考虑最左边的一行,最靠下的点,毫无疑问他的上方和右方必须有点

同时他的右上方也必须有点(不然就有桥了)。

依次类推,可以证明这个点一直往上到不能往上的这一列的右边都有点。

那么显然这一列除了到自己内部之外,都要先往右走一步。

那么在答案中加上这一列内部的情况,然后把他们加到右边那一列上去。。。

同时可以证明之后如果产生了桥,只可能是因为出现了1度点,处理掉即可。。。

看起来很复杂的样子。。。不过复杂度是线性的。。。

UPD:这做法太傻逼了。。

from wqs:注意到把所有横向的最长连续块压成一个点,那么必然形成一棵树,然后树形dp就行了。

我的搞法搞了那么多实际上只是想办法找到树的一个叶子然后往上推。。。本质上是差不多的。。。但是太麻烦了。。。

不过这么搞也行,其实不用求桥,我们可以维护所有边界上的连续块来找。。。。上下左右四个边界上总能找到树的叶子。。。

problem 2:

注意到我们一个点只能保存2个bit。。。

其实2个bit就够了。。。

我们不妨balabala求一个最优解。

然后一个颜料根据是从脚手架上拿的与否跟放不放到脚手架上,有四种状态(注意到,就算一个颜料是从脚手架上拿的,也要记他放不放到脚手架上,不放到的话意思就是会在将来被扔掉)。

那么对于从脚手架上拿的,我们得到了一个rest,如果不放到脚手架上的话,我们维护一个垃圾堆,放到垃圾堆里去。

对于从新的地方拿的,如果不放到脚手架上->直接扔掉。

放到脚手架上->我们随便扔掉一个之前垃圾堆里的颜色。

我傻叉了...不用记是不是从脚手架拿的,直接按脚手架里有没有判断就行了.然后要记一下一开始的k个是不是要直接扔掉.

那么只要N+K bit就能搞定了。。。。

另外这个的原理是什么呢。。。只要注意到这个本质上是一个从网络流的流量中构造解决方案的过程。。。你就明白了。。。

我们可以对这个问题网络流建模,那么可以发现只要2N的信息就能记录这个网络流的流量从而构造出解决方案。

UPD:

根据wqs说的是不用记是不是从脚手架上拿的的,只要记扔不扔掉就可以了,不过这就同时要记一下一开始在脚手架里的那k个扔不扔掉。。。要N+k位。。更优一些。。。

problem 3:

我才发现原来的搞法完全是扯淡。。。

对这个比赛按位置建一个博弈树。

同时将R标称0,比他强的标成1,弱的标成-1。

那么我们注意到,实际上我们要做的是将0跟它右边位置的叶子交换位置,和从0往上数胜利者有几个0。。。

这个是很好搞的。。。

比如说找一个跟当前0 Lca最低的1。。。

这个找0前后最近的两个1试一下就行了。

总体而言day2比day1难。。但是day1有坑爹构造题。。。。momo tourist。。。。 

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

这次还是我跟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

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

[我们都爱GYZ杯]NOIP模拟赛

时间过的真快啊>_<…离上次办这样的比赛也有2年了吧…

转眼间就这样了呢…

不管怎么说又来办比赛了,希望大家做的开心吧>_<…

题目效仿东方一共有4道:Easy,Normal,Hard,Lunatic.

Lunatic的话>.<,才不是专门为你们这群神犇出的呢!>_<

网址: http://new.tyvj.cn/Test_Show.aspx?id=1092 

总共3个小时.

比赛之后就会发布题解什么的.