Equation

灰太狼 2023-06-01 15:53 106阅读 0赞

\(Equation\)

m6aGge.png

这道题目把式子两面移一下项,变为
\[a_1*x_1+a_3*x_3+a_5*x_5=a_2*x_2+a_4*x_4+a_6*x_6\]

然后用类似于\(meet\ in\ the\ middle\)的方法进行对式子两边统计

为什么当时没有做出来??

  • 时间复杂度分析错了
  • 主要原因还是搜索的答案数弄错了,正解的搜索方案数应该是\(3^k\),如果考虑重复答案会更少,和a_i并没有关系。

    include #include #include #include #define ll long long using namespace std; const int N=10,MAXN=1e6+100; mapm; ll k,ans; int base; ll a[N],b[N]; int num[MAXN]; inline void dfs2(int x,ll sum) { if (!x) { if (m.find(sum)!=m.end()) ans+=num[m[sum]]; return ; } for (int i=1;i<=k;i++) dfs2(x-1,sum+b[x]i); return ; } inline void dfs1(int x,ll sum) { if (!x) { if (m.find(sum)!=m.end()) num[m[sum]]++; else { m[sum]=++base; num[base]=1; } return ; } for (int i=1;i<=k;i++) dfs1(x-1,sum+a[x]i); return ; } int main() { scanf(“%lld”,&k); int num1=0,num2=0; for (int i=1;i<=6;i++) if (i%2==1) scanf(“%lld”,&a[++num1]); else scanf(“%lld”,&b[++num2]); dfs1(3,0); dfs2(3,0); printf(“%lld\n”,ans); return 0; }

题外话:不要搞骚操作,多写几个变量,多写几句话死不了。

转载于:https://www.cnblogs.com/last-diary/p/11406078.html

发表评论

表情:
评论列表 (有 0 条评论,106人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Equation

    \\(Equation\\) ![m6aGge.png][] 这道题目把式子两面移一下项,变为 \\\[a\_1\x\_1+a\_3\x\_3+a\_5\x\_5=

    相关 机器学习笔记5——nomal equation

        还记得两个变量求极致么,有这么一个结论,如果你已知有个最值,那么你可以放心的把唯一的极值当作最值。当然要注意边界条件。比方开阔号那就可以直接用,闭括号就不行,最小值可能