-->

PA 2015

7/7


bzoj4291: [PA2015]Kieszonkowe

如果是奇数个奇数的话去掉最小的奇数就好了


bzoj4292: [PA2015]Równanie

写道水题舒缓一下心情 枚举F(N) 然后判断N就好了


bzoj4293: [PA2015]Siano

想到肯定是越大的就越容易被割掉 也越先被割掉
写一个恶心的线段树维护就好了
维护这段区间的增长速度 总和 最大的草有多高 还有天数 与需要下放的修改这棵草的标记即可


bzoj4294: [PA2015]Fibonacci

好题 但是搞了我很久才搞了出来
首先我记的是有循环结的 于是我去找 先找Mod 10下的

怎么 你还没看出来? 我放大一下

这下你看出来了吧
于是我找循环节
Mod 10 100 1000
6 300 1500
就是乘5嘛 搞什么哈哈哈哈
于是我就想从最低位开始做 先枚举前60个数 首先是个位满足的 假设这个数为x
下次只用找x 2x 3x 4x 5x 就好了嘛
于是很开心的开始码 然后WA了
难道我的规律有错
发现
Mod 10 100 1000 10000 100000
6 300 1500 15000 150000
膜题解才发现 原来规律是
$$60^{10(x-1)}$$
然后像刚才那样就对了
注意两个细节 我递归进去的时候用到了矩阵乘法和快速乘法
这里还要注意别以为第0项这个位置没有用 其实是有用的 60项 600项也是有值的
所以我们应该一开始预处理矩阵的时候把答案放在第0个位置
注意一下要用ULL就好了 然后最后面的答案加上 6*10^{18}就好了 防止补零没补完


bzoj4295: [PA2015]Hazard

这道题一开始以为NlogN可以过 然后做了一天的O(NlogN)
后来看题解发现原来时间复杂度不对 后来改O(N)的时间
原来的思路是对的 但是处理的时候麻烦了
做这道题可以都从下标0开始处理 这样比较方便

首先发现每次都是按这个顺序取的 一定会有出现环的情况
环上的点都是顺着这个环走的 先判断这个环有没有可能出现没走完的情况
要判断这个东西让我们想到要记录两个东西
走完整个环的贡献 还有从当前点开始顺时针走 在一圈内走到的减掉最多的地方(当然减完就够了 不需要再多减了)
而且这个地方我们希望是尽量靠前的

所以我们还要用上面的东西算出
1.一个环最多能减多少
2.可以转多少圈(这里的一圈指的是回到当前点位置)
3.找到最近的减掉剩余后最终到达地方

当然了细节还要判断能不能走够一圈

于是乎我写了一个O(NlogN)的线段树爽了一发
发现一个环最多能减多少可以用单调队列和前缀和算
至于最近的减掉剩余能到达的地方这个东西可以从后往前扫 如果有满足的位置的话
用一个last数组记录在环上每个前缀和的值对应的最前面的位置
然后就直接找对应的前缀和就好了


bzoj4296:[PA2015]Mistrzostwa

哈哈哈这道题好像不难
首先我们考虑先把图给联通了 然后那些小于D的用队列依次删掉 在过程中小于D的也要删掉 然后带权并查集跑一下就好了


bzoj4297:[PA2015]Rozstaw szyn

这道题很好的套路啊
首先考虑O(N^2)dp

F[i][j] i点上标j的权 子树的最小值

这样我们考虑有什么方法可以优化这个东西 好像这道题性质很多啊
发现有一个东西很优美 就是i点的取值肯定是固定的一个范围最优 就类似与中位数在中间一样

而且发现当前最优的答案 肯定要求先是孩子子树最优才行
这个的话应该相当容易证明吧…我YY了一下
如果孩子的值不是最优的 它如果产生更优的情况是往父亲的值上面靠 但是它往父亲的值一靠的话 它就会对孩子产生大于等于1的影响
还不如直接将孩子直接挪到最优的值
这个东西启发了我们 下面我们可以更加利用这个性质

我们仔细一想 记当前的数为x

那么如果孩子可以选的一个区间 假设[a,b] 有a<=x<=b 那么这个孩子的对答案的贡献是0 因为这个孩子可以取到和x一样

如果 x<a 的话 记录下有多少个左端点在数轴上要往左跑到x的 记为k1

如果 x>b 的话 记录下有多少个右端点在数轴上要往右跑到x的 记为k2
我们肯定希望|k1 - k2|最小的嘛 这样的话x挪动才会造成小的影响
当x在数轴上往右挪动的时候 肯定由 k1>k2变成k1<k2
所以最优的情况可以有
$$|k1 - k2| = 0 $$
这样回到上面所说的如果不是最优 对孩子产生大于等于1 即
$$|k1 - k2| \geq 1$$
然后按x从小到大排个序 每次暴力往右挪x就好了
每次选出最优值 维护当前点能选的最优值区间就好了 每次还要记录上答案