问题描述:
大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：
(1) a是集合Ba的基，且a是Ba的第一个元素；
(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；
(3)没有其他元素在集合Ba中了。
现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？
AC代码
LL Ba[1000010];
int main()
{
int a,n;
while(cin >> a >> n)
{
Ba[1] = a;
int x = 1,y = 1;// 轮到哪个元素"上"了
for(int i = 2; i <= n; ++i)
{
Ba[i] = min(Ba[x] * 2 + 1, Ba[y] * 3 + 1);// 取较小
if(Ba[i] == Ba[x] * 2 + 1)
x++;
if(Ba[i] == Ba[y] * 3 + 1)
y++;
}
cout << Ba[n] << endl;
}
return 0;
}算法描述:
本题与H数可谓是一模一样,代码也一模一样.
集合是具有互异性的,不能存在重复的元素.
同H数,每个元素都有机会去构造集合的下一个元素.
题面的特征是要求构造由给定规则生成的单调序列.
STL set正可以保证单调性和互异性.
STL 优先队列不能保证互异性.