• 今天考试

考试

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个数组会超空间，所以滚动数组就可以在这里。

     #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. 树状数组：老师的标程

#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;
}

1. 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
2. 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$字典树

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/31/
最后修改时间：2020-04-13 11:17:13
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！