数据科学与大数据...吧 关注:1,682贴子:4,473
  • 3回复贴,共1
上周的周赛T2,T3有点绕脑没写出来


IP属地:广东来自Android客户端1楼2025-03-24 12:39回复
    方法:并查集+哈希
    暴力枚举所有 properties[i] 和 properties[j],如果交集为k直接用并查集合并 i 和 j,并continue。
    优化1:用哈希枚举。为防止不同整数重复加,哈希properties[i]在hash0,在查properties[j]时,用copy一下hash0为hash,当加过就hash【】=0
    优化2:先find(i),find(j),如果连通就continue


    IP属地:广东来自Android客户端2楼2025-03-24 12:40
    回复
      分析思路,先看数据范围,N为1~10**2则可以知道这道大概可以用三个for循环,题目要求是要返回最后有几个连通块,这里可知可以用dfs,bfs或并查集,连通条件check为两个数组有k个以上相同数字,且这k个互不相同,可用哈希来对比,并且该题为无向图,那么用并查集更优


      IP属地:广东来自Android客户端3楼2025-03-24 12:50
      回复


        IP属地:安徽来自Android客户端4楼2025-03-25 10:29
        回复