BUPT2011网研院机试Java题解

题目搜集于各位前辈，侵删。

第一题

import java.util.Scanner;public class c1101 {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);StringBuffer sb = new StringBuffer(sc.next());int n = sc.nextInt();for(int j = 0;j<n;j++) {String temp = sc.next();int op = temp.charAt(0)-'0';if(op == 0) {int i = temp.charAt(1)-'0';int len = temp.charAt(2)-'0';for(int k = i;k<=(i+len)/2;k++) {char c = sb.charAt(k);sb.setCharAt(k, sb.charAt(i+len-1-k));sb.setCharAt(i+len-1-k, c);}}else {int i = temp.charAt(1)-'0';int len = temp.charAt(2)-'0';String newString  = temp.substring(3);sb.replace(i, i+len, newString);}System.out.println(sb);}}}

第二题

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
//差点忘了模怎么求
public class c1102 {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int n = sc.nextInt();ArrayList<Complex> al = new ArrayList<Complex>();for(int i = 0;i<n;i++) {String s = sc.next();if(s.equals("Pop")) {if(al.size()==0) {System.out.println("empty");}else {al.remove(al.size()-1);System.out.println("SIZE = "+al.size());}}else {String temp = sc.next();int pos = 0;for(int j = 0;j<temp.length();j++) {if(temp.charAt(j)=='+') {pos = j;break;}}int a = Integer.parseInt(temp.substring(0,pos));int b = Integer.parseInt(temp.substring(pos+2));Complex complex = new Complex(a,b);al.add(complex);Collections.sort(al, new complexComparator());System.out.println("SIZE = "+al.size());System.out.println(a+"+i"+b);}}}static class Complex{int a;int b;public Complex(int a, int b) {super();this.a = a;this.b = b;}}static class complexComparator implements Comparator<Complex>{@Overridepublic int compare(Complex c1, Complex c2) {// TODO Auto-generated method stubdouble mod1 = Math.sqrt(c1.a*c1.a+c1.b*c1.b);double mod2 = Math.sqrt(c2.a*c2.a+c2.b*c2.b);if(mod1 > mod2) {return 1;}else if(mod1<mod2){return -1;}else {return c2.b-c1.b;}}}
}

第三题

import java.util.Arrays;
import java.util.Scanner;public class i1103 {static int n;static String s;static boolean[][] connect;static boolean[] vis;static String result;static String min;public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()) {n = sc.nextInt();s = sc.next();connect = new boolean[n][n];vis = new boolean[n];init();for(int i = 0;i<n-1;i++) {int a = sc.nextInt();int b = sc.nextInt();connect[a][b] = true;connect[b][a] = true;}for(int i = 0;i<n;i++) {Arrays.fill(vis, false);vis[i] = true;result = dfs(i);if(i==0) {min = result;}else {if(islittle(result,min)) {min = result;}}}System.out.println(min);}sc.close();}static void init() {for(int i = 0;i<n;i++) {for(int j =0;j<n;j++) {connect[i][j] = false;}vis[i] = false;}}static String dfs(int k) {String left = "";String mid = String.valueOf(s.charAt(k));String right = "";int minvalue = 0;int minpoint = 0; boolean first = true;for(int i = 0;i<n;i++) {if(connect[k][i]&&!vis[i]) {if(first){minpoint = i;minvalue = s.charAt(i);first = false;}else {if(s.charAt(i)<minvalue) {minpoint = i;minvalue = s.charAt(i);}}}}if(!first) {result = String.valueOf(s.charAt(k))+result;vis[minpoint] = true;left = dfs(minpoint);}first = true;String tempright = null;for(int i = 0;i<n;i++) {if(connect[k][i]&&!vis[i]) {vis[i] = true;tempright = dfs(i);if(first) {right = tempright;}else {if(islittle(tempright,right)) {right = tempright;}first = false;}}}return left+mid+right;}static boolean islittle(String a,String b) {for(int i = 0;i<a.length()&&i<b.length();i++) {if(a.charAt(i)<b.charAt(i)) {return true;}else if(a.charAt(i)>b.charAt(i)){return false;				}}return false;}
}

第四题

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class i1104 {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc  = new Scanner(System.in);while(sc.hasNext()) {int n = sc.nextInt();Equation[] equ = new Equation[n];ArrayList<NT> nt = new ArrayList<NT>();for(int i =0 ;i<n;i++) {char c = sc.next().charAt(0);String s = sc.next();equ[i] = new Equation(c,s);}int flag = 0;//每一次扫描全部式子while(true) {flag = 0;//一次扫描for(int i = 0;i<n;i++) {char c1 = equ[i].c;char c2 = equ[i].s.charAt(0);//找一下c1对应的int flag1 = 0;int j1 = 0;for(j1 = 0;j1<nt.size();j1++) {if(nt.get(j1).c == c1) {flag1 = 1;break;}}//如果没有找到if(flag1 == 0) {NT a = new NT(c1);nt.add(a);j1 = nt.size()-1;}//大写字母找first，小写字母直接加if(c2>='A'&&c2<='Z') {//找c2的first，如果能找到，就加上c2的first，找不到就算了int flag2 = 0;int j2 = 0;for(j2 = 0;j2<nt.size();j2++) {if(nt.get(j2).c == c2) {flag2 = 1;break;}}if(flag2==1) {								for(char c : nt.get(j2).first) {if(!nt.get(j1).first.contains(c)) {nt.get(j1).first.add(c);flag = 1;}}}}else {if(!nt.get(j1).first.contains(c2)) {nt.get(j1).first.add(c2);flag = 1;}}}if(flag == 0) {break;}			}Collections.sort(nt,new ntComparator());for(int i = 0;i<nt.size();i++) {System.out.print(nt.get(i).c);for(char c:nt.get(i).first) {System.out.print(" "+c);}System.out.println();}}sc.close();}static class NT{char c;Set<Character> first = new HashSet<Character>();public NT(char c) {super();this.c = c;}}static class Equation{char c;String s;public Equation(char c, String s) {super();this.c = c;this.s = s;}}static class ntComparator implements Comparator<NT>{@Overridepublic int compare(NT n1, NT n2) {// TODO Auto-generated method stubchar c1 = n1.c;char c2 = n2.c;return c1-c2;}}
}