COCI 2014 / 2015

dzy posted @ 2014年11月15日 20:30 in COCI with tags COCI , 1534 阅读

无聊做做COCI。

Round 1 [6/6]


PROSJEK

暴力模拟


KLOPKA

记录四个端点


PIRAMIDA

推一推正反,然后随意搞搞。


MAFIJA

基环 + 外向树 一个十分基础的dp


ZABAVA

对每个房间分开考虑,让操作的每一部分尽量均匀,然后dp一遍即可。


KAMP(现已搬运至BZOJ 3743

假设当前在第i个点举行聚会。那我们会发现,司机花费的时间其实就是 2 * (【第i个点 + K个点组成的点集】生成的最小的树的边权和) - K个点中离第i个点最远的距离 即可。

因为司机一定会最后送最远的那个人,这样一定是最优的,其他的边都会重复经过两次。

我们可以随意取一个点集中的点为根dfs,然后得到这K个点生成的最小树。

然后问题转化成了,对于n个点中的每个点,求出它到点集中的K个点的最远距离。

这个可以通过树形dp在O(n)时间内完成。

另外,【第i个点 + K个点组成的点集】生成的最小的树的边权和=【K个点组成的点集】生成的最小的树的边权和+第i个点到【K个点的生成树】最近的距离

这个也可以通过树形dp一遍求出。

因此总的复杂度是[tex]O(n)[/tex]的。



 

Round 2 [6/6]


MOBITEL

暴力


UTRKA

排序就好?


STUDENTSKO

排个序之后编个号,然后算LIS。


BOB

考虑固定右下端点之后看这个点能向左上扩展多大的面积即可。用个单调栈维护就可以了。


SUMA

把相邻的两个需要的时间算出来。永远相同的先合并成一堆。然后按照时间排序然后用并查集维护。用过之后再还原回去就可以保证复杂度了。


NORMA(现已搬运至BZOJ 3745

先来考虑问题的弱化版:询问所有区间的min × max之和。

还是考虑弱化弱化版吧。询问所有区间的min之和。

考虑从n到1枚举i,线段树里第[tex]j(i\leq j \leq n)[/tex]位维护的是[tex]\text{min}(a_i,\cdots,a_j)[/tex]。i每左移一位,线段树里的值可能会发生变化。你会发现变化的值是一段一段的,因为这个序列是单调递减的,于是可以用单调队列维护下标。然后线段树只要支持区间加减即可。(为了推广所以才用的线段树,不然直接记个答案就好了。)

然后做弱化版,max的维护方法显然和min相似,反过来弄即可。然后我们只需要计算一下变化量。比如在维护min的时候,[tex][l,r][/tex]这个区间需要加上[tex]d[/tex],那我们先查询一下在维护max的线段树中[tex][l,r][/tex]的和,记为[tex]S[/tex],那对答案的贡献就是[tex]dS[/tex]。于是我们不停的维护对答案的贡献就好了。

最后做本题。仍然考虑贡献。我们可以再用两棵线段树维护区间内的【值 * 下标】之和。令[tex]seg(l,r)=\sum_{i=l}^{r}i\times a_i[/tex]。然后算[tex][l,r][/tex]这段贡献的时候就是[tex]seg(l,r)-sum(l,r) \times (l - 1)[/tex]。维护方法一样。

总体复杂度就是[tex]O(n\text{log}n)[/tex]


 


Round 3 前面题都是水题 最后一题好像是猎奇的分块。。

 

Round 4 前面水题照常。。最后一题也挺简单。。。暴力dp。。4个边界压二进制吧。。复杂度[tex]\text{O}(nm(n+m)2^4)[/tex]。。

  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
dzy493941464
Music
搜索
计数器
120324

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1