2019-team11/summary-191228

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
题面非常友好的一场。
ln开门推A，推了1h人推傻了，去写D，发现是初中题，费了点时间过掉了。
xtx发现F是板子题套个exkmp就秒了但因为long long喜+1。
xtx推E推了半天推完了。
ln思考G，把题目转化为青蛙跳荷叶的问题后和kc讨论了一下秒掉了（划掉，细节出了点锅+1）。
ln和xtx看B，看不太出来该怎么做，就搜题解然后回去睡了。
== 题解 ==
A。题意即求最小的b使得0<bx-py<b，即p/x < b/y < p/(x-1)，注意到p/x > 1，可以把整数部分剪掉取个倒数然后有点类欧几里得算法的味道。这个题目不用抄大数板子因为答案的数量级是对的，虽然中间会溢出但相当于在mod 1<<32的域内运算，答案必正确。
B。
D。n+1条一次函数之和，线性转移。
E。
F。
G。题目等价于有n片荷叶，x的位置是起点，y的位置是终点，要让青蛙从x跳到y且把所有荷叶都跳过一遍，跳的幅度至多是2。那么考虑ooooxooooyooo，要从x左边到x右边仅有一条道路，所以一开始得把左边跳完，而且跳法唯一。同理y右边也只有一种跳法了。那么题目就相当于求个前缀和，随便推推发现转移是f[x]=f[x-1]+f[x-3]。
H。
I。
J。

流水账

题面非常友好的一场。

ln开门推A，推了1h人推傻了，去写D，发现是初中题，费了点时间过掉了。

xtx发现F是板子题套个exkmp就秒了但因为long long喜+1。

xtx推E推了半天推完了。

ln思考G，把题目转化为青蛙跳荷叶的问题后和kc讨论了一下秒掉了（划掉，细节出了点锅+1）。

ln和xtx看B，看不太出来该怎么做，就搜题解然后回去睡了。

题解

A。题意即求最小的b使得0 1，可以把整数部分剪掉取个倒数然后有点类欧几里得算法的味道。这个题目不用抄大数板子因为答案的数量级是对的，虽然中间会溢出但相当于在mod 1<<32的域内运算，答案必正确。

B。

D。n+1条一次函数之和，线性转移。

E。

F。

G。题目等价于有n片荷叶，x的位置是起点，y的位置是终点，要让青蛙从x跳到y且把所有荷叶都跳过一遍，跳的幅度至多是2。那么考虑ooooxooooyooo，要从x左边到x右边仅有一条道路，所以一开始得把左边跳完，而且跳法唯一。同理y右边也只有一种跳法了。那么题目就相当于求个前缀和，随便推推发现转移是f[x]=f[x-1]+f[x-3]。

H。

I。

J。