Day 0

　　　　下午15:00，告别了“留守”在学校的学长学姐及同学们，开始前往清北学堂（济南）。

　　　　没想到，这车，一坐就是三个多小时，有种浑身酸痛的感觉。在车上，虽然没有电视看qwq， 但我们丝毫没有闲着，尤其是yjg 小朋友，不住嘴的吃。

　　　　18：00多（多多少忘记了 2333）终于来到听YYF、HMQ说过很多次的“如驿酒店”。看外观好像还不错的样子，里面怎么样就不知道了。

　　　　安排房间，吃饭。我跟小学妹的房间在一楼，然后，我们就在里面绕啊绕@_@，好不容易找到房间，结果又换掉了 2333，重新开始找。不过新房间（二楼的）好像要稍微大那么一丢丢（虽然远不及寒假青岛的，但胜在便宜啊T_T）。

　　　　吃饭是在老师念叨很久的“超意兴”，有点自助餐的感觉。话说那个 把子肉 好好吃，不过我就吃了一次   (¯﹃¯)。

---

 

Day 1 + Day 2

 　　学习内容：

　　　　　　1.排序 

　　　　冒泡排序：这个比较基础，早就听过两遍了，简单说就是 两两交换

/*数组中逆序对较少时*/#include
      
       #include
       
        using namespace std;int a[1000];int n = 20;void sort(int *a, int l, int r) {    for(int i = l; i <= r; i++)        for(int j = l; j <= r; j++)            if(a[j] > a[j+1]) swap(a[j], a[j+1]);}int main() {    sort(a, 0, n-1);    for(int i = 0; i < n; i++) printf("%d ", a[i]);    return 0;}
       
      

　　　　插入排序：应用于在线算法，挺好用的，而且之前做题也见过 （好像忘记记代码了 2333）

　　　　快速排序（即c++中的sort）：有人说：这个有什么好学的啊，但是我们还是在调用sort的时候多想一下它的核心内涵吧

/*快速排序 及 其应用——快速选择 */#include
      
       #include
       
        using namespace std;int n, k;int a[1000];void sort(int *a, int l, int r) {//时间复杂度 递归式T(n) = O(n) + 2*T(n)//即 O(nlogn)     swap(a[l], a[rand()*rand()%(r-l+1)+l]);    int tmp = a[l];    //右边的元素均小于tmp，左边的元素均大于tmp     int l_ = l, r_ = r;    while(l < r) {    //循环的时间复杂度为区间长度         while(l < r) {            if(a[r] > tmp) r--;    //a[r]落在正确的位置，不需要被调整             else { a[l++] = a[r]; break; }        }        while(l < r) {            if(a[l] < tmp) l++;    //同上             else { a[r--] = a[l]; break; }        }    }    a[l] = tmp;    if(l-l_ > 1) sort(a, l_, l-1);    if(r-r_ > 1) sort(a, r+1, r_);}int select(int *a, int l, int r, int k) {    swap(a[l], a[rand()*rand()%(r-l+1)+l]);    int tmp = a[l];    int l_ = l, r_ = r;    while(l < r) {        while(l < r) {            if(a[r] > tmp) r--;    //a[r]落在正确的位置，不需要被调整             else { a[l++] = a[r]; break; }        }        while(l < r) {            if(a[l] < tmp) l++;    //同上             else { a[r--] = a[l]; break; }        }    }    a[l] = tmp;    if(k == l-l_+1) return a[l];    if(k < l-l_+1) return select(a, l_, l-1, k);    //比较tmp左边的元素     if(k > l-l_+1) return select(a, r+1, r_, k-(l-l_+1));    //比较tmp右边的元素 }int main() {    sort(a, 0, n-1);    select(a, 0, n-1, k);    //寻找第k小的元素     for(int i = 0; i < n; i++) printf("%d ", a[i]);    return 0; }/*选择排序：T(n) = O(n) + T(n/2)T(n) = O(n)n = 2^k2^k+2^(k-2)+2^(k-2)+...+1 = 2*2^k = */
       
      

　　　　归并排序：核心思想为二分，所以它的时间复杂度是log级别的，也可以用于求逆序对

/*可用于求逆序对 会多开一倍空间，且比较慢 */#include
      
       #include
       
        using namespace std;int n;int a[1000], b[1000];    //b[]为辅助数组 void sort(int *a, int l, int r) {    if(l == r) return ;    int mid = (l+r) >> 1;    sort(a, l, mid);    sort(a, mid+1, r);        int i = l, j = mid+1;    for(int k = l; k <= r; k++) {        if(j>r || (a[i]
       
      

　　　　　　2.快速幂

　　　　话说我们刚学，下午考试就用到了它的亲戚：快速乘，比高精还快了 0.1 second   哈哈

 

/*快速幂    整数    矩阵    多项式    支持 a - a 运算         a是一个排列，- 是一种自定义的运算，表示a[a[x]] */ #include
      
       #include
       
        using namespace std;int a = 5, x = 7;int pow(int a, int x) {    //核心    int ans = 1;    for(int now = a; x; x >= 1, now = now*now)        if(x & 1) ans *= now;    return ans;}int main() {    printf("%d", pow(a, x));}
       
      

　　　　　　3.高精

　　　　为什么有高精呢？因为有些数是会爆 long long 滴，所以我们选择把这些数作为字符串（或字符数组）储存起来

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;string s;struct bignum {    //暂时不能处理负数     int n;    int a[500];    //int f; 用于处理负数     bignum() {        n = 0;        memset(a, 0, sizeof(a));    }    bignum(string s) {        n = s.size();        memset(a, 0, sizeof(a));        for(int i = 0; i < n; i++) a[i] = s[n-1-i]-'0';    }    bignum(int s) {        memset(a, 0, sizeof(a));        n = 0;        while(s > 0) {            a[n] = s%10;            s /= 10;            n++;        }    }    void work() {        for(int i = 0; i < n; i++) {            if(a[i] < 0) {                int tmp = (-a[i] - 1) / 10 + 1;                a[i] += 10*tmp;                a[i+1] -= tmp;            }            if(a[i] >= 10) {                int tmp = a[i] / 10 + 1;                a[i] -= 10*tmp;                a[i+1] += tmp;                if(i==n-1 && a[i+1]>0) n++;            }        }        while(n>0 && !a[n-1]) n--;    }    void print() {        for(int i = n-1; i >=0; i--)            cout << a[i];        cout << '\n';    }};bignum operator + (const bignum &a, const bignum &b) {    bignum c;    c.n = max(a.n, b.n);    for(int i = 0; i < c.n; i++)        c.a[i] = a.a[i]+b.a[i];    c.work();    return c;}bignum operator - (const bignum &a, const bignum &b) {    bignum c;    c.n = max(a.n, b.n);    for(int i = 0; i < c.n; i++)        c.a[i] = a.a[i]-b.a[i];    c.work();    return c;}bignum operator * (const bignum &a, const bignum &b) {    bignum c;    c.n = max(a.n, b.n);    for(int i = 0; i < a.n; i++)        for(int j = 0; j < b.n; j++)            c.a[i-j] += a.a[i]*b.a[i];    c.work();    return c;}int main() {    cin >> s;    int x;    cin >> x;    bignum a(s);    bignum b(x);    (a+b).print();    (a-b).print();    (a*b).print();    return 0;}
         
        
       
      

　　　　　　4.搜索

　　　　这个老师没这么讲，反正意思就是：你们天天写的暴力就差不多，不用多讲 2333

　　　　　　5.二分

　　　　二分法主要指通过二分某个参数的值，并快速判断二分值是偏大或偏小，进而调整下一个二分的值。 

　　　　二分法的核心在于寻找“单调性”——随着待二分的值增大或减小，计算出的检测值应该是单调的。当二分到合适的位置，检测值应该与期望情况相符。

/*头文件们*/int binary_search(int x){    int l = 1, r = n;    while (l < r)    {        int mid = (l + r) >> 1;        if (a[mid] <= x) l = mid + 1;        else r = mid;    }    //在a数组中，大于x的最小的整数     //a[l] == x?}int binary_search(int x)//数列分段-二分部分 {    int l = l0, r = r0;    while (l < r)    {        int mid = (l + r) >> 1;        int ret = check(mid);//check(mid)返回最大值设为mid的时候的最小段数        if (ret > m) l = mid + 1;        else r = mid;             }    //求出的l即为答案 }

　　　　　　6.倍增

　　　　倍增与二分法刚好相反——二分法通过不断将取值区间缩半来缩小取值的可能范围，而倍增法通过将考虑规模不断乘二来拓展维护的范围。

　　　　倍增法的一个最经典的应用是求解RMQ问题。即给定一个长度为n的序列，多次询问某个区间的最大值。 具体做法是：对于序列中的某个元素，记录下这个元素往后+1,+2,…,+2^p内的元素中的最大值。这一部分信息可以在O(nlogn)的时间内更新完成。 回答一次询问时，一个区间的最大值可以通过求两个长度恰好为2^p的区间的最大值的最大值来得到，因此单次回答的复杂度为O(1)。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int fpow(int a, int x) //核心代码{ int ans = 1; for (int now = a; x; x >>= 1, now = now * now) if (x&1) ans = ans * now; return ans; } int main(){ int a = 5, x = 7; cout << fpow(a, x) << endl;}
            
           
          
         
        
       
      

　　　　　　7.其他一些技巧

　　　　（1）差分与前缀和

　　　　（2）均摊分析

　　　　（3）贪心

　　　　（4）分治

　　Day 1 的考试详见：

---

 

Day 3 + Day 4

　　话说(@﹏@)~

　　学习内容：

　　　　　　Day 3   今天讲的我好像之前都会呢  qwq ，听起来很顺

　　　　图的基本知识   理解了就记住了

　　　　图的储存——邻接链表、邻接矩阵    理解的基础上，记代码

　　　　最短路：  Dijkstra+堆优化、spfa+SLF优化、spfa判负环、Floyd

　　　　最小生成树： Prim （稠密图）、 Kruskal （稀疏图）

　　　　拓扑排序   第三遍听。。。

　　　　强连通分量   要用到著名的 Tarjan 算法，像缩点、求LCA什么的。。。

　　　　然后是成堆的例题。。。。

　　　　　　Day 4   一整天，除了讲STL之外，整个人都是 懵的 2333    这是为什么呢？因为我们在讲数论。。。

　　　　具体的定理、算法我就不说了， so many。。。

　　　　下面粘一下抄的STL的笔记

using namespace std;#include
      
       int a[100];//[1, 99]int b[100];struct nond {    int x, y;    bool operator <(const nond &rhs) const{        if(x == rhs.x) return y < rhs.y;        return x < rhs.x;    }}e[100];    for(int i = 1; i <= n; i++) a[i] = i;    sort(&a[1], &a[100], cmp) //sort( , &a[99]+1, )    int a = unique(&a[1], &a[10]) - a;//数组必须有序    //void f(int *a, int n);//....        for(int i = 1; i <= n; i++)    while(next_permutation(&a[1], &a[n]+1)) {        f(a, n);    }    //lower_bound(&a[1], &a[n]+1, x); //>=xupper_bound(&a[1], &a[n]+1, x); //>x     #include
       
        pair
        
          p;p.first, p.second;    //    make_pair(1, 2);    #include
         
          cin; cout ; cerr;//stdin, stdout, stderr#include
          
           ios::sync_with_stdio(false); //加速cin, cout #include
           
            cout << fixed << setprecision(8) << f;//相当于 printf("%.8f", f); #include
            
             #include
             
            
           
          
         
        
       
      

---

Day 5 + Day 6

　　　　Day 5  主讲数据结构  兴奋

　　　　　　单调栈、单调队列   已经用的比较熟练了

　　　　　　二叉堆   嗯....好像跟二叉树差不多

 

　　　　　　堆的应用：Prim、Kruskal优化 or  堆排序

　　　　　　并查集   这个应该往图论里算吧。。。

　　　　　　树状数组   类似于线段树，不过不如线段树好理解

　　　　　　RMQ   静态（无法修改）求区间的最大/最小值，而利用倍增的ST表可以很好地解决这个问题

　　　　　　二叉搜索树   支持元素插入，查询前驱、后继、排名

　　　　　　线段树    二分实现，用于单点/区间  修改/查询，代码易懂

　　　　Day 6  动态规划（DP）

　　　　　　1.数字三角形

　　　　　　　　枚举 → 记忆化搜索 → 状态转移方程

　　　　　　2.最长上升子序列（LIS）

　　　　　　　　从数列中找出的数列满足 当 i < j 时， a[i] < a[j] 且  最长

　　　　　　3.最长公共子序列（LCS）

　　　　　　　　分别从两个数列中选出一些数，构成另外两个序列，且新的两个序列保证 i = j 时， a[i] = a[j] 且  最长

　　　　　　4.区间动规

　　　　　　　　当遇到环形情况时，可以通过将序列加倍的方法来用动规做

　　　　　　5.背包

　　　　　　　　完全背包、0/1背包、多重背包   这里不多介绍

　　　　　　6.树上动规

　　　　　　　　基础：求树的直径、树的重心

---

 

Day 7 + Day 8

　　　这两天讲课的是贪心大神 CCL，但是他并不给我们讲贪心

　　　唉，有点遗憾，不过经常上着课就会有人起哄：“讲贪心，讲贪心”，还是挺有意思的

　　　最有趣的要数老师的口音了，不知道是哪里的；讲课、讲题时很搞笑，但是思路清晰、易懂，逐步深入

　　　　　Day 7   主讲：字符串

　　　　　　1.字符串的储存及基本操作

　　　　　　2.KMP算法

　　　　　　　　暴力枚举 or KMP算法   求字符串B在字符串A中出现了几次 （B <= A）可转化为求 f[i]

　　　　　　　　用两个指针不断“跳”

　　　　　　3.Trie 树

　　　　　　　　支持插入、查询操作，可查询前缀出现次数、最长前缀、单词等

　　　　　　　　注意：Trie 树 的根为空；时间复杂度低

　　　　　　4.Hash 哈希

　　　　　　　　通过比较哈希值是否相等来比较两个字符串是否相等，有概率出错（不过很小哦）

　　　　　　　　选取基底作为被mod的数（一定要比字符种类多，最好是质数且不要太常见，万一出题人就卡你这个呢 qwq），将每个字符看做数字，然后进行取模运算。

　　　　　　5.后缀数组

 

---

        呐呐，还想吃那里的紫菜包饭，楼下的“开水泡馍”和烩面，还想吃烧烤，喝暖暖的奶茶，还想.....