-->

PA 2014

13/17


bzoj3709: [PA2014]Bohater

首先考虑把这些东西分成两组
如果是回血比扣血多的话,就从扣血少的开始打,反正都是回血没毛病
反之的话,我们可以推式子:
$$x-a_i+b_i-a_j < x-a_j+b_j-a_i$$

$$b_i > b_j$$
也就是回血多的开始大


bzoj3711: [PA2014]Druzyny

这道题做了我一天啊我擦
要有信仰才能做这题……..
首先,我们很快得到一个dp的式子
$$max(c_{j+1} … c_i) \leq i-j \leq min(d_{j+1} … d_i)$$
然后我们先看后面的条件
$$i \leq j+min(d_{j+1} …. d_i)$$
很明显j递增,后面部分也是递增的,所以当i逐渐增加的时候,维护一个双指针,就可以知道j的最前面的位置,记为pre[j]
c的部分就比较难了,看好了啊,我们可以分治处理这个问题。
首先我们对于一个区间[l,r],我们要求出这个区间的f值,然后我们还知道[l+1,r]的最大值的c,记位置为k。
那么我们以后就可以递归处理[l,k-1]区间的f值,和[k,r]区间的f值,然后还要处理[l,k-1]区间对[k,r]的f值的影响

那我们来看看怎么处理[l,k-1]区间对[k,r]的f值的影响应该怎么处理
首先j是要在[l,k-1]里面,i在[k,r]这个区间里面

我们考虑j还要满足什么条件呢?

第一个j>=pre[i], 也就是要满足上面最初式子d的条件
还有就是要在区间里面 j>=l,j<=r
还有就是,我们移一下项:j+c <=i
也就是说,我们总结一下:
$$j \in [max(pre[i],l) , min(k-1,i-c)]$$

同理,我们的i要满足的条件是
在区间内 i>=k i<=r
把式子移项 l+c<=i
$$i \in [max(k,l+c),r] $$

然后就是对j来讨论了
首先第一种情况
$$[pre[i] < l] \land [i-c < k-1] \Leftrightarrow j\in[l,i-c]$$
这个时候我们发现每次i移动一下,j也移动一下,只要第一次求出j这段的取值,以后的i可以O(1)转移
当i逐渐变大的时候:
$$[pre[i] < l] \land [i-c \geq k-1] \Leftrightarrow j\in[l,k-1]$$
发现这个时候j的区间是固定的
我们只需要二分找到这个时候满足上式的i区间的右端点(pre[i] 是递增的),然后这个区间的贡献直接就是j在上式中出现的区间的贡献
还有两种
$$[pre[i] \geq l] \Leftrightarrow j\in[pre[i],min(i-c,k-1)] $$
为什么要把这两种合成一种呢,因为我们可以直接求
观察到在分治中的不同部分,要不就是pre[i] 所在的区间不同,也就是说
$$l \leq pre[i] \leq k-1$$只有一个k满足,要不pre[i]相同,而i在不同的部分里面,总而言之,只会被计算到一次
所以这一部分可以直接算,鉴于每个i只会被算一次,总的时间复杂度是O(NlogN)的
整体的时间复杂度是:
$$T(n)=T(n-x)+T(x) + min(x,n-x) + log n =O(nlogn)$$
为什么是min(x,n-x)呢?因为从j的取值可以看到,只会挪这么多下,其他的都是算最后一种情况O(NlogN)里面的
有点启发式合并的感觉


bzoj3713: [PA2014]Iloczyn

超舒服有水题
一开始还WA了一发,处理到40位结果发现9位数是1e8
然后处理到45位就过了


bzoj3714: [PA2014]Kuglarz

感觉现在自己只有屎一样的能力,所以挑点简单的先做,这道题感觉以前做过类似的?
这道题很容易想到,如果一个区间可以被其他区间加减得到的话,肯定这个区间就不用选了
我所说的加减大概的定义是区间取并集然后每一小段就是它们得到的小区间
这样做好像是要N^3的,考虑只有N个区间,然后每次搞要N^2
一个更妙的做法?
比如说三个区间
[1,x],[1,y],[x+1,y]只要知道任意两个即可
那么我假设知道[1,x],[1,y]那么我们可以把他们的关系连边
1<->x+1,1<->y 那么x+1就不能连y了,就是一棵最小生成树
其实拓展到其它区间也是如此,就是[x,y]就连一条x<->y+1 的边就好了


bzoj3715: [PA2014]Lustra

记录所有的最大最小值,如果有一个全都是就TAK,否则NIE


bzoj3716&&bzoj4251: [PA2014]Muzeum

这道题好题啊,首先我们看到之后肯定想着怎么转成直角,然后方便统计
简单就是把横坐标和纵坐标,分别乘上h和w
显然这样我们还是难处理点的坐标,因为这两个基底是与坐标轴夹45度角的,我们可以套路一波,把基底转到坐标轴上
考虑逆时针旋转45度,那么所有的点的坐标变成了(x+y,y-x),
这个应该怎么解释,你试试把两个基底想办法构成逆时针旋转45度的向量,然后以这个向量为基底,上面坐标就很对了
这样处理之后其实就是,每个守卫管理x的负半轴方向,y的负半轴的方向

然后我们考虑物品对守卫连边,就是一个最大权闭合子图
但是这样网络流会超时,套路一波找性质
每个物品都是连去右上角的嘛,其实就是按横坐标和纵坐标从大到小排序一个个按顺序流
用set维护一下守卫的纵坐标,按排序的顺序插入和查找,每个物品找到对应守卫的纵坐标流就好了
总共就m个守卫,时间复杂度(n+m)logn
$$O((n+m)logn)$$


bzoj3717: [PA2014]Pakowanie

这道题先看排行榜,时间都是20s到30s
想想这个时间段跟什么时间复杂度对应,其中n=24,m有点蛇皮给了100,其实都知道用24就好了
所以猜一手复杂度
$$O(n2^n)$$
然后就是怎么转移了,我们应该从两个方向的状态压缩来考虑,这样的转移需要n的时间
等等,这些转移一般都是子集枚举,应该是3^n次方的呀,也就是说,不能从子集枚举来考虑,要枚举每个状态的每个数上面考虑
而且我们知道,背包肯定是越大越好,所以用背包来做状态压缩好像不是很需要
那么就用物品来做状态压缩

f[i] i这个状态的物品要的背包数量

这样显然还是不能转移的,我们需要一个最大的剩余数

g[i] i这个状态的物品的要的背包的数量最少的前提下,最大的剩余数

这样好像辅助一下还是很妥的,关于这个最大剩余数的转移,我们会枚举这个状态中其中哪个物品去用新的背包
这样下来就很对了,剩下的就用脚趾头转移就好了


bzoj3718: [PA2014]Parking

这道题很简单,就是保持相对位置不变,那么就排个序,然后问一下前面有多少个卡住了就好了
对输入的两个状态都这样询问一遍,然后如果目标状态有某一个矩阵卡住的比较小就有问题了


bzoj3721&&bzoj4250: PA2014 Final Bazarek

首先奇数偶数分开考虑的话,不是很好
我们考虑并在一起从大到小排序一下,如果没有限制的话肯定是顺着数最优的
那么如果加上了限制,刚好加上当前的数一共有偶数个奇数的话
我们考虑两种情况使得数目不变且达到最优:
1.把前面的一个偶数换成后面一个奇数
2.把前面的一个奇数换成后面的一个偶数
就解决了此问题


bzoj3722: PA2014 Final Budowa

这道题不难啊
首先考虑到,如果某个点,他的孩子一方占据优势,那么这个点就是优势这方的,
进而,这样就可以算出它的父辈节点,最后算到1号点,是什么就是什么
如果已经输了的话,那么就NIE了
如果是平局,那么枚举每个点,把这个点变1,如果还是平局的话,肯定就不行了,因为平局肯定是可以转成另外某方胜利的局面的


bzoj3725: PA2014 Final Matryca

我擦这道水题我居然不会做??????
首先考虑两个相邻的最小的不一样的,距离记为dis
那么你这个串就不能挪dis下,所以答案就是len-dis+1


bzoj3726: PA2014Final Wykladzina

简单的,如果没有障碍的话,就可以用极大化和单调栈做
不会的请去AC:
http://caioj.cn/problem.php?id=2004
然后对于这道题有一个障碍的话,我发现极大化就太难写了,我写了很久没写出来,好像Claris写了
后来我写了单调栈,就是枚举每个点,然后统计包含这个点上面的障碍点的矩阵个数
然后向两边拓展一下就好了
时间复杂度大约是O(N^2)的,我不会怎么证啊。。。


bzoj3728: PA2014Final Zarowki

很好的一个思维,其实并不难,只是看到题面很难,很容易想出来
首先我们秉着一种态度,就是能接近的尽量接近,没有比这个大的就换
其实就是这样,对现有的开一个set,从大到小找,能找到最近的比当前需要的大的那么就是它了
等等,可能这个值以后会被换掉,所以的话,还要把这个值插入大根堆里面,以后取出来换就好了
如果没有比当前的大的,就直接要换了嘛
这样的正确性闭眼证明一下肯定是最优的