问题描述：

小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X, Y, Z 增加 Ai , Bi ,Ci 。当游戏结束时 (所有事件的发生与否已经确定)，如果 X, Y, Z 的其中一个大于另外两个之和，我们认为其获胜。
例如，当 X > Y + Z 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件? 如果不存在任何能让某国获胜的情况，请输出 −1 。

输入格式：

输入的第一行包含一个整数 n 。

第二行包含 n 个整数表示 Ai，相邻整数之间使用一个空格分隔。

第三行包含 n 个整数表示 Bi，相邻整数之间使用一个空格分隔。

第四行包含 n 个整数表示 Ci，相邻整数之间使用一个空格分隔。

输出格式：

输出一行包含一个整数表示答案

样例输入：

3

1 2 2

2 3 1

1 0 7

样例输出：

2

样例说明：

发生两个事件时，有两种不同的情况会出现获胜方。

发生 1, 2 事件时蜀国获胜。

发生 1, 3 事件时吴国获胜。

测评用例规模与约束：

对于 40% 的评测用例，n ≤ 500 ；

对于 70% 的评测用例，n ≤ 5000 ；

对于所有评测用例，1 ≤ n ≤ 10^5，1 ≤ Ai , Bi ,Ci ≤ 10^9 。

个人思路：

按照题目要求，胜利条件为其中一方的积分大于另外两方积分之和

那么对于每一个事件而言，我们判定最终为A胜利的话，A在该事件中实际获得的积分为：

$A_{i}=a_{i}-b_{i}-c_{i}$

那么同理如下：

$B_{i}=b_{i}-a_{i}-c_{i}$

$C_{i}=c_{i}-a_{i}-b_{i}$

接下来我们从中选取X个事件，那么对应每一个的最终分值为：

$S_{A}=A_{1}+A_{2}+A_{3}+......+A_{x}$

$S_{B}=B_{1}+B_{2}+B_{3}+......+B_{x}$

$S_{C}=C_{1}+C_{2}+C_{3}+......+C_{x}$

如果有一方胜利需要满足下面三个条件中的任意一个：

$S_{A}>0$

$S_{B}>0$

$S_{C}>0$

因为题目要求的是最多的事件，那么我们对于每一个获胜的情况进行分开计算，通过贪心的方式（优先选取积分值高的），因此需要通过排序，然后遍历计算即可

个人代码：

import java.io.*;
import java.util.Arrays;

/**
 * @ClassName 三国游戏
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/4/8 13:40
 * @Version 1.0
 **/
public class 三国游戏 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int n=nextInt();
        int []a=new int[n];
        int []b=new int[n];
        int []c=new int[n];
        for (int i=0;i<n;i++) a[i]=nextInt();
        for (int i=0;i<n;i++) b[i]=nextInt();
        for (int i=0;i<n;i++) c[i]=nextInt();
        for (int i=0;i<n;i++){
            int x=a[i],y=b[i],z=c[i];
            a[i]=x-y-z;
            b[i]=y-z-x;
            c[i]=z-x-y;
        }
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);
        int s=0;
        long sum=0,ans=0,count=0;
        for (int i=n-1;i>=0;i--){
            sum+=a[i];
            ans+=b[i];
            count+=c[i];
            if (sum>0||ans>0||count>0) s=n-i;
        }
        pw.println(s);
        pw.flush();
    }

    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

D：平均

问题描述：

有一个长度为 n 的数组（n 是 10 的倍数），每个数 ai 都是区间 [0, 9] 中的整数。小明发现数组里每种数出现的次数不太平均，而更改第 i 个数的代价为 bi，他想更改若干个数的值使得这 10 种数出现的次数相等（都等于 n 10 ），请问代价和最少为多少。

输入格式：

输入的第一行包含一个正整数 n 。

接下来 n 行，第 i 行包含两个整数 ai , bi ，用一个空格分隔。

输出格式：

输出一行包含一个整数表示答案

样例输入：

10

1 1

1 2

1 3

2 4

2 5

2 6

3 7

3 8

3 9

4 10

样例输出：

27

样例说明：

只更改第 1, 2, 4, 5, 7, 8 个数，需要花费代价 1 + 2 + 4 + 5 + 7 + 8 = 27 。

测评用例规模与约束：

对于 20% 的评测用例，n ≤ 1000；

对于所有评测用例，n ≤ 100000, 0 < bi ≤ 2 × 10^5 。

个人思路：

个人认为是严格意义上的签到题，对于0-9之间的每一个数都会出现n/10次，那么对于多出来的那部分出现次数进行更改即可，那么进行更改的情况一定会选择花费代价小的进行更改（贪心），因此只需要将给定数据进行二维排序即可

个人代码：

import java.io.*;
import java.util.Arrays;

/**
 * @ClassName 平均
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/4/8 13:46
 * @Version 1.0
 **/
public class 平均 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int n=nextInt();
        int [][]f=new int[n][2];
        int []d=new int[10];
        for (int i=0;i<n;i++){
            f[i][0]=nextInt();//值
            f[i][1]=nextInt();//价
        }
        Arrays.sort(f,((a,b)->{
            if (a[0]!=b[0]) return a[0]-b[0];
            return a[1]-b[1];
        }));
        long sum=0;
        for (int i=n-1;i>=0;i--){
            d[f[i][0]]++;
            if (d[f[i][0]]>n/10) sum+=f[i][1];
        }
        pw.println(sum);
        pw.flush();
    }

    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

E：填充

问题描述：

有一个长度为 n 的 01 串，其中有一些位置标记为 ?，这些位置上可以任意填充 0 或者 1，请问如何填充这些位置使得这个 01 串中出现互不重叠的 00 和 11 子串最多，输出子串个数。

输入格式：

输入一行包含一个字符串。

输出格式：

输出一行包含一个整数表示答案

样例输入：

1110?0

样例输出：

2

样例说明：

如果在问号处填 0 ，则最多出现一个 00 和一个 11：111000 。

测评用例规模与约束：

对于所有评测用例，1 ≤ n ≤ 1000000 。

个人思路：

这题还是相同的使用贪心思路，因为题目给定条件为：不重叠

那么我们从左往右开始判断每一个组合即可，遇到问号的就相当于万能改变，优先满足前面的可以更改的情况，如果前面的已经组合过了，那么？将与后一个进行组合

对于第一个符号为?的情况进行特殊比较即可

个人代码：


import java.io.*;
import java.util.Scanner;

/**
 * @ClassName 填充
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/4/8 13:54
 * @Version 1.0
 **/
public class 填充 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        String ss=sc.nextLine();
        boolean []f=new boolean[ss.length()+1];
        int count=0;
        for (int i=1;i<ss.length();i++){
            if (ss.charAt(i)=='?'){//当前位置为?
                if (!f[i - 1]) {//判断上一个位置是否组合
                    count++;
                    f[i]=true;
                }else if (i!=ss.length()-1){//与下一个位置组合
                    count++;
                    f[i+1]=true;
                    i++;
                }
            }else if (ss.charAt(i)==ss.charAt(i-1)&& !f[i - 1]||ss.charAt(i-1)=='?'&&!f[i-1]){//当前位置不为?
                count++;
                f[i]=true;
            }
        }
        pw.println(count);
        pw.flush();
    }

    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

F：棋盘

问题描述：

小蓝拥有 n × n 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 m 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反 (也就是白色棋子变为黑色，黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式：

输入的第一行包含两个整数 n, m，用一个空格分隔，表示棋盘大小与操作数。

接下来 m 行每行包含四个整数 x1, y1, x2, y2，相邻整数之间使用一个空格分隔，表示将在 x1 至 x2 行和 y1 至 y2 列中的棋子颜色取反。

输出格式：

输出 n 行，每行 n 个 0 或 1 表示该位置棋子的颜色。如果是白色则输出 0 ，否则输出 1 。

样例输入：

3 3

1 1 2 2

2 2 3 3

1 1 3 3

样例输出：

001

010

100

样例说明：

只更改第 1, 2, 4, 5, 7, 8 个数，需要花费代价 1 + 2 + 4 + 5 + 7 + 8 = 27 。

测评用例规模与约束：

对于 30% 的评测用例，n m ≤ 500 ；

对于所有评测用例，1 ≤ n, m ≤ 2000 ，1 ≤ x1 ≤ x2 ≤ n ，1 ≤ y1 ≤ y2 ≤ m 。

个人思路：

这是一个裸二维差分题，但是比赛的时候写的是普通一维差分+暴力，因为时间复杂度为O(n*m),不超时，怎么简单怎么来（但是赛时输出我中间用空格隔开，所以-15）

不了解的朋友可以查看这篇文章，个人觉得挺好：二维差分矩阵

个人代码：

普通差分：

import java.io.*;

/**
 * @ClassName 棋盘
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/4/8 13:59
 * @Version 1.0
 **/
public class 棋盘 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int n=nextInt();
        int m=nextInt();
        int [][]f=new int[n+2][n+2];
        for (int i=0;i<m;i++){
            int x1=nextInt(),y1=nextInt(),x2=nextInt(),y2=nextInt();
            for (int j=x1;j<=x2;j++){
                f[j][y1]++;
                f[j][y2+1]--;
            }
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                f[i][j]+=f[i][j-1];
                if (f[i][j]%2==0) pw.print(0);
                else pw.print(1);
            }
            pw.println();
        }
        pw.flush();
    }

    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

二维差分：


import java.io.*;

/**
 * @ClassName 二维差分
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/4/8 14:10
 * @Version 1.0
 **/
public class 二维差分 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int n=nextInt();
        int m=nextInt();
        int [][]f=new int[n+2][n+2];
        for (int i=0;i<m;i++){
            int a=nextInt(),b=nextInt(),c=nextInt(),d=nextInt();
            f[a][b]++;
            f[c+1][b]--;
            f[a][d+1]--;
            f[c+1][d+1]++;
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                f[i][j] += f[i-1][j]+f[i][j-1]-f[i-1][j-1];
                pw.print(f[i][j]%2);
            }
            pw.println();
        }
        pw.flush();
    }

    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

G：子矩阵

问题描述：

给定一个 n × m （n 行 m 列）的矩阵。

设一个矩阵的价值为其所有数中的最大值和最小值的乘积。

求给定矩阵的所有大小为 a × b （a 行 b 列）的子矩阵的价值的和。

答案可能很大，你只需要输出答案对 998244353 取模后的结果。

输入格式：

输入的第一行包含四个整数分别表示 n, m, a, b ，相邻整数之间使用一个空格分隔。

接下来 n 行每行包含 m 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai, j

输出格式：

输出一行包含一个整数表示答案

样例输入：

2 3 1 2

1 2 3

4 5 6

样例输出：

58

样例说明：

1 × 2 + 2 × 3 + 4 × 5 + 5 × 6 = 58 。

测评用例规模与约束：

对于 40% 的评测用例，1 ≤ n, m ≤ 100 ；

对于 70% 的评测用例，1 ≤ n, m ≤ 500 ；

对于所有评测用例，1 ≤ a ≤ n ≤ 1000 1 ≤ b ≤ m ≤ 1000 1 ≤ Ai, j ≤ 10^9 。

个人思路：

这是个优先队列的题，但是优先队列写的比较少，不太能盲写，所以写了一个O(n*m^2)复杂度的方式，不过在C语言网上测试为通过，官方数据应该过70%+

我们先将每一行需要的个数提取，即输入中的a行b列中的b，然后我们从每一行的第b-1个开始计算每一行这个位置的最大值与最小值，然后同理，判断每一列的，但是在每一列的时候，我们可以直接从第a-1行，b-1列开始，用a*b大小的矩阵中已知的每一行的最大最小，通过最终的那一列进行判断即可

个人代码：


import java.io.*;

/**
 * @ClassName 子矩阵
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/4/10 23:47
 * @Version 1.0
 **/
public class 子矩阵 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int n=nextInt();
        int m=nextInt();
        int a=nextInt();
        int b=nextInt();
        int [][][]f=new int[n][m][3];
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++) f[i][j][0]=nextInt();
        }
        long sum=0;
        for (int i=0;i<n;i++){//行遍历
            for (int j=b-1;j<m;j++){//从第b-1列开始
                int max=0,min=2000000001;
                for (int k=j-b+1;k<=j;k++){//往前推，统计这b个数的最大最小
                    max=Math.max(max,f[i][k][0]);//统计最大值
                    min=Math.min(min,f[i][k][0]);//统计最小值
                }
                f[i][j][1]=min;//更改最小值
                f[i][j][2]=max;//更改最大值
            }
        }
        for (int i=a-1;i<n;i++){//a-1行开始
            for (int j=b-1;j<m;j++){//b-1列开始
                int max=0,min=2000000001;
                for (int k=i;k>=i-a+1;k--){//往上推，通统计这a行的数的最大最小
                    max=Math.max(max,f[k][j][2]);
                    min=Math.min(min,f[k][j][1]);
                }
                sum+=((long)max*min)%998244353;//求和
                sum%=998244353;
            }
        }
        pw.println(sum);
        pw.flush();
    }

    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

H：公因数匹配

问题描述：

给定 n 个正整数 Ai，请找出两个数 i, j 使得 i < j 且 Ai 和 Aj 存在大于 1 的公因数。

如果存在多组 i, j，请输出 i 最小的那组。如果仍然存在多组 i, j，请输出 i 最小的所有方案中 j 最小的那组

输入格式：

输入的第一行包含一个整数 n。

第二行包含 n 个整数分别表示 A1 A2 · · · An，相邻整数之间使用一个空格分隔。

输出格式：

输出一行包含两个整数分别表示题目要求的 i, j，用一个空格分隔。

样例输入：

5

5 3 2 6 9

样例输出：

2 4

测评用例规模与约束：

对于 40% 的评测用例，n ≤ 5000 ；

对于所有评测用例，1 ≤ n ≤ 10^5，1 ≤ Ai ≤ 10^6 。

个人思路：

用map去存储每一个>1的因子第一次出现的位置，如果后续的数字出现了该因子，则按照题目要求去进行更改，时间复杂度为O( $n*\sqrt{A_{i}}$ )

注意，在判断的时候需要判断这个数的因子下标与当前位置不同，且当前数值>1也应当属于因子，去进行特殊判定

个人代码：

import java.io.*;
import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName 公因数匹配
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/4/8 14:24
 * @Version 1.0
 **/
public class 公因数匹配 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        int n=nextInt();
        Map<Integer,Integer> map=new HashMap<>();
        int min=99999999,max=0;
        int r=min,l=0;
        for (int i=0;i<n;i++){
            int a=nextInt();
            int k= (int) (Math.sqrt(a)+2);//以防2/3
            for (int j=2;j<=k;j++){
                if (a%j==0&&a!=j){//存储因子
                    if (map.get(j)==null) map.put(j,i+1);//判断是否出现过
                    else if(map.get(j)!=i+1){//不可相同
                        r=Math.min(r,map.get(j));
                        l=i+1;
                    }
                    if (map.get(a/j)==null) map.put(a/j,i+1);//同上
                    else if(map.get(a/j)!=i+1){
                        r=Math.min(r,map.get(a/j));
                        l=i+1;
                    }
                }
            }
            if (map.get(a)==null) map.put(a,i+1);//判断该值，因为X的因子包括X
            else if (a!=1&&map.get(a)!=i+1){//同上
                r=Math.min(r,map.get(a));
                l=i+1;
            }
            if (r!=min){//判断是否进行更改
                min=r;
                max=l;
            }
        }
        pw.println(min+" "+max);
        pw.flush();
    }

    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

9/10两题没机会AC，没有AC思路，所以就到这吧

总的而言今年的JavaC题目没去年难的感觉，当然其他组比如JavaB，C++B，C++C这些组都挺难的，去的话估计爆0了，还是javac适合新手