【Plan U】UER+UR

NanoApe posted @ 2016年5月31日 19:45 in 蒟蒻不做题提前退役 , 1374 阅读

UER和UR都好难啊QwQ

9/??

题意巨长，然而难度决定是道语文阅读题，读懂了就会做了

首先它就像一棵二进制 Trie，然后假如是 && 的话就多一倍手机跳过后面所有 && ，假如是 || 的话停止执行函数的手机增加数为上次 || 剩下来的手机数，且此时继续执行函数的手机数得加上之前 && 多出来的那些手机，然后就$O(n)$搞搞就好了

最优策略当然是向右下移动然后 Fn，到底后再向右两次加 Fn

每次加一个组合数？只要仔细观察你就会发现组合数就是从 $(u,v)$ 到 $(u+i,v-i+j)$ 的方案数

然后弄个三维DP转移一下即可

找出最浅的叶子深度，然后贪心染色

假设数组无限长，每次找排 $K/3$ 的点比较

假设A组最小，那么 $A_{K/3}$ 的排名一定小于 $K$（最大为 $K/3*3-2$）那么我们可以将A组前 $K/3$ 删掉，然后递归直到 $K<3$

接下来暴力判断即可

容易发现只需找出行的最小变换次数和列的最小变换次数并相加即可

将无序的数组转成有序的，可以先按大小平均分成两份，然后递归使得两份都有序，然后再放回来

假如交换线段有交叉的话就不行，于是弄成树状数组

质因数分解后 xor 和为0嘛，那么树上路径就能转成到根路径了，然后质因数分解，对于小的质因数直接存，大的离散化后存

NanoApe's Blog