IME++ Starters Try-outs 2019 题解-阿里云开发者社区

IME++ Starters Try-outs 2019 题解

2022-12-01 114

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： IME++ Starters Try-outs 2019 题解

IME++ Starters Try-outs 2019 题解

A. Arnon-Degree of Separation

传送门

**题目大意：**找到人和人之间有直接联系的最长距离，如果存在不能到达的人就直接输出“=[”反之输出“=]”并输出最短距离

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class A {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int m=sc.nextInt();
    node a[]=new node[n+1];
    for(int i=1;i<=n;i++) {
      a[i]=new node();
    }
    for (int i = 0; i < m; i++) {
      int a1=sc.nextInt();
      int a2=sc.nextInt();
      //储存
      a[a1].list.add(a2);
      a[a2].list.add(a1);
    }
    int count=0;
    for (int i = 1; i <= n; i++) {
      Queue<Integer> queue=new LinkedList<>();
      boolean[] arr=new boolean [n+1];//标记为都没走
      int  b[]=new int [n+1]; //记录走的步数
      arr[i]=true;//标记
      b[i]=0;
      queue.offer(i);//放入队列之中
      while(!queue.isEmpty()) {
        int q=queue.poll();//弹出
        for (int nextX  : a[q].list) {//逐个便利相邻的数字
          if(!arr[nextX]) {//如果没到达
            arr[nextX]=true;//标记
            queue.offer(nextX);//放入队列中
            b[nextX]=b[q]+1;//纪录连接距离
          }
        }
      }
      for (int j = 1; j < arr.length; j++) {
        if(!arr[j]) {
          System.out.println("=[");
          return;
        }
      }
      for (int j : b) {
        count=Math.max(count, j);
      }
    }
    System.out.println("=] "+count);
  }
}
class node{
  List<Integer> list=new ArrayList<Integer>();
  public List<Integer> getList() {
    return list;
  }
  public void setList(List<Integer> list) {
    this.list = list;
  }
}

B. Building Bridges

传送门

题解：没读题，第一眼感觉就是LCS,写了一个模板，然后对了。dp的LCS模板题

import java.util.Scanner;
public class B {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    String s1=sc.next();
    String s2=sc.next();
    int max=-1;
    int dp[][]=new int [s1.length()+1][s2.length()+1];
    for (int i = 1; i < dp.length; i++) {
      for (int j = 1; j < dp[0].length; j++) {
        if(s1.charAt(i-1)==s2.charAt(j-1)) {
          dp[i][j]=dp[i-1][j-1]+1;
        }else {
          dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
        }
        max=Math.max(max, dp[i][j]);
      }
    }
    System.out.println(max);
    sc.close();
  }
}

C. Coach

传送门

题意：找打>x,同时队员之差小于等于d的组合数

**题解：**数据量很小，直接排序，然后剪枝就行

import java.util.Arrays;
import java.util.Scanner;
public class C {
  static int count=0;
  static int n,x,d;
  static long a[];
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    n=sc.nextInt();x=sc.nextInt();d=sc.nextInt();
    a=new long [n];
    for (int i = 0; i < a.length; i++) {
      a[i]=sc.nextLong();
    }
    Arrays.sort(a);
    for (int i = 0; i < a.length; i++) {
      dsf(i,a[i],a[i]);
    }
    System.out.println(count);
  }
  private static void dsf(int k, long min,long sum) {
    if(sum>x) count++;
    for (int i = k+1; i < a.length; i++) {
      if(a[i]-min<=d) dsf(i, min, sum+a[i]);
      }
  }
}

D. Donimo’s

传送门

题解：水题，直接排序，找到前后两个数之和相加得到的最大数字和最小数字的差

package test;
import java.util.Arrays;
import java.util.Scanner;
public class D {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int t=sc.nextInt()*2;
    long a[]=new long [t];
    for (int i = 0; i < a.length; i++) {
      a[i]=sc.nextLong();
    }
    Arrays.sort(a);
    long max=Integer.MIN_VALUE;
    long min=Integer.MAX_VALUE;
    for (int i = 0; i <=t/2; i++) { 
      long sum=a[i]+a[t-1-i];
      max=Math.max(max, sum);
      min=Math.min(min, sum);
    }
    System.out.println(max-min);
    sc.close();
  }
}

E. Essay Time

传送门

题解:将长度大于四的List1里面，然后如果已经存进去了的再存进去一个List2里，但是java过不了，卡java的题

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
public class E1 {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int t=sc.nextInt();
    Set <String >map1=new HashSet<String>();
    List <String >map2=new ArrayList<String>();
    while(t-->0) {
      String s=sc.next();
      if(s.length()>=4) {
        if(!map1.contains(s)) {
          map1.add(s);
        }else {
          map2.add(s);
        }
      }
    }
    System.out.println(map2.size());
    for (String string : map2) {
      System.out.println(string);
    }
  }
}

F. Friendship Matters

传送门

题解：并查集模板题，直接套板子就行了

import java.io.*;
import java.math.*;
import java.util.*;
public class Main {
  static HashMap<String, Integer>map=new HashMap<>();
  static int find(int arr[], int x) {//查找
        if(arr[x]!=x) {
            arr[x] =  find(arr, arr[x]);
        }
        return arr[x];
    }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m=sc.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = i;
            map.put(sc.next(), i);
        }
        for(int i=0;i<m;i++) {
          int s=sc.nextInt();
          if(s==1) {
            int a=find(arr, map.get(sc.next()));
            int b=find(arr, map.get(sc.next()));
            arr[a] = b;
          }else {
            int a=find(arr, map.get(sc.next()));
            int b=find(arr, map.get(sc.next()));
            if(a==b)System.out.println("yes");
            else System.out.println("no");
          }
        }
  }
}