2016-E07-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||TaZoF||F||TLE|| || ||G++||1027||2016-09-22 16:52:12||
||TaZoF||I||AC||15896||1185||G++||1503||2016-09-22 15:26:22||
||TaZoF||B||AC||2612||702||G++||1471||2016-09-22 14:48:02||
||TaZoF||M||AC||75080||4149||G++||2162||2016-09-22 14:32:10||
||TaZoF||B||TLE|| || ||G++||2209||2016-09-22 13:37:55||
||TaZoF||B||TLE|| || ||G++||2195||2016-09-22 13:23:50||
||TaZoF||D||AC||1412 KB||15 ms||GCC||408||2016-09-22 12:44:39||
比赛链接: http://bak.vjudge.net/contest/133358

== 流水账 ==
=== TsReaper ===
开场后很快发现了简单题D，'''D1y14'''。之后我们决定尝试通过数量较多的B，学长们想了一个AC自动机的做法，但是没有仔细运算复杂度，T了两次。starve学长写B期间hzf学长想到了M的做法，我也想到了B更科学的做法。starve学长下机后我写M，'''M1y122'''，之后starve学长'''B3y138'''。

之后我和hzf学长想F，starve学长发现I似乎是比较明显的三维偏序问题，而且数据范围也很好。虽然觉得I题还没什么队过真的科学吗，不过暂时没什么题可以写了，而且学长做法也比较科学，学长就写了，'''I1y176'''。F题我们想了一些办法，但是复杂度都太高了。

== 总结 ==
=== TsReaper ===
 * 做得好的地方
   * I题虽然没什么人过，但是对解法比较有自信，是正确的决策。
 * 做得不好的地方
   * B题AC自动机写之前没有仔细分析复杂度，一段时间思路都被AC自动机限制。
   * 10^9^以内因数最多的数只有1344个因数。这个数据不知道，使得复杂度分析不正确，很多简单的做法都没有考虑。

== 题解 ==
=== B - Bazinga ===
如果用AC自动机，复杂度是O(TN*2000*26)，时限只有1s太紧了。

可以这样想：如果最后一个字符串不能满足条件，那么之前所有的串都是最后一个串的子串。这样，我们可以预处理最后一个串里，哪些子串是之前的串。然后我们枚举之前所有串，看看它在最后一个串里的区间是否包含了它前面的串。这样，复杂度就是O(T(N*2000+N^2^))。

=== D - Pagodas ===
显然，所有能建成的塔的编号都能写成ax+by的形式。也就是说，这些编号都是gcd(a,b)的倍数。显然一共还能建成n/gcd(a,b)-2座塔，判断一下奇偶性即可。

=== F - Frogs ===
如果知道了10^9^以内因数最多的数只有1344个因数，很多方法就能使用了。

如果一只青蛙的步长为x，那么它能占领的石头编号就是gcd(x,m)的倍数。设f(i)表示所有满足“x能被m的因数i整除，而不能被m大于i的因数整除”的x值之和，显然有f(i) = (m-i)*(m/i)/2 - sum(f(j))，j是m的因数且是i的倍数。接下来我们枚举所有m的因数i，如果存在一只青蛙的步长可以整除i，说明f(i)所代表的石头编号都能被青蛙占领，那么答案加上f(i)。这样做的复杂度是因数的平方级。

=== I - Triple ===
很容易对于每对(c,d)，求出c和d已知时，最大的a是多少。然后就是对10^6^个点做三位偏序问题即可。

=== M - Meeting ===
像做dijstra一样，记一个当前已求出最短路的点集合S，和一个待考虑的优先队列Q。每次从Q里取出离起点最近的set，把set里所有的点都放进S里，再把这些点属于的其它set算好距离后放进Q中即可。

== 补题 ==
=== TsReaper ===
~~F~~, G
UserProblemResultMemoryTimeLanguageLengthSubmit Time
TaZoFFTLE G++10272016-09-22 16:52:12
TaZoFIAC158961185G++15032016-09-22 15:26:22
TaZoFBAC2612702G++14712016-09-22 14:48:02
TaZoFMAC750804149G++21622016-09-22 14:32:10
TaZoFBTLE G++22092016-09-22 13:37:55
TaZoFBTLE G++21952016-09-22 13:23:50
TaZoFDAC1412 KB15 msGCC4082016-09-22 12:44:39

比赛链接: http://bak.vjudge.net/contest/133358

流水账

TsReaper

开场后很快发现了简单题D，D1y14。之后我们决定尝试通过数量较多的B，学长们想了一个AC自动机的做法，但是没有仔细运算复杂度，T了两次。starve学长写B期间hzf学长想到了M的做法，我也想到了B更科学的做法。starve学长下机后我写M，M1y122，之后starve学长B3y138。

之后我和hzf学长想F，starve学长发现I似乎是比较明显的三维偏序问题，而且数据范围也很好。虽然觉得I题还没什么队过真的科学吗，不过暂时没什么题可以写了，而且学长做法也比较科学，学长就写了，I1y176。F题我们想了一些办法，但是复杂度都太高了。

总结

TsReaper

  • 做得好的地方
    • I题虽然没什么人过，但是对解法比较有自信，是正确的决策。
  • 做得不好的地方
    • B题AC自动机写之前没有仔细分析复杂度，一段时间思路都被AC自动机限制。
    • 109以内因数最多的数只有1344个因数。这个数据不知道，使得复杂度分析不正确，很多简单的做法都没有考虑。

题解

B - Bazinga

如果用AC自动机，复杂度是O(TN*2000*26)，时限只有1s太紧了。

可以这样想：如果最后一个字符串不能满足条件，那么之前所有的串都是最后一个串的子串。这样，我们可以预处理最后一个串里，哪些子串是之前的串。然后我们枚举之前所有串，看看它在最后一个串里的区间是否包含了它前面的串。这样，复杂度就是O(T(N*2000+N2))。

D - Pagodas

显然，所有能建成的塔的编号都能写成ax+by的形式。也就是说，这些编号都是gcd(a,b)的倍数。显然一共还能建成n/gcd(a,b)-2座塔，判断一下奇偶性即可。

F - Frogs

如果知道了109以内因数最多的数只有1344个因数，很多方法就能使用了。

如果一只青蛙的步长为x，那么它能占领的石头编号就是gcd(x,m)的倍数。设f(i)表示所有满足“x能被m的因数i整除，而不能被m大于i的因数整除”的x值之和，显然有f(i) = (m-i)*(m/i)/2 - sum(f(j))，j是m的因数且是i的倍数。接下来我们枚举所有m的因数i，如果存在一只青蛙的步长可以整除i，说明f(i)所代表的石头编号都能被青蛙占领，那么答案加上f(i)。这样做的复杂度是因数的平方级。

I - Triple

很容易对于每对(c,d)，求出c和d已知时，最大的a是多少。然后就是对106个点做三位偏序问题即可。

M - Meeting

像做dijstra一样，记一个当前已求出最短路的点集合S，和一个待考虑的优先队列Q。每次从Q里取出离起点最近的set，把set里所有的点都放进S里，再把这些点属于的其它set算好距离后放进Q中即可。

补题

TsReaper

F, G

附加文件