发表于 | 分类于 | | + s

poj 3581

  1. 因为第一个数比后面的大，所以将原串翻转后找出排第$i$位的后缀输出，符合$SA[i]>=2$的最小$i$(后缀数组中的排列是字典序)
  2. 之后将之前已经处理的数据删掉，然后题目变为将剩下的数据分为两份翻转后字典序最小，那么我们设$S$为这个序列，$S_1, S_2, …, S_k, S_{k+1},…S_n$，其中$k$是分割点，处理后变为$S_k, S_{k-1}, …, S_1, S_n, S_{n-1},…,S_{k+1}$，我们发现这个序列是$S_n, S_{n-1}, …, S_1, S_n, S_{n-1},…,S_{1}$的子串，那么我们将翻转后的数列复制一份放在后面，然后找出排第$i$位的后缀输出，符合$SA[i]>=1, SA[i]∈第一部分$的最小$i$输出。(后缀数组中的排列是字典序，设法构造一个串，使得欲求串的字典序能够求出)
  3. 输出剩余的数据，即可完成
    阅读全文 »

发表于 | 分类于 | | + s

poj 3648
1、注意2-SAT的定义(例如此题定义坐不坐新郎这边比坐不坐新娘这边更好解题)
2、取了和题目不同定义时，记得反一下

阅读全文 »

发表于 | 分类于 | | + s

poj 3678

1、加边a->b 代表选了a的话b也得选
例如 x->x` 表示选了x就必须选x` ，所以这个值必为x
2、最好2*a表示True，2*a+1表示FLASE

阅读全文 »

发表于 | 分类于 | | + s

poj 3683
1、区间重合的判定
2、想要输出数最少两位可以用”%.2d”输出
例如数是8，但想输出08，就可以用，如果是14，则还是输出14

阅读全文 »

发表于 | 分类于 | | + s

poj 3728

维护6个数组
pre[i][j] i的第2^j个祖先
deep[i] i的深度
up[i][j] i到i的第2^j个祖先的最优解
down[i][j] i的第2^j个祖先到i的最优解
dmax[i][j] i到i的第2^j个祖先路径上的最大值
dmin[i][j] i到i的第2^j个祖先路径上的最小值
然后可以通过倍增维护以上数组，期中包含一些dp思想，此题非常好，作为一个LCA的跳板

阅读全文 »