占个坑慢慢填

A

()[http://codeforces.com/contest/1062/problem/A]
题意:现在有一个长度为n的严格上升正整数序列
每个数的取值在[1, 1000]
现在求一个最长的连续子序列
使得删掉这个序列后 可以推导出原来的序列
求这个序列的最长长度

当然如果a[i] - a[j] == i - j那么a[j +1]到a[i-1]都是可以推导出来的
另外 第二个是2或倒数第二个是999 那么第一个或最后一个可以推导

B

现在有两种操作
mul x:把x乘上任意一个数
sqrt x: 如果x是完全平方数的话 可以把x开方
现在求经过若干次操作能得到的最小x
并求得到这个x的最小步数

设n 的质因数分解为 a1^q1 * a2^q2 * a3^q3 …… * ak^qk
其中ai都是质数
那么mul操作就相当于添加新的质因数 或者把已有的ai
sqrt操作就相当于把所有qi除以2(前提是每个qi都是偶数
显然 如果一个数质因数分解后 每个质数的指数为一 那么就不可能再变小了
显然这些的顺序操作可以交换 只不过操作的数值修改了而已
所以步数最小的情况下 乘法只用做一次
而这一次操作之后就可以不断sqrt使得qi全部为1
那么我们只用知道最大的那个qi
然后求比它大的最小的2的幂次就可以了

C

题意 给一个由0和1组成的序列
取出其中一个数时 ans加上这个数 序列中的其他数也加上这个数
求最大的ans

显然我们要优先取出1
假设ax到ay中有z个一
那么取1的过程中我们每次加的答案是1 2 4 8.....
此处总贡献2^z - 1
当一取完了 剩的就是(y - x + 1) - z个原来是0 现在是2^z - 1的元素了
而它们在取的过程中也会翻倍
此处总贡献为(2^(x-y+1-z) - 1) * (2^z - 1)
最终总贡献(2^(0的个数)) * (2^(1的个数) - 1)

D

题意 已知n
a可以转换为b,当且仅当|a|,|b|<n并且满足|a|是|b|的倍数或|b|是|a|的倍数(这个倍数的绝对值大于1)
本次操作的贡献为这个倍数 并且以后再也不可以做这个操作 即使相反 即b推a 也不行

太菜了并不会QAQ

E

题意 一棵树 n个点 q次询问
每次询问一个区间(长度大于1)
要求在这个区间中删除一个点
使得剩下点在树中lca的深度最大
输出被删点深度和最后那个lca的深度

先说到一个小技巧(其实也不算
一堆点的lca其实就是他们当中dfn最小和最大那两个点的lca
这里枚举一下就可以了

F

太菜了不会QAQ

05-11 14:10