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}\) 倍：
\
\
\
因为 \(a\) 太复杂度，不好带入，考虑也将 \(a\) 消掉，求出 \(b\)。
那么考虑令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1^2}{x_2^2}\) 倍：
\
\
\
那么我们可以得到经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式为：
\
可以通过这个解析式求出其它在这个抛物线上的点，设 \(A_{i,j}\) 表示经过点 \(i\) 和点 \(j\) 的抛物线经过的所有点的点集。
考虑状态压缩 dp，令 \(dp_S\) 表示 \(S\) 这个点集的鸟被射下来的最小次数，则：
\
\
\
时间复杂度为 \(O(Tn^22^n)\)。
完整代码：
#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 感谢发布原创作品，程序园因你更精彩 分享、互助 让互联网精神温暖你我 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 东西不错很实用谢谢分享 收藏一下 不知道什么时候能用到 收藏一下 不知道什么时候能用到 谢谢分享，试用一下 这个有用。 不错，里面软件多更新就更好了 很好很强大我过来先占个楼 待编辑 新版吗？好像是停更了吧。 前排留名，哈哈哈 这个有用。 鼓励转贴优秀软件安全工具和文档！ 谢谢分享，试用一下 谢谢楼主提供！ 收藏一下 不知道什么时候能用到 谢谢分享，辛苦了 前排留名，哈哈哈
页:
[1]
2