美团测开笔试| 交通距离 求大佬ac题解
字符串前缀 时间限制: 3000M S内存限制: 589824KB 题目描述:现在有两个字符串S和T,你需要对S进行若干次操作,使得S是T的一个前缀(空串也是一个前缀)。每次操作可以修改S的一个字符,或者删除一个S末尾的字符。小团需要写一段程序,输出最少需要操作的次数。 输入描述 第一行一个正整数C,表示数据组数;对于每一组数据输入两行仅包含小写字母的字符串S和T。 1≤|S|,|T|≤5X104 , 1≤C≤10 输出描述 对于每一组数据,输出一个整数,表示最少需要操作的次数。 样例输入 2 aba abbabcdefg 样例输出 14 提示第一组数据,可以修改最后一个字母,使得S=abb,是T的一个前缀;第二组数据,需要将S整个串删除,操作次数为4。
直接暴力比较ac了,但其实感觉思路有瑕疵,感觉测试用例不全面。
第二题
交通规划 时间限制: 4000MS 内存限制: 589824KB 题目描述: A国有n个城市,这n个城市排成一列,依次编号为1,2,3,...,n。一开始,这n座城市之间都没有任何交通路线,于是政府打算修建一些铁路来进行交通规划。接下来T天,每一天会进行如下操作的其中一种:- “L x”:表示编号为 x 的城市与其左边的城市之间修建一条铁路。如果 x 左边没有城市或者已经修建了铁路,则无视该操作;- “R x”:表示编号为 x 的城市与其右边的城市之间修建一条铁路。如果 x 右边没有城市或者已经修建了铁路,则无视该操作;- “Q x”:表示查询 x 往左边和往右边最远能到达的城市编号。你的任务是模拟以上操作,并对于每一条“Q x”操作,输出对应的答案。 输入描述 第一行输入两个正整数 n , T ;接下来T行,每行输入形如题面中的其中一种。 1≤n≤10000, 1≤T≤200, 1≤x≤n 输出描述 对于每一个"Q x”操作,输出一行两个正整数,分别表示 x 往左边和往右边最远能到达的城市编号,中间用空格隔开。 样例输入 3 5 Q 2 L 2 Q 2 R 2 Q 2 样例输出 2 2 1 2 1 3 提示 “Q 2”:一开始城市2没有与左边和右边联通,故最左和最右都是城市2;“L 2”:城市2与城市1联通;“Q 2”:此时最左能够到达城市1,最右能到达城市2;“R 2”:城市2与城市3联通:“Q 2”:此时最左能够到达城市1,最右能到达城市3;
只能过27%测试用例,想不明白为什么??
Scanner input = new Scanner(System.in); int n=input.nextInt(); int T=input.nextInt(); int[][] table = new int[n+2][n+2]; for(int i=1;i<=n;i++){ table[i][i]=1; } while (T-->0){ String op = input.next(); int opCity = input.nextInt(); if(op.equals("Q")){ int i=opCity; int j=opCity; while (table[opCity][i]==1){ i--; } i++; while (table[opCity][j]==1){ j++; } j--; System.out.println(i+" "+j); } if(op.equals("L")){ if(opCity==0){ break; } table[opCity][opCity-1]=1; table[opCity-1][opCity]=1; } if(op.equals("R")){ if(opCity==n){ break; } table[opCity][opCity+1]=1; table[opCity+1][opCity]=1; } } }#美团4.15笔试##悬赏#