tsy: “复: 你礼貌吗?”

由于一直使用的 Gmail, 很想有一个在 Gnome 下的邮件通知. 尝试过 Geary, 非常对胃口, 简单, 开机自启, 后台接收, 但他不能手动配置代理, 而系统代理终归很不方便(而且不知道为啥不好用); 也尝试过 Evolution, 虽然应用可以设置代理, 但是根本连不上 Gmail, 不知道是啥原因. 折腾了半天, 终于暴力的解决了这个问题:

Thunderbird + Birdtray + Minimize on Close + Startup

以前学埃筛的时候, 自以为自己理解了, 可实际上并没有理解, 而且是属于那种完全不知道原理的状态. 从 2020 年小米邀请赛开始, 就接触过了一些关于整除关系转移的 dp 题, 直到上周(还是上上周来着? 咕太久了, 不知道哩)cf的两个题, 都能够用埃筛优化. 做 cf 那两题时, 把埃筛优化 dp 的原理想清楚了, 同时也理解了埃筛为什么能够加速求素数的原理.

给出长度为 $n$ 的, 仅由 a, b, c 组成的字符串. 问长度最小的满足条件的子串, 条件为:

1. 长度至大于等于 $2$
2. a 在字串中的出现次数严格大于 b 的出现次数
3. a 在字串中的出现次数严格大于 c 的出现次数

不存在输出 -1.

记录一下一个小时没写出来的简单题, 主要讲讲这种思维题怎么想.

贪心很容易知道, 子串开头结尾一定是两个 a.

然后没有很好的思路, 于是可以考虑从小数据开始玩, 尝试发掘性质.

题目问长度, 所以从长度小的开始玩.

aa, 满足条件, aba, aca 也满足条件. axxa 这样的东西(x 不能是 a), 如果是 abba 或者 acca 就不满足了, 如果是 abca 或者 acba 才满足.

然后 axxxa 根据鸽子原理, 一定会有两个 b 或者两个 c, 一定不满足.

再接着考虑 axxxxa, 如果 x 还是填 b 或 c, 也一定不满足, 如果填 a, 则有一定满足的字串.

被学弟带飞, 最后终榜 21 名, 校外 19 名 (也就是说这水平可以进南邮校队???)

从 $2n$ 个点的无向完全图中, 删除给定的 $2n - 1$ 条边, 且这些边是一棵树. 问剩下的图的完美匹配数是多少.

$1 \le n \le 2000$

正难则反, 考虑求 “至少包含一条树边的完美匹配数”, 然后用完全图的完美匹配数相减.

无法直接数出 “至少包含一条树边的完美匹配数”, 所以这里考虑容斥. 如果能够求出包含树边 A 的完美匹配数, 包含树边 B 的完美匹配数, 包含树边 C 的完美匹配数… 包含树边 A 和 B 的完美匹配数, 包含树边 B 和 C 的完美匹配数, 包含树边 C 和 A 的完美匹配数… 包含树边 A, B, C 的完美匹配数… 这样就可以用容斥求出包含 A 或 B 或 C… 的完美匹配数, 即至少包含一条树边的完美匹配数了.

这样的话会有一个问题, 每条树边都得枚举, 复杂度会炸. 可以发现, 恰好包含一条树边, 无论是哪一条, 完美匹配数都是一样的. 进一步, 如果是恰好包含两条树边, 那么剩下来的点是可以随便连的, 而剩下来的点个数又是一样的, 所以, 无论选哪两条树边, 完美匹配数都是一样的. 那么我只要知道选择两条树边的方案有多少种, 然后乘以剩下来的点的匹配方案数, 就可以了. 推而广之, 现在的任务就是计算 “恰好选择k条树边的方案”.

期中考前打星, 勇!