2019.5.26高中部集训

  • 今天考试

考试

  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个数组会超空间,所以滚动数组就可以在这里。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      #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;
      }
      1. 树状数组:老师的标程
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      #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. 队列
  • 普及
    • 搜索:
      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. 单调队列
    • 图论:
      1. $SPFA$
      2. $Prim$
      3. 匈牙利算法
      4. 网络流
        • Dinic
      5. $Tarjan$
    • 字符串:
      1. $KMP$
      2. $Trie$
      3. $AC$字典树

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×