Test_Day1

雅礼联考

题目大意

  • 维护一个数列

\[X_n=aX^2_{n-1}+bX_{n-1}+c\]

信息均已知,问:

\[X_n.mod.m\]

  • 完成一种搜索

你从左上角出发,最后返回左上角,路径内部的区域视为被
你圈住。你不可以进入网格内部,只能在边上行走。你的路径不
能在左上角以外自交,但是边足够宽,你可以重复经过而不自交。

网格中有一些格子对你很重要,你要尽量圈住它;而另一些
格子对你有坏处,你不能圈住它。

求圈住\(i\)个重要的格子的最小路径长度。

  • 维护一种规划

面临的是一条有\(N\)个地点的路,他们从0号地点出发,要逃到\(N\)号地点去。每个地点的战斗都有一定的金币收入\(Ai\),也有一定的部队损失\(Bi\)。

这些人可以向后传送不超过\(L\)的距离。从一个地点传送到另一个地点时,他们会选择路径上除起点外的地形指数\(Ci\)最大的地点进行战斗,地形指数相同时选择最靠后的。

部队希望总金币收入与总部队损失的比值最大。


取模取得少,没判循环节,没想次方次方不能取模的事导致T1爆了

T2搜索最后炸了,T3分数规划套动态规划没写出来

一次惊险刺激的4个小时考试


题解

T1

对于前35%的数据,\(n,m<=10^6\)直接暴力就好

对于中间35%的数据,\(m<=10^6,n<=10^9\)对\(m\)下手.

可以看出来答案的范围在[0,m-1]之间,而\(m\)在\(10^6\)以内,我们可以近似地把答案看成一个\(\rho\)字形的答案区间,最后的答案一定在\(\rho\)字形内的圈里循环,我们可以直接\(O(1)\)解决.

具体实现可以开一个\(vis\)数组记录一下,周期就是这次出现这个答案-上次出现答案的地方,后面直接找到对应的位置就好了.

对于后面30%的数据

满足这个条件\(2a|b,4ac=b^2-2b\)

我们可以令\(b=2ak\)

继续推导公式

\[4ac=4a^2k^2-4ak\]

得到

\[c=ak^2-k\]

\[X_n=aX_{n-1}^2+bX_{n-1}+c\]

带入\(b,c\)

\[X_n=aX^2_{n-1}+2akX_{n-1}+ak^2-k\]

左右移项,完全平方公式合并

\[X_n+k=a(X_{n-1}+k)^2\]

令\(P_n=X_n+k\)

得到

\[P_n=aP_{n-1}^2\]

根据\(P_n\)的递推公式求通项公式可得

\[P_n=a^{2^{n}-1}*P_0^{2^n}\]

由上面的式子可知

\[P_0=X_0+k\]

\[X_n=P_n-k\]

所以我们难以解决的事如何快速的求出\(2^n-1\)和\(2^n\)

因为是幂的幂,所以我们不能取模,但是不取模的话会导致爆龙龙,所以当然是弃坑啊

我们可以考虑一个叫费马小定理的东西.

如果\(p\)是一个质数

\[a^{p-1}\%p\equiv1\]

题目中的特殊条件之三就是在这30%的数据中\(m\)是一个质数.

所以我们可以用\(m-1\)对幂进行取模.

剩下的任务就交给快速幂啦~


T2

状压搜索.

欠着喽,等会写再填坑了…

T3

用二分解决分数规划问题,由于精度暂时无法保证,所以我们需要用动态规划解决,但是因为数据的原因,对于这个动态规划我们需要用到数据结构优化.

最后就完了.

这我tm能写出来???我不把北门shichiguang????

我还是一个刚学01分数规划的孩子啊…

QAQ


By:Wahacer

2017.12.21

20:43

发表评论

电子邮件地址不会被公开。 必填项已用*标注