跳至主要內容
  • Hostloc 空間訪問刷分
  • 售賣場
  • 廣告位
  • 賣站?

4563博客

全新的繁體中文 WordPress 網站
  • 首頁
  • 请教三道算法题 给个思路就行 谢谢
未分類
30 8 月 2020

请教三道算法题 给个思路就行 谢谢

请教三道算法题 给个思路就行 谢谢

資深大佬 : Newyorkcity 5

快递员问题

第一行有两个整数,用空格分开。第一个整数 k 表示快递员的电动车还能跑 k 公里,第二个整数 n 表示快递员还需要前往 n 个地方送货。 第二行为 n-1 个整数,用空格分开。第 i 个整数 I 表示编号为 i+1 的地方和编号为 I 的地方之间有一条长度一公里的路。

现在快递员从编号为 0 的地方出发,骑着电动车送货,问它最多能送多少地方?(快递员不必一定要回到编号 0 的地方)。

约会问题

第一行是多个用空格分开的整数,每个整数是一个男生的编号。
第二行是多个用空格分开的整数,每个整数是一个女生的编号。
编号是唯一的。
第三行只有一个整数 n,表明接下来还有多少行数据。
接下来每一行都只有两个用空格分开的整数,其中第一个整数是一个男生的编号,第二个整数是一个女生的编号。
出现在同一行表示这对男女都彼此都希望能进一步认识。但是同一天一个男生(女生)只能和一个女生(男生)约会。

现在由你来安排,则明天一天你最多能安排多少对男女约会?

例子:
1 2 3
4 5 6
6
1 4
1 5
2 6
2 4
3 4
3 6

则 1-5 2-6 3-4 是最佳安排,三场约会。如果 1-4 2-6 则 3 号男嘉宾无人约会。

字符串问题

给出一个字符串 s,要求给出字符串 s 中满足 ‘a’,’b’,’c’,’x’,’y’,’z’ 这六个字符各自出现的次数为偶数(零也为偶数)的最大子串的长度。

刚秋招做的题,这几道没什么思路。谢谢了。

大佬有話說 (6)

  • 資深大佬 : oahebky

    1. 图 BFS -> Dijkstra (题意没说明清楚,如果我没脑补错的话)

    2. 类似课程表问题,是一种算法,忘了叫什么,个人没学过。

    3. 不是很确定,但是感觉 [分治法+增强归纳假设] 可解。

  • 資深大佬 : zxCoder

    有数据范围吗?

  • 資深大佬 : zxCoder

    第三题我的思路是计算一下奇偶的前缀和,比如前缀 ab,那么 a 和 b 出现 1 次,奇数,其他出现 0 次,偶数,所以就是 110000,然后才 6 个字符所以压成一个数,然后计算出前缀和之后就从右到左枚举子串左端点,用 map 查询一下右边相同的这个数的最右的位置。

  • 資深大佬 : zxCoder

    第二题就是二分图最大匹配的问题吧

  • 資深大佬 : zxCoder

    第一题我咋看不太懂,如果有样例数据就好了

  • 資深大佬 : seasona

    第一题看不懂,大概率是 bfs 或者最短路径或者最小费用最大流中的一个
    第二题二分图最大匹配
    第三题 leetcode 原题 1371,前缀和+状态压缩

文章導覽

上一篇文章
下一篇文章

AD

其他操作

  • 登入
  • 訂閱網站內容的資訊提供
  • 訂閱留言的資訊提供
  • WordPress.org 台灣繁體中文

51la

4563博客

全新的繁體中文 WordPress 網站
返回頂端
本站採用 WordPress 建置 | 佈景主題採用 GretaThemes 所設計的 Memory
4563博客
  • Hostloc 空間訪問刷分
  • 售賣場
  • 廣告位
  • 賣站?
在這裡新增小工具