基础算法(二)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn = 1e6+10;
int a[maxn], q[maxn];
int n, ans=0;

int main(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0,j=0;i<n;i++){
        q[a[i]]++;
        while(q[a[i]]>1){
            q[a[j]]--;
            j++;
        }
        ans=max(ans,i-j+1);
    }
    cout << ans << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<iostream>
using namespace std;

int lowbit(int x){
    return x & -x;  // 返回x二进制的最后一位1 (返回值是一个二进制数)
} 

int main(){
    int n;
    cin >> n;  // 多次测试
    while(n--){
        int x;
        cin >> x;
        int res = 0;
        while (x){
            x -= lowbit(x);  // 把最后一位1去掉
            res ++;
        }
        printf("%d ", res);
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

vector<int> alls;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

int find(int x){
    int i=0, r=alls.size()-1;
    while (l < r){
        int mid = (l+r)/2;
        if (alls[mid] >= x) r = mid;
        else l = mid+1;
    }
    return r+1; // 
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;

const int N=300100;

int a[N], s[N];
vector<int> alls;
vector<PII> add, query;

int find(int x){
    int l=0, r=alls.size()-1;
    while (l < r){
        int mid = (l+r)/2;
        if (alls[mid] >= x) r = mid;
        else l = mid+1;
    }
    return r+1; // 
}

int main(){
    int n, m;
    cin >> n >> m;
    
    while(n--){
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        
        alls.push_back(x);
    }
    
    while(m--){
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        
        alls.push_back(l);
        alls.push_back(r);
    }
    
    //去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    
    for (auto item: add){
        int x = find(item.first);
        a[x] += item.second;
    }
    
    for(int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    
    for (auto item: query){
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> PII;
vector<PII> p1, p2;

int main(){
    int n;
    cin >> n;
    while(n--){
        int l, r;
        cin >> l >> r;
        p1.push_back({l,r});
    }
    
    sort(p1.begin(), p1.end());
    
    int res = 1;
    for(auto item: p1){
        if (p2.size() == 0) p2.push_back(p1[0]);
        int l = item.first, r = item.second;
        if (l <= p2[p2.size()-1].second){
            if (r >= p2[p2.size()-1].second)
                p2[p2.size()-1].second = r;
        }
        else{
            res += 1;
            p2.push_back({l,r});
        }
    }
    cout << res << endl;
    return 0;
}