长沙集训~春~Notes

Day 0

时光飞逝，眨眼间三个半月过去了。显然Nerlci_上次还没有被吊打满足，那么，再次踏上旅程如何？
（以上为废话）
显然有Nerlci_在的所有旅程都不是风平浪静的。坐的高铁非常准时地晚点了近1hr，以及这次来长沙时我刚做完手术==上次是拄拐，这次是手术创伤我死了好吧Qw
这次培训的时长为14天，双倍的快乐（但是，为什么会这样呢（被打死），OI界第一鸽子将继续准时（个鬼）为您带来每天的集训日记，请诸位尽情吐槽
Day 0入住三和大酒店的豪华标间！！！比标间大了好多的说！可惜明天就要回标间了==

Day 1

听说题目为我这位蒟蒻特意降低了难度？但是蒟蒻肯定还是会爆零啊QwQ

T1 完美子串

看到连续子串第一反应就是尺取。我们先从头开始向后取字母，每取一个字母判断当前子串头部有没有与子串中字母重复的，如果存在这样的头部，则可将头部向后推直至头部字母不与子串重复位置。由于需要求连续子串的原因，我们只能从头部开始删除。同时使用一个计数器统计已经有了多少种字母。若已经有26个字母则我们得到了一种可行的子串划分方案。显然会有很多种方案，那么我们取长度最小的即可。（蒟蒻第一反应是用一个堆存下所有方案==其实只要用一个变量比较一下就行了）
（似乎这套题比想象中的简单？）

T2 游戏

（AHOI2016初中组 游戏）
看到乘法想到质因数分解，将两个分数质因数分解后判断相同质因子个数之和能否被三整除。应该是一种可行的方案。但是时间复杂度劝退我啊！！总共有10^{6}次询问，每次两个数都是10^{9}级别的==T飞了好吧
这种时候就需要一些奇技淫巧。既然我们要算的是质因子个数之和能否被三整除，不如直接把两个数乘起来之后开三次方根！只要我们找到在O(log(n))级别的算法求立方根就好了！那么，自然是二分啦。我们二分出答案后要看一下两个数能否被立方根整除，以防出现两个数是两个完全立方数这种不符合题意的情况。
（以下是误导）
其实咱在开立方根这件事上第一反应是标准库……然后就被精度误差搞死了，所以说珍爱生命，远离double。

T3 泥泞的牧场

这个数据范围简直引人犯罪暴力啊！
可惜这并不是一道暴力模拟题。
（前置技能：二分图匹配）
我们可以将横行上的能连成片泥地的区域视作一个点，竖行上也同样处理。现在对于每一块泥地，我们可以视作是在横行和纵行点构成的二分图中连了一条边。考虑这条边的意义。这条边可以视为在该点所在的横行（竖行）放置了一块木板。我们求出二分图的最小覆盖，即为能覆盖所有泥地放置最少的木板数量。可证二分图最小覆盖与最大匹配相等，求出最大匹配即可。