V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
codechaser
V2EX  ›  程序员

今天帮别人做笔试被虐了,凭记忆写出来希望有大牛给出解法。

  •  
  •   codechaser · 2019-08-09 21:29:07 +08:00 · 2804 次点击
    这是一个创建于 1934 天前的主题,其中的信息可能已经有所发展或是发生改变。

    输入数据: 第一行是 n 和 m 以空格隔开。n 指记录数,m 指查询次数。 下面 n 行: 给出 n 行数据库里面的记录,每行为一条记录,空格隔开,分别是 a(int),b(str),c(int),d(bool)。 在下面 m 行: 每行给出a_deltac_x。一共 m 行,表示每条查询操作。 要求针对每条查询操作,输出满足一下条件c_y的个数...打字实在太麻烦了,我直接上图吧:

    100446289.jpg 118102464.jpg 232567891.jpg eqaS6P.jpg

    台风天想我在家里思考的老哥来做做。

    Rorshach
        1
    Rorshach  
       2019-08-09 21:52:36 +08:00
    台风天?
    lz 是在浙江么
    Hstar
        2
    Hstar  
       2019-08-09 22:02:02 +08:00   ❤️ 4
    这题考察什么?阅读理解能力吗
    nolan1864
        3
    nolan1864  
       2019-08-09 22:17:20 +08:00
    1. 数据存两遍 vec1,vec2 ; vec1 按 c 排序,vec2 按 b 排序
    2. 对于每次查询,二分 vec1 找第一个 c,然后向后遍历 vec1 中 c 为 cx 的
    3. 遍历过程中对于每一个新出现的 b,在 vec2 中二分找第一次出现的 b,向后遍历 vec2,构造 vec3
    4. 对于 vec3 中的元素对,判断是否满足条件,将满足条件的 cy 加到容器比如 set 中
    5. 经过 2,3,4 后,统计 set 的大小

    总之就是模拟
    复杂度大概是 m * logn * 30 * (logn + 300 + 300 * 300),没算那些判断第一次 b 出现或者最后的容器 set 的复杂度

    感觉复杂度差不多,欢迎讨论
    1070794219
        4
    1070794219  
       2019-08-09 22:19:12 +08:00 via iPhone
    不知道您毫不谦虚的说"帮别人做笔试"的目的是什么,我总觉得还是低调点,你这本来就算不公平了,牛客拉黑会进企业黑名单的
    brainfxxk
        5
    brainfxxk  
       2019-08-09 22:20:39 +08:00
    没读懂这题 甚至看不懂样例
    brainfxxk
        6
    brainfxxk  
       2019-08-09 22:24:09 +08:00
    原来是没刷出第一张图
    b 相同的记录数不超过 300 按 b hash 之后随便做吧...
    whileFalse
        7
    whileFalse  
       2019-08-09 23:26:00 +08:00 via iPhone
    标题不是说凭记忆写出来的吗?
    感情 lz 的记忆还是 jpg 格式的。
    zjsxwc
        8
    zjsxwc  
       2019-08-09 23:39:40 +08:00 via Android
    阅读理解题, 这题就是模拟而已
    aijam
        9
    aijam  
       2019-08-10 07:36:24 +08:00   ❤️ 2
    我觉得出题的人,要不语文有问题,要不逻辑有问题。a_delta, c_x, c_y 都不带定义的,全靠审题的人通过零星的描述和例子意会。工作生活中挺讨厌这种人,思路和语言组织都是乱的。
    codechaser
        10
    codechaser  
    OP
       2019-08-10 10:22:52 +08:00
    @Hstar 这题我读就花了 15 分钟。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   896 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 20:25 · PVG 04:25 · LAX 12:25 · JFK 15:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.