BNU1065：简单的问题(数位dp)

时间复杂度是评估一个算法的重要参考标准。 

比如常见的冒泡排序和选择排序，时间复杂度是O(n^2)，而快速排序、归并排序的时间复杂度是O(nlogn)。这两类算法在实现的时候,其运行时间随着数据规模的增长而增长的速率不同。一般来说到n=10000的规模的时候两类算法的运行时间就会有显著差异。 

下面有一个程序：

-----------------------------------------------

#include<stdio.h>

int main()

{

   int n,a[10001];

   int T;

   int i,j,k;

   int ans=0;

   scanf("%d",&T);

   while(T--)

   {

       scanf("%d",&n);

       ans=0;

       for(i=0;i<n;++i)

           scanf("%d",&a[i]);

       for(i=0;i<n;++i)

           for(j=0;j<n;++j)

               ans+=(a[i]|a[j]);

       printf("%d\n",ans);

   }

return 0;

}

-----------------------------------------------

上面这个程序的时间复杂度就是O(n^2)的，输入规模增长到原来的n倍，运行时间将会是原来的n^2倍（两重循环内部的操作的次数变为原来的n^2倍）。这样的程序对于n高达10000的数据规模运行时间显然太长了，无法达到我们的要求。所以请你帮忙修改一下这个程序（只是两重循环的部分），降低算法的时间复杂度，但是程序的功能不能改变。

Input

测试数据有多组，第一行给出了测试数据的组数T（T<100）

每组数据的第一行有一个正整数 n (1≤n≤10000)。 

接下来同一行有n个非负整数，每个数都不超过 2^16范围。两个数之间用空格分开。

 

Output

输出有T行，每行为一个非负整数，为每组输入数据的对应输出，结果不会超出32位整数的范围。

Sample Input

1

2 18467 6334

 

Sample Output

70239

 

这题根据代码的意思就是将数组里的每个数与其他数进行或运算并相加，但是仅仅是对题目给出的代码，怎么优化都是超超时的，所以就要自己对来编写一个优化的代码

其实意思也很简单，就是统计一下每一位1的个数即可

 

#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
using namespace std;  
  
int dp[10005][17];  
int sum[17];  
  
int set(int n)  
{  
    int i,ans = 1;  
    if(n == 0)  
        return 1;  
    for(i = 1; i<=n; i++)  
        ans*=2;  
    return ans;  
}  
  
int main()  
{  
    int n,a[10001];  
    int T;  
    int i,j,k,t,r;  
    int ans;  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%d",&n);  
        ans=0;  
        memset(dp,0,sizeof(dp));  
        memset(sum,0,sizeof(sum));  
        for(i=0; i<n; ++i)  
        {  
            scanf("%d",&a[i]);  
            t = a[i];  
            for(j = 0; j<=16; j++)  
            {  
                r = t%2;  
                if(r)  
                {  
                    sum[j]++;//第j位1的总个数  
                    dp[i][j]=1;//该数的第j位2进制是1  
                }  
                t/=2;  
            }  
        }  
        for(i = 0; i<n; i++)  
        {  
            for(j = 0; j<=16; j++)  
            {  
                if(dp[i][j])//现在此位是1，与任何其他数相或都必为1，所以是总数加这位化为十进制的值  
                    ans+=n*set(j);  
                else//该位是0，则将其他数字同位为1的个数相加  
                    ans+=sum[j]*set(j);  
            }  
        }  
        printf("%d\n",ans);  
    }  

 

补充：软件开发 , C++ ,