淘天笔试简单题解

第一题：我猜是贪心，分别统计每个数字的最大值，然后统计每个频次出现的数字数目，然后分别从最大值开始贪心，最后写的，没时间了

当前值的频次a

小于等于频次a的所有的数字总数为 m

频次大于a的数字个数（不是总数）为b

如果 a + m + b*a >=k ，那么当前数就是最大的众数

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();in.nextLine();
        int[] res = new int[t];
        for(int i = 0;i<t;i++){
            int n = in.nextInt(),k = in.nextInt();in.nextLine();
            int[] a = new int[n];
            Map<Integer,Integer> map = new HashMap<>();
            for(int j=0;j<n;j++){
                a[j] = in.nextInt();
                map.put(a[j],map.getOrDefault(a[j],0)+1);
            }
            Map<Integer,Integer> map2 = new HashMap<>();
            for(Map.Entry<Integer,Integer> e:map.entrySet()){
                map2.put(e.getKey(),map2.getOrDefault(e.getKey(),0)+1);
            }
            Arrays.sort(a);
            int cnt = 0;
            int mx;
            for(int j=n-1;j>=0;j--){
                int times = map.get(a[j]);
                int c = times;
                for(int z=1;z<=times;z++){
                    if(map2.get(z)!=null){
                        c+=map2.get(z);
                        if(c>=k){
                            res[i]=a[j];
                            break;
                        }
                    }
                }
                if(res[i]!=0){
                    break;
                }
                j-=times-1;
            }
        }
        for(int i=0;i<t;i++){
            System.out.println(res[i]);
        }
    }
}

第二题：数论？（菜鸟不懂是哪个类别的）

就是如果当前的x>n ，那么在n位置就是x%n的值，所以需要一次取余

在[x+1,... ]位置就是 x 的值，因为x对于一个大于x的值取余为x，这里右界看一下就好了，不好写，因为n的值不定（所以有一个特判）

在[1,x] 的左侧就是0，因为x一旦到了x的位置取余之后一直是0

但是这题需要看一下边界，就是 k<=x+1（被边界卡了不少时间）

import java.util.Scanner;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();in.nextLine();
        int[] res = new int[t];
        for(int i = 0;i<t;i++){
            int n = in.nextInt(),x = in.nextInt(),k = in.nextInt();
            if(k==n+1){
                // System.out.println("special");
                res[i] = x; // 特判
            }
            else{
                x = x%n; // 第 n 项
                if(k<=x+1){
                    // System.out.println("left");
                    res[i] = 0; // 如果查询在 x 的左侧，取余结果为0
                }
                else{
                    // System.out.println("right");
                    res[i] = x; // 如果查询在 x 右侧，得到 x 
                }
            }
        }
        for(int i=0;i<t;i++){
            System.out.println(res[i]);
        }
    }
}

这题没看懂，应该是并查集，如果两个端点祖先相同，输出yes，否则no

然后看了示例感觉好像可以构成多个那个不知道什么名字的玩意儿

那么需要确定之前出现的边有没有构成环，我就用一个map记录每次构成环的时候的祖先节点，

如果一个无环的域和成环的域连接了，需要将无环域的原本祖先也记录进去，否则无环域的非祖先节点没有当前域已经承欢的信息

但是最后也不行

这题调了快半个小时，绝望了

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        class Union{
            int[] fa;
            public Union(int n){
                fa = new int[n+1];
                for(int i = 0;i<n+1;i++){
                    fa[i] = i;
                }
            }
            public int find(int u){
                if(fa[u] == u){
                    return u;
                }
                int f = find(fa[u]);
                fa[u] = f; // 变胖
                return f;
            }

            public boolean isU(int u,int v){
                if(find(u)==find(v)){
                    return true;
                }
                return false;
            }

            public void u(int u,int v){
                int uu = find(u),vv = find(v);
                fa[uu] =vv;
            }

            public void print(){
                for(int i=0;i<fa.length+1;i++){
                    System.out.println(i+ " de fa is "+ fa[i]);
                }
            }
        }

        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();in.nextLine();
        boolean sign = true;
        Union union = new Union(n);
        boolean[] res = new boolean[n];
        Map<Integer,Boolean> map = new HashMap<>();
        for(int i = 0;i<n+1;i++){
            map.put(i,false);
        }
        // union.print();
        for(int i=0;i<m;i++){
            int u=in.nextInt(),v = in.nextInt();in.nextLine();
            int uf = union.find(u);
            int uv = union.find(v);
            if(map.get(uf) || map.get(uv) ){
                res[i] = false;
                if(!map.get(uf)){ // 顺序不能错
                    union.u(u,v);
                    map.put(uf,true);
                }else if (!map.get(uv)){
                    union.u(v,u);
                    map.put(uv,true);
                }
                continue;
            }
            if(union.isU(u,v)){
                // System.out.println(i+ "  "+" true");
                map.put(union.find(u),true);
                res[i] = true;
            }
            else{
                // System.out.println(i+ "  "+" false ");
                res[i] = false;
                union.u(u,v);
            }
        }
        // union.print();
        for(int i = 0;i<n;i++){
            System.out.println(res[i]?"Yes":"No");
        }
    }
}

总得分0+1+0.03，哎

一开始忘记了笔试，中途开始写，太慌了，而且不给用IDEA，好难调代码啊