Liny_@NotePad

沉迷ACG中

High数

YOYO posted @ 2009年10月24日 02:47 in 【ICPC】解题报告 , 1772 阅读

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:

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int main(void)
  5. {
  6.         int t, a[20];
  7.         cin >> t;
  8.  
  9.         a[0] = 1;
  10.         for(int i = 1, k = 1; i< 20; ++i)
  11.         {
  12.                 a[i] = 2 * a[i-1] + k;
  13.                 k *= 2;
  14.         }
  15.  
  16.         while(t--) {
  17.                 int n;
  18.                 cin >> n;
  19.                 cout << a[n - 1] << endl;
  20.         }
  21.  
  22.         return 0;
  23. }
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter