Luobuyu's Blog

0%

2019-A组

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.5k 阅读时长 ≈ 2 分钟
2019年蓝桥杯C++本科A组省赛，考的比较基础，有些题目还是比较好的，后面的填空题有一些麻烦

H. 修改数组

题目描述：

一个数组，里面有重复整数，按照一下操作将其修改为没有重复元素的数组。

  • 依次修改 $ a_1 \cdots a_n $ ，当修改 $ a_i $ 时，检查 $ a_i $ 是否在 $ a_1\cdots a_{i-1} $ 中出现过，出现过则给 $ a_i $ 加 $ 1 $ ，如果仍存在则继续，直到没有出现过

得到一个新的数组，没有重复元素。给出初始数组，计算最终数组

数据范围：
$ 1 \le N \le 1e5 \\\\ 1\le a_i \le 1e6 $

题解：

最终得到的肯定是一些连续的上升线段。肯定不能直接暴力，当然暴力可以骗分。考虑使用并查集， $ f[i] $ 表示当访问到 $ i $ 的时候，应该被替换的数，也就是每个线段的末尾。刚开始时所有的 $ f[i] = i $ ，升序排列，都还没有被访问过。当访问完 $ i $ 后， $ i $ 被用过了，线段末尾后移 $ f[i] = f[i + 1] $ ，就是这样。

也可以直接做，考虑不能暴力的原因，如果所有的数都是一样的，由于每个元素都在重复的 $ +1 $ 判断，导致重复严重，可以考虑优化。如果一个数被访问了 $ k $ 次，那么说明他后面的 $ k $ 个数都不能用了，所以如果把 $ vis $ 数组改为记录访问次数的数组，直接跳。

代码：

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 <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;
int n, m, t;
int a[maxn];
bool vis[maxn];
int fa[maxn];
int getFa(int u)
{
    return u == fa[u] ? u : fa[u] = getFa(fa[u]);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i < maxn; i++)
        fa[i] = i;
    for(int i = 1; i <= n; i++)
    {
        a[i] = getFa(a[i]);
        fa[a[i]] = getFa(a[i] + 1);
    }
    for(int i = 1;  i<= n; i++)
        cout << a[i] << " ";
    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
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 1e6 + 10;
int n, m, t;
int a[maxn];
int vis[maxn];
int fa[maxn];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        while (vis[a[i]])
        {
            int tmp = a[i];
            a[i] += vis[a[i]];
            vis[tmp]++;
        }
        vis[a[i]] = 1;
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    return 0;
}

I. 糖果

题目描述：

$ M $ 种口味糖果，每包 $ K $ 颗，总共 $ N $ 包，给出每一包的口味，最少买几包，可以品尝所有的口味

数据范围：
$ 1\le N \le 1e2, 1\le M \le 20, 1\le K \le 20, 1\le t_i \le M $

题解：

数据范围很小，考虑使用二进制标记状态，这样的话每一包糖果的口味就是一个 $ int $ ，多包就是或起来。因此可以考虑使用状态 $ dp $ ， $ dp[i] $ 表示状态为 $ i $ 时所需的最小包数。比较简单

代码：

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
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e8 + 10;
int n, m, k;
int dp[maxn];
int s[200];
int main()
{
    freopen("in.txt", "r", stdin);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
    {
        int tmp = 0;
        for(int x, j = 1; j <= k; j++)
        {
            cin >> x;
            tmp |= 1 << (x - 1);
        }
        dp[tmp] = 1;
        s[i] = tmp;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < (1 << m); j++)
        {
            if(dp[j] == 0) continue;
            int tmp = s[i] | j;
            if(dp[tmp] == 0) dp[tmp] = dp[s[i]] + dp[j];
            else 
            {
                dp[tmp] = min(dp[tmp], dp[s[i]] + dp[j]);
            }
        }
    }
    if(dp[(1 << m) - 1] == 0)
        cout << -1 << endl;
    else
        cout << dp[(1 << m) - 1] << endl;
    return 0;
}