贝壳java开发笔试 2020 8 11

第二题

题目

给一个n*m的表格染色，相邻（左右上下，紧挨着）的格子颜色必须不同，每个颜色染的格子数量必须相同，问最少需要多少种颜色。

思路

输入	输出
1，1	1
2，3	2
10，10	2
3，3	3
15，27	3
77，49	7

自己画个图推一推，发现了什么？仔细想想应该知道怎么做了。

第三题

题目

输入n，表示将要输入n个数字，求其连续的一段数字的异或值最大。显然所有的数字进行异或就是最大的值，但是题目要求的是，求一个最短的区间，让它们进行异或，也能得出这个最大异或值，你要求最短的区间。

样例

输入

1 2 3

输出

解释

1，2，3

1，2

都满足异或值最大，但是单独一个数字3就是最短的区间。

限制

n >= 1 && n <= 10^6

输入的n个数字都是int型

思路：二分 + 暴力

代码

package 贝壳;
 
import java.util.Scanner;
 
public class Question3_3 {
 
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int []A = new int[n];
        long ans = 0;
        for (int i = 0; i < n; i++){
            A[i] = sc.nextInt();
            ans |= A[i];
        }
        //System.out.println("ans : " + ans);
        int left = 0;
        int right = n;
        int mid;
        boolean flag = false;
        long temp;
        int min0 = 9999999;
        while (left <= right) {
            mid = (left + right) / 2;
            flag = false;
            for (int i = 0; i <= n - mid; i++) {
                temp = 0;
                for (int j = i; j < i + mid; j++) {
                    temp |= A[j];
                    if (temp == ans) {
                        flag = true;
                        break;
                    }
                    //System.out.print(j + " ");
                }
                //System.out.println();
                //System.out.println( i + " : " + temp);
                if (flag) {
                    break;
                }
            }
 
            if (flag) {
                right = mid - 1;
                min0 = Math.min(mid,min0);
            } else{
                left = mid + 1;
            }
        }
        System.out.println(min0);
    }
}

第四题

题目意思翻译过了...
输入 n(表示有n个城市，城市编号1-n), m
m表示接下来输入m行数据
每行输入三个数u,v,w 表示u能通向v, 花费为w。
删除一些边，让最少的边保证城市的连通。在这个基础上，求城市连通的最大花费。
5 5
1 2 1
1 5 1
3 5 1
2 4 1
4 5 2

输出 5

思路：最小生成树，改成最大

移步最小生成树