9
18
2014
5

Solution of PA2014

JC大爷搬了一堆好题到BZOJ上,一些题目比较水而一些题目比较不可做QAQ。

JC大爷好像还没放题解?那我就先把这些天刷掉的一些可做的PA题解写出来吧。。Blog不更总有一种罪恶感


part.1

[PA2014]Bohater:好像很明显是贪心把?我们把能补血的怪能打都打掉,然后按照回血量从大到小排序打就可以了。按照回血量排序需要仔细斟酌下,一开始我贪心错了QAQ。

[PA2014]Ciagi:吓退,留坑。

[PA2014]Druzyny:留坑。

[PA2014]Fiolki:首先能想到可持久化并查集,也就是按秩合并不路径压缩,应该是可以做的但是没必要而且复杂度是[tex]O(nlogn)[/tex]。我们可以留两个并查集,一个用来按秩合并,一个用来路径压缩,路径压缩来取得最高祖先,另外一个用来保留过程,由于我们时间有先后顺序,所以不妨按秩合并成一个二叉树,每次合并加进来一个点。最后我们的工作就是在按秩合并的树上寻找LCA计算答案,所以就是tarjanLCA,但是由于有先后关系。。所以在每个节点上还是要排一次,所以最坏复杂度依然是[tex]O(nlogn)[/tex],但期望复杂度到不了。(其实按秩合并的并查集说的不对。。到最后其实就是一个二叉树了。。深度没有保证)

[PA2014]Iloczyn:不多说了,fib数列增长奇快,40项左右就可以了。

[PA2014]Kuglarz:好题,感觉好神QAQ。其实是最小生成树。。。因为奇偶是满足加减性质的,我们可以把一条边[tex](i,j)[/tex]当作前缀和相减[tex]p_j-p_{i-1}[/tex],然后我们发现只要相邻两个点之间联通,就一定可以知道后一个点是否有球,所以就是最小生成树了。

[PA2014]Lustra:把w1,w2,h1,h2看作矩形坐标,显然只有面积最大的厂家才有可能成为满足条件的厂家,拿最大的判一下就好了,注意trick,第一次我WA了,换CF估计就fst了,o(︶︿︶)o 唉。

[PA2014]Muzeum:留坑。

[PA2014]Pakowanie:BZOJ终于好了,Stillwell验证爆搜是可过的,然后剪枝搞了搞就变成rk1了233333,后来发现状压也行。。不过状压不能剪枝对吧w

[PA2014]Parking:按照从左往右(从右往左同理)摆放顺序的话那么最右是最后一个放的,没有任何障碍,那我们就倒推,用树状数组维护前缀最值就可以了。

[PA2014]Plemiona:单调栈+扫描线。。把矩形都按x轴右端点排个序,插矩形的时候判交,那就是y轴上询问区间max,判了以后扩大该插入矩形并删除与其相交的矩形,删除的时候在其之前未相交的矩形就“露出来了”,所以就要用到单调栈,实现起来其实就是挂链表。。然后还有奇怪的情况会导致删单调栈中间的值,大概自己画几张图就知道是怎么回事了。。


part.2
 
[PA2014]Final Bazarek:奇偶分开来,排个序贪心搞搞。
 
[PA2014]Final Budowa
 
[PA2014]Final Gra w podwajanie
 
[PA2014]Final Krolestwo
 
[PA2014]Final Matryca:这才是真·水题
 
[tex]ans=max\{n-i+j~(i>j~and~s_i,s_j!='*'~and~s_i!=s_j)\}[/tex]
 
[PA2014]Final Wykladzina
 
[PA2014]Final Zadanie:默认根为[tex]1[/tex],设[tex]S_x[/tex]表示以[tex]x[/tex]为根的子树中的人的个数,首先可以列[tex]n-1[/tex]个方程。
 
[tex](u,v)\in E,~a_v-a_u=S_1-S_v-S_v[/tex]
 
还缺一个方程:
 
[tex]a_1=\sum_{i=2}^{n}{S_i}[/tex]
 
然后用点技巧就可以做到[tex]O(n)[/tex]了。
 
[PA2014]Final Zarowki:这种题一看就是贪心对吧。。。但贪心可以非常神。显然每个灯泡要物尽其用,所以从小到大排序,枚举灯泡,找最后一个小于等于这个灯泡的房间去照亮,然后删掉这个房间,把差值存在一个大根堆里,如果没有,那么这个灯泡必然需要加大功率,如果必须加大功率的灯泡>k那么就NIE,否则把这些灯泡和最后剩下来的房间取等,k减去这些灯泡的个数,最后把大根堆从堆首拿出k个就可以了。但是我们需要一个数据结构upper_bound和delete,平衡树嘛,什么?不想手写?“set大法好!”

 

 

Category: BZOJ | Tags: bzoj Problem sets | Read Count: 2589
Avatar_small
__Shi said:
Sat, 20 Sep 2014 12:13:01 +0800

膜拜 "爆搜+剪枝还是A*之类的"

Avatar_small
jcvb said:
Sat, 27 Sep 2014 11:11:38 +0800

Bazarek那题只有我是三分吗。。。写的贪心WA掉了。。。

Avatar_small
Memphis said:
Sat, 27 Sep 2014 22:35:20 +0800

@jcvb: orz。。贪心不止一种吧。。我和wwt15他们的就不一样,而且一开始也写疵了QAQ

Avatar_small
Chenayo said:
Wed, 29 Oct 2014 08:32:08 +0800

[PA2014]Plemiona 抱歉我实在没有看懂扫描线的做法,能否简略题一下.感激不尽>_<

Avatar_small
Memphis said:
Thu, 30 Oct 2014 07:53:26 +0800

@Chenayo: 补充了一下。。T T。。


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com