蓝桥杯官网练习题
2020-02-25 14:05:17 #DS & Algorithms
本文总阅读量次

习题链接

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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 输出二进制表示

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
#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 矩阵转置

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
#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 数组求和

数据范围较小，暴力就可以了。

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 <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 秘密行动

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 <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 字符串压缩

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
#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

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
#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]; // maxh[i][j]代表 i~j 个作品中 高度的最大值

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 快速排序

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
#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;
}
上一页
2020-02-25 14:05:17 #DS & Algorithms
下一页