Practice.

代码略去了快读模板

A. Two Permutations

题意

给定三个整数 \(n, a, b\)，构建两个长为 \(n\) 的排列，满足前 \(a\) 个数和后 \(b\) 个数一致。输出是否能构建出两个不同的排列。

特别地，当 \(n = a = b\) 时，输出 \(YES\)。

思路

如题。

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

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{
    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        while(t -- > 0){
            int n = console.nextInt(), a = console.nextInt(), b = console.nextInt();
            if(n == a && b == a){
                console.println("YES");
                continue;
            }
            console.println(n - a - b >= 2 ? "YES" : "NO");
        }
        console.close();
    }
}

什么离谱的特判啊

B. Elimination of a Ring

题意

给定一个首尾相连的序列，序列中的相邻元素不相等。定义一次操作为删去任意元素，在每次删去后，若出现相邻元素相等，那么删去任意重复元素，直到没有相邻元素相等。

思路

我们不妨来考虑下面的一种情况：

1
6
1 2 1 2 1 2

显然，对于这类相间的数，在剩余两个数之前，我们都是成对删除的（如删除 \(1\) 后左边或右边的 \(2\) 也将被删去）。

而若我们在里面添加任意数字，那么相间的环将会被打破，我们不难发现，我们只需删去添加的任意数的相邻数，即可避免删除数以后出现重复数字。

更具体地说，除了两个数字相间成环的情况，我们应该输出 \(\frac{n}{2} + 1\) 外，其余情况均输出 \(n\)。

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

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{
    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0){
            int n = console.nextInt();
            if(n <= 2 || n % 2 == 1) {
                for(int i=0;i<n;i++) console.nextInt();
                console.println(n);
            }
            else{
                int a = console.nextInt(), b = console.nextInt();
                boolean f = false;
                for(int i = 1;i<n / 2;i++){
                    if(console.nextInt() != a | console.nextInt() != b){
                        if(f) continue;
                        console.println(n);
                        f = true;
                    }
                }
                if(!f) console.println(n / 2 + 1);
            }
        }
        console.close();
    }
}

硬猜就完事了（

C. Set Construction

题意

给定一个二进制矩阵 \(b\)，构造 \(n\) 个无重复数字的序列 \(A\)，满足矩阵对应的限制：

\(b_{i, j} = 1\) 表示 \(A_i\subsetneq A_j\)，\(b_{i, j} = 0\) 则相反。

思路

显然，序列是不唯一的，那么我们不妨来初始化 \(A\)，满足 \(A_i\) 中一定包含 \(i\)。

那么，显然地，若 \(A_i\subsetneq A_j\)，那么 \(A_j\) 中就一定有 \(i\)。

更简单地说，我们只需遍历输出的矩阵，若 \(b_{i, j} = 1\)，那么我们在 \(A_j\) 里添加 \(i\)。

输出满足上述条件的序列即可。

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

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{
    public static void main(String[] args) throws Exception{
        Console console = new Console();
        int t = console.nextInt();
        nxt:
        while(t -- > 0) {
            int n = console.nextInt();
            List<List<Integer>> ans = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                List<Integer> e = new ArrayList<>();
                e.add(i + 1);
                ans.add(e);
            }
            for (int i = 1; i <= n; i++) {
                String s = console.next();
                for (int j = 0; j < n; j++) {
                    if(s.charAt(j) == '1') ans.get(j).add(i);
                }
            }
            for(int i=0;i<n;i++){
                console.print(ans.get(i).size());
                for(int j : ans.get(i)) console.print(" " + j);
                console.println();
            }
        }
        console.close();
    }
}

好一个思维题...