A.Lucky Conversion
题意
- 给定两个长度为 (N(N le 10^5)) 且由4和7构成的 (a, b)串
- 对 (a) 可以有两种操作：
- 交换两个位置的字符;
- 改变一个位置的字符。
- 求最少到操作次数，使得两串相同。
思路
- 统计需要改变4的个数和改变7的个数。
- 两个数到最小值表示两两交换使得对应位相同，剩下的只有其中一种，再进行操作2使得对应位相同。
- 也就是取两者最大值即答案。
B. Lucky Number 2
题意
- 用 (cnt(x)) 表示串 (x) 在一个串 (s) 中出现到次数。
- 现给出 (cnt(4), cnt(7), cnt(47), cnt(74))，求满足这些条件的最小的串 (s)，串 (s) 仅包含4和7。
思路
- 47和74只出现在4、7交界处，即如果我们把连续的4和连续的7看成4和7,则最后的串到形式为4、7交替出现，例如……47474……。
- 显然，47和74的个数差值不会超过1。
- 那么只要根据47和74的3种差值构造，多余的4插到前面，7则放到后面。
C. Lucky Subsequence
题意
- 给定 (N(N le 10^5)) 个数 (a_i(1 le a_i le 10^9)) ，其中仅由4、7构成的数是幸运数。
- 求出长度为 (K) 的子序列，满足序列中没有相同的幸运数的方案数，结果对 (10^9 + 7) 取模。
- 只要序列选取到位置不同，则认为两种方案不同。
思路
- 在 (10^9) 范围内幸运数的个数就1000个左右。
- 用 (f(i,j)) 表示前 (i) 种幸运数中取 (j) 种放入集合中的权值积之和，转移： $$f(i,j) = f(i - 1, j) + c_i f(i - 1, j - 1) $$ (c_i) 表示第 (i)种幸运数出现的次数。
- 假设取了 (j) 个幸运数，则从非幸运数集合中取 (K - j) 个放入集合即可。
D. Lucky Pair
题意
- 给一个长为 (N(N le 10^5)) 的序列。
- 其中幸运数的个数不超过 (10^3) 。
- 求 ([l_1,r_1]) 和 ([l_2, r_2]) 的对数，满足 (l_1 le r_1 lt l_2 le r_2)，且两个区间没有幸运数的交集，就是对于每种幸运数最多只能出现在一个区间中。
思路
- 可以用总方案数 (-) 不合法的方案数。
- 总方案数 = (inom{N}{4} + 2inom{N}{3} + inom{N}{2})
- 假设已经得到了左区间 ([l_1, r_1]) ，那么右半部分 ((r_1, n]) 会被lucky number分割成若干的区间，使得这些小区间不包含lucky number。
- 先固定左区间的右端点 (r_1)，然后从大到小枚举左端点 (l_1) ，右半部分 ((r_1, n]) 区间会发生变化，当且仅当 (l_1) 是lucky number并且在 ((l_1, r_1]) 未出现，所以我们只要枚举lucky number的位置即可。
- 考虑右半部分新增的分割点，假设为 (p) ，(pre)表示 (p) 的前一个分割点，(nxt)为后一个。那么新增的不合法右区间为包含 (p) 的且不包含(pre,nxt)的区间。
- 由于有非lucky number的存在，所以还要考虑左右端点不是lucky number的扩展。
E. Lucky Queries
题意
- 给一个长为 (N(N le 10^6)) 且由4、7构成的串 (s) 。
- 有 (M(M le 3 imes 10^5)) 次操作：
- switch l r：将区间 ([l, r]) 的 (4 o 7, 7 o 4) 。
- count：求串s的最长上升子序列。
思路
- 将4看成0, 7看成1
- 线段树维护区间0的个数 (c_0)， 1的个数 (c_1)， 最长上升子序列长度 (lis), 下降 (lds)。