简单的问题
1000ms
1000ms
65536KB
算法的渐进时间复杂度是算法的运行时间的一种度量方式，通常用运行时间随输入规模的增长而增长的速率来表示。
时间复杂度是评估一个算法的重要参考标准。
比如常见的冒泡排序和选择排序，时间复杂度是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的数据规模运行时间显然太长了，无法达到我们的要求。所以请你帮忙修改一下这个程序（只是两重循环的部分），降低算法的时间复杂度，但是程序的功能不能改变。
时间复杂度是评估一个算法的重要参考标准。
比如常见的冒泡排序和选择排序，时间复杂度是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范围。两个数之间用空格分开。
每组数据的第一行有一个正整数 n (1≤n≤10000)。
接下来同一行有n个非负整数，每个数都不超过 2^16范围。两个数之间用空格分开。
Output
输出有T行，每行为一个非负整数，为每组输入数据的对应输出，结果不会超出32位整数的范围。
Sample Input
1 2 18467 6334
Sample Output
70239
这是一道涉及位运算的题目。按位或运算规则：1 | 1 = 1， 1 | 0 = 1，0 | 1 = 1, 0 | 0 = 0。
所以可以记录每个数的二进制表示每一位上的数是0还是1，当是1时，和其他数运算时这一位上的结果就是1.具体请参考代码。
//s[i]记录有多少个数的第i位上的数字是1
//flag[i][j]表示第i个数的第j位上的数字是0还是1
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int N = 1e4 + 5;
int a[N], s[20], flag[N][20];
int Pow(int x)
{
if(x == 0)
return 1;
int ans = 1;
for(int i = 1; i <= x; i++)
ans *= 2;
return ans;
}
int main()
{
int t, n, i, j;
scanf("%d",&t);
while(t--)
{
memset(s, 0, sizeof(s));
memset(flag, 0, sizeof(flag));
scanf("%d",&n);
int ans = 0;
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
int k = a[i];
for(j = 0; j <= 16; j++)
{
int r = k % 2;
if(r == 1)
{
s[j]++;
flag[i][j] = 1;
}
k /= 2;
}
}
for(i = 0; i < n; i++)
{
for(j = 0; j <= 16; j++)
{
if(flag[i][j] == 1)
ans += n * Pow(j);
else
ans += s[j] * Pow(j);
}
}
printf("%d\n",ans);
}
return 0;
}