第十二届 省赛(真题课件134)

1. ASC

   已知大写字母 A 的 ASCII 码为 65，请问大写字母 L的 ASCII 码是多少?

   答案：76

   备注：就填数，直接秒了

2. 空间

   小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问256MB 的空间可以存储多少个 32 位二进制整数?

   public class KongJian {
   public static void main(String[] args) {
       System.out.print(256 >> 2 << 20);
   }
   }

   答案：67108864

   备注：纯数学计算就秒了，32位就是4B，256MB换算成B再除4，$256*2^{20}/4=2^{26}=$67108864

3. 卡片

   小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
   小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个,就保存起来，卡片就不能用来拼其它数了。
   小蓝想知道自己能从 1 拼到多少。
   例如，当小蓝有 30 张卡片，其中 0到9各3张，则小蓝可以拼出 1到 10但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
   现在小蓝手里有 0 到9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1拼到多少?

   public class KaPian {
   public static void main(String[] args) {
       int sum=2021;
       int a1=0;
       for (int i = 1; i <= 20210; i++) {
           a1=i;
           while(a1>0) {
               if(a1%10==1&&sum>0) {
                   sum--;    
               }
               a1/=10;
           }
           if(sum==0) {
               System.out.println(i);
               break;
           }
       }
   }
   }

   答案：3181

4. 相乘

   小蓝发现，他将 1 至 1000000007 之间的不同的数与 2021 相乘后再求除以1000000007 的余数，会得到不同的数。
   小蓝想知道，能不能在 1 至 1000000007 之间找到一个数，与 2021 相乘后再除以 1000000007 后的余数为 999999999。如果存在，请在答案中提交这个数:如果不存在，请在答案中提交 0。

   public class XiangCheng {
   public static void main(String[] args) {
       for(long i =1;i<=1000000007;i++) {
           if(((i*2021)%1000000007)==999999999) {
               System.out.println(i);
               break;
           }
       }
   }
   }

   答案：17812964

5. 路径

   小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
   小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
   对于两个不同的结点 a.b，如果 a 和 b的差的绝对值大于 21，则两个结点之间没有边相连:如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
   例如: 结点 1 和结点 23 之间没有边相连:结点 3 和结点 24 之间有一条无向边，长度为 24: 结点 15 和结点 25 之间有一条无向边，长度为 75。请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

   public class LuJing {
   public static void main(String[] args) {
       int a = 21;
       for (int i = 21; i + 21 < 2021; i += 21) {
           a = a + i * (i + 21) / 21;
       }
       a = a + 2016 * 2021;
       System.out.println(a);
   }
   
   }

   答案：10266837

6. 时间显示

   小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日 00:00:00 到当前时刻经过的毫秒数。
   现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
   给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

   public class ShiJianXianShi {
   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       long n = scan.nextLong();
       n /= 1000;
       n %= (24 * 60 * 60);
       long hours = n / 3600;
       long minutes = n / 60 % 60;
       long seconds = n % 60;
       System.out.printf("%02d:%02d:%02d", hours, minutes, seconds);
       scan.close();
   }
   }

   测试用例：case 1：I：46800999 ，O：13:00:00 ；case 2：I：1618708103123 ，O：01:08:23

7. 最少砝码

   你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
   那么这套砝码最少需要包含多少个砝码?
   注意砝码可以放在天平两边。

   public class ZuiShaoFaMa {
   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       int n = scan.nextInt();
       scan.close();
       int number = 1;// 砝码数量，默认必须有砝码1
       int count = 1;// 砝码重量1，砝码每次递增都是*3
       int scope = 1;// 范围从1开始
       while (scope < n) {
           count *= 3; // count每次都是*3倍
           scope += count; // 范围数量都是加上当前的砝码重量
           number++;
       }
       System.out.println(number);
   }
   }

   测试用例：I：7 ，O：3

8. 杨辉三角形

   

   如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列:
   1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
   给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数?

   public class YangHuiSanJiaoXing {
   static long[] num = new long[44723];
   
   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       long N = scan.nextLong();
       if (N == 1) {
           System.out.println(1);
           return;
       }
       num[1] = 1L;
       // dp计算
       for (int i = 2; i <= 44722; ++i) {
           for (int j = i; j >= 1; --j) {
               num[j] += num[j - 1];
               if (num[j] == N) {
                   /*
                    * 这里容易出错! 因为是下标从大到小的dp,杨辉三角是对称的，先满足的是对称轴右边的数 这里结果res的计算需要做一下对称处理，不是i*(i-1)/2 +j
                    * 实际上是第i行的第i-j+1个数首先满足相等条件
                    */
                   long res = (((long) i * ((long) i - 1)) >> 1) + i - j + 1;
                   System.out.println(res);
                   return;
               }
           }
       }
       // 此时，N一定是 第N+1行的第二个数
       long res = ((N * (N + 1)) >> 1) + 2;
       System.out.println(res);
   }
   }

   测试用例：I：6　，O：13

9. 左孩子右兄弟

   对于一棵多叉树，我们可以通过“左孩子右兄弟”表示法，将其转化成一棵二叉树。
   如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。给定一棵包含 N 个结点的多叉树，结点从 1至 N 编号，其中 1 号结点是根，每个结点的父结点的编号比自己的编号小。请你计算其通过“左孩子右兄弟”表示法转化成的二叉树，高度最高是多少。注: 只有根结点这一个结点的树高度为 0。
   例如如下的多叉树:

   

   可能有以下 3 种(这里只列出 3 种，并不是全部) 不同的“左孩子右兄弟表示:

   

   其中最后一种高度最高，为 4。

   public class ZuoHaiZiYouXiongDi {
   static Map> map = new HashMap<>();
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       for (int i = 2; i <= n; i++) {
           int a = sc.nextInt();
           // 判断一个键在集合里面是否存在，如果不存在就将这个a添加到集合中
           map.putIfAbsent(a, new ArrayList<>());
           map.get(a).add(i);
       }
       int max = dsf(1);
       System.out.println(max);
   }
   
   public static int dsf(int x) {
       int sum = 0, max = 0;
       if (!map.containsKey(x)) {
           return 0;
       } else {
           List aa = map.get(x);
           sum = aa.size();
           for (Integer item : aa) {
               max = Math.max(dsf(item), max);
           }
           return sum + max;
       }
   }
   }

   测试用例：I：5\n1\n1\n1\n2 ，O：4

10. 双向排序

    给定序列 $(a_1,a_2,...,a_n)=(1,2,...,n)$，即$a_i=i$
    小蓝将对这个序列进行 m 次操作，每次可能是将 $a_1,a2,...,a{qi}$降序排列或者将$a{qi},a{q_i+1},...,a_n$升序排列。
    请求出操作完成后的序列。

    public class ShuangXiangPaiXv {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(); // 接收n和m
            int m = sc.nextInt();
            Integer[] nums = new Integer[n + 1];
            for (int i = 1; i < n + 1; i++) { // 初始化所有数字
                nums[i] = i;
            }
            for (int i = 0; i < m; i++) {
                int p1 = sc.nextInt(), p2 = sc.nextInt();
                if (p1 == 0) // 若操作是0，则倒序排序
                    downSort(nums, p2 + 1);
                if (p1 == 1) // 若操作是1，则升序排序
                    upSort(nums, p2);
            }
            for (int i = 1; i < n + 1; i++) {
                System.out.print(nums[i] + " ");
            }
        }
    
        private static void upSort(Integer[] arr, int start) { // 升序排序方法
            Arrays.sort(arr, start, arr.length);
        }
    
        private static void downSort(Integer[] arr, int end) { // 降序排序方法
            Arrays.sort(arr, 1, end, Collections.reverseOrder());
        }
    }

    测试用例：I：3 3\n0 3\n1 2\n0 2 ，O：3 1 2

第十三届 省赛(真题课件143)

1. 排列字母

   小蓝要把一个字符串中的字母按其在字母表中的顺序排列。例如，LANQIAO 排列后为 AAILNOQ。又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY
   请问对于以下字符串，排列之后字符串是什么?

   WHERETHEREISAWILLTHEREISAWAY

   public class PaiLieZiMu {
   public static void main(String[] args) {                        java.util.Arrays.stream("WHERETHEREISAWILLTHEREISAWAY".split("")).sorted().forEach(System.out::print);
   }
   }

   答案：AAAEEEEEEHHHIIILLRRRSSTTWWWY

2. 特殊时间

   2022 年 2 月 22 日 22:20 是一个很有意义的时间，年份为 2022，由3个2和 1个0组成，如果将月和日写成 4 位，为 0222，也是由3个2和1个0组成，如果将时间中的时和分写成 4 位，还是由 3 个 2 和 1个0 组成
   小蓝对这样的时间很感兴趣，他还找到了其它类似的例子，比如 111 年 10月 11 日 01:11，2202 年 2 月 22 日 22:02 等等。
   请问，总共有多少个时间是这种年份写成 4 位、月日写成 4 位、时间写成4 位后由 3 个一种数字和 1 个另一种数字组成。注意 1111 年 11 月 11 日 11:11不算，因为它里面没有两种数字。

   public class TeShuShiJian {
   public static void main(String[] args) {
       DateTimeFormatter d1 = DateTimeFormatter.ofPattern("MMdd");
          DateTimeFormatter d2 = DateTimeFormatter.ofPattern("HHmm");
          LocalDateTime start = LocalDateTime.of(0000, 01, 01, 00, 00);
          LocalDateTime end = LocalDateTime.of(0000, 12, 31, 23, 59);
          int[] buff = new int[128];
          int ans = 0;
          for (; start.compareTo(end) <= 0; start = start.plusMinutes(1)) {
              for (char i = '0'; i <= '9'; ++i) buff[i] = 0;
              for (byte b : start.format(d1).getBytes()) ++buff[b];
              boolean flag1 = true, flag3 = true;
              for (char i = '0'; i <= '9'; ++i)
                  if (buff[i] == 1) flag1 = false;
                  else if (buff[i] == 3) flag3 = false;
              if (flag1 || flag3) continue;
              for (byte b : start.format(d2).getBytes()) --buff[b];
              for (char i = '0'; i <= '9'; ++i)
                  if (buff[i] != 0) flag1 = true;
              if (!flag1) ++ans;
          }
          System.out.println(4 * ans);
   }
   }

   答案：212

3. 纸张尺寸

   在 ISO 国际标准中定义了 A0 纸张的大小为 1189m x 841mm，将 AO 纸沿长边对折后为 A1 纸，大小为 841mm x 594mm，在对折的过程中长度直接取下整 (实际裁剪时可能有损耗)。将 A1 纸沿长边对折后为 A2 纸，依此类推。输入纸张的名称，请输出纸张的大小。

   public class ZhiZhangChiCun {
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       Scanner sc = new Scanner(System.in);
       // A0尺寸
       int a = 1189;
       int b = 841;
       String c = sc.next();
       sc.close();
       for (int i = 0; i < c.charAt(1) - 48; i++) {
           if (a >= b) {
               a /= 2;
           } else {
               b /= 2;
           }
       }
       if (a >= b) {
           System.out.println(a);
       }
       System.out.println(b);
       if (a < b) {
           System.out.println(a);
       }
   }
   }

   测试用例：case 1：I：A0 ，O：1189\n841 ，case 2：I：A1 ，O：841\n594

4. 求和

   给定 n 个整数 $a_1,a_2,...,a_n$ ，求它们两两相乘再相加的和，即$S=a_1a_2+a_1a_3+...+a_1a_n+a_2a3+...+a{n-2}a{n-1}+a{n-2}an+a{n-1}*a_n$

   public class QiuHe {
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       Scanner sc = new Scanner(System.in);
       int a = sc.nextInt();
       int[] array = new int[a];
       long count = 0;
       for (int i = 0; i < array.length; i++) {
           array[i] = sc.nextInt();
       }
       sc.close();
       for (int i = 0; i < array.length; i++) {
           for (int j = i + 1; j < array.length; j++) {
               count += array[i] * array[j];
           }
       }
       System.out.println(count);
   }
   }

   测试用例：I：4\n1 3 6 9 ，O：117

5. 矩形拼接

   已知 3 个矩形的大小依次是 $a_1b_1,a_2b_2$ 和 $a_3*b_3$。用这 3 个矩形能拼出的所有多边形中，边数最少可以是多少?
   例如用 3x2 的矩形(用A 表示)、4X1 的矩形(用 B 表示) 和2x4 的矩形 (用 c 表示) 可以拼出如下 4 边形。

   

   例如用 3x2 的矩形(用 A 表示)、3X1 的矩形(用 B 表示) 和 1X1的知形(用 c 表示) 可以拼出如下 6 边形。

   

   public class JvXingPinJie {
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int[] b = new int[n];
       for (int i = 0; i < n; i++) {
           int[][] squares = new int[3][2];
           for (int j = 0; j < 3; j++) {
               squares[j][0] = sc.nextInt();
               squares[j][1] = sc.nextInt();
           }
           boolean matchingSides = false;
           for (int j = 0; j < 3; j++) {
               for (int k = 0; k < 3; k++) {
                   if (j != k && (squares[j][0] == squares[k][0] || squares[j][0] == squares[k][1]
                           || squares[j][1] == squares[k][0] || squares[j][1] == squares[k][1])) {
                       matchingSides = true;
                       break;
                   }
               }
               if (matchingSides) {
                   break;
               }
           }
   
           b[i] = matchingSides ? 4 : 6;
       }
       sc.close();
       for (int i = 0; i < n; i++) {
           System.out.println(b[i]);
       }
   }
   }

   测试用例：I：2\n2 3 4 1 2 4\n1 2 3 4 5 6 ，O：4\n6

6. 选数异或

   给定一个长度为 n 的数列 $A_1,A_2,...,A_n$ 和一个非负整数 x，给定 m 次查询,每次询问能否从某个区间$[l,r]$中选择两个数使得他们的异或等于 x。

   public class XuanShuYiHuo {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int m = sc.nextInt();
       int x = sc.nextInt();
       int a = 0;
       int dep[] = new int[n + 1];// 储存数列某个位置，至少存在一对数异或等于x的最大左下标。
       int map[] = new int[1 << 20];// 储存数列中任意一个元素的位置。大小为2^20
       for (int i = 1; i <= n; i++) {
           a = sc.nextInt();
           dep[i] = Math.max(dep[i - 1], map[a ^ x]);// 数列前一个元素也可能有满足条件的下标，取最大即可。
           map[a] = i;// 写在最后是防止有a^a=x,的可能出现。
           // 如果map[a^x]>a,由于还没有输入过a^x,所以map[a^x]实际上是默认值0
       }
       for (int j = 0; j < m; j++) {
           int l = sc.nextInt();
           int r = sc.nextInt();
           System.out.println(dep[r] >= l ? "yes" : "no");
       }
       sc.close();
   }
   }

   测试用例：I：4 4 1\n1 2 3 4\n1 4\n1 2\n2 3\n3 3 ，O：yes no yes no

   备注：输入时就会输出对应结果，继续按样例输入至程序结束即可

7. GCD

   给定两个不同的正整数 a,b，求一个正整数 k 使得 gcd(a + k,b + k) 尽可能大，其中 gcd(a,b) 表示 a 和 b 的最大公约数，如果存在多个 k，请输出所有满足条件的 k 中最小的那个。

   public class GCD {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       long a = sc.nextLong();
       long b = sc.nextLong();
       sc.close();
       long max = Math.abs(a - b);
       System.out.print(max - (a % max));
   }
   }

   测试用例：I：5 7 ，O：1

8. 青蛙过河

   小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
   河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上(某次跳跃后使石头高度下降到 0 是允许的)。
   小青蛙一共需要去学校上 天课，所以它需要往返 2x 次。当小青蛙具有个跳跃能力 y 时，它能跳不超过 y 的距离。
   请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课

   public class QingWaGuoHe {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       long x = sc.nextLong();
       long[] arr = new long[n + 1];
       for (int i = 1; i < n; i++) {
           arr[i] = sc.nextLong() + arr[i - 1];
       }
       sc.close();
       arr[n] = arr[n - 1] + 999999999999L;
       int l = 0;
       int sum = 0;
       for (int i = 1; i <= n; i++) {
           if (arr[i] - arr[l] >= 2L * x) {
               sum = Math.max(sum, i - l);
               l += 1;
           }
       }
       System.out.println(sum);
   }
   }

   测试用例：I：5 1\n1 0 1 0 ，O：4

9. 因数平方和

   记f(x) 为x 的所有因数的平方的和。例如: $f(12)=1^2+2^2+3^2+4^2+6^2+12^2$
   定义 $g(n)=\sum_{i=1}^nf(i)$ 。给定 n,求 g(n) 除以 $10^9+7$ 的余数

   public class YinShuPingFangHe {
   public static void main(String[] args) {
       final long N = 1000000007;
       final long inv6 = 166666668;
       Scanner sc = new Scanner(System.in);
       long res = 0, temp = 0, sum = 0;
       long n, l, r, k;
       n = sc.nextInt();
       sc.close();
       for (long i = 1; i <= n; i = r + 1) {
           l = i;
           k = n / i;
           r = n / (n / l);
           temp = sum;
           sum = r * (r + (long) 1) % N * ((long) 2 * r + 1) % N * inv6 % N;
           res = (res + k * (sum - temp) + N) % N;
       }
   
       System.out.println(res);
   }
   }

   测试用例：I：100000 ，O：680584257

10. 最长不下降子序列

    给定一个长度为 N 的整数序列: $A_1,A_2,...,A_N$。现在你有一次机会，将其中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。
    最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。

    public class ZuiChangBuXiaJiangZiXvLie {
        static int n_max = 1000000;
        static int[] arr = new int[n_max];
        static boolean[] c = new boolean[n_max];
        static long n, k;
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            k = sc.nextInt();
            c[0] = true;
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            sc.close();
            for (int i = 1; i < n; i++) {
                if (arr[i] < arr[i - 1]) {
                    c[i] = false;
                } else {
                    c[i] = true;
                }
            }
            int max = 0;
            for (int i = 0; i < n; i++) {
                if (k > 0) {
                    if (c[i]) {
                        max++;
                    } else {
                        k--;
                        max++;
                    }
                } else if (k == 0) {
                    if (c[i]) {
                        max++;
                    } else {
                        System.out.println(max);
                        break;
                    }
    
                }
            }
        }
    }

    测试用例：I：5 1\n1 4 2 8 5 ，O：4

第十四届 省赛(真题课件189)

1. 求和

   求 1 (含) 至 20230408 (含)中每个数的和

   public class QiuHe {
   public static void main(String[] args) {
          System.out.println((long) (1 + 20230408) * (20230408 >>> 1));
      }
   }

   答案：204634714038436

2. 分糖果

   两种糖果分别有 9 个和 16 个，要全部分给 7 个小朋友，每个小朋友得到的糖果总数最少为 2 个最多为 5 个，问有多少种不同的分法。糖果必须全部分
   只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。

   public class FenTangGuo {
   public static void main(String[] args) {
       dfs(1, 9, 16);
       System.out.println(sum);
   }
   
   static int sum = 0;
   
   static void dfs(int x, int a, int b) {
       if (x == 8) {
           if (a == 0 && b == 0) {
               // 如果七个人恰好分完则计数加一
               sum++;
           }
           return;
       }
   
       for (int i = 0; i <= a; i++) {
           for (int j = 0; j <= b; j++) {
               if (i + j >= 2 && i + j <= 5) {
                   // 只有满足2-5的条件才可以
                   dfs(x + 1, a - i, b - j);
               }
           }
       }
   }
   }

   答案：5067671

3. 三国游戏

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

   public class SanGuoYouXi {
   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 {
       st.nextToken();
       return (int) st.nval;
   }
   
   public static long nextLong() throws Exception {
       st.nextToken();
       return (long) st.nval;
   }
   }

   测试用例：I：3 \n 1 2 2\n2 3 2\n1 0 7 ，O：2

4. 平均

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

   public class PingJun {
   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 {
       st.nextToken();
       return (int) st.nval;
   }
   
   public static long nextLong() throws Exception {
       st.nextToken();
       return (long) st.nval;
   }
   }

   测试用例：I：10\n1 1\n1 2\n1 3\n2 4\n2 5\n2 6\n3 7\n3 8\n3 9\n4 10 ，O：27

5. 填充

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

   public class TianChong {
   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;
   }
   }

   测试用例：I：1110?0 ，O：2

6. 棋盘

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

   public class QiPan {
   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;
   }
   }

   测试用例：I：3 3\n1 1 2 2\n2 2 3 3\n1 1 3 3 ，O：0 0 1 \n0 1 0 \n1 0 0

7. 子矩阵

   给定一个 nxm (n行 m列)的矩阵。
   设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a x b (a 行 b 列)的子矩阵的价值的和。
   答案可能很大，你只需要输出答案对 998244353 取模后的结果

   public class ZiJvZhen {
   public static void main(String[] args) {
       int n = nextInt(), m = nextInt();
          int a = nextInt(), b = nextInt();
          long ans = 0;
          for (int i = 1; i <= n; ++i)
              for (int j = 1; j <= m; ++j)
                  matrix[i][j] = nextInt();
          Deque maxq = new ArrayDeque();
          Deque minq = new ArrayDeque();
          for (int j = 1; j <= m; ++j) {
              maxq.clear();
              minq.clear();
              for (int i = 1; i <= n; ++i) {
                  while (!maxq.isEmpty() && maxq.peekFirst() <= i - a) maxq.pollFirst();
                  while (!minq.isEmpty() && minq.peekFirst() <= i - a) minq.pollFirst();
                  while (!maxq.isEmpty() && matrix[i][j] >= matrix[maxq.peekLast()][j]) maxq.pollLast();
                  while (!minq.isEmpty() && matrix[i][j] <= matrix[minq.peekLast()][j]) minq.pollLast();
                  maxq.offerLast(i);
                  minq.offerLast(i);
                  max[i][j] = matrix[maxq.peekFirst()][j];
                  min[i][j] = matrix[minq.peekFirst()][j];
              }
          }
          for (int i = 1; i <= n; ++i) {
              maxq.clear();
              minq.clear();
              for (int j = 1; j <= m; ++j) {
                  while (!maxq.isEmpty() && maxq.peekFirst() <= j - b) maxq.pollFirst();
                  while (!minq.isEmpty() && minq.peekFirst() <= j - b) minq.pollFirst();
                  while (!maxq.isEmpty() && max[i][j] >= max[i][maxq.peekLast()]) maxq.pollLast();
                  while (!minq.isEmpty() && min[i][j] <= min[i][minq.peekLast()]) minq.pollLast();
                  maxq.offerLast(j);
                  minq.offerLast(j);
                  if (i >= a && j >= b)
                      ans = (ans + (long) max[i][maxq.peekFirst()] * min[i][minq.peekFirst()]) % 998244353;
              }
          }
          System.out.println(ans);
   }
   
      static int[][] matrix = new int[1001][1001];
   static int[][] max = new int[1001][1001];
   static int[][] min = new int[1001][1001];
   
      static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   
      static int nextInt() {
          try {
              in.nextToken();
          } catch (IOException e) {
              e.printStackTrace();
          }
          return (int) in.nval;
      }
   }

   测试用例：I：2 3 1 2\n1 2 3\n4 5 6 ，O：58

8. 公因数匹配

   给定 n 个正整数 A;，请找出两个数 使得 i<j且 A;和 A存在大于 1的公因数。
   如果存在多组 i;j，请输出 i最小的那组。如果仍然存在多组 i.i，请输出 i最小的所有方案中 最小的那组。

   public class GongYinShuPiPei {
   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 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);
   
           for (int j = 2; j <= k; j++) {
               if (a % j == 0 && a != j) {
                   if (map.get(j) == null)
                       map.put(j, i + 1);
                   else {
                       r = Math.min(r, map.get(j));
                       l = i + 1;
                   }
                   if (map.get(a / j) == null)
                       map.put(a / j, i + 1);
                   else {
                       r = Math.min(r, map.get(a / j));
                       l = i + 1;
                   }
               }
           }
           if (map.get(a) == null)
               map.put(a, i + 1);
           else if (a != 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;
   }
   }

   测试用例：I：5\n5 3 2 6 9 ，O：2 4

9. 异或和之差

   给定一个含有 n 个元素的数组 A;，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。

   public class YiHuoHeZhiCha {
   public static void main(String[] args) {
       int n = nextInt(), ans = 0;
       for (int i = 1; i <= n; ++i)
           A[i] = nextInt();
       Trie lt = new YiHuoHeZhiCha().new Trie(), rt = new YiHuoHeZhiCha().new Trie();
       lmin[0] = rmin[n + 1] = 0x3f3f3f3f;
       for (int i = 1, s = 0; i <= n; ++i) {
           lt.insert(s);
           s ^= A[i];
           lmax[i] = Math.max(lmax[i - 1], lt.xorMax(s));
           lmin[i] = Math.min(lmin[i - 1], lt.xorMin(s));
       }
       for (int i = n, s = 0; i >= 1; --i) {
           rt.insert(s);
           s ^= A[i];
           rmax[i] = Math.max(rmax[i + 1], rt.xorMax(s));
           rmin[i] = Math.min(rmin[i + 1], rt.xorMin(s));
       }
       for (int i = 1; i < n; ++i) {
           ans = Math.max(ans, rmax[i + 1] - lmin[i]);
           ans = Math.max(ans, lmax[i] - rmin[i + 1]);
       }
       System.out.println(ans);
   }
   
   static int[] A = new int[200001];
   static int[] lmax = new int[200002];
   static int[] lmin = new int[200002];
   static int[] rmax = new int[200002];
   static int[] rmin = new int[200002];
   
   class Trie {
       int high = 20;
       Node root = new Node();
       void insert(int x) {
           Node cur = root;
           for (int i = high; i >= 0; --i) {
               int bit = (x >> i) & 1;
               if (cur.ch[bit] == null)
                   cur.ch[bit] = new Node();
               cur = cur.ch[bit];
           }
       }
   
       int xorMax(int x) {
           int max = 0;
           Node cur = root;
           for (int i = high; i >= 0; --i) {
               int bit = (x >> i) & 1;
               if (cur.ch[bit ^ 1] != null) {
                   cur = cur.ch[bit ^ 1];
                   max |= 1 << i;
               } else {
                   cur = cur.ch[bit];
               }
           }
           return max;
       }
   
       int xorMin(int x) {
           int min = 0;
           Node cur = root;
           for (int i = high; i >= 0; --i) {
               int bit = (x >> i) & 1;
               if (cur.ch[bit] != null) {
                   cur = cur.ch[bit];
               } else {
                   min |= 1 << i;
                   cur = cur.ch[bit ^ 1];
               }
           }
           return min;
       }
   
       class Node {
           Node[] ch = new Node[2];
       }
   
   }
   
   static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   
   static int nextInt() {
       try {
           in.nextToken();
       } catch (IOException e) {
           e.printStackTrace();
       }
       return (int) in.nval;
   }
   }

   测试用例：I：6\n1 2 4 9 2 7 ,O：14

10. 太阳

    这天，小蓝在二维坐标系的点 (X,Y) 上放了一个太阳，看做点光源。他拿来了 m 条线段，将它们平行于 x 轴放置在了坐标系中，第i 条线段的左端点在 x,y，长度为飞。线段之间不会有重合或部分重合的情况(但可能出现端点相交)。小蓝想知道有多少条线段能被太阳照亮 (一条线段有长度大于 0的部分被照亮就算)。

    public class TaiYang {
        static Scanner sc = new Scanner(System.in);
        static int n = sc.nextInt();
        static int X = sc.nextInt();
        static int Y = sc.nextInt();
    
        public static void main(String[] args) {
            List list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int l = sc.nextInt();
                list.add(new Triple(x, y, l));
            } // 将所有x,y,l读入list中
            list.sort(new Comparator() {
                @Override
                public int compare(Triple l1, Triple l2) {
                    return -Integer.compare(l1.y, l2.y);
                }
            }); // 以y从大到小排序
            double[] arr1 = new double[2 * n]; // 保持以y从大到小排序的顺序进行在x轴上的覆盖
            double[] arr2 = new double[2 * n]; // 以在x轴上的坐标值排序，方便二分查找
            int i = -1;
            for (Triple item : list) {
                arr1[++i] = arr2[i] = y0x(item.x, item.y);
                arr1[n + i] = arr2[n + i] = y0x(item.x + item.l, item.y);
            }
            Arrays.sort(arr2);
            boolean[] tree = new boolean[1 << 19]; // 将已覆盖的位置进行标记
            boolean f = false;
            int ans = 0;
            for (int j = 0; j < n; j++) {
                int l = Arrays.binarySearch(arr2, arr1[j]);
                int r = Arrays.binarySearch(arr2, arr1[j + n]);
                for (int k = l; k < r; k++) {
                    if (!tree[k]) {
                        tree[k] = true;
                        f = true;
                    }
                }
                if (f) {
                    ++ans;
                    f = false;
                }
            }
            System.out.println(ans);
        }
    
        public static double y0x(int x, int y) {
            if (x == X)
                return x;
            long a = (long) X * y;
            long b = (long) Y * x;
            return (b - a) / ((Y - y) * 1.0);
        } // 返回端点在x轴上的投影
    }
    
    class Triple {
        int x, y, l;
    
        public Triple(int x, int y, int l) {
            this.x = x;
            this.y = y;
            this.l = l;
        }
    }

    测试用例：I：3 10 2000000\n5 3 5\n6 2 4\n0 1 10 ，O：2

終わり