习题链接

考前集中把蓝桥杯官网上的算法提高里的习题做一做，希望有备战的小伙伴与我一起刷题😄，上面的题都不难，比y总的课简单多了😂。

学算法不到半年时间，假如有小伙伴做的方法比我的更简单或者我的代码有bug，欢迎在下方评论，谢谢啦。

欢迎关注

ADV-306 输出三个整数的最大数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3;

int a[3];

int main(){
    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a, a + N);
    cout << a[2] << endl;
    return 0;
}

ADV-305 输出二进制表示

#include <iostream>
#include <cstdlib>

using namespace std;

char s[10];
int n;

int main()
{
    cin >> n;
    itoa(n, s, 2);

    int end = 0;
    while (s[end] != '\0')
        end++;
    end--;
    if (n >= 0) cout << 0;
    else cout << 1;

    int mask = 1, num = 0;
    for (int i = end; i >= 0 && i >= end - 6; i--) 
    {
        num += (s[i] - '0') * mask;
        mask *=  10;
    }
    printf("%07d", num);

    return 0;
}

ADV-304 矩阵转置

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25;

int n, m;
int a[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            printf("%d ", a[j][i]);
        puts("");
    }
    return 0;
}

ADV-303 数组求和

数据范围较小，暴力$O(n^2)$就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int a[N * 2];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[i + n] = a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int sum = 0;
        for (int j = i; j <= i + m - 1; j++) sum += a[j];
        ans = max(ans, sum);
    }    

    printf("%d\n", ans);

    return 0;
}

ADV-302 秘密行动

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int a[N];
int f[N][2]; // 第二维为0的话表示到达某一层是跳上来的，为1表示爬上来的。
             // 一开始做时根本没想第二维，但是怎么做也做不对，所以又想了一下，其实上楼的过程是有限制的，
             // 比如这一层是跳上来的话，上一层一定是爬上来的，这一层是爬上来的，那么上一层既可以是跳上来的，也可以是爬上来的。

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    f[1][0] = 0;
    f[1][1] = a[1];
    for (int i = 2; i <= n; i++)
    {
        f[i][0] = min(f[i - 1][1], f[i - 2][1]);
        f[i][1] = min(f[i - 1][0], f[i - 1][1]) + a[i]; // 这个不应该是a[i]-a[i-1]吗？但是因为样例没过，所以改了一下，居然才对了。。。
    }

    cout << min(f[n][0], f[n][1]) << endl;

    return 0;
}

ADV-301 字符串压缩

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

int main()
{
    map<char, int> m;
    string s, s1;
    getline(cin, s);

    for (string::iterator it = s.begin(); it != s.end(); it++)
    {
        m[*it]++;

        if (*it == ' ') s1.push_back(*it);
        if (m[*it] == 1 || m[*it] == 3 || m[*it] == 6) s1.push_back(*it);
    }

    cout << s1 << endl;

    return 0;
}

ADV-300 字符串生成器

不会啊。。

ADV-299 宰羊

题解链接，之前我在问答区问过，这是胡图图大佬写的。

ADV-298 和谐宿舍2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int h[N];
int f[N][N]; // f[i][k]代表 用k块木板 从把前i个作品盖住的集合的最小值
int maxh[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    int sum = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
        {
            int s = 0;
            for (int k = i; k <= j; k++) s = max(s, h[k]);
            maxh[i][j] = s;
        }

    for (int i = 1; i <= n; i++)
            for (int k = 1; k <= m && k <= i; k++)
            {
                if (k == 1) f[i][k] = i * maxh[1][i];
                else if (k == i) 
                {
                    int sum = 0;
                    for (int u = 1; u <= i; u++) sum += h[u];
                    f[i][k] = sum;
                }
                else
                {
                    f[i][k] = 0x3f3f3f3f;
                    // u代表最后一块木板的起始位置
                    for (int u = i; u >= k; u--)
                    {
                        f[i][k] = min(f[i][k], f[u - 1][k - 1] + maxh[u][i] * (i - u + 1));
                    }
                }
            }

    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= m; i++)
        ans = min(ans, f[n][i]);

    printf("%d", ans);

    return 0;
}

ADV-297 快速排序

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int a[N];

void quick_sort(int l, int r)
{
    if (l == r) return;

    int x = a[l + r >> 1];
    int i = l - 1, j = r + 1;
    while (i < j)
    {
        while (a[++i] < x) ;
        while (a[--j] > x) ;
        if (i < j)
            swap(a[i], a[j]);
    } 
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

int main()
{
    int x, cnt = 0;
    while (cin >> x, x)
        a[cnt++] = x;

    quick_sort(0, cnt - 1);

    for (int i = 0; i < cnt; i++) cout << a[i] << " ";

    return 0;
}