我一万年也不更新一次博客

sgu 270-280

• sgu270
  分类讨论，考虑各种各样的情况
• sgu271
  简单的splay翻转
• sgu272
  题目只需要找出任意一种合法方案，那么一遍一遍dfs直到dfs不动了就行了
• sgu273
  题意是给你一个由b,r,w,y组成的串，并且给定若干个规则，每个规则的意思是相邻的两个字母可以合并成另一个字母，问这个串最终能合并成哪几个字母。
  DP。(f[i][j][c])表示能否把子串([i,j])变成字符c。
• sgu274
  按题意模拟
• sgu275
  n个数里选k个，使得异或和最大
  逐位处理，尽可能让高位的异或和为1。
  补个链接：http://dtyfc.com/acm/962
• sgu276
  弱智题
• sgu277
  动态凸包
• sgu278
  每种原料有两种代价属性A、B和一个价值属性C，每种原料可以取任意量（可以非整数），问不超过两种代价上限的情况下C的最大值。
  首先因为可以取任意非整数量，所以三个属性可以规约为两个。可以计算出一个单位C对应的A和B。
  然后如果把A和B看做点((A,B))，那么平面上n个点中只有凸包边上的点有可以选择的价值。因为对于凸包里面的点肯定存在凸包边上点两种属性都比它更优。
  接下来，因为我们需要C的和最大，每种原料又可以去任意量，所以最终的选取方案中，A和B的比值一定等于A和B上限的比值。而且我们只需要最多两种原料调和比例就可以了。所以我们取线段((0,0))到((A_{max},B_{max}))，这条线段和凸包的交点就是我们要求的答案了。
• sgu279
  贪心
• sgu280
  按照一个什么规则贪心？（我没想明白）

CF && BC

• CF#296 B
  问题等价于有一堆线段，选取最多的一堆线段使得任意两个线段都不相交。
  按照线段右端点排序，能加入当前这条线段就加入，否则就不加入。
  因为如果你非要把当前这个加不进来的线段加进来，那么你就必须去掉之前选过的至少一条线段，还会造成已选择区间的右端点右移，这显然是不合适的。
• BC#33 C
  (2^{30})枚举不了的时候可以考虑分别枚举两个(2^{15})，并且用贪心把这两个连起来。