High数
YOYO
posted @ 2009年10月24日 02:47
in 【ICPC】解题报告
, 1808 阅读
NUAA 1101：http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1101
在soso上看到此题，太长了直接看Sample，根据1->1，2->3，3->8直接推断是1->1/n->n^2-1，
还好没有直接回答 囧，我百度了发现是NUAA的题，提交立刻WA~ 还是test 1~
于是回头仔细看题目 发现是求n二进制数里面有多少个1，o(╯□╰)o。。
但是好懒得去想怎么做，反正n最大只到20，那就找规律吧 = _ = ，于是我算出来4等于20，5等于48。
于是找到了。。。a[0] = 0, a[n] = a[n-1] * 2 + n。。。
下面是代码，不过这里的0代表1，因此a[0] = 1：
-
#include<iostream>
-
using namespace std;
-
-
int main(void)
-
{
-
int t, a[20];
-
cin >> t;
-
-
a[0] = 1;
-
for(int i = 1, k = 1; i< 20; ++i)
-
{
-
a[i] = 2 * a[i-1] + k;
-
k *= 2;
-
}
-
-
while(t--) {
-
int n;
-
cin >> n;
-
cout << a[n - 1] << endl;
-
}
-
-
return 0;
-
}
- 无匹配
评论 (0)
