OJ刷题笔记

结束读取

while (!cin.eof())

---

叶结构

typedef struct node
{
    char value;
    node* left;//这里不能用pnode
    node* right;
}*pnode;

stdlib.h

---

qsort

    qsort(p,n,sizeof(node),cmp);
    //一维数组的排序
    int cmp(const void* a, const void* b)
    {
        int* c = (int* )a;//加括号
        int* d = (int* )b;
        return *c - *d;
    }
    //结构体的排序
    int cmp(const void* a, const void* b)
    {
        node* c=(node*) a;
        node* d=(node*) b;
        if (c->x!=d->x)//是指针 用->
            return c->x-d->x;
        else
            return c->y-d->y;
    }
//对树节点的排序：
int cmp(const void *a, const void *b)
{
    node **x = (node **)a;
    node **y = (node **)b;
    return (*x)->name.compare((*y)->name) ;
}
qsort(root->children, root->child, sizeof(node *), cmp);

bsearch

node* find,key;
//在前面添加要找的key，后面是一样的
//转换两次类型
find = (node*)bsearch((const void*)key, p, n, sizeof(node), cmp);//the same cmp
if(find == NULL)
  //didn't find

algorithm

---

有：

• max min函数
• sort(s,s+n)//两个参数
• next_permutation 、prev_permutation求字符串的下一个（前一个）字典序全排列
  若手动实现，原理是
  从尾端向前找两个相邻元素，前一个是i，后一个是ii，并满足i<ii。再从尾端向前找一个j，满足i<*j。将第i个元素和第j个元素对调，并将ii之后（包括ii）的所有元素颠倒排序，即求出下一个元素。
  善用swap(s[i],s[j])。

没有自带的GCD函数！！

typedef long long ll
ll gcd(ll x, ll y)
{
    return y == 0 ? x : gcd(y, x%y);
}

map

---

map<int, int> record;
//map自动排序，record.begin()是it->first从小到大的排序
//map.end()是没有赋值的
record.count(a);//a出现的次数
record.clear();
record[a]=b; 
//or 
record["ddd"]=b;  

map<int, int>::iterator it;
it = record.lower_bound(power);//第一项
if (it == record.end()) //没有找到
//删除该项
erase(it++);

queue stack

---

queue<int> q;
1. while(!q.empty())
2. q.top();
3. q.pop();
4. q.push(3);

stack<int> s;
//the same

priority_queue<node,vector<node>,cmp>q;//只管push即可，会按cmp规则排队
struct cmp//和qsort的规则不一样
{
    bool operator()(node a,node b)
    {
        return a.step>b.step;//不是指针
    }
};

string.h

---

memset，只能用来置零，或所有字节一样的数，它会让每个字节（32位）填充相同的内容。

大数问题

10^{12} long long a; scanf("%lld",&a)

动态规划

• 最长子序列：不必考虑前后的连续关系，用a[i]、b[i]来记录。
• 最大公约数：需要两个数是连续的，把得到的最大公约数的second变成最小的序号
  • 同样是二重循环
  • 判断map中有没有该数：if(!map.count(9))代表没有该数

参数传递

• 字符串的传递，实参直接用字符串名a，形参用char *a，使用正常，仍然可以用strlen等。修改之后不用返回，因为传入的是地址。

文件操作

int main(int argc,char **argv)
{
        freopen(argv[1],"r",stdin);
        freopen(argv[2],"w",stdout);
        /*
                        算法程序设计
        */
        return 0;
}