美团测开笔试| 交通距离 求大佬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笔试##悬赏#
全部评论
我后来知道为啥了 本笨逼没dfs
点赞 回复 分享
发布于 2023-04-26 21:48 陕西
是不是没考虑到,A城市往左边修路的同时A城市左边城市右边的路也一起修好了
点赞 回复 分享
发布于 2023-04-15 23:15 吉林
我和你思路代码都差不多
点赞 回复 分享
发布于 2023-04-15 19:58 广东

相关推荐

刘湘_passion:出国旅游?那就小心你的腰子咯
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务