UOJ Logo Scape的博客

博客

JOI计划

2018-02-22 22:43:32 By Scape

大概是。。发现自己太颓了。。每天稳定$\ge 5h$遗迹暖暖dota2没啥救了。。所以给自己开个坑来让自己不那么自爆。。。

感觉JOI的题还不错,所以就切点JOI来压压惊。

发现没有地方评测。所以做一题之前就先上传到uoj上。

因为是在打dota2,看番,水知乎中抽出时间来做JOI。所以可能要慢慢做。。切得慢了请各位观众老爷轻喷。

我比较懒,所以val.cpp懒得写了暂时先坑着。等有空了或者有好心人再填上。

因为是我一个人在加题(而且只有我和fsf在翻译)所以可能题面数据啥的会出锅。大家发现问题可以和我直接联系。

JOI2017春季合宿 Day1T1 Cultivation

首先易知和顺序无关,只要确定上下左右的天数就可以了。

先考虑下一维的情况。大概就是$\max(x[i]-x[i-1],x[1]+w-x[n])$之类的。

考虑如果把向左和向右的确定了,那么向上和向下的你一列一列去确定就算完了。

考虑一下这样一个事情,如果一个$l,r,u,d$是合法的,且$l$不等于某个$x_i-1$,那么$l-1,r+1,u,d$一定也是合法的,所以可能的$l$只有$O(n)$种。

考虑完$l$后,考虑一下$r$,可能的$r$显然也只有$O(n^2)$中,就是$x_i-x_j-l-1$之类的。然后从小到大枚举一下$r$维护一下每一段大概能做到$O(n^3logn)$

但是感觉不太能过。。然后又注意$u,d$本质不同的答案只有$O(n^2)$个,且随着$r$的增大$u,d$只会变小,所以大概把答案预处理下然后用数组来维护。应该能做到$O(n^3)$..(只是嘴巴bb没写过。。

有个更好些的写法是先枚举$r$,然后$l$可以用单调队列扫一遍。。这样也是$O(n^3)$的。。。

JOI2017春季合宿 Day1T2 Port Facility

显然是把图建出来之后判断是否是二分图。如果是二分图答案就是$2^{联通块个数}$。

考虑一下先把三元环给判掉。判完之后考虑一下,令$fa_i$为最短的包含第$i$个的线段,并建树后发现那么连边就是一个点向树上的一条链连边。

然后就用并查集维护下把树上相同颜色的点缩一起然后BFS染色一下就可以了。。

JOI2017春季合宿 Day1T3 Sparklers

评论

AnzheWang
前排资磁 !
mcfxmcfx
你们都会JOI
BillXu2000
joi的题目哪里有啊?
lych_cys
https://joisc2017.contest.atcoder.jp/可评测
wangxiuhan
所以还加不加题啊(大雾
qmqmqm
为啥不支持hack呀qaq
zhouyi
这个 。。 Sparklers被毒瘤@wangxiuhan 出noip模拟
xia_xue_QAQ
啵啵 来开车吗Scape
Planet6174
1. 本人是 LibreOJ 上负责 JOI 题目翻译的译者之一。 2. JOISC 的题目大多很不错,大家都想早点有熟肉。 3. 本人正在翻译 JOISC 2017 的题目,并给 UOJ/LOJ。 4. 所以能否本人翻译完 JOISC 2017 的题目后发给您,免得大家做重复工作?(或是您翻译后发给我?) 5. 您有没有兴趣来 LibreOJ 翻译组?
Planet6174
6. 目前,JOISC 2017 题目本人已经快翻译完了(还差 Day4 两题)

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。