A

题解

知识点：贪心。

代码

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

bool solve() {

    int n;

    cin >> n;

    int cnt = 0;

    for (int i = 1;i <= n;i++) {

        int x;

        cin >> x;

        if (x == 1) cnt++;

    }

    int rst = n - cnt / 2 * 2;

    cout << rst + cnt / 2 << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

B

题解

知识点：贪心。

代码

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

bool solve() {

    int a, b, c, d;

    cin >> a >> b >> c >> d;

    if (a == 0) {

        cout << min(b + c + d, 1) << '\n';

        return 1;

    }

    else {

        int ans = a + 2 * min(b, c) + min(a, abs(b - c) + d) + (abs(b - c) + d > a);

        cout << ans << '\n';

    }

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

C

题意

给一个长为 \(n\) 的排列，每次操作可以任选两个数，其中小的挪到开头，大的挪到末尾，问最少几次操作可以使得排列有序。

题解

知识点：贪心，枚举，双指针。

注意到，操作不影响没有被操作过的数字的相对位置，因此考虑排列中不需要操作的数字。显然，最终被保留的数字应该是连续上升的一个子序列，如 23456 是，而 13456 不是因为 \(1\) 和 \(3\) 中间没有 \(2\) 。

假设我们操作了某一组数 \((x,y)\) ，那么 \((x,y),(x-1,y+1),\cdots ,(1,n)\) 一定都需要操作一遍才能保证这些数字有序。因此只有中间的数我们不需要操作，所以我们保留的数字应该从中间开始往外拓展。

若 \(n\) 为奇数，则从中点 \(\dfrac{1+n}{2}\) 开始往两边扩展；若 \(n\) 为偶数，先保证 \(\left\lfloor \dfrac{1+n}{2} \right\rfloor ,\left\lceil \dfrac{1+n}{2} \right\rceil\) 有序，再从这两个数两边扩展，如果不有序直接输出 \(\dfrac{n}{2}\) 。

为了方便找到某个数的位置，我们可以先处理数到位置的映射 \(pos\) ，再利用双指针 \(l,r\) 指向扩展的边界，向两边同时扩展，如果有一边扩展不了那就不需要继续了，最后结果是 \(l-1\) 。

代码

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int pos[200007];

bool solve() {

    int n;

    cin >> n;

    for (int i = 1;i <= n;i++) {

        int x;

        cin >> x;

        pos[x] = i;

    }

    int l = (1 + n) / 2, r = (1 + n + 1) / 2;

    if (pos[l] > pos[r]) {

        cout << n / 2 << '\n';

        return 1;

    }

    while (1 < l && r < n) {

        if (pos[l - 1] > pos[l] || pos[r] > pos[r + 1]) break;

        l--;

        r++;

    }

    cout << l - 1 << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

D

题意

给你 \(n\) 个长为 \(m\) 的排列 \(a_i\) 。

定义一个排列 \(p\) 的值为满足 \(p_i = i,i \in[1,k]\) 中 \(k\) 的最大值。

定义两个排列 \(p,q\) 的乘法 \(p \cdot q\) 为 \(r_i = q_{p_i}\) 。

对于给定的 \(n\) 个排列中，对于每个排列 \(a_i\) 找到另一个排列 \(a_j\) （ \(j\) 可以等于 \(i\) ）使得 \(a_i \cdot a_j\) 的值最大，求出这 \(n\) 个最大值。

题解

知识点：枚举。

先考虑两个排列 \(p,q\) 乘积的求值过程，即如何求出 \(q_{p_1} = 1,\cdots,q_{p_k} = k\) 中 \(k\) 最大值。

显然 \(q_{p_1} = 1\) ，即 \(q\) 中 \(1\) 的位置是 \(p_1\) ，我们就能得到 \(k\) 至少是 \(1\) ，以此类推直到 \(q_{p_i} \neq i\) 就能得到 \(k = i-1\) ，复杂度是 \(O(n^2m^2)\) ，先考虑先优化枚举过程。

既然我们要知道某个数的位置，那么我们可以先预处理出 \(q\) 所有数字出现的位置 \(pos\) 。我们发现 \(q_{p_i} = i\) 等价于 \(pos_i = p_i\) ，即 \(i\) 出现的位置等于 \(p_i\) 那么自然可以得到 \(q_{p_i} = i\) ，由此我们从 \(pos_1 = p_1\) 开始找到最大的 \(k\) 满足 \(pos_k = p_k\) 即可。现在复杂度是 \(O(n^2m)\) ，考虑优化 \(n\) 次查找。

我们发现查找的过程，其实就是一个 \(p\) 和 \(n\) 个 \(pos\) 匹配最长前缀的过程，可以用字典树 trie 解决，复杂度是 \(O(nm)\) 。但这里 \(m\) 不大（其实是我不会字典树），我们可以将排列用十进制压缩成一个整数，用 map 记录 \(n\) 个排列的前缀信息来解决。设 \(mp_i\) 为 \(n\) 个排列的 \(pos\) 前 \(i\) 个数的前缀信息，例如排列 \(pos = [3,1,4,2]\) 前三个数字的信息就是 \(314\) ，记录在 \(mp_3\) 中。例如，我们查找 \(p = [4,3,2,1]\) 前 \(2\) 个数的匹配信息时，只要判断 \(mp_2\) 中有无 \(43\) 即可。到此为止，我们对 \(p\) 从前 \(1\) 个数依次查找，最多查找 \(m\) 次就可以找到最大的 \(k\) 了，复杂度是 \(O(nm\log n)\) 。

时间复杂度 \(O(nm \log n)\)

空间复杂度 \(O(nm)\)

代码

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int a[50007][11];

int pos[11];

map<ll, int> mp[11];

bool solve() {

    int n, m;

    cin >> n >> m;

    for (int i = 1;i <= m;i++) mp[i].clear();

    for (int i = 1;i <= n;i++) {

        for (int j = 1;j <= m;j++) {

            cin >> a[i][j];

            pos[a[i][j]] = j;

        }

        ll _t = 0;

        for (int j = 1;j <= m;j++) {

            _t = _t * 10 + pos[j] - 1;

            mp[j][_t] = 1;

        }

    }

    for (int i = 1;i <= n;i++) {

        ll _t = 0;

        int ans = m;

        for (int j = 1;j <= m;j++) {

            _t = _t * 10 + a[i][j] - 1;

            if (!mp[j][_t]) {

                ans = j - 1;

                break;

            }

        }

        cout << ans << ' ';

    }

    cout << '\n';

    return true;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    cin >> t;

    while (t--) {

        if (!solve()) cout << -1 << '\n';

    }

    return 0;

}

巴特西

Educational Codeforces Round 142 (Rated for Div. 2) A-D

A

题解

代码

B

题解

代码

C

题意

题解

代码

D

题意

题解

代码

最新文章

热门文章