Contestant. Rank 2570. Rating +70.

A. GamingForces

题意

给定一个数组 ，定义操作可任选其一：

1. 将其中两个元素减
2. 将某个元素减为

输出最少的操作数，使 的所有元素都减为 。

思路

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

时间复杂度：最坏

对应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

题意

给定整数 ，，，， 个整数代表了四个类型对应的笑话数量：

1. 和 都喜欢
2. 喜欢， 不喜欢
3. 喜欢， 不喜欢
4. 和 都不喜欢

初始状态下，两人的心情值都为 ，对于喜欢的笑话，心情会 ，否则会 。

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

思路

模拟+思维

首先，我们先把类型 讲完，如果 ，直接判 个。

接着，我们讨论 和 的大小关系，若 较小，那么笑话是讲不完的，只有 个笑话可以讲。

否则，将 讲完后，判断剩余的可以讲多少个 即可。

时间复杂度：

对应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

题意

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

思路

逆向思维

显然，我们需要对形如 的元素对进行操作。

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

1. 在 前面
2. 在 前面
3. 在 前面

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

时间复杂度：

对应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

题意

给定整数 和 ，定义两个排列 ， 的乘积为一个新的排列 ，其中 $rj=q{p_j}mnnp_1=1,p_2=2,…,p_k=kkp_1 \neq 10$）。

思路

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

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

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

时间复杂度：

对应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';
    }
}

题目真的很难看懂…