标題: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 }