天天看點

曆屆試題_log大俠

标題:Log大俠

    atm參加了速算訓練班,經過刻苦修煉,對以2為底的對數算得飛快,人稱Log大俠。

    一天,Log大俠的好友 drd 有一些整數序列需要變換,Log大俠正好施展法力...

    變換的規則是: 對其某個子序列的每個整數變為: [log_2 (x) + 1]  其中 [] 表示向下取整,就是對每個數字求以2為底的對數,然後取下整。

    例如對序列 3 4 2 操作一次後,這個序列會變成 2 3 2。

    drd需要知道,每次這樣操作後,序列的和是多少。

【輸入格式】

第一行兩個正整數 n m 。

第二行 n 個數,表示整數序列,都是正數。

接下來 m 行,每行兩個數 L R 表示 atm 這次操作的是區間 [L, R],數列序号從1開始。

【輸出格式】

輸出 m 行,依次表示 atm 每做完一個操作後,整個序列的和。

例如,輸入:

3 3

5 6 4

1 2

2 3

1 3

程式應該輸出:

10

8

6

【資料範圍】

對于 30% 的資料, n, m <= 10^3

對于 100% 的資料, n, m <= 10^5

資源約定:

峰值記憶體消耗 < 256M

CPU消耗  < 1000ms

請嚴格按要求輸出,不要畫蛇添足地列印類似:“請您輸入...” 的多餘内容。

所有代碼放在同一個源檔案中,調試通過後,拷貝送出該源碼。

注意: main函數需要傳回0

注意: 隻使用ANSI C/ANSI C++ 标準,不要調用依賴于編譯環境或作業系統的特殊函數。

注意: 所有依賴的函數必須明确地在源檔案中 #include <xxx>, 不能通過工程設定而省略常用頭檔案。

送出時,注意選擇所期望的編譯器類型。

思路:首先我的算法可以解決較小的用例,但是否可以通過所有的用例我不清楚,因為藍橋杯練習系統沒有這道題,應該逾時,不可能那麼簡單。個人就是按照題中的要求來的,整個代碼的

時間複雜度為O(n^2),隻不過要注意log函數在c++下标是e,是以要轉換為求下标為2的對數函數則可以表示為log(x)/log(2);

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int array[100000];
 5 int f(int a1,int a2)
 6 {
 7     for(int i=a1;i<=a2;i++){
 8         array[i]=(int)(log(array[i])/log(2)+1);
 9     }
10     int sum=0;
11     for(int i=0;i<sizeof(array)/sizeof(int);i++){
12         sum+=array[i];
13     }
14     return sum;
15 }
16 int main()
17 {
18     cin >> n >> m;
19     int ans[m];
20     memset(array,0,sizeof(array));
21     memset(ans,0,sizeof(ans));
22     for(int i=0;i<n;i++){
23         cin >> array[i];
24     }
25     int a1,a2;
26     int t=0;
27     while(m--){
28         cin >> a1 >> a2;
29         a1--;
30         a2--;
31         ans[t++]=f(a1,a2);
32     }
33     for(int i=0;i<t;i++){
34         cout << ans[i] << endl;
35     }
36 }      

裡對區間裡的值進行對數運算,可以看做是更新,區間更新,求和,很明顯是線段樹...

下面提供一個大佬的代碼隻供參考:

1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5  
  6 
  7 const int maxn = 100010;
  8 
  9 int num[maxn];
 10 
 11 int tree[maxn*2];
 12 
 13 int n,m;
 14 
 15 int l,r;
 16 
 17 int cnt;
 18 
 19  
 20 
 21  
 22 
 23 void build(int x,int l, int r)
 24 
 25 {    
 26 
 27     if (l == r){
 28 
 29         cin >> tree[x];
 30 
 31         if (tree[x] == 1){//統計數值1的個數 ,友善優化程式 
 32 
 33             cnt++;    
 34 
 35             tree[x] = 2;//将所有1均變為2,防止1幹擾程式優化 
 36 
 37         }
 38 
 39         return;
 40 
 41     }
 42 
 43     
 44 
 45     int mid = (l+r)/2;
 46 
 47     build(x*2,l,mid);
 48 
 49     build(x*2+1,mid+1,r);
 50 
 51     tree[x] = tree[x*2]+tree[x*2+1];
 52 
 53 }
 54 
 55  
 56 
 57 void update(int x,int l,int r,int L,int R)
 58 
 59 {
 60 
 61     if (tree[x] == (r-l+1)*2){        //如果全為2,直接傳回 
 62 
 63         return ;
 64 
 65     }
 66 
 67     if (l == r){
 68 
 69         tree[x] = num[tree[x]];
 70 
 71         return;
 72 
 73     } 
 74 
 75     
 76 
 77     int mid = (l+r)/2;
 78 
 79     if (R <= mid)
 80 
 81         update(x*2,l,mid,L,R);
 82 
 83     else if (L > mid)
 84 
 85         update(x*2+1,mid+1,r,L,R);
 86 
 87     else{
 88 
 89         update(x*2,l,mid,L,mid);
 90 
 91         update(x*2+1,mid+1,r,mid+1,R);
 92 
 93     }
 94 
 95     tree[x] = tree[x*2]+tree[x*2+1]; 
 96 
 97 } 
 98 
 99  
100 
101 int main()
102 
103 {
104 
105     for(int i = 1; i <= maxn; i++)    //打表 
106 
107         num[i] = (int)(log2(i) + 1);
108 
109     cin >> n >> m;
110 
111  
112 
113     build(1,1,n);
114 
115     while(m--){
116 
117         cin >> l >> r;
118 
119         update(1,1,n,l,r);
120 
121         cout << tree[1]-cnt << endl;
122 
123     }
124 
125     return 0;    
126 
127 }      

繼續閱讀