ToB企服应用市场:ToB评测及商务社交产业平台

标题: P2831 [NOIP2016 提高组] 愤怒的小鸟 [打印本页]

作者: tsx81428 时间: 2024-8-4 22:51
标题: P2831 [NOIP2016 提高组] 愤怒的小鸟
思绪：

思量先求出经过 \((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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)