美团测开笔试| 交通距离 求大佬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;
        }

    }



}