2019年11月NOIP笔记总结

2019-11-25 10:54

1前言

本篇主要讲的是我最近学的关于堆和树的知识。  (我好菜呀)

峰位于中国境内。2内容

  1. 有n个节点的树有(n-1)条边

  2. 树:无环无向图,任意两点之间只有一条边

  3. 经过所有边回到原点--哈密尔顿回路

    经过所有点回到原点--欧拉回路

  4. 中序:父亲在中间,左儿子在左边,左儿子在右边(人脑习惯)

  5. vectora :定义不定长数组

    a.push_back :加入元素

    a.size() :获取元素个数

  6. 二叉树:每个节点最多有两个子树的树。

    完全二叉树:一棵深度为h的二叉树,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就 是完全二叉树。

    满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子 结点的二叉树。

    1. 将权值从大到小排序

    2. 取2个数做子节点,建一个空白父节点

    3. 将新建的树放回序列

    4. 重复步骤2

  7. 生成哈夫曼树

    • B:只有0的

    • I:只有1的

    • F:其他的j


    ②图

    1. 堆就是完全二叉树。

      • 最大堆:根结点的键值是所有堆结点键值中最大者的堆。

      • 最小堆:根结点的键值是所有堆结点键值中最小者的堆。

    2. 最小堆排序

      #include
      using namespace std;
      int n;
      int heap[11]={0,1,8,2,11,12,4,6};
      int ans[8];
      void d(int i)
      {
      int t;
      while(i*2<=n)
      {
         t=i;
         if(heap[2*i]
         {
             t=2*i;
         }
         else
         {
             t=i;
         }
         if(2*i+1<=n)
         {
             if(heap[2*i+1]
             {
                 t=2*i+1;
             }
         }
         if(t!=i)
         {
             swap(heap[t],heap[i]);
             i=t;
         }
         else
             break;
      }
      return;
      }
      int main()
      {
      heap[1]=10;
      n=7;
      d(1);
      int k = 0;
      while(n>0)
      {
         k++;
         ans[k] = heap[1];
         heap[1] = heap[n];
         n--;
         d(1);
      }
      for(int i=1;i<=7;i++)
      {
         cout<<ans[i]<<" ";
      }
      return 0;
      }

      正确结果:2 4 6 8 10 11 12


    ③其他

    • queue->队列

    • 位运算

      x>>1 除以2

      x<<1 乘以2

      可以用来计算x的n次方

    • pow函数

      power :求冥

      pow(x,y) :求x的y次方

    • floor(x)向下取整,返回一个<=x的int整型。

      ceil(x)向上取整,返回一个>=x的int整型。

    • 用一个数据和数据的关系,通过图和线段之间的关系来表示。

      前提条件:BFS

  8. FBI树


3一些问题
  • VIM是什么?好像是个编译器?

  • 我同学写了一个神奇的代码,哪位大佬明白是什么意思?

    #include
    #include
    #define
    int1 long long using namespace std;
    priority_queueq1;
    queueq2;
    queueq3;
    int1 n,m,t,q,u,v;
    int main()
    {
    cin>>n>>m>>q>>u>>v>>t;
    for(int i=1; i<=n; i++)
    {
       int1 a;
       cin>>a;
       q1.push(a);
    }
    int1 tag=0;
    for(int i=1; i<=m; i++)
    {
       int1 x=-1000000000,y=-1000000000,z=-1000000000;
       if(!q1.empty()) x=q1.top();
       if(!q2.empty()) y=q2.front();
       if(!q3.empty()) z=q3.front();
       int1 a;
       a=max(x,max(y,z));
       if(a==x) q1.pop();
       else if(a==y) q2.pop();
       else if(a==z) q3.pop();
       a+=(i-1)q;
       if(i%t==0) cout<<a<<" ";
       int1 px=a(long long)u/v;
       q2.push(px-iq);
       q3.push(a-px-iq);
    }
    cout<<endl;
    for(int i=1; i<=n+m; i++)
    {
       int1 x=-100000000000,y=-100000000000,z=-100000000000;
       if(!q1.empty()) x=q1.top();
       if(!q2.empty()) y=q2.front();
       if(!q3.empty()) z=q3.front();
       int1 a;
       a=max(x,max(y,z));
       if(a==x) q1.pop();
       else if(a==y) q2.pop();
       else if(a==z) q3.pop();
       if(i%t==0) cout<<a+m*q<<" ";
    }
    }

    好了,本月的笔记到此结束。

--end--

后记,小编朋友公司研发了一个游戏化的少儿编程在线课程(5-12岁),游戏化教学结合scratch(一款在线少儿编程工具,类似乐高的积木拼搭),我家娃娃学了几次课,非常喜欢(超预期),16次课才200多块钱,对锻炼孩子的思维能力和动手动力很有帮助。

感兴趣的朋友可以扫描二维码,关注一下,或微信搜索“大耳猴少儿编程”

https://www.china-scratch.com/Uploads/Editor/2018-04-22/5adca08bdc212.jpg

声明:本文章由爬虫自动处理和转载作为教育分享用途,原作者可通过邮件及时和我们联系处理:freemanzk@qq.com