hihocoder.com Offer收割赛 #37

Presentation on theme: "hihocoder.com Offer收割赛 #37"— Presentation transcript:

1 hihocoder.com Offer收割赛 #37
2017 November 26 Offer收割赛 #37 程序员通过编程找工作的平台

2 Offer收割赛 #37 热门号码 字符串/哈希 三角形面积和 区间处理 最少换乘 最短路 完美命名的烦恼 拆点、欧拉路

3 热门号码 一个“字母”串𝑺对应的“数字”串𝑻，如下构造： 现在有𝑵个“字母”串 𝑺 𝟏 ~ 𝑺 𝑵 ，以及𝑴个“数字”串 𝑻 𝟏 ~ 𝑻 𝑵
题目描述 一个“字母”串𝑺对应的“数字”串𝑻，如下构造： 将𝑆中所有大写英文替换成手机键盘中对应的数字 𝐴𝐵𝐶⇒2,𝐷𝐸𝐹⇒3,…,𝑊𝑋𝑌𝑍⇒9 现在有𝑵个“字母”串 𝑺 𝟏 ~ 𝑺 𝑵 ，以及𝑴个“数字”串 𝑻 𝟏 ~ 𝑻 𝑵 询问对于每个“数字”串，有多少个“字母”串与其对应？ 𝑁,𝑀≤5∗ 10 4 , 𝑆 , 𝑇 ≤10

4 热门号码 样例解释 3 2 HIHO IGGO CODER 4446 26337

5 热门号码 对于 𝑺 𝟏 ~ 𝑺 𝑵 ，计算其对应的“数字” 𝑺 𝟏 ′ ~ 𝑺 𝑵 ′
基本思路 对于 𝑺 𝟏 ~ 𝑺 𝑵 ，计算其对应的“数字” 𝑺 𝟏 ′ ~ 𝑺 𝑵 ′ 统计 𝑺 𝟏 ′ ~ 𝑺 𝑵 ′ 中 𝑻 𝟏 ~ 𝑻 𝑵 的出现次数 对 𝑺 𝟏 ′ ~ 𝑺 𝑵 ′ 和 𝑻 𝟏 ~ 𝑻 𝑵 分别进行排序 4446,4446,26337 4446,26337 双指针统计 哈希表 − 𝑯𝒂𝒔𝒉 𝑺 根据哈希值进行统计与查询（桶排序）

6 三角形面积和 𝑵个等腰直角三角形 询问覆盖的面积之和 𝑵≤𝟏 𝟎 𝟓 ,𝟎≤𝑿,𝒀≤𝟏 𝟎 𝟓 斜边均与𝑋轴重合
题目描述 𝑵个等腰直角三角形 斜边均与𝑋轴重合 顶点坐标为 𝑋 𝑖 , 𝑌 𝑖 询问覆盖的面积之和 𝑵≤𝟏 𝟎 𝟓 ,𝟎≤𝑿,𝒀≤𝟏 𝟎 𝟓 (11,5) (4,4) /\ /\(7,3) \ / \/\/ \ / /\/\ \ / / /\ \ \ >

7 三角形面积和 容斥原理 𝑆=16+9+25−4−4−1+1=42 𝑆 1 =4∗4=16 𝑆 2 =3∗3=9 𝑆 3 =5∗5=25
样例解释 容斥原理 𝑆 1 =4∗4=16 𝑆 2 =3∗3=9 𝑆 3 =5∗5=25 𝑆 12 =2∗2=4 𝑆 23 =2∗2=4 𝑆 13 =1∗1=1 𝑆 123 =1∗1=1 𝑆= −4−4−1+1=42 (11,5) (4,4) /\ /\(7,3) \ / \/\/ \ / /\/\ \ / / /\ \ \ >

8 三角形面积和 容斥原理 𝑂 2 𝑁 优化 被完全覆盖的三角形不用进行考虑 考虑剩下的三角形 如果区间完全不相交——直接算三角形面积
基本思路 容斥原理 𝑂 2 𝑁 优化 被完全覆盖的三角形不用进行考虑 考虑剩下的三角形 如果用区间 𝐿 𝑖 , 𝑅 𝑖 表示其在𝑋轴上的斜边 则这些区间是不会相互包含的 如果区间完全不相交——直接算三角形面积 如果区间相交？ (11,5) (4,4) /\ /\(7,3) \ / \/\/ \ / /\/\ \ / / /\ \ \ >

9 三角形面积和 将三角形按照区间左端点排序 依次考虑每一个三角形 𝑳 𝒊 , 𝑹 𝒊
优化思路 (11,5) (4,4) /\ /\(7,3) \ / \/\/ \ / /\/\ \ / / /\ \ \ > 将三角形按照区间左端点排序 𝐿 𝑖 < 𝐿 𝑖+1 ⇒ 𝑅 𝑖 < 𝑅 𝑖+1 依次考虑每一个三角形 𝑳 𝒊 , 𝑹 𝒊 如果已经计算出1~ 𝑖−1 的所有三角形的面积 如何计算第𝑖个三角形“多”出来的面积？ 只需要考虑第𝑖−1个三角形 如果与第𝑖−1个三角形不相交—— 𝑅 𝑖 − 𝐿 𝑖 如果与第𝑖−1个三角形相交—— 𝑅 𝑖 − 𝐿 𝑖 − 𝑅 𝑖−1 − 𝐿 𝑖 𝐿 𝑖 𝑅 𝑖−1 𝑅 𝑖

10 三角形面积和 具体实现 注意总面积需要使用64位整型存储 将区间按左端点从小到大，右端点从大到小排序 维护右端点的最大值 𝑅 𝑚𝑎𝑥
优化思路 具体实现 将区间按左端点从小到大，右端点从大到小排序 维护右端点的最大值 𝑅 𝑚𝑎𝑥 𝑅 𝑖 ≤ 𝑅 𝑚𝑎𝑥 ⇒不作处理 𝐿 𝑖 ≥ 𝑅 𝑚𝑎𝑥 ⇒𝐴𝑛𝑠=𝐴𝑛𝑠+ 𝑅 𝑖 − 𝐿 𝑖 𝐿 𝑖 < 𝑅 𝑚𝑎𝑥 ⇒ 𝑅 𝑖 − 𝐿 𝑖 − 𝑅 𝑚𝑎𝑥 − 𝐿 𝑖 注意总面积需要使用64位整型存储 𝐿 𝑖 𝑅 𝑚𝑎𝑥 𝑅 𝑖

11 最少换乘 𝑁条公交线路 第𝑖条公交线路有 𝐾 𝑖 个车站 询问从车站𝑆到车站𝐸至少需要换乘多少次公交车？ 𝑁≤5∗ 10 4 ,𝐾≤100
题目描述 𝑁条公交线路 第𝑖条公交线路有 𝐾 𝑖 个车站 询问从车站𝑆到车站𝐸至少需要换乘多少次公交车？ 𝑁≤5∗ 10 4 ,𝐾≤100

12 最少换乘 题目描述 123→222→345

13 最少换乘 最短路 困难之处 𝑓 𝑖 表示抵达车站𝑖至少需要的换乘次数 𝑓 𝑖 = min (𝑓 𝑗 +1,𝑗和𝑖在同一条路线中) 𝑂 𝑁 2
基本思路 最短路 𝑓 𝑖 表示抵达车站𝑖至少需要的换乘次数 𝑓 𝑖 = min (𝑓 𝑗 +1,𝑗和𝑖在同一条路线中) 𝑂 𝑁 2 困难之处 在建图的过程中 如果点为车站，则边的数量可能达到𝑂 𝑁 𝐾 2 级别 如果点为线路，边的数量也可能达到𝑂 𝑁 2 级别 不妨将车站和线路均建成点

14 最少换乘 二分图 最短路 具体实现 连边表示该车站在该线路中 边数为 𝐾 𝑖 从车站𝑆到车站𝐸的最短路 换乘次数= 𝑙𝑒𝑛𝑔𝑡ℎ 2 −1
321 优化思路 375 二分图 连边表示该车站在该线路中 边数为 𝐾 𝑖 最短路 从车站𝑆到车站𝐸的最短路 换乘次数= 𝑙𝑒𝑛𝑔𝑡ℎ 2 −1 具体实现 1~𝑁, 𝑁+1 ~ 𝑁+5∗ 10 4 123 1 456 2 222 333 3 444 345

15 完美命名的烦恼 𝑵个长度相同的单词 𝑾 𝟏~𝑵 构造一个长度为𝑵+𝑳−𝟏的字符串 𝑵≤𝟓∗𝟏 𝟎 𝟒 ,𝑳≤𝟏𝟎 互不相同 长度为𝐿
题目描述 𝑵个长度相同的单词 𝑾 𝟏~𝑵 互不相同 长度为𝐿 构造一个长度为𝑵+𝑳−𝟏的字符串 其每一个长度为𝐿的子串组成的集合与 𝑊 1~𝑁 等价 𝑵≤𝟓∗𝟏 𝟎 𝟒 ,𝑳≤𝟏𝟎

16 完美命名的烦恼 题目描述 ate cat tea ⇒𝑐𝑎𝑡𝑒𝑎

17 完美命名的烦恼 搜索 平方级的边数 预处理两个单词之间能否“邻接” 判断是否存在一条哈密尔顿路 指数级复杂度
基本思路 搜索 预处理两个单词之间能否“邻接” 𝑊 𝑖 1…𝑙−2 =𝑊 𝑗 0…𝑙−1 ? 判断是否存在一条哈密尔顿路 从某个点出发经过所有点正好一次 指数级复杂度 平方级的边数 如果 𝑖 1 ⇒ 𝑗 1 , 𝑖 1 ⇒ 𝑗 2 , 𝑖 2 ⇒ 𝑗 2 𝑐𝑎𝑡→𝑎𝑡𝑒,𝑐𝑎𝑡⇒𝑎𝑡𝑚,𝑒𝑎𝑡⇒𝑎𝑡𝑚 那么就有 𝑖 2 ⇒ 𝑗 1 𝑒𝑎𝑡→𝑎𝑡𝑒

18 完美命名的烦恼 拆点 哈密尔顿路⇒欧拉路 将一个长度为𝑙的单词拆分成 边数从𝑛𝑚⇒𝑛+𝑚 原图中的点变成新图中的边 连通图（并查集）
优化思路 𝑒𝑎 𝑡𝑚 拆点 将一个长度为𝑙的单词拆分成 其长度为𝑙−1的前缀 其长度为𝑙−1的后缀 边数从𝑛𝑚⇒𝑛+𝑚 哈密尔顿路⇒欧拉路 原图中的点变成新图中的边 连通图（并查集） 至多存在一个点入度大于出度（且仅大1） 至多存在一个点出度小于入度（且仅小1） 方案构造：欧拉路·三 𝑎𝑡 𝑐𝑎 𝑡𝑒 𝑎𝑡 𝑐𝑎 𝑡𝑒 𝑒𝑎

19 提问时间