构造题目训练(4.25-5.10)

发表于 更新于 分类于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 11 分钟
The gloomiest night will wear on to a morning.

注意：构造题目集要多看，里面有好多是自己现有的思维想不到的点

CF 478B

思路：

  • 对于给定的n和k，分别取最大和最小值时的情况为：
  • 最大值：有一个极端值很大，其他值都是1，对于一个数 ，它的方案数为 。
  • 最小值：所有数都很平均。

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    int t = n - (m - 1);
    int a = ((n % m == 0 ? 0 : 1) + n / m), b = n / m;
    i64 max = 1LL * t * (t - 1) / 2;
    i64 min = 1LL * a * (a - 1) / 2 * (n % m) + 1LL * (m - n % m) * (b - 1) * b / 2;
    std::cout << min << " " << max << "\n";
    
    return 0;
}

CF 1365B

思路：

  • a[i]和a[j]交换的条件是 b[i]和b[j]不相等，这也就意味着，只要b数组种存在一个1或者一个0，且另一个数不为0，那么这个数就可以到任意一个地方。
  • 所以，只要count(b[i], 0) >= 1 && count(b[i], 1) >= 1就说明，a数组中任意一个元素可以到达数组内的任意位置。

时间复杂度：

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
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<int> b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
    }

    bool ok = true;
    for (int i = 0, j = 1; j < n; i++, j++) {
        if (a[j] < a[i]) {
            ok = false;
        }
    }

    if (ok) {
        std::cout << "YES\n";
    } else {
        int cnt = std::count(b.begin(), b.end(), 0);
        std::cout << (cnt > 0 && cnt < n ? "YES\n" : "NO\n");
    }
}

CF 1348B

思路：

  • 题目不限定要加的元素个数，所以我们只要凑出每一个周期里的元素和相等，将最终的数组长度固定到 。
  • 如果数组 中的元素个数大于 ，就说明一定不行，因为他无论怎么样都不能形成一个周期，我们一开始把所有元素添加到一个集合，然后每次输出 个元素，不够的添加 ，因为无论怎么操作，我们都可以使得这个最终序列按照周期 的形式进行排列。

时间复杂度：

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
void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> a(n);
    std::set<int> cnt;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        cnt.insert(a[i]);
    }
    if (cnt.size() > k) {
        std::cout << "-1\n";
    } else {
        std::cout << n * k << "\n";
        for (int i = 0; i < n; i++) {
            for (int x : cnt) {
                std::cout << x << " ";
            }
            for (int j = 0; j < k - cnt.size(); j++) {
                std::cout << 1 << " ";
            }
        }
        std::cout << "\n";
    }
}

CF 1401C

思路：

  • 如果两个数的最大公约数等于 ，那么这两个数可以交换。
  • 根据题意，如果找到一个位置不在它有序的位置(b[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
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int min = *min_element(a.begin(), a.end());

    bool ok = true;
    std::vector<int> b = a;
    std::sort(b.begin(), b.end());
    for (int i = 0; i < n; i++) {
        if (b[i] != a[i] && a[i] % min != 0) {
            ok = false;
        }
    }

    if (ok) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

CF 1367C

思路：

  • 给你一个二进制字符串，你可以将某些地方从0变换到1，但要求每个1之间的距离不能小于k，然后求最多可以加多少个1。
  • 对于一个首尾都是1的字符串1000....001，可以推导出公式，总共可以插入 两个之间的距离 ，如果当 两个之间的距离 就说明最后一个位置不能插入，否则会违法，那么就需要 。

时间复杂度：

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
void solve() {
    int n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    if (std::count(s.begin(), s.end(), '1') == 0) {
        std::cout << (n + k) / (k + 1) << "\n";
        return ;
    }

    std::vector<int> a; 
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            a.push_back(i);
        }
    }

    int ans = 0;
    if (a[0] != 0) {
        ans += a[0] / (k + 1);
    }
    for (int i = 0, j = 1; j < a.size(); i++, j++) {
        int d = a[j] - a[i] - 1;
        ans += d / (k + 1);
        if (d % (k + 1) < k) {
            ans -= 1;
        }
    }
    if (a.back() != n - 1) {
        ans += (n - a.back() - 1) / (k + 1);
    }

    std::cout << ans << "\n";
}

CF 1909C

思路：

  • 你要把两个长度为n的点集给组成n个区间，然后用每个区间的权重与之相乘，求最小的价值和。
  • 对于两个相同长度的序列，我们如何两个相乘可以使得它们的总和最小呢 ?
    • 本题有个性质：如果一个序列升序，一个序列降序，那么它们两两相乘一定最小。
  • 结合这个性质，我们在利用一个单调栈的思想，首先，我们把左端点和右端点都标记一下，然后合并为一个长度为 序列，同时排序，然后遇到左端点，就把它存到单调栈中，然后遇到右端点，就把用当前的右端点来减去单调栈里的左端点，然后当作一个区间长度，最后我们按照这个性质，求最小值。

时间复杂度：

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
void solve() {
    int n;
    std::cin >> n;

    std::vector<std::pair<int, int>> a;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a.emplace_back(x, 1);
    }
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a.emplace_back(x, -1);
    }

    std::sort(a.begin(), a.end());

    std::vector<int> c(n);
    for (int i = 0; i < n; i++) {
        std::cin >> c[i];
    }
    std::sort(c.rbegin(), c.rend());

    std::vector<int> stk, len;
    for (auto [x, t] : a) {
        if (t == 1) {
            stk.emplace_back(x);
        } else {
            assert(!stk.empty());
            len.emplace_back(x - stk.back());
            stk.pop_back();
        }
    }
    std::sort(len.begin(), len.end());

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        ans += 1LL * c[i] * len[i];
    }
    std::cout << ans << "\n";
}

CF 1896C

思路：

  • 对于一个序列 ， 我们要使得它对于序列 的 恰好为 ，那么我们需要将序列 进行升序排序，然后把序列 中前 小的数放到 中前 的数的位置，这样可以保证序列 中一定有 个位置是满足 的，然后直接进行判断是否恰好有 个满足条件的位置即可。

时间复杂度：

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
void solve() {
    int n, x;
    std::cin >> n >> x;

    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
    }

    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);

    std::sort(p.begin(), p.end(), [&](int i, int j) {
        return a[i] < a[j];
    });
    std::sort(b.begin(), b.end());

    std::vector<int> ans(n);
    for (int i = 0; i < x; i++) {
        ans[p[n - x + i]] = b[i];
    }
    for (int i = x; i < n; i++) {
        ans[p[i - x]] = b[i];
    }

    for (int i = 0; i < n; i++) {
        x -= a[i] > ans[i];
    }
    if (x == 0) {
        std::cout << "YES\n";
        for (auto x : ans) {
            std::cout << x << " ";
        }
        std::cout << "\n";
    } else {
        std::cout << "NO\n";
    }
}

CF 1873G

思路：

  • 如果字符串中只有一种字符，那么一定为 ，然后我们只需要统计其中一种字符的总个数，然后统计这种字符的所有子段长度，然后如果出现了没有出现连续的另一种字符的子段，我们就将统计的总字符个数减去最大子段的长度，即为最终答案 。

时间复杂度：

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
void solve() {
    std::string s;
    std::cin >> s;

    if (s.find("A") == -1 || s.find("B") == -1) {
        std::cout << "0\n";
        return ;
    }

    bool ok = s[0] == 'A';
    int ans = std::count(s.begin(), s.end(), 'A');
    int A = 0, n = s.size();
    std::vector<int> a;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'B') {
            if (A) {
                a.push_back(A);
                A = 0;
            } else {
                ok = false;
            }
        }
        A += s[i] == 'A';
    }

    if (A) a.push_back(A);
    else {
        ok = false;
    }
    if (ok) {
        ans -= *min_element(a.begin(), a.end());
    }
    std::cout << ans << "\n";
}

CF 1820C

题目大意：你可以选择一个区间 ，然后将这个区间内的所有数修改为任意数字 ，请问，是否可以让数组的 。

思路：

  • 首先，我们可以确定的是，如果我们要让数组的 ，那么 一定不能存在，否则他会变为 ，然后，我们就可以确定策略。
  • 首先，我们把数组里所有等于 的数字位置确定，然后将在第一个 和最后一个 之间的所有数改为 ，然后，将那些出现次数大于 的数字也改了，那些 的数全部改为 ，最后，判断是否合法即可

时间复杂度：

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
62
63
64
65
66
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    std::set<int> st;
    for (int i = 1; i <= n; i++) {
        st.insert(a[i]);
    }

    int mex = 0;
    for (int v : st) {
        if (mex != v) {
            break;
        }
        mex++;
    }
    if (mex == 0) {
        std::cout << "Yes\n";
        return ;
    }

    std::vector<int> p;
    for (int i = 1; i <= n; i++) {
        if (a[i] == mex + 1) {
            p.push_back(i);
        }
    }

    if (p.size()) {
        for (int i = p[0]; i <= p.back(); i++) {
            a[i] = mex;
        }
    }
    
    std::map<int, int> cnt;
    for (int i = 1; i <= n; i++) {
        cnt[a[i]]++;
        if (cnt[a[i]] >= 2 || a[i] >= mex + 1) { 
            a[i] = mex;
        }
    }

    st.clear();
    for (int i = 1; i <= n; i++) {
        st.insert(a[i]);
    }

    int tot = 0;
    for (int v : st) {
        if (v != tot) {
            break;
        }
        tot++;
    }

    if (tot == mex + 1) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

CF 814B

题目大意：给你两个不同的序列，他们和一个排列 一定有一个字符不同，请你还原这个排列 。

思路：

  • 对于给定的两个数组，我们要判断他们是在同一个位置不同，还是在两个位置不同

  • 然后，我们把剩余的没有出现的元素存一下，由于最多只有两个位置不同，我们直接可以填入答案，然后判断即可

    1. 一个元素不同就直接填入，然后输出。

    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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        std::cin >> b[i];
    }

    std::set<int> set;
    std::vector<int> p(n + 1, -1);
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) {
            p[i] = a[i];
            set.insert(p[i]);
        }
    }
        
    std::set<int> cur;
    for (int i = 1; i <= n; i++) {
        if (!set.count(i)) {
            cur.insert(i);
        }
    }
    std::vector<int> pos;
    for (int i = 1; i <= n; i++) {
        if (p[i] == -1) {
            pos.push_back(i);
        }
    }

    auto check = [&](auto a, auto b, auto p) {
        if (a == b) return false;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] != p[i]) {
                cnt++;
            }
        }
        if (cnt > 1) return false;
        cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (b[i] != p[i]) {
                cnt++;
            }
        }
        if (cnt > 1) return false;
        return true;
    };

    if (pos.size() == 1) {
        p[pos[0]] = *cur.begin();
    } else {
        p[pos[0]] = *cur.begin();
        p[pos[1]] = *--cur.end();
        if (check(a, b, p)) {
            for (int i = 1; i <= n; i++) {
                std::cout << p[i] << " \n"[i == n];
            }
            return 0;
        }
        p[pos[1]] = *cur.begin();
        p[pos[0]] = *--cur.end();
    }

    for (int i = 1; i <= n; i++) {
        std::cout << p[i] << " \n"[i == n];
    }

    return 0;
}

CF 538B

题目大意：题目定义了一个十进制整数如果是只包含 或者 ，那么就把它称为准二进制数，现在，我们拿到一个数，要求我们把这个数 ，分解为最少数量的准二进制数之和

思路：

  • 边分解这个数 的位数，边构造一个准二进制数，然后把剩余的 ，进行继续重复上面的操作，直到最后 为 ，即可

时间复杂度：

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 main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
     int n;
     std::cin >> n;

     auto get = [](int x) {
         int res = 0, add = 1;
         while (x) {
             if (x % 10 != 0) {
                 res += add;
             }
             x /= 10;
             add = add * 10;
         }
         return res;
     };

     std::vector<int> p;
     while (n > 0) {
         int x = get(n);
         p.push_back(x);
         n -= x;
     }

     std::cout << p.size() << "\n";
     for (int i = 0; i < p.size(); i++) {
         std::cout << p[i] << " \n"[i == p.size() - 1];
     }

    return 0;
}

CF 330B

题目大意：给 个点，和 条边，你不能在这 条边上修建道路，然后每两个点之间的道路数量，最多为 ，请你构造一张满足以上条件的无向图

思路：

  • 那我们之直接找到一个可以建道路的点，然后把其他的道路全部建在它上，这样任意两个点的距离最多为 ，其实就是直接构造一张菊花图，你要找到一个中心点而已

时间复杂度：

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
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<int> vis(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;

        vis[u] = vis[v] = true;
    }

    std::cout << n - 1 << "\n";
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue ;
                std::cout << i << " " << j << "\n";
            }
            break;
        }
    }
    
    return 0;
}

CF 1174C

题目大意：从 到 中的所有互质的数都不相同，不互质的数全部相同

思路：

  • 直接枚举因子，然后填充数字即可
  • 因为互质的数在过程中不会被填充，所以顺序填充有共同因子的数即可

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    int tot = 1;
    std::vector<int> ans(n + 1);
    for (int i = 2; i <= n; i++) {
        if (!ans[i]) {
            ans[i] = tot++;
            for (int j = i; j <= n; j += i) {
                ans[j] = ans[i];
            }
        }
    }
        
    for (int i = 2; i <= n; i++) {
        std::cout << ans[i] << " \n"[i == n];
    }

    return 0;
}