博文
string流(2006-08-17 20:51:00)
摘要： ostringstream类向一个string插入字符，istringstream类从一个string对象读取字符，而stringstream类可以用来支持读和写两种操作。为了使用string流,我们必须包含相关的头文件： #include <sstream> 例如， string read_file_into_string() { ifstream ifile( "alice_emma" ); ostringstream buf; char ch; while(buf && ifile.get( ch )) buf.put( ch ); return buf.str(); } 成员函数str()返回与ostringstream类对象相关联的string对象。 istringstream由一个string对象构造而来，它可以读取该string对象。istringstream的一种用法是将数值字符串转换成算术值。
---摘抄自《C++PRIME》.......
最小生成树(2006-08-17 15:23:00)
摘要：public static void prim(int n,float [][]c){ float []lowcost = new float[n+1]; int []closest = new int[n+1]; boolean []s = new boolen[n+1]; s[1] = true; for (int i = 2; i <= n; i++) { lowcost = c[1][i]; closest[i] = 1; s[i] = false; } for (int i=1; i < n; i++) { float min = Float.MAX_VALUE; int j = i; for (int k = 2; k <= n; k++) { &n......
随机排序算法(2006-08-07 16:01:00)
摘要：void InterChange(int a[],int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
int partition(int a[],int p,int q)
{
int v = a[p],i = p,j = q;
do{
do i++;
while (a[i] < v);
do j--;
while (a[j] > v);
if (i < j)InterChange(a,i,j);
}while (i < j);
a[m] = a[j];a[j] = v;
return j;
}
void RQuickSort(int a[],int p,int q)
{
if (p < q)
{
if (q-p > 5)InterChange(a,rand()%(q-p)+p,p);
int j = partition(a,p,q);
RQuickSort(p,j);
RQuickSort(j,q);
}
}
PS：随机排序算法的时间复杂度也是O(nlogn),但算法的平均性能是很好的。在解POJ1186题时，用分治＋二分查找算法，要用到排序，排序的对象最多有33万个，如果用qsort或sort可能会超时，但我用上面的RQuickSort就AC了。由此可见，当对象数目很多时，RQuickSort的性能要比qsort,sort要好。......
“死了都要编”--改篇自信乐团"死了都要爱"（转）(2006-07-28 14:58:00)
摘要：死了都要编不动态规划不痛快算法多深只有这样才足够表白死了都要编不A星算法不痛快宇宙毁灭星还在把每天当成是比赛来编程一分一秒都编到汗水掉下来不理会别人是搜索或贪心只要你勇敢跟我编编不用刻意安排凭感觉去编程提交就会很愉快享受现在别一提交就怕WRONG ANSWER许多奇迹我们相信才会存在死了都要编不用后缀树不痛快算法多深只有这样才足够表白死了都要编不遗传算法不痛快宇宙毁灭基因还在穷途末路都要编不升起气球不痛快超时会TIME出错会RUN空间不会MEM到绝路都要编不AC题目不痛快不怕机房变火海编到沸腾才精采......
POJ2800，Joseph's Problem解题报告(2006-07-28 14:48:00)
摘要： 题目很简单，你的解答也很简单：
int calc(int n,int k){
int ret = 0,i;
for (i = 1; i <= n; i++)ret += k%i;
return ret;}
可是，它怎么就超时了呢？
注意约束条件：
The input file contains n and k(1<= n,k <= 10^9).
n的最大值是10^9。。。。你的程序不超时才怪呢？
O(n)的算法，还能怎么优化呢？
对给定的K，所求为不大于n的所有正整数除K的余数r1,r2,......,rn的总和。假设它们对应的商为s1,s2,.....,sn.
注意到，商的可能取值只有O(sqrt(n))种情况，对每个可能的商的值，k%i成等差数列。容易看出，此问题的解的时间复杂度不大于O(sqrt(n)).
分析，解决问题
对N，K比较小的情况，写出具体的余数和商数表。
观察，分析这个表格。
现在，你能否为本问题设计出复杂度为O(sqrt(n))的算法？......
STL算法学习(七)(2006-07-28 14:37:00)
摘要：/*find_end: 函数原型： template <class FdwIt1,class FdwIt2> FdwIt1 find_end(FdwIt1 first1,FdwIt1 last,FdwIt2 first2,FdwIt2 last2); template <class FdwIt1,class FdwIt2,class Pred> FdwIt1 find_end(FdwIt1 first1,FdwIt1 last,FdwIt2 first2,FdwIt2 last2, Pred pr); 功能：在由[first1,last1)标记的序列中查找“由iteratior对[first2,last2)标记 的第二个序列”的最后一次出现。例如，已知亭子符序列mississippi和第二 个序列ss，则find_end()返回一个FwdIt1指向第二个ss序列的第一个s。如果 &nbs......
C++学习笔记·输入输出(4)(转)(2006-07-27 19:59:00)
摘要：四、格式化输入输出 C++语言中有两种方法可以控制格式化输入输出：流对象的成员函数和操纵器。 <1> 流对象的成员函数 下表中的格式化标志，可以通过成员函数setf()来设置，也可以用unsetf()来复位，如果需要设置多个标志，可以使用 | 运算符(使用标志时前边加上ios::)。───────┬───────────────────────┬──── 格式化标志 │ 描 述 │ 默 认───────┼───────────────────────┼──── boolalpha │ 以alpha格式进行布尔输入输出 │ off showbase │ 显示8进制或16进制前缀 │ off showpoint │ 显示10进制浮点数末尾的零 &n......
STL算法学习(六)(2006-07-27 00:26:00)
摘要：/*fill: 函数原型： template <class FwdIt,class T> void fill(FwdIt first,FwdIt last,const T& value); 功能：将value拷贝到区间[first,last)中的每一个元素。
fill_n: 函数原型： template <class FwdIt,class Size,class T> void fill_n(FwdIt first,Size n,const T& value); 功能：将value拷贝到从first开始的n个元素上。 find: 函数原型： template <class InputIterator,class T> InputIterator find(InputIterator first,InputIterator last,const T&......
STL算法学习(五)(2006-07-24 17:37:00)
摘要：/*equal: 函数原型： template <class InputIterator1,class InputIterator2> bool equal(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2); template <class InputIterator1,class InputIterator2 class Predicate> bool equal(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2, Predicate pred); 功能： 第一个版本将序列[first1,la......
STL算法学习(四)(2006-07-22 16:51:00)
摘要：/*count: 函数原型： template <class InputIterator,class Type> typename iterator_traits<InputIterator>::difference_type count(InputIterator first,InpurIterator last,const Type& value); 功能： 在序列[first,last)中查找和value相等的元素个数，统计其个数，返回其值。
count_if: 函数原型: template <class InputIterator,class Predicate> typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first,InputIterator last,Predicate pred); 功能： 在序列[first,last)中统计满足关系pred的元素个数，并返回其值。......