Practice.

A. Everybody Likes Good Arrays!

题意

给定一个数组 \(a\)，定义一次操作为将奇偶性相同的相邻元素相乘并合并为一个元素，输出让数组 \(a\) 满足所有相邻数奇偶性不同的最小操作数量。

思路

显然，奇偶性相同的两个数相乘后奇偶性是不变的，那么我们只需统计有多少组相邻元素的奇偶性相同即可。

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

对应AC代码

import java.math.BigInteger;
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 cur = scanner.nextInt() % 2;
            int cnt = 0;
            for(int i=1;i<n;i++){
                int a = scanner.nextInt();
                if(a % 2 == cur) cnt ++;
                else cur = a % 2;
            }
            System.out.println(cnt);
        }
    }
}

还是挺简单的思维题

B. Emordnilap

题意

给定一个整数 \(n\)，对于所有 \(n\) 的排列，分别将各个排列镜像复制到右边，输出所有新数对的逆序对的总数量。

思路

可以证明，对于任意一个排列，所有大于 \(1\) 的数字 \(t\) 总能在其右边找到总共为 \(2 \times (t-1)\) 个比它小的数，从而构成对应数量的逆序对。因而，对于一个长度为 \(n\) 的排列，进行镜像复制后，逆序对总数为 \(2 \times (1+2+...+(n-1))=n \times (n-1)\)。

显然，对于 \(n\)，总共有 \(A_n^n\) 种排列，与上式相乘即可。

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

对应AC代码

import java.math.BigInteger;
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){
            long n = scanner.nextInt();
            long fact = 1L, mod = 1000000007;
            for(long i=2;i<=n;i++) fact = (fact * (i % mod)) % mod;
            System.out.println((((fact * (n % mod)) % mod) * ((n - 1) % mod)) % mod);
        }
    }
}

难得B题想的这么快

C. Quiz Master

题意

给定数组 \(a\)，选择任意可不连续的子序列 \(b\)，满足对于任意 \(t \in [1,m]\)，有 \(b_i \bmod t = 0\)，输出满足条件的子序列中 \(b_{\max}-b_{\min}\) 的最小值。

思路

双指针，类似于滑动窗口的解法。

我们考虑用双指针维护一个 \([l,r]\) 的满足题意的区间，在向右移动 \(r\) 的同时，找出满足条件的 \(l\) 的最小值即可。

更具体地说，我们可以开一个数组 \(cnt\) ，在向右移动 \(r\) 之前，我们先将 \(a[r]\) 的所有因子 \(f[a[r]]\) 对应的 \(cnt[f[a[r]]] +1\)，并在加之前判断值是否为 \(0\)，如果是，那么这个因数是第一次出现，因此即可统计 \([1,m]\) 是否被完全覆盖。向右移动 \(l\) 之前的操作与上述操作类似。

时间复杂度：\(O(n \times f(x)),f(x)为x的因数数量\)

对应AC代码

import java.math.BigInteger;
import java.util.*;

public class Main{

    static int N = 100010;

    private static List<List<Integer>> init(){
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<=N;i++) res.add(new ArrayList<>());
        for(int i=1;i<=N;i++)
            for(int j=i;j<=N;j+=i){
                res.get(j).add(i);
            }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<List<Integer>> f = init();
        int t = scanner.nextInt();
        nxt:
        while(t -- > 0){
            int n = scanner.nextInt(), m = scanner.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = scanner.nextInt();
            Arrays.sort(a);
            int l = 0, r = 0, best = Integer.MAX_VALUE, now = 0;
            int[] cnt = new int[N];
            while(r < n){
                for(int each : f.get(a[r])){
                    if(each > m) break;
                    if(cnt[each] == 0) now ++;
                    cnt[each] ++;
                }
                while(now == m){
                    best = Math.min(a[r] - a[l], best);
                    for(int each : f.get(a[l])){
                        if(each > m) break;
                        if(cnt[each] == 1) now --;
                        cnt[each] --;
                    }
                    l ++;
                }
                r ++;
            }
            System.out.println(best == Integer.MAX_VALUE ? -1 : best);
        }
    }
}

妙啊.jpg