2019-Sp043-lyk

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(1.png,700px)]]

[[Image(2.png,700px)]]


[wiki:2019-team2 返回Runespoor]

[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001491 contest]

== 流水账 ==


== 总结 ==

'''zqq: ''' 这场前期比较顺利，两个小时完成了签到。还过了K题。

            后面三个小时就非常崩溃。G题是FFT，但是我们一直没有找到方向。打表还假了一次。后来heltion靠组合数的规律强行搞过去了

            lyk的D题一开始写了一个错误的记忆化搜索。但是调试的过程中他爆栈了但是我们一开始以为linux的栈空间无限大，不知道怎么错了。（'''百度才知道默认只有10M'''）

            后来帮他调就忘了管算法。直到最后半小时才发现算法有问题。我想到了从终态开始bfs，但是没有想清楚。

            J题是一个图论，但是我想了10分钟左右，以为是一个很牛逼的字符串。其实不那么难。

            感觉我今天的状态非常混沌，3个小时后精神就很差。其实E题我见过非常类似的。但是今天这样也没有时间写了。

'''Heltion: ''' G的m小似乎只是为了系数不会爆.

== 题解 ==

[wiki:2017-Sp74-team2 legilimens]

wiki:2016-E34-team1 

[http://clatisus.com/Petrozavodsk%20Winter-2017.%20Jagiellonian%20U%20Contest#a.-the-catcher-in-the-rye G from Nonsense Time]

* A: 优秀的黄金分割三分是可以艹过去的

* D ： 从终态开始bfs，对于黑棋（想要使得距离max）只有一个状态的所有后继状态都被转移到，才加入队列更新。而对于白棋，任意一个后继状态被转移到就应该加入队列（因为其他后继状态肯定更长）。然而sub写的记忆化搜索，要去问下他的做法

* G : 对于素数幂q=p^k^, C(q^n^,i)%q中总是只有q/p+1项不为0. 因此可以O(q)得到q^n^步后模q的值. 复杂度最坏是n*64*32*log(64,t),根本过不了. 但显然出题人没有想到这种弱智算法没有造m=64的满数据.

* K ： lyk用了一个很简单的做法。避免了正解后缀自动机的麻烦。直接hash判断，相同长度的放一起(利用长度不同的只有sqrt(n)个，用unordered_map。复杂度O((n * sqrt(n) + 26 * n) * constant of undered_map) 出题人时限给的太大，直接过了

* J : 其实是一个图论题，我们开始还以为是字符串。。把所有前缀向相邻的后缀连边（用hash维护标号，用trie树比较麻烦）。然后要在二分图中找有向四元环。利用二分图的性质，枚举一个点的邻居的邻居，标记这个点，第二次枚举到即可得到答案。枚举时度数按根号n分治，如果第一个点的度数 > 根号n，则任意枚举（这里统计所有至少包含了一个度数 > 根号n的四元环）；而小于根号n则第二步只考虑小于根号n的邻居。

== 补题 ==

* D []

* E []

* J [zqq]

返回Runespoor

contest

流水账

总结

zqq: 这场前期比较顺利，两个小时完成了签到。还过了K题。

后面三个小时就非常崩溃。G题是FFT，但是我们一直没有找到方向。打表还假了一次。后来heltion靠组合数的规律强行搞过去了

lyk的D题一开始写了一个错误的记忆化搜索。但是调试的过程中他爆栈了但是我们一开始以为linux的栈空间无限大，不知道怎么错了。（百度才知道默认只有10M）

后来帮他调就忘了管算法。直到最后半小时才发现算法有问题。我想到了从终态开始bfs，但是没有想清楚。

J题是一个图论，但是我想了10分钟左右，以为是一个很牛逼的字符串。其实不那么难。

感觉我今天的状态非常混沌，3个小时后精神就很差。其实E题我见过非常类似的。但是今天这样也没有时间写了。

Heltion: G的m小似乎只是为了系数不会爆.

题解

legilimens

wiki:2016-E34-team1

G from Nonsense Time

A: 优秀的黄金分割三分是可以艹过去的
D ：从终态开始bfs，对于黑棋（想要使得距离max）只有一个状态的所有后继状态都被转移到，才加入队列更新。而对于白棋，任意一个后继状态被转移到就应该加入队列（因为其他后继状态肯定更长）。然而sub写的记忆化搜索，要去问下他的做法
G : 对于素数幂q=p^k, C(qⁿ,i)%q中总是只有q/p+1项不为0. 因此可以O(q)得到qⁿ步后模q的值. 复杂度最坏是n*64*32*log(64,t),根本过不了. 但显然出题人没有想到这种弱智算法没有造m=64的满数据.
K ： lyk用了一个很简单的做法。避免了正解后缀自动机的麻烦。直接hash判断，相同长度的放一起(利用长度不同的只有sqrt(n)个，用unordered_map。复杂度O((n * sqrt(n) + 26 * n) * constant of undered_map) 出题人时限给的太大，直接过了
J : 其实是一个图论题，我们开始还以为是字符串。。把所有前缀向相邻的后缀连边（用hash维护标号，用trie树比较麻烦）。然后要在二分图中找有向四元环。利用二分图的性质，枚举一个点的邻居的邻居，标记这个点，第二次枚举到即可得到答案。枚举时度数按根号n分治，如果第一个点的度数 > 根号n，则任意枚举（这里统计所有至少包含了一个度数 > 根号n的四元环）；而小于根号n则第二步只考虑小于根号n的邻居。

补题

D []
E []
J [zqq]

附加文件

1.png by zhangqingqi
2.png by zhangqingqi
handout-day-4 (1).pdf by zhangqingqi