Practice.

A. Joey Takes Money

题意

给定一个包含 个 的元素的数组 ，定义操作为：

1. 选定 ；
2. 选两个 的正整数 ，满足 ；
3. 将 改为 。

输出任意次操作后数组的和的最大值 x2022。

思路

显然，对于 ， 一定是所有操作中最大的和，那么我们可以依次从左到右将所有数都执行一遍该操作，得到 ，求和即可。

时间复杂度：

对应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();
            long[] a = new long[n];
            for(int i=0;i<n;i++) a[i] = scanner.nextInt();
            Arrays.sort(a);
            for(int i=0;i<n-1;i++){
                a[n - 1] = a[n - 1] * a[i];
                a[i] = 1;
            }
            System.out.println(2022 * ((long) (n - 1) + a[n - 1]));
        }
    }
}

简单思维题 & 2022x1

B. Kill Demodogs

题意

给定一个 的矩阵， 位置的元素值为 。定义人物从 走到 ，期间人物只能向下或向右移动一格，输出到达终点后经过的元素的值的总和的最大值。

思路

显然，我们走对角线是最优的，此时横坐标和纵坐标的值最相近。

此时，我们可以得到下面的式子：

。

我们将其拆成两个式子：

1. ；
2. 。

对于上述两个式子，我们套用公式即可。

最后，我们可以得到下面的式子：

。

此时，我们有两个选择：大数或者逆元。任选其一即可。

时间复杂度：

对应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(), mod = 1000000007;
        while(t -- > 0){
            long n = scanner.nextInt();
            System.out.println((2022 *
                    ((BigInteger.valueOf(n).multiply(BigInteger.valueOf(n + 1)).multiply(BigInteger.valueOf(2 * n + 1)).divide(BigInteger.valueOf(6)).mod(BigInteger.valueOf(mod)).longValue() +
                            BigInteger.valueOf(n - 1).multiply(BigInteger.valueOf(n)).multiply(BigInteger.valueOf(n + 1)).divide(BigInteger.valueOf(3)).mod(BigInteger.valueOf(mod)).longValue()) % mod)) % mod);
        }
    }
}

大数yyds

C. Even Subarrays

题意

给定一个长度为 的数组 ，，输出连续的子序列的个数，子序列需满足子序列的异或值有偶数个因数。

思路

这里需要用到一个性质：只有完全平方数的因数数量是奇数。

所以，我们不妨找完全平方数，然后取一个补集即可。

考虑到异或的交换性，我们不妨用答案来枚举。

更具体地说，我们不妨从前向后遍历， 为前 个元素的异或值，我们用 数组存储这些异或值出现的次数，然后，我们枚举所有可能的答案，算出 需要和 前面的哪一段区间的异或值 进行异或后得到完全平方数，用类似于前缀和的方式记录答案。

考虑到 的范围，我们只需枚举 及以下的完全平方数即可。

时间复杂度：

对应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[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = scanner.nextInt();
            long[] m = new long[2 * n];
            int cur = 0;
            long cnt = 0;
            m[cur] = 1;
            for(int i=0;i<n;i++){
                cur ^= a[i];
                for(int j=0;j*j<2*n;j++){
                    int now = cur ^ (j * j);
                    if(now < 2 * n) cnt += m[now];
                }
                m[cur] ++;
            }
            System.out.println((long) n * (n - 1) / 2 + n - cnt);
        }
    }

}

异或的性质太多力