蓝桥杯04

发表于

连号区间数

题目

题目

模拟题，虽然简单，但是题目看了半天，宛如智障

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
#include<iostream>
#include<vector>
using namespace std;
const int N = 10010;
int n;
int a[N];

int main(){
    cin >> n;
    
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int res = 0;
    for(int i = 0; i < n; i++){
        int max_val, min_val;
        for(int j = i; j < n; j++){
            if(i == j) {
                max_val = a[j];
                min_val = a[j];
                res ++;
            }
            else {
                max_val = max(max_val, a[j]);
                min_val = min(min_val, a[j]);
                if(max_val - min_val + 1 == j - i + 1) res ++;
            }
        }
    }
    cout << res << endl;
    
    return 0;
}

第 N 位数字

题目

首先找规律，然后进行模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findNthDigit(int n) {
        long long k = 1, x = 9, s = 1;
        // k是数的位数, x是这一位数有多少个数, s是这一位数开始的数
        while(n > k * x){
            n -= k * x;
            k++, x *= 10, s *= 10;
        }
        int key = s + (n - 1) / k; //求出具体是哪一位数, 转换为字符串处理
        return to_string(key)[(n - 1) % k] - '0';
    }
};

二分法

关于二分法，一般是确定想找的条件，然后再举出它的相反的条件（比如求大于等于target的第一个数，就举出小于target的式子，然后破坏它）

看下面一段代码

1
2
3
4
5
while(l < r){	//l是区间的左端点， r是右端点， 都是能取得到的左闭右闭区间【l，r】
	int mid = (l + r) >> 1;
	if(a[mid] < target) l = mid + 1; //选择相反的条件， 然后给左端点值赋值破坏这个条件（mid不符合条件，换成mid+1）
	else if(a[mid] >= target) r = mid; //下面这一步就不用破坏了， 而是延续这个条件， 这就是二分法
}

递增三元组

菜到令人发指的地步， 写了半天二分，结果发现原来是二分思路的问题，不是我的问题，lower_bound函数在失败时会返回last，而我手写的二分没有这个功能，误入歧途了

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<algorithm>
using namespace std;

const int N = 100010;
int a[N], b[N], c[N];


int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    sort(c + 1, c + n + 1);
    long long res = 0;
    for(int i = 1; i <= n; i++){
        int pos1, pos3;
        //第一次查找小于b[i]的第一个数
        int l = 1, r = n;
        while(l < r){
            int mid = (l + r + 1) / 2;
            if(b[i] <= a[mid]) r = mid - 1;
            else l = mid;
        }
        pos1 = l;

        l = 1, r = n;
        //第二次查找大于b[i]的第一个数
        while(l < r){
            int mid = (l + r) / 2;
            if(c[mid] <= b[i]) l = mid + 1;
            else r = mid;
        }

        pos3 = l;
        
        if(a[pos1] < b[i] && b[i] < c[pos3])
        res += (long long)pos1 * (n - pos3 + 1);
        //cout << pos1 - 1 << ' ' << n - pos3 + 1 << endl;
    }
    cout << res << endl;
}

经过这么一遭，算是加深二分的印象了，想要求什么就直接二分什么，不要曲线救国