2011 年文章归档
共 3 篇文章
使用sort进行拓扑排序的比较函数
C++等语言自带的sort函数使用的排序算法基本都是快速排序,快速排序是一种不稳定的排序算法,也就是说两个相等的元素排序前后的相对位置是有可能变化的。在使用sort对一个有偏序关系的序列进行拓扑排序时,比较函数的设计要特别注意。例如我们对格点(x,y)进行排序,使得如果有x0 <= x1 而且 y0 <= y1时,(x0,y0)在(x1,y1)前面。 代码大致如下: const int N = 10; struct Node { int x, y; void init(int _x, int _y) { x = _x; y = _y; } }node[N * N]; bool cmp(con…
2011-09-29 20:16 · 常识
519_900
1. 数据小, 充分挖潜数据的特点 2. 该DP的DP, 该枚举的枚举 3. 注意将一些枚举简化成O(1)的式子: a[i] + a[i + 1] + ... + a[j] = sum[j] - sum[i - 1] import java.util.*; import java.util.regex.*; import java.text.*; import java.math.*; import java.awt.geom.*; public class VerySmoothDecompositions { public BigInteger [] BI = new BigInteger…
2011-09-20 16:06 · SRM
517_600
d[u][v] : 用v - u次交换把第u个至第v个变成升序的方法数 t[u][k][v] : 最后一次交换k, k + 1两个位置的数的方法数 可见, d[u][v] = sum{t[u][k][v] | k = u, .., v - 1} t[u][k][v] = zh[v - u - 1][k - u] * d[u][k] * d[k + 1][v] 两个状态相互推算!! 递归写法思路比较清晰. class AdjacentSwaps { public: int theCount(vector <int>); }; const int mod = 1000000007; const …
2011-09-15 20:51 · SRM