方知蓦然回首之时
那人却已不在灯火阑珊处

之前利用 aliyun 的学生机作为跳板机连几台在学校的机子,可是每次输入长长的一串命令总感觉比较麻烦,加上最近再写一个小工具来方便自己维护服务器,如果考虑跳板的命令又会比较麻烦,就去简单学习了一下如何通过配置 ssh config 来达到目的。

READ MORE

如果没有洗衣 + 烘干这种鬼畜的限制,只考虑一个做的话是非常简单的,用一个堆维护贪心即可。假设我们已经求出了 a_i 表示洗完 i 件衣服需要的最小时间,b_i 表示烘干 i 件衣服需要的最小时间。

考虑到所有衣服都被烘干后烘干机全部是空的,可以把这个过程倒过来,这样子就和洗衣服一样了,如下图:

考虑这个东西随便排是没有关系的,设一个排列 p_1 , p_2 , p_3 , ... , p_l ,我们需要最小化

\max ( a_1 + b_{p_1} , a_2 + b_{p_2} , a_3 + b_{p_3} , ... , a_l + b_{p_l} )

这个「取最大值」+「加法」与「加法」+「乘法」操作是十分类似的,同样满足排序不等式,并且同样可以用数学归纳法证明。

回忆一下结论,顺序和大于等于乱序和大于等于逆序和,我们只需要令 p_i = n - i + 1 即可直接求出答案。

READ MORE

先考虑 K = 0 的情况。我们显然需要将 x 轴和 y 轴分开考虑。但是考虑到 x 轴和 y 轴不能同时只增长 0 ,这个就可以二项式反演了。定义 f_i 表示恰好出现 i(0, 0) 的方案数,g_i 表示至少出现 i(0, 0) 的方案数,也就是题目给我们的 R 只能用 R - i 次。显然

\binom R k g_k = \sum_{i=k}^R \binom i k f_i \Leftrightarrow f_k = \sum_{i=k}^R (-1)^{k-i} \binom i k \binom R i g_i

ans = f_0 ,我们只需要求出 \{g_i\}_{i=0}^R 即可。

这个东西显然可以直接卷一下 \forall k \in [0, R] ,\; \left( \sum_{i=0}^M x^i \right)^k ,然而这个东西显然会让你 get TLE ,考虑有没有什么优秀的方法。

再次考虑容斥,用 f'_i 表示恰好有 i 步超出限制,g'_i 表示至少 i 步超出限制。显然

g'_k = \sum_{i=k}^R \binom i k f'_i \Leftrightarrow f'_k = \sum_{i=k}^R (-1)^{k-i} \binom i k g;_i

g_iR = i 时的 f'_0 。这个 g'_i 就比较好求了,可以插板法,我们硬点一些箱子至少选 M + 1 ,另一些至少选 0 个。7

以上部分的时间复杂度是 O(R^2) 的,也可以通过 60\% 的数据。

READ MORE