CF 1257 题解
A Two Rival Students
每次交换都可以让距离增加 \(1\), 上界是 \(n-1\).
题目说至多而不是恰好交换 \(x\) 次, 于是不需要考虑边界.
B Magic Stick
一个重要的观察是: 如果能够得到 \(x\), 那么就能得到任意小于等于 \(x\) 的数, 这是操作二保证的.
考虑操作 \(1\) 有什么用:
首先, 一个观察是, 如果我有 \(2^k\), 那么我就能得到 \(3^k\), 这个增量是不小的, 而我们还可以再把 \(3^k\) 减掉一个数把它变成 \(2\) 的指数次幂, 再重复这个过程, 这个过程能否一飞冲天呢?
进行一些尝试:
考虑我现在想找到一个数 \(x\), 它能够变成 \(10^9\) 以内的任何数.
如果它能够变成 \(3^{19}=1162261467\), 那它一定合法;
因此如果它能变成 \(2^{19}=524288\) 就可以了;
这个数加上一个数约束严格更强, 把它变成 \(531441=3^{12}\);
因此有 \(2^{12}=4096\) 就够了.
以此类推:
\[2^{12}=4096<6561=3^8\\\rightarrow 2^8=256<729=3^6\\\rightarrow 2^6=64<84=3^4 \\ \rightarrow 2^4=16<27=3^3\\\rightarrow 2^3=8<9=3^2\\\rightarrow 2^2=4<9=3^4\\\rightarrow 2^4\ldots \]我们发现, 大于等于 \(4\) 的数能变成小于等于 \(10^9\) 的任意数, 那小于 \(4\) 的怎么办呢?
模拟一下就能发现, \(3\) 能变成 \(1,2,3\), \(2\) 能变成 \(1,2,3\), \(1\) 能变成 \(1\).
C Dominated Subarray
发现一个合法序列至少要有两个一样的元素, 找最近的两个相邻元素距离即可.
D Yet Another Monster Killing Problem
发现这个怪物需要顺序的打, 那只能 dp 了.
设 \(f_i\) 表示打败前 \(i\) 个怪兽需要的最少天数.
设 \(lst_i\) 表示第 \(i\) 天至多到第 \(lst_i\) 可以一次杀完, 发现如果一个集合里的怪兽可以一次杀完, 那么它的子集都可以, 因此这个贪心是对的, 而且有可二分性.
考虑如何 check.
我们二分到一个 \(mid\) 作为 \(lst_i\), 那么需要:
\[\exist k, stat. i-mid\leq s_k , \max_{j=mid+1}^ia_j\leq p_k. \]抽象出来, 现在有 \(m\) 个点 \((x_i,y_i)\), 每次询问给一个点 \((x_0,y_0)\), 请你回答是否存在点 \(k\) 使得 \(x_k\geq x_0,y_k\geq y_0\).
维护一个横坐标递增, 纵坐标递减的链, 找到第一个横坐标能够包住 \(x_0\) 的, 看看 \(y_k\) 是否能包住 \(y_0\).
这个链用单调栈即可.
二分套二分, 复杂度 \(O(n\log^2n)\).
E The Contest
发现操作数等于初始时不在指定位置的元素数量.
我们钦定结束时 \(A\) 掌管 \([1,l)\) , \(B\) 掌管 \([l,r)\), \(C\) 掌管 \([r,n]\), 其中 \([1\leq l\leq r \leq n + 1]\).
根据上面的理论, 则有:
\[ans=\sum_{a\in A}[a\geq l]+\sum_{a\in B}[a<l]+\sum_{a\in B}[a \geq r]+\sum_{a\in C}[a<r] \]这样, 答案就拆成了 \(ans=f_l+g_r\) 的形式, 可以拆开算了.
先用差分优化区间加来求出来 \(f\) 和 \(g\), 然后考虑, 我们枚举 \(l\) 的值, \(r\) 的唯一约束是 \(r\geq l\), 因此:
\[ans=\min_{l=1}^{n+1}(f_l+\min_{r=l}^{n+1}g_r) \]\(g\) 用后缀和即可.
F Make Them Similar
发现前面一半和后面一半的二进制位是独立的, 可以前后分开搜两边.
设对于一个 \(x\) 来说, 前一半二进制位得到的 popcount 是 \(a_i\), 后一半是 \(b_i\), 那么有:
\[a_1+b_1=a_2+b_2=a_3+b_3\dots \\ \rightarrow \forall k, a_1-a_k=b_k-b_1 \]这可以转化为一个字符串相等的问题. 用 hash 维护, 然后把两边搜出来的东西查看 hash 是否有一致的.
G Divisor Set
对于一个集合 \(A\), 寻找它的一个最大子集族 \(\mathcal{F}\) 使得其中任意两个集合互不包含, 那么 \(|\mathcal F|=\binom{|A|}{\lfloor\frac{|A|}{2}\rfloor}\).
首先, 容易构造这样一个方案, 充分性显然.
下证必要性:
对 \(F\) 中的每一个元素 \(S\) , 把 \(S\) 的全排列 和 \(A/S\) 的全排列做组合, 有 \(|S|!(|A|-|S|)!\) 种方案.
把所有的 \(S\) 得到的结果拼到一起, 得到一个排列, 由于 \(F\) 中的元素互不包含, 那么序列是不重的, 则有下面的式子:
\[\sum_{i=1}^ts_i!(n-s_i)!\leq n! \\ \rightarrow 1\geq\sum_{i=1}^t\frac{1}{\binom{n}{s_i}}\geq \sum_{i=1}^t\frac{1}{\binom{n}{\lfloor\frac{n}{2}\rfloor}} =\frac{t}{\binom{n}{\lfloor\frac{n}{2}\rfloor}}\\ \rightarrow t\geq\binom{n}{\lfloor\frac{n}{2}\rfloor} \\ \]这个结论对于数字一样成立, 证明特别复杂 不会
求方案数相当于你现在有 \(k\) 种物品, 每种物品有 \(s_i\) 个, 满足 \(\sum_{i=1}^ks_i=n\), 请你选出 \(\lfloor\frac{n}{2}\rfloor\) 个.
这个问题相当于一个背包, 而背包就等价于卷积. 我们设 \(F_i(x)=\sum_{k=0}^{s_i}x^k\), 答案即为 \([\lfloor\frac{n}{2}\rfloor]\prod_{i=1}^kF_i(x)\), 现在的问题是怎么快速的求出来所有的多项式乘起来.
实际上是好做的, 每次考虑用前面一半的结果和后面一般的结果做 NTT 即可, 递归的去做, 每一层的复杂度单 log, 有 log 层, 因此总复杂度 \(O(n\log^2n)\).
标签：lfloor,geq,frac,leq,题解,sum,CF,rfloor,1257 From： https://www.cnblogs.com/snowycat1234/p/18539801