HDOJ 2062 Subset sequence
题目描述
解题思路
1. 确定子串数量，缩小问题规模。
题意想要得到的是指定序号的子串，因此需要先分析每个串有几个子串，通过观察发现，n个数字的串，其子串的数量满足f[n] = n * (f[n - 1] + 1)。如图：
同时子串的排列是分组的，其关系满足f[n] = g[n] * n，推导出
g[n] = （n-1) * g[n - 1] + 1。因此对于每个序列我们能得到它在第first组中。那么能确定第一个数字之后问题的规模就变成了确定（n - 1, m - (first - 1) * g[n] - 1))的第一个数字。此时指定序号m = m - (first - 1)*g[n] - 1，去掉了多余数量只讨论在第first组中的次序，-1，是因为每组的首个子串只有一项数字，输出这个数字后，这个子串已经变成空集，不再参与后面的计算。
2. 确定每组的数字
得到组号first后，利用ah数组来确定输出的值，ah数组大小为20，初始值为1从0开始遍历ah，统计1的数量，等于first时，将当前序号+1输出，并将数组元素置0,。
因此解题过程：
- 确定组号first，输出组号对应数字i + 1，将ah[i]置0。
- m减去(first - 1)*g[n] - 1
- 重复1,2步骤直到m变为0，输出完毕。
代码
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;
int ah[20];
int ordernum(int order)
{
int i,s = 0;
for(i = 0; i < 20; i++)
{
if(ah[i] != 0)
{
s++;
if(s == order)
{
ah[i] = 0;
return (i + 1);
}
}
}
}
int main(int argc, char** argv) {
long long gn[21],num,order;
int i,first;
gn[1] = 1;
ah[0] = 1;
for(i = 2; i < 21; i++)
gn[i] = (i - 1) * gn[i - 1] + 1;
while(cin >> num >> order)
{
for(i = 0; i < 20; i++) ah[i] = 1;
while(order)
{
first = order / gn[num] + (order % gn[num]? 1 : 0);
order = order - (first - 1) * gn[num] - 1;
num--;
cout << ordernum(first);
if(order)
cout << " ";
}
cout << endl;
}
return 0;
}
想法
这道题想了挺久，后面参考了https://blog.csdn.net/qq_33266889/article/details/53468509的博客，了解了一下解题步骤，自己实现了代码。但是一直WA，后面发现原来是没有将输入的两个变量设置为long long类型，发现错误后真是欲哭无泪。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2062