Contestant. Rank 2570. Rating +70.

A. GamingForces

题意

给定一个数组 \(a\)，定义操作可任选其一：

将其中两个元素减 \(1\)
将某个元素减为 \(0\)

输出最少的操作数，使 \(a\) 的所有元素都减为 \(0\)。

思路

将所有为 \(1\) 的元素配对，扣去偶数个 \(1\) 后，剩下的元素全都执行操作 \(2\) 即可。

时间复杂度：最坏\(O(n)\)

对应AC代码

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0){
            int n = scanner.nextInt();
            int cnt = 0;
            for(int i=0;i<n;i++) if(scanner.nextInt() == 1) cnt ++;
            System.out.println(n - cnt / 2);
        }
    }

}

简单签到题

B. Stand-up Comedian

题意

给定整数 \(a_1\)，\(a_2\)，\(a_3\)，\(a_4\)，\(4\) 个整数代表了四个类型对应的笑话数量：

\(A\) 和 \(B\) 都喜欢
\(A\) 喜欢，\(B\) 不喜欢
\(B\) 喜欢，\(A\) 不喜欢
\(A\) 和 \(B\) 都不喜欢

初始状态下，两人的心情值都为 \(0\)，对于喜欢的笑话，心情会 \(+1\)，否则会 \(-1\)。

输出最多能讲多少个笑话。

思路

模拟+思维

首先，我们先把类型 \(1\) 讲完，如果 \(a_1=0\)，直接判 \(1\) 个。

接着，我们讨论 \(|a_2-a_3|\) 和 \(a_1\) 的大小关系，若 \(a_1\) 较小，那么笑话是讲不完的，只有 \(2 \times (a_1+\min(a_2,a_3)) + 1\) 个笑话可以讲。

否则，将 \(|a_2-a_3|\) 讲完后，判断剩余的可以讲多少个 \(a_4\) 即可。

时间复杂度：\(O(1)\)

对应AC代码

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0){
            int[] a = new int[4];
            for(int i=0;i<4;i++) a[i] = scanner.nextInt();
            if(a[0] == 0){
                System.out.println(1);
                continue;
            }
            int n = Math.min(a[1], a[2]), ans = 0;
            ans += a[0] + n * 2;
            int m = Math.max(a[1] - n, a[2] - n);
            if(a[0] < m){
                System.out.println(2 * (a[0] + n) + 1);
            }else{
                ans += m;
                ans += Math.min(a[0] - m + 1, a[3]);
                System.out.println(ans);
            }
        }
    }

}

思路好乱

C. Min Max Sort

题意

给定一个排列 \(p\)，定义一次操作为任选两个元素，将其从原排列中取出，将较小元素放至排列头部，较大元素放至排列尾部，输出最小的操作数，使最后的排列升序。

思路

逆向思维

显然，我们需要对形如 \([i,n-i+1]\) 的元素对进行操作。

考虑到一个不需要移动的元素对，应满足三个条件：

\(i\) 在 \(n-i+1\) 前面
\(i\) 在 \(i+1\) 前面
\(n-i\) 在 \(n-i+1\) 前面

筛出所有不需要移动的元素对并取补集即可。

时间复杂度：\(O(n)\)

对应AC代码

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            int[] w = new int[n + 1];
            int ans = n / 2;
            for (int i = 1; i <= n; i++) w[scanner.nextInt()] = i;
            for (int i = n / 2; i >= 1; i--) { //排除不用移动的
                if (w[i] < w[i + 1] && w[n - i + 1] > w[n - i] && w[i] < w[n - i + 1]) ans--;
                else break;
            }
            System.out.println(ans);
        }
    }

}

反着想简单多了

D. Fixed Prefix Permutations

题意

给定整数 \(n\) 和 \(m\)，定义两个排列 \(p\)，\(q\) 的乘积为一个新的排列 \(r\)，其中 \(r_j=q_{p_j}\)。给定长度为 \(m\) 的 \(n\) 个排列，对于每一个排列，输出其与所有 \(n\) 个排列的乘积构成的排列的最大美丽值。其中美丽值定义为满足 \(p_1=1,p_2=2,...,p_k=k\) 的 \(k\) 的最大值（\(p_1 \neq 1\)时美丽值为 \(0\)）。

思路

显然，对于给定的排列 \(p\) 和 \(q\)，若已知 \(q\)，那么所构造出来的 \(r\) 和 \(p\) 是一一对应的。所以，我们可以将问题转化一下：

对于所有 \(q\)，先预处理构造出满足 \(k=m\) 的排列 \(p_t\) ，然后对于每一个 \(p\) ，在所有 \(p_t\) 中依次匹配，输出从第一个开始最大的连续匹配数量。

为了让匹配的复杂度降到最低，我们可以采用字典树。

时间复杂度：\(O(nm)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 50010;

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

class Trie {
private:
    vector<Trie*> children;

public:
    Trie() : children(12){}

    void insert() {
        Trie* node = this;
        for (int i=0;i<m;i++) {
            int ch = tmp[i];
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
    }

    int find(int index) {
        Trie* node = this;
        int dep = 0;
        for (int i=0;i<m;i++) {
            int ch = a[index][i];
            if (node->children[ch] == nullptr) {
                return dep - 1;
            }
            node = node->children[ch];
            dep ++;
        }
        return dep;
    }

};

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        Trie root = *new Trie();
        cin >> n >> m;
        for(int i=0;i<n;i++){
            for(int j=1;j<=m;j++){
                cin >> a[i][j];
                tmp[a[i][j]] = j;
            }
            root.insert();
        }
        for(int i=0;i<n;i++){
            cout << root.find(i) << " ";
        }
        cout << '\n';
    }
}

题目真的很难看懂...