蓝桥杯01

发表于

机器人跳跃问题

题目

把二分复习了一遍

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
#include<iostream>
#include<vector>
using namespace std;
const int N = 100010;
int a[N];
int n;
bool check(int e){
    for(int i = 0; i < n; i++) {
        e = 2 * e - a[i];
        if(e >= 1e5) return true;
        else if(e < 0) return false;
    }
    return true;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int l = 0, r = 1e5;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

二分题，不过要考虑许多边界问题

子矩阵的和

题目

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], s[N][N];
int n, m, x;

int main(){
    cin >> n >> m >> x;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    while(x--){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
    }
}

图解

前缀和模板题

四平方和

题目

题目

先上一个tle的解法， O(n^2)超时

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
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int n;
unordered_map<int, pair<int, int>> p;

int main(){
    
    cin >> n;
    for(int c = 0; c * c <= n; c++){
        for(int d = c; c * c + d * d <= n; d++){
            int t = c * c + d * d;
            if(p.count(t) == 0) p[t] = {c, d};
        }
    }
    
    for(int a = 0; a * a <= n; a++){
        for(int b = 0; b * b + a * a <= n; b++){
            int t = n - b * b + a * a;
            if(p.count(t)) {
                cout << a << " " << b << " " << p[t].first << " " << p[t].second;
                return 0;
            }
        }
    }
    
    return 0;
}

找了个能过的代码改了一下， 二分法确实牛b

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
#include<iostream>
#include<vector>
#include<unordered_map>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 2500010;
int n;
struct Sum{
    int s, c, d;
    bool operator < (const Sum &t)const{
        if(s != t.s) return s < t.s;
        if(c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];

int main(){
    int m = 0;
    cin >> n;
    for(int c = 0; c * c <= n; c++){
        for(int d = c; c * c + d * d <= n; d++){
            int t = c * c + d * d;
            sum[m++] = {t, c, d};
        }
    }
    sort(sum, sum + m);
    for(int a = 0; a * a <= n; a++){
        for(int b = 0; b * b + a * a <= n; b++){
            int t = n - b * b - a * a;
            int l = 0, r = m - 1;
            while(l < r){
                int mid = (l + r) >> 1;
                if(sum[mid].s >= t) r = mid;
                else l = mid + 1;
            }
            if(sum[l].s == t){
                cout << a << ' ' << b << ' ' << sum[l].c << ' ' << sum[l].d << endl;
                return 0;
            }
        }
    }
    
    return 0;
}

分巧克力

题目

题目

对区间数进行二分查找，时间复杂度为O（nlog（n））

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N], w[N];
int n, k;

bool check(int mid){
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        res += (h[i] / mid) * (w[i] / mid);
        if (res >= k) return true;
    }
    return false;
}
int main(){
    
    cin >> n >> k;
    for(int i = 0; i < n ;i++){
        cin >> h[i] >> w[i];
    }
    int l = 0, r = 1e5;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r << endl;
    return 0;
}