Maples' Space

蓝桥杯选拔赛

Posted on In 2.9k 3 mins.
蓝桥杯选拔赛。涉及排序，分治法求中位数，动态规划

一题滚粗555，第一题一直t，直接裂开

A. 合并区间

leetcode-56

签到题，但是我想偏了……

排序之后合并区间即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return {};
        
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res;
        for (int i = 0; i < intervals.size(); i++) {
            if (res.size() == 0 || res.back()[1] < intervals[i][0]) {
                res.push_back(intervals[i]);
            }
            else {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
        }
        return res;
    }
};

B. 士兵排队

POJ-1723

考虑$y$轴方向上：

假设目标坐标为$y_0$，$n$个士兵的$y$轴坐标分别为$y_1, y_2, y_3, …, y_n$，则$y$轴上的移动步数为

$ S=|y_1-y_0|+|y_2-y_0|+…+|y_n-y_0| $，当$y_0$取中位数时最小。

考虑$x$轴方向上:

n个士兵的x轴坐标从小到大排序后分别为$x_1, x_2, …, x_n$，假设移动后分别对应的x轴坐标为$x_0, x_0+1,x_0+2,…,x_0+n-1$，则x轴上的移动步数为

$S=|x_1-x_0|+|x_2-x_0-1|+…+|x_n-n+1|=|x_1-x_0|+|(x_2-1)-x_0|+…+|(x_n-n+1)-x_0|$，

当$x_0$取$x_1, x_2-1, x_3-2, …, x_n-n+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
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 10005;
int x[maxn];
int y[maxn];
int newx[maxn];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    sort(x + 1, x + n + 1);
    for (int i = 1; i <= n; i++) newx[i] = x[i] - i + 1;
    
    sort(newx + 1, newx + n + 1);
    sort(y + 1, y + n + 1);
    
    int x0 = newx[n / 2 + 1];
    int y0 = y[n / 2 + 1];
    
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += abs(y[i] - y0);
        res += abs(newx[i] - x0);
    }
    cout << res << endl;
    
    return 0;
}

上面代码通过排序求得中位数，算法复杂度为$O(n log n)$，我们可以通过分治算法求，算法复杂度为$O(n)$，当然这种算法也可以用于求解第k大。参考快排。

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
int partition(int *a, int low, int high) {
    int base = a[low];
    while (low < high) {
        while (low < high && a[high] >= base) high--;
        a[low] = a[high];
        while (low < high && a[low] <= base) low++;
        a[high] = a[low];
    }
    a[low] = base;
    return low;
}

// 找出数组a中[low, high]范围的第k大
int selectk(int a[], int k, int low, int high) {
    int j = partition(a, low, high);
    if (j == k) {
        return a[j];
    }
    else if (j > k) {
        return selectk(a, k, low, j - 1);
    }
    else {
        return selectk(a, k, j+1, high);
    }
}

int main()
{
    int a[10] = {2, 1, 3, 4, 7, 9, 8, 10, 5, 11};
    cout << selectk(a, 5, 0, 9); // 第6大
    
    return 0;
}

C. 打鼹鼠

luogu-2285

动态规划，假设$dp[i]$为出现第$i$只小鼠时最多能抓到第几只。

当能从第$j$只到达第$i$只时，$dp[i] = max(dp[i], max(dp[j]))$，其中，$j < i$。

memset不能初始化数组为非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
// 动态规划 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
const int maxm = 10005;
int t[maxm];
int x[maxm];
int y[maxm];
int dp[maxm]; 

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) cin >> t[i] >> x[i] >> y[i];
    
    for (int i = 0; i < m; i++) dp[i] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 0; j < i; j++) {
            if (abs(t[i] - t[j]) >= abs(x[i] - x[j]) + abs(y[i] - y[j])) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < m; i++) ans = max(ans, dp[i]);
    
    cout << ans;
    
    return 0;
}

D. 海豚与Osu!

WHUOJ-2922

大水题，不说了