最近周赛的压轴题都是dp，总结一下

trie树，又称单词查找树，前缀树，字典树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计，自动补全等。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

哎 每次都只能做出来前前前前面三道，左后一道永远卡住，永远排名几百

leetcode 55 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。

• 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  一个空字符串也被视为有效字符串。
  字符串大小将在 [1，100] 范围内。
  阅读全文 »

Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

• 禁止一名参议员的权利：
  参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。

• 宣布胜利：
  如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

  阅读全文 »

给定两条线段（表示为起点$start = {X1, Y1}$和终点 $end = {X2, Y2}$ ），如果它们有交点，请计算其交点，没有交点则返回空值。

要求浮点型误差不超过$10^{-6}$。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：

postTweet(userId, tweetId): 创建一条新的推文
getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
follow(followerId, followeeId): 关注一个用户
unfollow(followerId, followeeId): 取消关注一个用户

完全背包问题的模型如下：
有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。每件物品只能用一次。体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

有 N 种物品和一个容量是 V 的背包。
物品一共有三类：

1. 第一类物品只能用1次(s<0时)（01背包）；
2. 第二类物品可以用无限次(s=0时)（完全背包）；
3. 第三类物品最多只能用 $s_i$ 次(s>0时)（多重背包）；
   每种体积是 $v_i$，价值是 $w_i$。

• 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
  输出最大价值。
  阅读全文 »