蓝桥杯06

发表于

日志统计

题目

题目

双指针+piar，技巧性题目

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> PII;

PII logs[N];		//统计日志
int cnt[N], st[N];	// cnt是点赞数统计   
					// st是满足要求的id数

int main(){
    int n, limit, k;
    scanf("%d%d%d", &n, &limit, &k);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &logs[i].first, &logs[i].second);
    }
    sort(logs, logs + n);
    for(int i = 0, j = 0; i < n; i++){
        int id = logs[i].second;
        cnt[id]++;
        while(logs[i].first - logs[j].first >= limit){
            cnt[logs[j].second]--;
            j++;
        }
        if(cnt[id] >= k) st[id] = 1;
    }
    
    for(int i = 0; i <= 1e6; i++){
        if(st[i] == 1) printf("%d\n", i);
    }
    return 0;
}

献给阿尔吉侬的花束

题目

题目

#define 命令是 C 语言中的一个宏定义命令 ,它用来将一个标识符定义为一个字符串

typedef 关键字来定义自己习惯的数据类型名称，来替代系统默认的基本类型名称、数组类型名称，后面有省略号

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<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N = 210;
int n, m;
char grid[N][N];
int dist[N][N];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

#define x first
#define y second

int bfs(pair<int, int> start, pair<int, int> end){
    memset(dist, -1, sizeof dist);
    queue<pair<int, int>> q;
    
    dist[start.x][start.y] = 0;
    q.push(start);
    
    while(q.size()){
        auto t = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            if(grid[x][y] == '#') continue;
            if(dist[x][y] != -1) continue;
            
            dist[x][y] = dist[t.x][t.y] + 1;
            
            if(end == make_pair(x, y)) return dist[x][y];
            q.push({x, y});
        }
    }
    return -1;
}

int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n >> m;
        pair<int, int> start, end;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> grid[i][j];
                if(grid[i][j] == 'S') {
                    start = {i, j};
                }
                if(grid[i][j] == 'E') end = {i, j};
            }
        }
        int distance = bfs(start, end);
        if(distance == -1) puts("oop!");
        else cout << distance << endl;
    }
    return 0;
}

红与黑

题目

题目

对于bfs搜索，要特别注意标记数组标记的位置，遵循开始点在哪赋值，后面就在哪赋值

比如这题。开始点在while循环之前就标记好了，然后再开始队列循环。同理，对于后面的点，也应该是先标记后从队列中取出来操作，所以就是在for循环中标记

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
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 25;
char grid[N][N];
int st[N][N];
int n, m;
#define x first
#define y second
typedef pair<int, int> PII;
PII start;
int res;

void bfs(){
    memset(st, -1, sizeof st);
    res = 0;
    queue<PII> q;
    q.push(start);
    st[start.x][start.y] = 0;
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    while(q.size()){
        auto t = q.front();
        q.pop();
        
        res++;
        for(int i = 0; i < 4; i++){
            int x = t.x + dx[i], y = t.y + dy[i];
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            if(grid[x][y] == '#') continue;
            if(st[x][y] == 0) continue;
            st[x][y] = 0;
            q.push({x, y});
            
        }
    }
}

int main(){
    while(cin >> m >> n, m || n){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> grid[i][j];
                if(grid[i][j] == '@') start = {i, j};
            }
        }
        bfs();
        cout << res << 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
#include<iostream>
using namespace std;
const int N = 10010;
int a[N];

int main(){
    int n , m;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(a[i] == i + 1) continue;
        for(int j = i + 1; j < n; j++){
            if(a[j] == i + 1) {
                ans ++;
                swap(a[j], a[i]);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

这个题目很经典,建议深刻记忆

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;
const int N = 10010;
int a[N];
int b[N] = {0};

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(b[i] == false){  //如果这个点没有环, 就从它开始遍历, 并且此时环数+1
            cnt++;
            for(int j = i; !b[j]; j = a[j]) b[j] = true;    //从这个点的本来的位置出发,连成一个环
        } 
    }
    printf("%d", n - cnt);
    return 0;
}