COCI 2014 / 2015

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

无聊做做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]。。

  • 无匹配
Small_feed 评论 (12)
1
[回复]
Avatar_small
Digital Ali 说:
2021年9月05日 18:03

I have read your article couple of times because your views are on my own for the most part. It is great content for every reader. m4ufree

2
[回复]
Avatar_small
Gullam Mohiyoddin 说:
2021年9月28日 00:10

For the current condition you will begin it is tremendous, it's beginning and end nearby's a site a strong key page: เสือมังกร ออนไลน์

3
[回复]
Avatar_small
William 说:
2021年9月30日 02:04

For the current condition you will begin it is tremendous, it's beginning and end nearby's a site a strong key page: starvegus

4
[回复]
Avatar_small
William 说:
2021年9月30日 23:47

This is influencing, yet it is valid for tap on this conspiracy: sagaming

5
[回复]
Avatar_small
William Johnson 说:
2021年10月02日 18:26

I can propose as shown by a general viewpoint striking and interminably fit tips, in this way see it: metamorphosis literary agency

6
[回复]
Avatar_small
William Johnson 说:
2021年10月02日 23:47

I went onto your blog while focusing just sensibly submits. Stunning improvement for rapidly, I will be bookmarking rapidly handle your full scale risings... หวยหุ้น

7
[回复]
Avatar_small
link 说:
2021年10月06日 19:49

Only aspire to mention ones content can be as incredible. This clarity with your post is superb and that i may think you’re a guru for this issue. High-quality along with your concur permit me to to seize your current give to keep modified by using approaching blog post. Thanks a lot hundreds of along with you should go on the pleasurable get the job done. สล็อตออนไลน์

8
[回复]
Avatar_small
link 说:
2021年10月07日 21:44

Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info. soaptoday

9
[回复]
Avatar_small
link 说:
2021年10月10日 17:14

You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers. North American Bancard Agent Program

10
[回复]
Avatar_small
William Johnson 说:
2021年10月22日 12:06

I should say on a tremendously major level that its tangling! The blog is edifying and particularly produce stunning things. 우리카지노

11
[回复]
Avatar_small
William Johnson 说:
2022年1月21日 01:56

Acclaimed read, Positive page, where did u a couple of the articles on your site page now, and I truly like your style. You're truly frustrating and on the off chance that it's especially not firm difficulty, keep up the reasonable work. https://twitchviral.com/blog/what-is-twitch/

12
[回复]
Avatar_small
EPF Grievance 说:
2022年8月09日 10:12

Once the grievance is registered on the EPFiGMS portal, a unique number is allotted to the EPF account holder, where the unique number generated helps to track the status of the compliant any point after the registration, EPF Grievance and every complaint logged on the system would be let under strict surveillance on a daily basis and the necessary manual supervision is done on regular basis.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter