P2831 [NOIP2016 提高组] 愤怒的小鸟

打印 上一主题 下一主题

主题 853|帖子 853|积分 2561

思绪:

思量先求出经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式
我们有:

\[\begin{cases} ax_1^2 + bx_1 = y_1 \\ ax_2^2 + bx_2 = y_2\end{cases}\]
思量将 \(b\) 消掉,求出 \(a\)。
那么思量令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1}{x_2}\) 倍:

\[ax_1^2 + bx_1 - ax_1x_2 - bx_1 = y_1 - \frac{x_1}{x_2} y_2\]

\[a(x_1^2 -x_1x_2) = y_1 - \frac{x_1}{x_2} y_2\]

\[a = \frac{y_1 - \frac{x_1}{x_2} y_2}{x_1^2 -x_1x_2} = \frac{y_1x_2 - x_1 y_2}{x_1^2x_2 - x_1x_2^2}\]
由于 \(a\) 太复杂度,欠好带入,思量也将 \(a\) 消掉,求出 \(b\)。
那么思量令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1^2}{x_2^2}\) 倍:

\[ax_1^2 + bx_1 - ax_1^2 - b\frac{x_1^2}{x_2} = y_1 - y_2 \frac{x_1^2}{x_2^2}\]

\[b(x_1 - \frac{x_1^2}{x_2}) = y_1 - y_2 \frac{x_1^2}{x_2^2}\]

\[b = \frac{y_1 - y_2 \frac{x_1^2}{x_2^2}}{x_1 - \frac{x_1^2}{x_2}} = \frac{y_1x_2^2 - y_2 x_1^2}{x_1x_2^2 - x_1^2 x_2}\]
那么我们可以得到经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式为:

\[y = \frac{y_1x_2 - x_1 y_2}{x_1^2x_2 - x_1x_2^2} x^2 + \frac{y_1x_2^2 - y_2 x_1^2}{x_1x_2^2 - x_1^2 x_2} x\]
可以通过这个解析式求出其它在这个抛物线上的点,设 \(A_{i,j}\) 表现经过点 \(i\) 和点 \(j\) 的抛物线经过的所有点的点集。
思量状态压缩 dp,令 \(dp_S\) 表现 \(S\) 这个点集的鸟被射下来的最小次数,则:

\[dp_0 = 0\]

\[dp_{S \operatorname{or} A_{i,j}}  = \min(dp_{S \operatorname{or} A_{i,j}},dp_S + 1)\]

\[dp_{S \operatorname{or} 2^{i-1}} = \min(dp_{S \operatorname{or} 2^{i-1}},dp_S+1)\]
时间复杂度为 \(O(Tn^22^n)\)。
完备代码:

[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=19,M=(1ll
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

tsx81428

金牌会员
这个人很懒什么都没写!
快速回复 返回顶部 返回列表