360笔试-10.24

题目1

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author wanna
 * @version v1.0
 * @Package com.wanna.main50
 * @date 2021/10/19 11:06 下午
 */
public class Main {
    /*
    @360-1
    时间限制： 3000MS
    内存限制： 786432KB
    题目描述：
       小A的英语考了个不及格，老师很生气，并且发现他英语的语法几乎全错！于是老师决定好好教教他英语语法。
       老师想先从句子结构开始教他。一个句子至少需要包含主谓结构，即主语和谓语，并且主语在前，谓语在后。
       有些句子会在谓语后面加上宾语。避免复杂，本题中句子的顺序严格按照主语-谓语-宾语的顺序（即无宾语前置和倒装等情况）。
       老师给了小A三张单词表，分别是主语单词表、谓语单词表和宾语单词表。老师要让小A用这些单词表中的单词来造句，
       并且规定：谓语有且仅有一个单词，主语和宾语可以包含任意个单词（主语不可为空）。
       老师暂时不想让小A造出能保证意思通顺的句子，他只想让小A能够学会基本的句子结构就行。
       现在，小A根据这些单词造了m条句子，现在假设你是老师，你需要判断每条句子是否符合上述句子结构。

    输入描述
      第一行三个正整数n1,n2,n3，分别表示主语、谓语、宾语单词表的单词数；
      第二行包含n1个单词，单词仅由小写英文字母组成，每两个单词之间有一个空格，单词长度不超过10；
      第三行包含n2个单词，其他格式同上；
      第四行包含n3个单词，其他格式同上；
      第五行一个正整数m；
      接下来m行，每行一个句子。句子由若干单词（至少一个）组成，并且保证出现的单词都在上面的单词表内。每两个单词之间一个空格隔开。
      数据保证一个单词最多只可做一种句子成分。即每个单词仅会出现在一个单词表上。
      1≤n1,n2,n3≤1000,1≤m≤20,1≤句子单词数≤10

      输出描述
      对于每条句子，如果其符合句子结构，输出一行“YES”（不含引号），否则输出一行“NO”（不含引号）。


    样例输入
        3 3 3
        i you he
        am is are
        yours his hers
        5
        i am yours
        you is his
        he are hers yours
        i am am yours
        is his
    样例输出
        YES
        YES
        YES
        NO
        NO
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int n1 = scanner.nextInt();  // 主语的单词数量
        final int n2 = scanner.nextInt();  // 谓语的单词数量
        final int n3 = scanner.nextInt();  // 宾语的单词数量
        Set<String> set1 = new HashSet<>();  // 存放主语
        Set<String> set2 = new HashSet<>();  // 存放谓语
        Set<String> set3 = new HashSet<>();  // 存放宾语
        for (int i = 0; i < n1; i++) {
            set1.add(scanner.next());
        }
        for (int i = 0; i < n2; i++) {
            set2.add(scanner.next());
        }
        for (int i = 0; i < n3; i++) {
            set3.add(scanner.next());
        }
        int m = scanner.nextInt();  // 读取的是下面要输入的句子的数量
        scanner.nextLine();  // 跳转到下一行去
        List<List<String>> data = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            List<String> data0 = Arrays.stream(scanner.nextLine().split(" ")).collect(Collectors.toList());
            data.add(data0);
        }
        data.forEach(e -> process(set1, set2, set3, e));
    }

    // 要求，谓语只能有一个，主语数量>=1，宾语数量>=0，句子结构严格按照`主谓宾`的结构进行
    public static void process(Set<String> set1, Set<String> set2, Set<String> set3, List<String> data0) {
        int weiYuCount = 0, weiYuIndex = 0;
        for (int i = 0; i < data0.size(); i++) {
            final String e = data0.get(i);
            if (set2.contains(e)) {
                weiYuCount++;  // 如果这个词是谓语的话，那么把谓语的数量++
                weiYuIndex = i;  // 修改谓语所在的索引
            }
        }

        // 如果谓语的数量不是1个，return 并输出NO
        if (weiYuCount != 1) {
            System.out.println("NO");
            return;
        }
        // 如果谓语的数量是1个的话...

        // 如果谓语是句子中的第一个单词，那么输出NO
        if (weiYuIndex == 0) {
            System.out.println("NO");
            return;
        }
        System.out.println("YES");
    }
}

题目2

import java.util.Scanner;

/**
 * @author wanna
 * @version v1.0
 * @Package com.wanna.main51
 * @date 2021/10/19 11:07 下午
 */
public class Main {
    /*
    @360-2
    时间限制： 3000MS
    内存限制： 786432KB
    题目描述：
       一日，小A走在路上时看到路边摆着一面大镜子。他对着这面镜子注视了半天，突然发现自己穿越到了另一个世界！

       这个世界很奇怪：他所在的地方可视为一个n行m列的矩阵，每一个位置上都有一个非负整数或者-1。
       这时，他的耳边响起了一个很空灵的声音：“如果您想要回到原来的世界，你需要解决下面的问题：
       你需要在整个矩阵上选择一个正方形区域，使得该区域不包含任何负数，并且该区域内的数字之和最大。”

       然而这个问题对于小A来说还是太难了，所以他请了你来帮忙解决这个问题。



    输入描述
        第一行一个正整数T，表示一共有T组数据。

        对于每组数据，第一行两个正整数n,m，含义见题面；

        接下来一个n行m列的整数矩阵aij。

        1≤n,m≤500,1≤T≤5,aij∈{-1,[0,100]}

        输出描述
        对于每组数据，输出一行一个正整数，表示满足条件的最大值。如果该矩阵全为-1，则输出0.


        样例输入
        1
        4 4
        3 0 5 6
        0 9 -1 4
        -1 8 1 1
        4 -1 5 -1
        样例输出
        12
    @ AC100%
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int T = scanner.nextInt(); // 数据的组数

        // 读取T组数据
        for (int i = 0; i < T; i++) {
            final int n = scanner.nextInt();  // 矩阵的行数
            final int m = scanner.nextInt();  // 矩阵的列数
            int[][] matrix = new int[n][m];  // 矩阵

            // 读取矩阵中的数据...
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    matrix[j][k] = scanner.nextInt();
                }
            }
            process(matrix, n, m);  // 调用处理函数去进行处理...
        }
    }

    public static void process(int[][] matrix, int n, int m) {
        int maxSize = Math.min(m, n);  // 最大的正方形的边长为m和n的最小值
        int max = 0;  // 统计最终的最大值，如果遇到了非负数的正方形，那么就需要与当前值判断书否需要进行更新
        // 遍历所有的边长的正方形
        for (int i = 1; i <= maxSize; i++) {
            // 边长为i的正方形左上角坐标是[0,n-i]，纵坐标是[0,m-i]，这样下面进行遍历时就不会有非法的情况了...
            for (int x = 0; x <= n - i; x++) {
                for (int y = 0; y <= m - i; y++) {
                    final int check = check(matrix, x, y, i);
                    // 如果check==-1，那么max不变，不然的话，max需要判断是否发生更新
                    max = check == -1 ? max : Math.max(check, max);
                }
            }
        }
        System.out.println(max);
    }

    // (x,y)对应的是左上角的坐标，size代表的是当前的正方形的大小
    public static int check(int[][] matrix, int x, int y, int size) {
        int sum = 0;  // 统计当前正方形中的所有元素之和
        boolean flag = false;  // 表示是否出现过-1了

        // 遍历当前这个正方形中的所有数...
        loop:
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (matrix[i][j] < 0) {  // 如果遇到了负数，那么跳出整个循环
                    flag = true;
                    break loop;
                }
                sum += matrix[i][j];
            }
        }
        return flag ? -1 : sum;  // 如果有负数，那么return -1，不然return sum
    }
}