https://www.luogu.com.cn/training/113#problems

【数据结构1-1】线性表

P3613 【深基15.例2】寄包柜

向量

https://www.luogu.com.cn/problem/P3613
直接开a[N][N]数组， a[100005][100005]就肯定MLE 了，
怎样设置数组才能节省内存呢？我们想到动态数组 vector

数组实现链表

P1160 队列安排
要用链表
第一次提交有部分未通过是因为可能有重复删除的数。所以要先判断是不是删过，加了判断之后AC了。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int N = 100010;

int n, m;
int e[N], l[N], r[N], idx;
int st[N];

//在k右边插入 
void insert(int k, int x){
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

//删除下标为k的数
void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
} 

int main(){
    cin >> n;
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0, idx = 2;
    //先插入1 
    insert(0, 1);
    for(int i = 2; i <= n; i++){
        int k, p;
        cin >> k >> p;
        if(p == 0) insert(l[k + 1], i);
        else insert(k + 1, i);
    }
    cin >> m;
    while(m--){
        int x;
        cin >> x;
        if(!st[x]) {
            st[x] = 1;
            remove(x + 1);
        }
    }
    for(int i = r[0]; i != 1; i = r[i]){
        printf("%d ", e[i]);
    }
    cout << endl;
    //printf("%.2lf", ans);
    return 0;
}

P4387 【深基15.习9】验证栈序列
主要看思路，还有细节处理栈的情况，及时跳出、清空等。

P2234 [HNOI2002]营业额统计
直接每次往前遍历会超时。
题解思路都不常碰到，看看。
https://www.luogu.com.cn/problem/solution/P2234

【数据结构1-2】二叉树

树的遍历

P1827 [USACO3.4]美国血统 American Heritage
前序遍历中序遍历后序遍历。

二分

P5076 【深基16.例7】普通二叉树（简化版）
//upper_bound(begin,end,number)函数是求begin-end中（排好序）第一个大于 number的数
//lower_bound(begin,end,number)函数是求begin-end中（排好序）第一个大于等于 number的数
//以上两个函数传回一个指针，指针-a就是一个相对位置（所求number的下标）
这里本来自己写二分，但是WA了，没看出哪里漏了。所以直接用上面的函数，AC了。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int N = 10010;
const int INF = 0x3f3f3f3f;

int n, l, r;
int a[N];

int main(){
    cin >> n;
    int cnt = 0;
    while(n--){
        int op, x;
        cin >> op >> x;
        if(op == 1){
            int l = 1, r = cnt;
            while(l < r){
                int mid = (l + r) / 2;
                if(a[mid] >= x) r = mid;
                else l = mid + 1;
            }
            l = lower_bound(a + 1, a + cnt + 1 , x) - a;
            //printf("l = %d r = %d\n", l, r);
            cout << l << endl;
        }
        else if(op == 2){
            cout << a[x] << endl;
        }
        else if(op == 3){
            int l = 1, r = cnt;
            while(l < r){
                int mid = (l + r) / 2;
                if(a[mid] >= x) r = mid;
                else l = mid + 1;
            }
            l = lower_bound(a + 1, a + cnt + 1 , x) - a;
            //printf("l = %d r = %d\n", l, r);
            if(l == 1) cout << -2147483647 << endl;
            else cout << a[l - 1] << endl;
        }
        else if(op == 4){
            int l = 1, r = cnt;
            while(l < r){
                int mid = (l + r + 1) / 2;
                if(a[mid] <= x) l = mid;
                else r = mid - 1;
            }
            l = upper_bound(a + 1, a + cnt + 1 , x) - a;
            //printf("l = %d r = %d\n", l, r);
            if(l == cnt + 1) cout << 2147483647 << endl;
            else cout << a[l] << endl;
        }
        else if(op == 5){
            a[++cnt] = x;
            sort(a + 1, a + cnt + 1);
        }
    }
    //cout << ans << endl;
    //printf("%.2lf", ans);
    return 0;
}

最短路径

P1364 医院设置 多种解法！
bfs floyed等最短路径问题的算法

P1229 遍历问题
思路很巧妙

LCA

P3884 [JLOI2009]二叉树问题
LCA问题，这里n小所以可以暴力，但可以了解下思路。

【数据结构1-3】集合

并查集

判断关系应用：
P1551 亲戚 普通int型
P2814 家谱 string型

分组：
P1525 [NOIP2010 提高组] 关押罪犯
参考题解用数组b[i]代表i的敌人
图片说明
P1892 [BOI2003]团伙
这里也可以向上面那样开一个敌人数组
图片说明
也可以使用反集
图片说明
图片说明

并查集+埃氏筛质数
P1621 集合

字符串哈希

P3370 【模板】字符串哈希
这里我直接偷懒用集合去重了，正常是要实现哈希这个过程，y总算法基础也有讲。

字典树Tire

P3879 [TJOI2010]阅读理解
这里我用map和set解决了，但如果题目查询次数特别多时会TLE，这时用字典树。
两种方法我都实现了

map

P3405 [USACO16DEC]Cities and States S
关键是怎么处理成对。

P5250 【深基17.例5】木材仓库
可以详细了解map的用法，begin，end，find，erase等

P4305 [JLOI2011]不重复数字
我想的是用set，但是部分TLE
图片说明
解决：
图片说明
改了之后还是TLE，然后把cin改为scanf，就AC了。。。。

【数据结构1-4】图的基本应用

dfs，bfs

P5318 【深基18.例3】查找文献
关键在于怎么存图，并且它的要求是从编号小的输出。

P3916 图的遍历
解决思路很巧妙，求经过的最大点，把路径反过来就是每个点能到达哪些位置，从大点开始遍历可以剪枝，因为已经到过的点不会有更大的点了。

P1113 杂务
还可以用dp，很厉害的思路！！
因为任务可以并发，所以一个任务如果有前驱的话，最优方案便是在它的最晚一个前驱结束后就立即开始，而且任务k的前驱节点一定小于k，所以读入时顺便从它的前驱里挑一个最大的转移即可。同时可以更新最终答案。

P1807 最长路
这个题我是自己按题意写的AC了，没想到用最短路的模板，可以看下题解。

P1363 幻象迷宫
用走到“同一点”作为可以到达无限远的判断标志。
图片说明

拓扑排序

P1347 排序
特别多细节判断！值得一看。

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int n, m, now;
int ru[N], ruu[N], vis[N], q[N]; //q存拓扑序列 
vector<int> e[N]; 

int tuopu(){
    //1代表合法 2代表有环，3代表无法确定 
    int hh = 0, tt = -1;
    bool mul = false;  //如果同时有多个入度为0的点则我们不能判断它们的大小顺序 
    bool uncertain = false;
    for(int i = 0; i < 26; i++){ 
        ruu[i] = ru[i];  //不能影响下一次插入的判断 
        if(ruu[i] == 0 && vis[i]){
            if(!mul) mul = true;
            else uncertain = true;
            q[++tt] = i;
        }
    }
    //printf("tt = %d\n", tt); 
    if(tt == -1) return 0; //没有入度为0的点 

    while(hh <= tt){
        int t = q[hh++];
        mul = false; //重新判断 
        for(int i = 0; i < e[t].size(); i++){
            int p = e[t][i];
            ruu[p]--;
            if(ruu[p] == 0) {
                if(!mul) mul = true;
                else uncertain = true;
                q[++tt] = p;
            }
        }
    }
    //printf("tt = %d now = %d\n", tt, now); 
    if(tt != now - 1) return 0; //有环 
    if(uncertain) return 2; //不确定 
    if(tt == n - 1) return 1; //确定 
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        char ch;
        cin >> ch;
        int a = ch - 'A'; 
        if(!vis[a]) vis[a] = true, now++;
        cin >> ch; //'<'
        cin >> ch;
        int b = ch - 'A'; 
        if(!vis[b]) vis[b] = true, now++;
        ru[b]++;
        e[a].push_back(b);
        if(tuopu() == 0) {
            printf("Inconsistency found after %d relations.", i + 1);//存在矛盾 
            return 0;
        }
        if(tuopu() == 1){
            printf("Sorted sequence determined after %d relations: ", i + 1);
            for(int j = 0; j < n; j++){
                printf("%c", q[j] + 'A');
            }
            printf(".");
            return 0;
        }
    }
    printf("Sorted sequence cannot be determined.");
    return 0;
}