memset0 的博客

CF749G Replace All

2019-08-13
口胡
1 comment

给定两个 01 串 X, Y，其中可以包含若干问号表示这一位可以是 0 也可以是 1。求有多少对这样的二元字符串 (S, T) 满足 |S|, |T| \leq n 且将 X, Y 的每个 0 1 替换为 S, T 后两个串相等。

|X|, |Y|, n \leq 3 \times 10^5。

Link: https://codeforces.com/problemset/problem/794/G

配置 SSH config 使用跳板机连接

2019-08-10
运维
1 comment

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

Min_25 筛重新学习笔记

2019-07-30
算法
8 comments

大半年以前被集训队大爷 CMXRYNP 教育过一次，然而由于本人记忆力太差所以只能重新学习一遍。

LOJ6035 「雅礼集训 2017 Day4」洗衣服

2019-07-23
口胡
6 comments

如果没有洗衣 + 烘干这种鬼畜的限制，只考虑一个做的话是非常简单的，用一个堆维护贪心即可。假设我们已经求出了 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 即可直接求出答案。

LOJ6374 「SDWC2018 Day1」网格

2019-07-21
口胡
0 comment

先考虑 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_i 即 R = i 时的 f'_0 。这个 g'_i 就比较好求了，可以插板法，我们硬点一些箱子至少选 M + 1 ，另一些至少选 0 个。7

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