题目链接
HDU 5334
想法题
题目分析
题目大意
给定一个数字n,让你构造出一个数列,这个数列的连续子数列数量为n,先输出这个数列的长度k,再输出这个数列。
解析
通过找规律可以发现,有m种不同的数字a,b,c,d…时,这些数字各有A,B,C,D…个,如果依次排列的话,可以生成长度为A+B+C+D+...+AB+BC+AC+...
个不同的子数列。举例来讲,abbbccdddd
,共有1个a,3个b,2个c,4个d,那么这个数列就可以生成1+2+3+2+1*3+1*2+1*4+3*2+3*4+2*4
个不同的子数列。根据题意要求,不得超过105个数,所以计算一下,三种不同数字的情况下可以达到109种子数列。这样,就变成了一个解三元二次方程的问题。a+b+c+a*b+b+c+a*c=n
并且a+b+c<1e5
,求a,b,c
值。将表达式变形,(a+c+1)(b+c+1)=n+(1+c)^2-c
,所以,只要对c
进行枚举,然后再枚举左侧对一个括号,整出时即可算出此时的a, b, c
,输出对应数量的不同数字即可。
代码
1 |
|