gpt4 book ai didi

c++ - 所有可能的游戏分数的总和

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:56:43 24 4
gpt4 key购买 nike

我正在处理一个解决方案无法理解的问题。我提出了自己的解决方案,但未被接受:

N+1 个数从 A0 到 AN 依次出现(一次一个)。每个数字都可以放在最后一个序列的任一侧。此时的分数将是该数字与其相邻数字的乘积,例如:A0.A1.A2 或 A2.A0.A1(A2 可以放在 A0.A1 的任一侧,因此分数可以是 A1.A2 或 A2。 A0;在 A2 出现之前也可能存在 A1.A0)。我们需要总结所有可能组合的所有可能得分;即第一个序列在 N+1 个数字上的得分总和,然后对其他一些序列求和,依此类推,最后是所有这些总和的总和。

这是被认为可以接受的逻辑:

int pwr[0] = 1;

for (int i = 1; i < 100000; i++)
pwr[i] = (pwr[i - 1] << 1) % MOD;

extra = A0 * 2;
sum = 0;
for (int i = 1; i <= N; i++){
Ai = scan();
sum = (sum * 2 + Ai * extra) % MOD; //Mod is a scaling factor
extra = (extra + pwr[i] * Ai) % MOD;
}

有人可以解释一下这是如何工作的吗?

这是我对同一问题的逻辑(解决方案),但没有接受:

#include <iostream>
#include <cmath>

int main()
{
int T;
std::cin>>T;
long long int output[T];
for (int i = 0; i < T; ++i)
{
int N;
std::cin>>N;
long long int inp[N+1];
for (int j = 0; j <= N; ++j)
{
std::cin>>inp[j];
}
long long int tot = 0;
for (int j = 0; j < N; ++j)
{
for (int k = j+1; k <= N; ++k)
{
tot += (inp[j] * inp[k] * pow(2,N-k+1));
}
}
long long int num = pow(10,9) + 7;
output[i] = tot % num;
}
for (int i = 0; i < T; ++i)
{
std::cout<<output[i]<<std::endl;
}
return 0;
}

最佳答案

解释

我相信在循环的每次迭代开始时:

  1. sum 表示元素 0..i-1 所有排列的总分
  2. extra表示元素0..i-1所有排列的两条边元素之和

另请注意,元素 0..i. 有 pow[i]=2^i 排列

开始时,唯一的排列是 [A0],其总和为 0,总边为 2.A0,因为 A0 在左右两边。

在第 i 次迭代中,我们通过考虑 Ai 在左侧的所有排列以及 Ai 在右侧的所有排列,将排列数加倍。因此,这些排列的内部分数是 2*sum,考虑边缘样本的额外分数是 Ai*extra

对于所有 2^i 排列,extra 也需要增加 Ai,因为它在每个新排列中要么在左边,要么在右边。

例子

考虑 [A0,A1,A2]。

有 4 种可能的构建序列的方法:

  1. 右/右 A0,A1,A2 得分 = A0.A1+A1.A2
  2. 右/左 A2,A0,A1 得分 = A0.A1+A2.A0
  3. 左/右 A1,A0,A2 得分 = A0.A1+A2.A0
  4. 左/左 A2,A1,A0 得分 = A0.A1+A2.A1

总分4A0.A1+2A1.A2+2A2.A0

关于c++ - 所有可能的游戏分数的总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44463946/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com