题目链接
给出B数组，B数组的下标i代表A数组中的子集和（存在空集，代表0），然后B[i]代表A数组中子集和为i的有多少个 类似背包这里给出了B数组，要你反向求数组A，思路是B数组中从下标1开始第一个非零的数的下标i肯定是A数组中的第一个元素 然后开始反向背包 从B数组中依次去掉A数组中的元素 例如样例：B:[1,1,1,1] 代表A中子集和为0的有1个 子集和为1的有1个 子集和为2的有1个 子集和为3的有1个 所以元素1必定在数组A中 再从数组B中去掉这个这个元素1 变成B:[1,0,1,0] 所以现在下标2必定在数组A中 然后B数组去掉这个元素2变成B:[1,0,0,0] 所以最终A数组为[1,2] 公式为B[j]=B[j-i]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;const int maxn = 1e4;
int A[maxn], B[maxn];
int t, n, m;void solve()
{int cnt = 0;int i = 1;while (cnt <= n){if (B[i]!=0){A[++cnt] = i;for (int j = i; j <= m; j++){B[j] -= B[j - i];}}elsei++;}printf("%d", A[1]);for (int k = 2; k <= n; k++)printf(" %d", A[k]);printf("\n");
}int main()
{scanf("%d", &t);while (t--){scanf("%d%d", &n, &m);for (int i = 0; i <= m; i++)scanf("%d", &B[i]);solve();}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
