1001

求10^k <= 2 ^m - 1 对于给定的m  k的最大值

取个log搞一下

1002

给定n个字符串 字符串中仅包含小写字母 为每个字母分配一个 0 ~ 25的 整数权值 使得这n个字符串转换后的26进制数最大

单个字符串长度  <= 1e5 不允许前导0

给每个字符创建一个长度为1e5的数组 代表每个26进制位上出现次数

进位后像高精度一样比较大小来排序 为权值最大的分配大数

维护当前剩下多少个字符可以取0 当仅剩下一个时 为当前可以为0的字符分配为0

*有个标记没清零WA了一发

1003

n个点的树 每个点有一种颜色 一条路径的权值是路径上不同颜色的个数 问所有路径的权值之和

n <= 2*10^5 颜色数 <= 2*10^5

当仅有一种颜色的时候 把所有带颜色的点删去 用剩下的每个联通块的大小来统计答案

当多种颜色放到树上的时候 我们把每种颜色的点放到一起 深度从大到小排序

DFS序维护子树和 枚举到一个点 就遍历他的儿子节点 算出贡献 然后把包括他自己在内的子树都删除

当删除完最后一个节点的 统计整个树剩下的大小 那是最后的联通块

复杂度O(nlogn)

*潘学姐取模WA了一发

1006

a是0 ~ n-1的一个排列 b是 0 ~ m -1的一个排列

a->b的映射f 要满足 f(i) = b[f(a[i])] 问f的个数

可以发现 i会和a[i] 和 a^(-1)[i]有约束关系

可以知道a中每个点都会有两条边 所以一定是若干个环

b也是同理

那么对于a的一个环 它的长度是la 只有长度为la的约数的b环可以是约束条件成立

所以先找b环 筛法处理贡献 再找a环 最后乘起来

O(nloglogn) （筛法的部分

1008

考场没写

给你一个 1000w的序列 100次询问 查找第K大

每次询问 bi， 满足 bi + bj <= bk

考场上没做出来

由于bi + bj <= bk 对 bi < bk, bj < bk 都成立

可以直到b序列排序后增长很快

生成序列后 b从大到小 nth_element取出第bi大

由于nth_element后 返回的位置之前都比他小 之后都比他大

所以其实挺快 nth_element用法

1011 没看 zkc和潘学姐搞过了。。。

1012

全程被不是极大迷惑 感觉题目描述很迷

求长度为n的某种排列个数 排列要满足 第i个元素当且仅当在 [Li,Ri]的范围内最小

知道是约束条件是极大之后就有些舒服了

一定有一个 [1,n]的区间 这个位置的数是1

假如这个位置是x

在[1, x-1]和[x+1, n]一定有类似的覆盖整个区间的约束条件

没有的话就无解了

假如都能找到的话 就在答案乘上C(n-1, x - 1) 代表 忘前一个区间随便放几个数就行了 顺序都会确定的

递归下去两部分做相同处理

O(nlogn)

今天是没时间搞题了

昨天CF的c感觉对了 但据说我题意理解错了很迷

还有那个UVALIVE的题也得再看看

明天再搞完之前说的剩下部分吧。。。

多校1