2013年9月5日

总结

连通性判断

分析

题目很长,但是意思很简单。首先要做 data consistancy 的检查。
  1. 如果 a 在 b 前面,但是 b 不在 a 后面,那么就是有问题的数据
  2. 如果不连通,数据也是有问题的
数据没有问题之后,一次 DFS 就可以找到各个方向上的最长长度,比如设起始点的坐标为 (0,0,0,0)。

posted @ 2013-09-04 21:50 happyac 阅读(295) | 评论 (0)编辑 收藏

总结

从最后一位开始判断

分析

  1. 如果$n$是偶数,那么最后一位一定是0。
  2. 如果是奇数,那么最后一位一定是1。如果对应的比特位为正,那么$n \leftarrow (n-1) / 2$,否则 $n \leftarrow (n +1) / 2$。

posted @ 2013-09-04 21:46 happyac 阅读(1209) | 评论 (0)编辑 收藏

总结

就是连通性和图的同构判断。

分析

找出属于同一组的点很简单,DFS就可以搞定。图的同构可以用图的Hash来判断。这个不是我想出来的,是网上看来的:
$\sum\nolimits_{i,]} distance(p_i, p_j)$
即同一组中所有点的距离加起来,这个数值做为这个图的哈希值。我不知道如何去证明,但是目前我没找到反例。至少这个题可以用。如果有同学可以帮证明可以或是不可以,那就多谢了。

posted @ 2013-09-04 21:36 happyac 阅读(1450) | 评论 (0)编辑 收藏

2013年8月30日

总结

搜索问题。

分析

设:
  1. $c_i$ 表示第$i$行最后一个被添的列,即第$i$行第$c_{i+1}$列以后是空的,以前都已经被添满
  2. $p_i$ 表示边长为$i$的蛋糕的数量
基本想法如下:每次搜索都找到最短的那一行,然后试着添上蛋糕,如果不能添了就返回false。如果可以,那么就更新$c_i$和$p_i$继续搜索。 有人说直接暴搜也可以过。

posted @ 2013-08-29 15:19 happyac 阅读(1040) | 评论 (0)编辑 收藏

2013年8月28日

总结

简单但是有点绕。

分析

根据题意,基本的想法就是找到$S_k$,然后在$S_k$中找相应的数字。很多算法和实现都会有溢出的问题。

陷阱

如果一直WA,可能是溢出问题。将int换成long long试试。

posted @ 2013-08-27 18:29 happyac 阅读(188) | 评论 (0)编辑 收藏

总结

枚举即可

分析

  1. 找到所有最小带宽中最小的,$ b_0 $
  2. 找到所有最大带宽中最小的,$ b_1 $
  3. 计算在以上范围内所有可能的结果,选最大的输出即可
这个是最笨的方法,可以通过,但是有0ms就可以AC的算法。我还没想出来。

posted @ 2013-08-27 18:25 happyac 阅读(149) | 评论 (0)编辑 收藏

总结

简单的模拟问题。

posted @ 2013-08-27 18:22 happyac 阅读(199) | 评论 (0)编辑 收藏

2013年8月24日

总结

简单模拟

陷阱

边缘数据,70在15次进入长度为2的循环,而80在第16次进入长度为2的循环,按题目来说,80是"can not be cassified"。

posted @ 2013-08-23 13:51 happyac 阅读(138) | 评论 (0)编辑 收藏

2013年8月22日

总结

动态规划问题

分析

目标是从$n$个人中选出$m$个人,使得:
  1. $|D-P|$最小
  2. 如果最小不唯一,选$D+P$最大一组
设$s[i][j][k]$保存从$i$个人中选$j$个人的所有状态,那么根据第$i$个人选不选即可列出状态转移方程。

陷阱

状态数组的維数是可以减少的,可以将每一维去掉,但是需要有额外的操作:
  • 考虑第$i$个人选不选时,还需要考虑这个人是否已经被选择
  • 要将结果按人的先后次序排序

posted @ 2013-08-21 14:09 happyac 阅读(1340) | 评论 (0)编辑 收藏

2013年7月2日

總結

  1. 方法1:視爲多重揹包問題。請見dd牛揹包問題九講
  2. 方法2: 对于任意一种珠宝的个数n,如果n>=8, 可以将n改写为 11(n为奇数) 或 12(n为偶数)。証明

陷阱

不要將 "divided" 錯寫爲 "devided",3 次 WA 都是因爲這個。

posted @ 2013-07-01 23:24 happyac 阅读(1304) | 评论 (0)编辑 收藏