簡單的問題

Time Limit:?1000ms Case Time Limit:?1000ms Memory Limit:?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的數據規模運行時間顯然太長了，無法達到我們的要求。所以請你幫忙修改一下這個程序（只是兩重循環的部分），降低算法的時間復雜度，但是程序的功能不能改變。

Input

測試數據有多組，第一行給出了測試數據的組數T（T<100）
每組數據的第一行有一個正整數 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);elseans += s[j] * Pow(j);}}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的bnuoj 1065 简单的问题（位运算）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。