Archive for March, 2009

C++简明基础教程 – 结语

Tuesday, March 31st, 2009

零零散散地写了七篇教程,本想再好好写一篇结语的,可是这两天突然发烧了,也没啥精力写了,只好这样了……

教程可能分布得比较散,所以有了新的Category,可以直接从那里浏览到所有教程,但是突然发现因为使用了<pre>标签的原因,代码显示出来太难看了……好吧,在这里重新把教程的所有链接贴出来:

C++简明基础教程 – 第一篇 Dev-C++安装与配置

C++简明基础教程 – 第二篇 编程语言学习引论

C++简明基础教程 – 第三篇 C++ in a Nutshell(代码部分)

C++简明基础教程 – 第三篇 C++ in a Nutshell(测试用例部分)

C++简明基础教程 – 第三篇 C++ in a Nutshell(解释部分)

C++简明基础教程 – 第四篇 STL In A Nutshell

C++简明基础教程 – 第五篇 面向对象设计

C++简明基础教程 – 第六篇 C++ and Its World

C++简明基础教程 – 第七篇 补充代码部分

顺便在这里说一句,不要试图用“教程”标签找到所有教程,因为真的有几篇我忘了打这个标签了,也不想改了……

还有,把原来写的第一篇关于Dev-C++安装的内容放出来吧,其实是很多张截图而已。俗话说,授之以鱼,不如授之以渔,还是把详细的手工操作的流程拿出来给大家看比较好。(点击这里获取截图压缩包)

最后,为了证明我的身份,在这里写这么一行字。太囧了~我真是挂线的!

C++简明基础教程 – 第七篇 补充代码部分

Saturday, March 28th, 2009

这是本系列教程的最后一篇内容了(还会有一篇结语)。为了让读者对C++有一个更直接的认识,我编写了几段很小很精炼的程序,当做是对第三篇中使用到的关键字的补充内容吧。多看看这些代码,多动手自己写一些东西,把C++当做一门语言,像学英语一样来学,不久之后你就会提高很多的。

// hello.cpp
// print message "Hello World"

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
    cout << "Hello World" << endl;
    return 0;
}

// sort.cpp
// input n integers, sort and print

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; ++ i)
        cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; ++ i)
        cout << a[i] << ' ';
    delete[] a;
    return 0;
}

// reverse.cpp
// input a string, print the reversed

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    getline(cin, s);
    int i = s.length();
    while (i)
        cout << s[--i];
    return 0;
}

// file.cpp
// read a file, print all the content

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main(int argc, char* argv[])
{   // usage: file <FIlENAME>
    if (argc != 2) return -1; // error
    ifstream fin(argv[1]);
    string line;
    while (fin.good() && !fin.eof())
    {
        getline(fin, line);
        cout << line << endl;
    }
    fin.close();
    return 0;
}

// copy.cpp
// copy from one file to another

#include <fstream>
#include <string>
using namespace std;

int main(int argc, char* argv[])
{   // usage: file <SOUR> <DEST>
    if (argc != 3) return -1; // error
    ifstream fin(argv[1]);
    ofstream fout(argv[2]);
    string line;
    while (fin.good() && !fin.eof())
    {
        getline(fin, line);
        fout << line << endl;
    }
    fout.close();
    fin.close();
    return 0;
}

// calc.cpp
// a simple calculator

#include <iostream>
using namespace std;

int main()
{
    double a, b;
    char c;
    cin >> a >> c >> b;
    if (c == '+')
        cout << a + b << endl;
    else if (c == '-')
        cout << a - b << endl;
    else if (c == '*')
        cout << a * b << endl;
    else if (c == '/')
        cout << a / b << endl;
    else
        cout << "ONLY + - * /" << endl;
    return 0;
}

// mul9x9.cpp
// print out the famous table...

#include <iostream>
using namespace std;

int main()
{
    cout << '\t';
    for (int j = 1; j <= 9; ++ j)
        cout << '\t' << j;
    cout << endl;
    for (int i = 1; i <= 9; ++ i)
    {
        cout << i;
        for (int j = 1; j <= 9; ++ j)
            cout << '\t' << i*j;
        cout << endl;
    }
    return 0;
}

// guess.cpp
// a simple guessing game

#include <iostream>
using namespace std;

int main()
{
    int ans = rand()%100;
    int n;
    do
    {
        cin >> n;
        if (n > ans)
            cout << "too high" << endl;
        else if (n < ans)
            cout << "too low" << endl;
        else
            cout << "right on" << endl;
    }
    while (n != ans);
    return 0;
}


Fix@2009.4.5: 增加一个筛法求素数的例子。
#include <iostream>
#include <vector>
using namespace std;

int main()
{   // pre  : n >= 1
    // post : print all prime numbers
    //          less than n
    int n;
    cin >> n;
    // first, assume all the numbers
    //  are prime numbers
    vector<bool> b(n, true);
    // then, choose a number i >= 2,
    //  multiply j >= 2, get i*j,
    //  so i*j is a composite number
    for (int i = 2; i < n; ++ i)
        for (int j = 2; i*j < n; ++ j)
            b[i*j] = false;
    // finally, we print them out
    for (int i = 2; i < n; ++ i)
        if (b[i]) cout << i << ' ';
    return 0;
}


C++简明基础教程 – 第六篇 C++ and Its World

Friday, March 27th, 2009

本篇对C++世界的关键之处作以补充,便于初学者对C++有一个直观的了解,可以作为第三篇的参考材料。

每个C++ 程序通常分为两个文件。一个文件用于保存程序的声明(declaration),称为头文件。另一个文件用于保存程序的实现(implementation),称为定义(definition)文件。C++程序的头文件以“.h”为后缀,C++程序的定义文件通常以“.cpp”为后缀(也有一些系统以“.cc”或“.cxx”为后缀)。头文件主要包括一些预编译命令以及函数、类结构的声明等。定义文件则包含了对一些头文件的引用,还有程序的实现体(包括数据和代码)。

头文件(header)的作用大致有两点:(1)通过头文件来调用库功能。某些情况下源代码不向用户公布,只要提供编译后的二进制库文件和相应的头文件即可,用户按照头文件中对接口的声明来使用库,编译器会从库中提取相应的代码(二进制)。(2)头文件能加强类型安全检查。如果某个接口被实现或被使用时,其方式与头文件中的声明不一致,编译器就会指出错误,这一简单的规则能大大减轻程序员调试、改错的负担。

C++中的运算符有数十个,清楚它们的优先级与结合律对编写逻辑复杂的代码至关重要(当然,过于复杂的表达式逻辑,强烈建议适当地使用括号,以增强代码的可读性)。下表简要说明了各运算符的优先级与结合律。

优先级 运算符 结合律





( ) [ ] -> . 从左至右
! ~ ++ — (类型) sizeof
+ – * &
从右至左
* / % 从左至右
+ - 从左至右
<< >> 从左至右
< <= > >= 从左至右
== != 从左至右
& 从左至右
^ 从左至右
| 从左至右
&& 从左至右
|| 从右至左
?: 从右至左
= += -= *= /= %= &= ^=
|= <<= >>=
从左至右

if语句是C++中最常用也最简单的语句,需要注意的有:(1)else子句是可选的;(2)多级if的排版要注意美观以防止发生错误;(3)在不过于冗余的情况下尽量多地使用花括号,以保证代码结构严谨;(4)if的条件是与零比较,非零的值都表示条件成立。

for语句在越专业的C++代码中出现的频率就越高,因为它极为灵活。对于初学者最需要注意的就是,for的括号中声明的变量在for语句之外是不可用的。比如“for(int i = 1; i <= 10; ++ i) { cout << i << endl; }”将打印出1~10的值,此后i就“消失”了,再写比如“cout << i << endl;”就是错误的了。

上一段的论述是片面的,下面考虑真正的带有“域”的情况。C++中一个域(scope)就是由花括号包围起来的一个相对独立的代码区间(当然也包含省略了花括号的单条语句)。变量作用范围对应着相应的域,即变量作用域,其核心概括起来有三点:(1)同一域内声明的变量对于声明语句之后的语句可用;(2)上级域中声明的变量对下级域(子域)可用,而反之则不可用(作用域终止);(3)下级域(子域)内声明的变量会覆盖上级域中的同名变量,但域终止后不会对以后有影响。

常量的定义与声明是在一起的(或者说声明的同时就初始化),使用像“const float PI = 3.14;”的格式声明常量。不要使用C语言中遗留下来的#define预编译命令来定义所谓的常量,因为它只是简单地进行格式替换,并不包含语法信息,编译器也不会报告潜在的语义错误。同样,简短的方法应使用inline内联定义,而不是#define。

C++函数参数可以按值传递(pass by value),也可以按引用传递(pass by reference)。引用(reference)是C++中很重要的一个概念,与之紧密相关的指针则是C++深入学习的重头戏。我们在这里简单地看一下引用的一个应用:“void swap(int &a, int &b) { int t = a; a = b; b = t; }”。这个swap()函数用来交换两个int的值,可以这样使用:“int x = 1, y = 2; swap(x, y);”。上面的语句执行完后,x的值变为2而y的值变为1。而如果把swap()声明部分的“&”符号去掉,则对传入的值并没有影响。

回顾我们最开始的“Hello World”程序(注:在这个版本的教程中这个入门示例从第一篇砍掉了,我会在本教程的结束篇把最初版本的关于环境配置的图片打包发布,其中就包含了这个程序):

#include <iostream>
using namespace std;
int main()
{
    cout << "Hello World!" << endl;
    return 0;
}

这段代码将打印出一行“Hello World!”字样。我们称“”Hello World!””为字符串字面量(string literal)。字符串,顾名思义,就是一串字符,用来显示一些数字之外的有意义的信息。从C到C++,字符串一直没有被很好地支持:C中没有原生的字符串,使用字符(char)数组来表示“串”;C++中有了STL实现的string,大多数情况下可以当做原生的类型使用,但与C字符数组等的关系又很复杂,其间涉及到非常关键的指针的内容。所以,关于字符串,真正在基础范围内的东西很少,几乎也只有一个字面量而已;如果把字符串“基础”化了,必然会使读者入了歧途,所以希望读者可以自己参考相关的权威书籍(本篇末尾会推荐)。

那么,如果不展开去讲字符串,回顾这个“Hello World”干嘛呢?其实是让你真正看看C++世界与现实世界边缘的一些东西。考虑下面的代码:

#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
    cout << "argc = " << argc << endl;
    for (int i = 0; i < argc; ++ i)
        cout << "argv[" << i << "] = " << argv[i] << endl;
    return 0;
}

亲自从命令行运行上面的代码。比如存盘为cpptut6.cpp,编译后为cpptut6.exe,在命令行下输入“cpptut6 blabla hahaha”,观察输出结果。更换命令行参数多试几次,体会一下主函数main()的这种声明格式的作用。

好了,这篇差不多也应该结束了。有朋友说教程太过“简”,根本没学明白。那么我就在这里推荐一些书籍留作后续的学习。在看这些书籍之前,保证你看过本教程两遍以上(我指有不同体验的两遍),才有提升的效果。注意,第六篇不是最后一篇,还有第七遍,不过那将是关于C++的一些代码例子,让你更加深入熟悉C++的,所以本篇是最后一篇说明性的文字了。嗯,不啰嗦了,列出推荐书籍如下:

  • The C++ Programming Language —— C++发明者编写的书籍
  • Professional C++ —— 精通C++的首选
  • The C++ Standard Library —— 关于库的使用(我在第四篇发过了)
  • C++ Primer —— 很厚,如果以上三本书实在不愿意看,看Primer吧

(本篇完;做人要厚道,转载请注明出处)

2018 — Best Cow Fences

Tuesday, March 24th, 2009

这道题我就不多说了,周源在集训队论文里讲的很明白了,重点就是数形结合,只贴一下代码吧,具体的请看论文

// 1060K 719MS
#include <iostream>
using namespace std;
int n, f, a[100001], s[100001];
int main()
{
    cin >> n >> f;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        s[i] = a[i] + s[i-1];
    }
    int ans = 1000*s[f]/f;
    int last = 1;
    for (int i = f+1; i <= n; ++ i)
    {
        int lastval = 1000*(s[i]-s[last-1])/(i-last+1);
        int fval = 1000*(s[i]-s[i-f])/f;
        if (lastval >= fval)
        {
            ans = max(ans, lastval);
        }
        else
        {
            ans = max(ans, fval);
            last = i-f+1;
        }
    }
    cout << ans << endl;
    return 0;
}


2003 — Hire and Fire

Monday, March 23rd, 2009

题目本身很简单,处理晋级的时候应该当做“改名”来处理,这样会方便很多。下面的代码主要是可以作为指针和多叉树的练习参考使用,不过运算过程中内存没有释放(为了简单)。[576K, 594MS]

#include <iostream>
#include <map>
#include <list>

using namespace std;

struct Node
{
    string name;
    list<Node *> children;
    Node *parent;
};

map<string, Node *> hashmap;
Node *root;

void print(Node *p, int nplus)
{
    for (int i = 0; i < nplus; ++ i)
        cout << '+';
    cout << p->name << endl;
    list<Node *>::iterator iter, end = p->children.end();
    for (iter = p->children.begin(); iter != end; ++ iter)
        print(*iter, nplus+1);
}

void hire(Node *p, string new_name)
{
    Node *new_node = new Node;
    hashmap[new_name] = new_node;
    new_node->name = new_name;
    new_node->parent = p;
    p->children.push_back(new_node);
}

void promote(Node *p)
{
    p->parent->name = p->name;
    hashmap[p->name] = p->parent;

    if (p->children.empty())
        p->parent->children.remove(p);
    else
        promote(p->children.front());
}

void fire(Node *p)
{
    hashmap.erase(p->name);

    if (p->children.empty())
    {
        if (p == root)
            root = NULL;
        else
            p->parent->children.remove(p);
    }
    else
        promote(p->children.front());
}

int main()
{
    root = new Node;
    cin >> root->name;
    root->parent = NULL;
    hashmap[root->name] = root;

    string tempstr;

    cin >> tempstr;
    while (cin.good() && !cin.eof())
    {
        if (tempstr == "print")
        {
            if (root)
                print(root, 0);
            for (int i = 0; i < 60; ++ i)
                cout << '-';
            cout << endl;
        }
        else if (tempstr == "fire")
        {
            cin >> tempstr;
            fire(hashmap[tempstr]);
        }
        else
        {
            Node *parent = hashmap[tempstr];
            cin >> tempstr;
            assert(tempstr == "hires");
            cin >> tempstr;
            hire(parent, tempstr);
        }

        cin >> tempstr;
    }

    return 0;
}


算是周记吧

Sunday, March 22nd, 2009

很疲劳地做了一周的题,今晚休息一下吧,写这个算是周记好了。

一周之前定下的计划实施得还算可以,一周过去了,题没少做,但关于Oasis我的想法变了。看了一些OA产品,无论从哪个方面都很烂(所以就不点名了),它们得以生存的原因可能是因为使用者的无知。当然这并不是说好的技术带来的用户体验跟差的技术是一样的,而是用户根本没体验过好的技术是什么样子的。所以,甚至在普通用户心里,信息化产品的体验就这么回事了,他们甚至抱有一种“将就”的态度,或者说,好一些的,认为是“局外人”理解不了技术人员的所谓的“设计美学”。然而,事实上,大多数人是不懂得“设计美学”的,尤其在软件开发这个问题上。所以看过这些OA产品之后感觉很矛盾,心里很复杂,并且决定要稳下来重新定位Oasis的市场潜力,毕竟,这是我设计上与架构上的一次革命性实践,我不能把它当儿戏。

说点别的(正在听“Fish Leong 2008 Concert (1 Live Love CD).ape”)。保送复习的时候曾经信誓旦旦地说,考完了要写《RP导论》,旨在填补RP研究的空白。但一等奖的保送居然就这么被风吹走了,我的OJ也没啥市场潜力了,RP这个东西原本的崇拜者OIers都去忙数学物理甚至化学生物去了。那么,RP研究还有用吗?经过一晚上的思考,我觉得还是很有用的。其根本原因在于,RP这个东西不真的是像大家看到的那么肤浅。RP是一门真正的科学,其应用范围是很广泛的,原有的各种版本《RP导论》初衷很好,但最终都流于搞笑,没有严肃认真地研究下去。RP事实上是关于模糊逻辑的一个分支(至少我是这么认为的),所以,它是有科学依据的,再所以,准备下周(可能)开始写一些关于RP的随笔,为写出一部真正的《RP导论》做铺垫。

《C++简明基础教程》的名字正式确定下来了,下周会再写两篇就完事了,然后开始更加简短的《PHP简明基础教程》,而且计划要整理出一篇《Scheme简明基础教程》来。这几天发现教程的访问次数还是不少的,虽然有不少的一部分是Google来的(而且关键词很离谱)。我希望Google到这个站点来就能留住人;事实上PV增长的速度从某个侧面可以证明这一点,目前已经超过5K了。

最近依然是在刷PKU(准确的说是POJ但说习惯了),计划是9月份开学之前把2000~2999能做的做完。什么叫能做?就是一周以内解决的都算能做,暂时不会的也要弄明白,只要能做!1A的次数还是少,问题看得也不是很透彻,需要继续努力。所以,写到这里,做题去了~

2002 — Squares

Sunday, March 22nd, 2009

题目本身没有什么,但Hash的优化值得我们深思。下面的代码用到了一些优化方法,但那个取模的运算如果换成逻辑与(And)的话会更快的(前提是HASHSIZE是2的整次幂)。大体思路就是对每条找到的边向两个方向试着做正方形,只要判断生成的点是否在输入内就可以了。注意,并不需要记录正方形并判重,因为每个正方形一定是被重复算了4次(j=i+1,所以边是有方向的,正方形四条边,所以有四个不同的向量,分别都被算了一次),只要最后把计数除以4就可以了。

#include <iostream>
using namespace std;

int n;
int kount, x3, y3, x4, y4, vx0, vy0, vx1, vy1, vx2, vy2;
static int x[1000], y[1000], h[1000];

#define HASHSIZE 61447777
#define hash(x, y) ( ((x+20000)*40001 + (y+20000)) % HASHSIZE )
static char hashtab[HASHSIZE];
static char hashscale;

int main()
{
    cin >> n;
    while (n)
    {
        hashscale ++;
        for (int i = 0; i < n; ++ i)
        {
            cin >> x[i] >> y[i];
            h[i] = hash(x[i], y[i]);
            hashtab[h[i]] = hashscale;
        }

        kount = 0;
        for (int i = 0; i < n; ++ i)
        {
            for (int j = i+1; j < n; ++ j)
            {
                vx0 = x[j] - x[i];    vy0 = y[j] - y[i];
                vx1 = -vy0;           vy1 = vx0;
                vx2 = vy0;            vy2 = -vx0;

                x3 = x[j] + vx1;      y3 = y[j] + vy1;
                x4 = x3 - vx0;        y4 = y3 - vy0;

                if (hashtab[hash(x3, y3)]==hashscale &&
                    hashtab[hash(x4, y4)]==hashscale)   kount ++;

                x3 = x[j] + vx2;      y3 = y[j] + vy2;
                x4 = x3 - vx0;        y4 = y3 - vy0;

                if (hashtab[hash(x3, y3)]==hashscale &&
                    hashtab[hash(x4, y4)]==hashscale)   kount ++;
            }
        }
        cout << kount/4 << endl;

        cin >> n;
    }

    return 0;
}


下面指出用到的优化。

  • static数组会稍稍加快一点速度(对底层的寻址进行优化)
  • 把哈希函数写成宏,而不是inline(那只是对编译器的建议)
  • hashtab的类型是char,为了节省空间(空间分配少也会加快一点速度)
  • 使用了hashscale,这个很少见。原来的代码里“hashscale ++;”这一行是个memset,但memset再怎么快也是全域扫描一遍,加上我们的HASHSIZE并不算小,这个消耗足有半秒左右。所以,用hashscale吧

以上。

P.S. 顺便说一句,3432跟2002是一道题(差不多),但那个219MS就过了,这个需要800MS+(顺便突出一下hashscale的巨大作用~)。