• 今天考试

考试

1. Toy（toy,cpp/toy.in/toy.out）：

   • 题面：有很多玩具，第$i$个玩具插入在现有序列中第$k[i]$个空，编号为$m[i]$。现在要按顺序插入玩具，问最后的编号顺序。

   • 输入格式：第一行一个$n$，接下来的$n$行中，对应有两个数$k[i]$和$m[i]$。

   • 输出格式：一行编号顺序。

   • 输入样例：

     4 0 7 1 5 1 3 2 6

   • 输出样例：

     7 3 6 5

   • 分析：两种解法

     1. 平衡树：不过这道题没有专门卡二叉搜索树（90分），但是我在两个子树都满的情况下，替换出问题了（我没有打平衡树），暴力也没有调出来。所以完美爆零$qwq$。
   • $STD$

2. Guinness（guinness.cpp/guinness.in/guinness.out）：

   • 题面：原来有一个队列，里面的人身高递增排列，现在陆续有很多队列加入，求每次加入一个队列时每个人插入在主队列的位置（第几个空）。

   • 输入格式：第1行为$m$，表示最开始时主队伍中的人数。第2行为$m$个递增的数，表示这时的主队伍中每个人身高。第3行为$n$，表示按时间先后顺序陆续赶来的分队数目。以后的$2 \times n$行中，前一行为$m’$表示按时间顺序出现的分队的人数，后一行$m’$个递增的数，表示这个分队伍中每个人身高的相对值。

   • 输出格式：每一队伍的插入位置。

   • 输入样例：

     4 2 11 12 15 2 4 1 3 10 14 3 5 6 18

   • 输出样例：

     1 2 2 4 4 4 9

   • 分析：三种正解

     1. 平衡树：果然省选算法就是强$qwq$。
     2. 归并排序：$NOIP$曾有一道题（瑞士轮）也是合并，那道题我至今没有AC，只有60分不知道为什么？？两道题都是让你合并，并且合并的两个队列都有序，所以可以在归并的同时合并。位置自然也就在合并的时候出来了。我是先二分出位置，然后再合并，如此复杂，以至于我在$Code$的时候错了，再次完美爆零$qwq$。
     3. 树状数组/线段树：可以发现，若要插入一个身高为$x$的人，只需要计算前面有几个人比他高即可。这个值可以使用树状数组或线段树维护。
   • $Code$：
     1. 归并：我发现归并中这个数组的循环使用有点意思，如果用for覆盖会超时，用600个数组会超空间，所以滚动数组就可以在这里。
     CPP

     #include <iostream>
     #include <cstdio>
     #define INF 2147483647
     using namespace std;
     const int MAXN=2e5+5;
     int m,n,data[4][MAXN],len[4],a,b,c;
     inline int in(){
         int X=0,w=0; char ch=0;
         while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
         while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
         return w?-X:X;
     }
     inline void out(int x){
         if(x<0) putchar('-'),x=-x;
         if(x>9) out(x/10);
         putchar(x%10+'0');
     }
     inline int Mod(int num,int x){
         return (num&(x-1));
     }
     inline void update(){
         a=Mod(a+1,4);
         b=Mod(b+1,4);
         c=Mod(c+1,4);
         return;
     }
     int main(){
         m=in();
         a=1;
         b=0;
         c=2;
         len[a]=m;
         for (register int i=1;i<=m;i++){
             data[a][i]=in();
         }
         n=in();
         while (n--){
             len[b]=in();
             for (register int l=1;l<=len[b];l++){
                 data[b][l]=in();
             }
             int i=1,j=1,k=0;
             data[a][len[a]+1]=INF;
             data[b][len[b]+1]=INF;
             while (i<=len[a]||j<=len[b]){
                 if (data[a][i]<data[b][j]){
                     data[c][++k]=data[a][i++];
                 }
                 else {
                     data[c][++k]=data[b][j++];
                     out(i);
                     printf (" ");
                 }
             }
             len[c]=k;
             printf ("\n");
             update();
         }
         return 0;
     }

     2. 树状数组：老师的标程
     CPP

     #include <bits/stdc++.h>
     using namespace std;
     
     #define initIO(pn) freopen(pn ".in", "r", stdin), freopen(pn ".out", "w", stdout)
     const int MAXM = 1e6 + 10;
     const int MAXN = 610;
     
     int B[MAXM];
     vector<int> r, v[MAXN];
     map<int, int> mp;
     
     int lowbit(int x) {
         return x & (-x);
     }
         
     void update(int x, int v) {
         for (; x < MAXM; x += lowbit(x))
             B[x] += v;
     }
     
     int query(int x) {
         int res = 0;
         for (; x; x -= lowbit(x))
             res += B[x];
         return res;
     }
     
     int main() {
         int n, m, x;
         initIO("guinness");
         
         cin >> m;
         for (int i = 1; i <= m; i++) {
             cin >> x;
             v[0].push_back(x);
             r.push_back(x);
         }
         cin >> n;
         for (int i = 1; i <= n; i++) {
             cin >> m;
             for (int j = 1; j <= m; j++) {
                 cin >> x;
                 v[i].push_back(x);
                 r.push_back(x);
             }
         }
     
         sort(r.begin(), r.end());
         for (int i = 0; i < r.size(); i++)
             mp[r[i]] = i + 1;
         for (int i = 0; i <= n; i++)
             for (int j = 0; j < v[i].size(); j++)
                 v[i][j] = mp[v[i][j]];
     
         for (int i = 0; i < v[0].size(); i++)
             update(v[0][i], 1);
         for (int i = 1; i <= n; i++) {
             for (int j = 0; j < v[i].size(); j++)
                 cout << query(v[i][j]) + 1 << " ";
             cout << endl;
             for (int j = 0; j < v[i].size(); j++)
                 update(v[i][j], 1);
         }
         return 0;
     }

3. Furit（furit.cpp/furit.in/furit.out）：

   • 题面：小$R$家种了一棵神奇的果树，果树的顶部有一个母果实（编号为1），母果实向所有的果实提供养分，并且母果实向下方分出许多藤蔓连接子果实，然后子果实也以这样的方式连接其他果实。每一天，小R会到这棵树前摘果子吃，但是对于他来说一、两个果子是显然不够的。他想在一天中尽可能多吃，但是一旦果树上的某个果子被摘下来，就会影响到从母果实发出并经过这个果子的所有藤蔓的养分供给，小$R$担心果树结出坏果子，所以在同一天，他不敢再摘这样的藤蔓上的其他果子。因为懒得算，小R想让你告诉他这果树上的果子，至少能让他吃多少天。

   • 输入格式：第一行一个正整数$n$，表示树上有$n$个果子。第$2$ ~ $n+1$行，描述编号为$1$ ~ $n$的果子。每一行开头一个正整数$m[i]$，表示编号为$i$的果子有$m[i]$条藤蔓连向下方的果子，然后是用空格隔开的$m[i]$个数，表示藤蔓连向的果子编号。

   • 输出格式：一个正整数$d$，表示至少能吃的天数。

   • 输入样例：

     7 2 2 3 2 4 5 2 6 7 0 0 0 0

   • 输出样例：

     3

   • 分析：这题关键是看懂题目，其实就是求整棵树的最大深度，因为你不能去一个藤蔓的中间结点。所以$dfs$求深度即可$qwq$。

   • STD

4. Quantum（quantum.cpp/quantum.in/quantum.out）：

知识清单

• 基础
  • $STL$
    1. vector
    2. stack
    3. queue
    4. set
    5. map
    6. priority_queue
    7. string
  • 算法：
    1. 枚举
    2. 模拟
    3. 贪心
    4. 递归/递推
  • 数据结构：
    1. 栈
    2. 队列
• 普及
  • 搜索：
    1. $DFS$
    2. $BFS$
  • $DP$动态规划：
    1. 背包
    2. 区间
    3. 序列
    4. 树形
  • 图论：
    1. 边集数组
    2. 邻接矩阵
    3. 邻接链表
    4. $Dijkstra$
    5. $Floyd$
    6. $Kruskal$
    7. 并查集
  • 数据结构：
    • $ST$表
• 提高
  • 搜索：
    1. 迭代加深
    2. $A*$
  • 数据结构：
    1. $ST$表
    2. 线段树
    3. 树状数组
    4. 块状数组
    5. 二叉搜索树
    6. 平衡树
    7. 堆
    8. 单调队列
  • 图论：
    1. $SPFA$
    2. $Prim$
    3. 匈牙利算法
    4. 网络流
       • Dinic
    5. $Tarjan$
  • 字符串：
    1. $KMP$
    2. $Trie$
    3. $AC$字典树