Blog - Floating Ocean
0%

Codeforces - Pinely Round 1 Div 1 plus 2

发表于 更新于
本文字数： 2.5k 阅读时长 ≈ 5 分钟
阅读次数： Valine：

Practice.

代码略去了快读模板

A. Two Permutations

题意

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

特别地，当 时，输出 。

思路

如题。

时间复杂度：

对应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();
    }
}
java

什么离谱的特判啊

B. Elimination of a Ring

题意

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

思路

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

1
6
1 2 1 2 1 2
Plain text

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

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

更具体地说，除了两个数字相间成环的情况，我们应该输出 外，其余情况均输出 。

时间复杂度：

对应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();
    }
}
java

硬猜就完事了（

C. Set Construction

题意

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

$b{i, j} = 1表示A_i\subsetneq A_j，b{i, j} = 0$ 则相反。

思路

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

那么，显然地，若 ，那么 中就一定有 。

更简单地说，我们只需遍历输出的矩阵，若 ，那么我们在 里添加 。

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

时间复杂度：

对应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();
    }
}
java

好一个思维题…