POJ 3187 Backward Digit Sums(暴力)
题意:给定一个n和m,然后你会有一个序列,里面有n个元素,且这n个元素是1到n的。按照题中树塔的形状,给出了最后的值m,问初始序列是怎样的。如果有多个答案输出字典序最小的。且没有说如果没有答案输出啥,那就默认这个肯定有解。解法:首先我算了算最上层每个值对m的贡献,发现这是一个杨辉三角。所以先预处理一下得到一个杨辉三角,然后直接枚举上面n个数字,n最大为10,最大运算量也就10!=3e6,所以这
·
题意:给定一个n和m,然后你会有一个序列,里面有n个元素,且这n个元素是1到n的。按照题中树塔的形状,给出了最后的值m,问初始序列是怎样的。如果有多个答案输出字典序最小的。且没有说如果没有答案输出啥,那就默认这个肯定有解。
解法:首先我算了算最上层每个值对m的贡献,发现这是一个杨辉三角。所以先预处理一下得到一个杨辉三角,然后直接枚举上面n个数字,n最大为10,最大运算量也就10!=3e6,所以这是完全没有压力的。
代码如下:
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int num[15][15];
int n, m, a[15];
bool Check() {
int ans = 0;
for(int i = 1; i <= n; i++) {
ans += num[n][i] * a[i];
}
if(ans == m)
return 1;
return 0;
}
int main() {
num[1][1] = 1;
for(int i = 2; i <= 10; i++) {
for(int j = 1; j < i; j++) {
num[i][j] = num[i - 1][j - 1] + num[i - 1][j];
}
num[i][i] = 1;
}
cin >> n >> m;
for(int i = 1; i <= n; i++)
a[i] = i;
if(Check()) {
for(int i = 1; i <= n; i++) {
printf("%d%c", a[i], i == n ? '\n' : ' ');
}
} else {
while(next_permutation(a + 1, a + n + 1)) {
if(Check())
break;
}
for(int i = 1; i <= n; i++) {
printf("%d%c", a[i], i == n ? '\n' : ' ');
}
}
return 0;
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献1条内容
所有评论(0)