Day 3 高中部寒假集训
浏览 81 | 评论 0 | 字数 9618
Snowflake_Pink
2019年01月25日
  • Day3:

    先放课程表:

    2019.1.25

    上午
    • 讲解订正$Day2$晚上考试的题目。
    下午
    • 图论:二叉搜索树​
    晚上
    • 考试:搜索

    考试(选讲)

    • 时空限制:1000ms/128MB
    1. 调和数列问题(math.cpp/math.in/math.out):

      • 题目描述:输入一个实数$x$,求最小的$n$使得,$\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+....\frac{1}{n+1}\geq x$。 输入的实数$x$保证大于等于0.01,小于等于5.20,并且恰好有两位小数。你的程序要能够处理多组数据,即不停地读入$x$,如果$x$不等于0.00,则计算答案,否则退出程序。 输出格式为对于一个$x$,输出一行$n card(s)$。其中$n$表示要计算的答案。
      • 输入格式:分行输入$x$的具体数值。
      • 输出格式:分行输出$n$的数值,格式为$n card(s)$。
      • 样例输入:

      1.00

      3.71

      0.04

      5.19

      0.00

      • 样例输出:

      3 card(s)

      61 card(s)

      1 card(s)

      273 card(s)

      • 数据范围:不告诉你(其实我也不知道),反正绝对不会超时,请放心食用。
      • 分析:这题WA​了一点只能怪评测姬了,我也不知道为什么错了(lemon​垃圾)看出错误的请留言
      • My Code:
      #include <iostream>
      #include <cstdio>
      #include <cmath>
      using namespace std;
      long double sum,x;
      int n;
      int main(){
          freopen("math.in","r",stdin);
          freopen("math.out","w",stdout);
          while (1){
              x=0.000;
              scanf("%llf",&x);
              if (fabs(x)<0.000001) return 0;
              n=1;
              sum=0.000;
              while (sum<x){
                  n++;
                  sum+=1.0/n;
              }
              cout <<n-1<<" card(s)"<<endl;
          }
          fclose(stdin);
          fclose(stdout);
          return 0;
      }
      • STD:
      #include <bits/stdc++.h>
      using namespace std;
      
      int solve(double x) {
          double t = 0;
          for (int i = 2; ; i++) {
              t += 1.0 / i;
              if (t >= x) return i - 1;
          }
          return -1;
      }
      
      int main() {
          double x;
          freopen("math.in", "r", stdin);
          freopen("math.out", "w", stdout);
          while (cin >> x, x != 0)
              cout << solve(x) << " card(s)" << endl;
          fclose(stdin);
          fclose(stdout);
          return 0;
      }
    2. 数字环打印(circle.cpp/circle.in/circle.out):

      • 题目描述:指定从某个数N开始递增沿逆时针方向生成数字环。其中$N$位于环最左上角,环大小为$S(1\leq S \leq 10)$,环中数字均为两位数
      • 输入格式:2个整数:$N$和$S$。
      • 输出格式:打印数字环,所有的数字要上下对齐。
      • 输入样例1:

      20 2

      输入样例2:

      10 3

      • 输出样例1:

      20 23

      21 22

      输出样例2:

      10 17 16

      11 15

      12 13 14

      • 分析:这道题的坑点是S=1时的特判,算法是直接开数组,4个循环模拟填数for (i=1;i<=s-1;i++),但是当S=1时,是不会填数的。
      • My Code:
      #include <iostream>
      #include <cstdio>
      
      using namespace std;
      int ans[105][105],s,n,cnt;
      int main(){
          freopen("circle.in","r",stdin);
          freopen("circle.out","w",stdout);
          scanf("%d%d",&s,&n);//s和n写反了,不要在意这些细节
          cnt=s;
          if (n==1) ans[1][1]=s; 
          for (int i=1;i<n;i++)
              ans[i][1]=cnt++;
          for (int i=1;i<n;i++)
              ans[n][i]=cnt++;
          for (int i=n;i>1;i--)
              ans[i][n]=cnt++;
          for (int i=n;i>1;i--)
              ans[1][i]=cnt++;
          for (int i=1;i<=n;i++)
              for (int j=1;j<=n;j++)
                  if (!ans[i][j]) cout <<"  "<<" ";
                  else if (j==n) cout <<ans[i][j]<<endl;
                  else cout <<ans[i][j]<<" ";
          fclose(stdin);
          fclose(stdout);
          return 0;
      }
    3. 序列(seq.cpp/seq.in/seq.out)

      • 题目描述:有一个整数序列,它的每个数各不相同,我们不知道它的长度是多少(即整数个数),但我们知道在某些区间中间至少有多少个整数,用$L_i$,$R_i$,$C_i$来描述,表示这个整数序列中至少有$C_i$个数来自区间$[L_i,R_i]$(即序列中至少有$C_i$个数的值$\geq L_i$且$\leq R_i$)。给出若干个这样的限制,问这个整数序列最少包含多少个整数?
      • 输入格式:第1行1个整数$N$,表示区间个数;接下来$N$行,每行3个整数$L_i$,$R_i$,$C_i$,描述1个限制。
      • 输出格式:仅1个数,表示该整数序列的最小长度。
      • 输入样例:

      4

      4 5 1

      6 10 3

      7 10 3

      5 6 1

      • 输出样例:

      4

      • 数据范围:对于40% 的数据:$N\leq5$,$0\leq L_i\leq R_i\leq15$。对于100%的数据:$N\leq1000$,$0\leq L_i \leq R_i \leq1000$,$1 \leq C_i \leq R_i-L_i+1$。
      • 分析:这是一道贪心题,我贪了一个半小时没贪出来QAQ。但是看到那个40%没有??所以可以爆搜拿40分,但是我并没有这么做。还是讲正解吧:像这种有区间的贪心,基本上是要排序的。按照每个区间的$R_i$进行排序,每次把数学从右端点开始填数,这样可以尽量满足右边的区间的要求。我觉得如果按$L_i$端点排序也行,但是填数时,要从最右边的区间开始往左填数。
      • STD
      #include <bits/stdc++.h>
      using namespace std;
      
      const int MAXN = 1e3 + 10;
      
      struct rec {
          int l, r, c;
      };
      
      bool cmp(const rec &a, const rec &b) {
          return a.r < b.r;
      }
      
      int n, flag[MAXN];
      rec a[MAXN];
      
      int main() {
          freopen("seq.in", "r", stdin);
          freopen("seq.out", "w", stdout);
          cin >> n;
          for (int i = 1; i <= n; i++)
              cin >> a[i].l >> a[i].r >> a[i].c;
          sort(a + 1, a + n + 1, cmp);
          for (int i = 1; i <= n; i++) {
              for (int j = a[i].l; j <= a[i].r; j++)
                  a[i].c -= flag[j];
              if (a[i].c <= 0) continue;
              for (int j = a[i].r; a[i].c > 0; j--)
                  if (!flag[j])
                      flag[j] = 1, a[i].c--;
          }
          int ans = 0;
          for (int i = 0; i <= a[n].r; i++)
              ans += flag[i];
          cout << ans << endl;
          fclose(stdin);
          fclose(stdout);
          return 0;
      }
    4. 信息(msg.cpp/msg.in/msg.out):

      • 题目描述:有些同学(编号为1到$n$)正在玩一个信息传递的游戏。编号为i的同学的信息传递对象是编号为Ti的同学。开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?
      • 输入格式:输入共2行,第1行包含1个正整数$n$,表示总共有$n$个同学,第 2 行包含$n$个用空格隔开的正整数$T_1,T_2,…,T_n$,其中第$i$个整数$T_i$表示编号为$i$的同学的信息传递对象是编号为$T_i$的同学,$T_i \leq n$且$T_i \neq i$。数据保证游戏一定会结束。
      • 输出格式:1个整数,表示游戏一共可以进行多少轮。
      • 输入样例:

      5

      2 4 2 3 1

      • 输出样例:

      3

      • 数据范围:对于30%的数据,$n \leq 200$;对于60%的数据,$n \leq 2500$;对于100%的数据,$n \leq 200000$。
      • 分析:这道题的本质就是在一个图中,求这个图的最小环的环长。因为不用回溯,所以可以使用$dfs$,每个点都dfs一遍。如果当前在点x,发现$t_x$在这次遍历中到达过,则产生一个长为$dep[x]-dep[t_x ]+1$的环,每形成一个环就更新一下最小环的值,当发现所有后继都已被遍历时,输出答案。
      • STD
      #include <bits/stdc++.h>
      using namespace std;
      
      const int MAXN = 2e5 + 10;
      
      int n, a[MAXN], num[MAXN], vis[MAXN], cnt, ans = 1 << 30;
      
      void dfs(int x, int dep) {
          vis[x] = cnt;
          num[x] = dep;
          if (vis[a[x]] > 0) {
              if (vis[x] == vis[a[x]])
                  ans = min(ans, num[x] - num[a[x]] + 1);
          } else
              dfs(a[x], dep + 1);
      }
      
      int main() {
          freopen("msg.in", "r", stdin);
          freopen("msg.out", "w", stdout);
          cin >> n;
          for (int i = 1; i <= n; i++)
              cin >> a[i];
      
          cnt = 1;
          for (int i = 1; i <= n; i++)
              if (!vis[i]) dfs(i, 1), cnt++;
          cout << ans << endl;
          return 0;
      }
      • 扩展:当然这道题还可以用并查集做,我就使用这一算法。当发现两个节点的根节点相同时,就形成了一个环,然后更新环最小值。【具体解法】
      • My Code
      #include <iostream>
      #include <cstdio>
      using namespace std;
      int n,f[200005],dis[200005],Min=999999999,last,t;
      int find(int now){
          if (f[now]!=now){
              int last=f[now];
              f[now]=find(f[now]);
              dis[now]+=dis[last];
          }
          return f[now];
      }
      void check(int a,int b){
          int x=find(a),y=find(b);
          if (x!=y){
              f[x]=y;
              dis[a]=dis[b]+1;
          }
          else Min=min(Min,dis[a]+dis[b]+1);
          return;
      }
      int main(){
          freopen("msg.in","r",stdin);
          freopen("msg.out","w",stdout);
          cin >>n;
          for (int i=1;i<=n;i++) f[i]=i;
          for (int i=1;i<=n;i++){
              cin >>t;
              check(i,t);
          }
          cout <<Min;
          fclose(stdin);
          fclose(stdout);
          return 0;
      }

    总结

    emming,我真是太菜了,连普通的模拟题都WA了40分。昨天的贪心是不太容易出来的贪心,我已经想到要排序(不过我觉得排序没用就没排),标记一个数字的重要程度,但是离正解还是有点差距的。拿了30分,比爆搜少了10分QAQ。看来我哪个部分都要加强......


    笔记

    1. 堆

    • 相关概念:

      1. 二叉树:有一个根结点,每个结点至多有两个儿子结点的树。
      2. 满二叉树:每一层结点数都达到最大的二叉树。
      3. 完全二叉树:除最下层可不满,其它层都满,且最下层所有结点都集中在左侧的二叉树。满二叉树一定是完全二叉树。
      4. 二叉树的储存:使用数组顺序储存,根节点下标为1,点$i$的左儿子为$2i$,右儿子为$2i+1$。若子节点下标为$n$,则父节点下标为$\frac{n}{2}$(C++的自动取整)。
      5. $n$个点的完全二叉树,高度为$⌈log_2⁡(n+1)⌉$。
    • 作用:

      1. 求集合中元素最小值(最大值亦可):取树根
      2. 删除集合中最小元素(最大值亦可):删树根并使用二叉树的最后一个节点(数组最后一个节点)替换,然后下沉。如果它的值大于左右儿子的最小值,则将它与左右儿子中最小者交换,如此往复,直到它小于左右儿子或到达最底层。
      3. 往集合中加入一个元素:将新元素放在完全二叉树的末尾位置(数组末尾),然后上浮。如果它的值小于它的父节点,则将两个元素交换,如此反复,知道它的值大于父节点或到达根节点。
    • 时间复杂度:取最小值:$O(1)$,插入元素:最坏$O(\log n)$,删除最小值:最坏$O(\log n)$。
    • 模板
    #include <bits/stdc++.h>
    #define INF 999999999
    using namespace std;
    int dui[1000005],n,t,cnt,x;
    void up(int k){
        if (k==1) return;
        if (dui[k]<dui[k>>1]){
            swap(dui[k],dui[k>>1]);
            up(k>>1);
        }
        return;
    }
    void down(int k){
        int p=2*k;
        if (2*k>cnt) return;
        if (dui[p]>dui[p+1]) p++;
        if (dui[k]>dui[p]){
            swap(dui[k],dui[p]);
            down(p);
        }
        return;
    }
    inline void Input (){
        cnt++;
        dui[cnt]=x;
        up(cnt);
        return;
    }
    inline void out(){
        dui[1]=dui[cnt];
        dui[cnt]=INF;
        cnt--;
        down(1);
        return;
    } 
    int main(){
        for (int i=1;i<=1000005;i++)
            dui[i]=INF;
        scanf("%d",&n);
        for (int i=1;i<=n;i++){
            scanf("%d",&t);
            if (t==1){
                scanf("%d",&x);
                Input();
            }
            if (t==2){
                printf("%d\n",dui[1]);
            }
            if (t==3){
                out();
            }
        }
        return 0;
    }

    2. 二叉搜索树

    • 支持:维护一个元素不重复的集合

      1. 在集合中查找一个值$v$是否存在。
      2. 在集合中插入一个值。
      3. 求集合中最小值/最大值。
      4. 删除集合中最小值/最大值。
      5. 将集合中的数从小到大输出。
      6. 求集合中的第$k$大数。
    • 性质:对于树中的任意节点$v$,都要满足:

      1. $v$的左子树中结点权值$<v$的权值。
      2. $v$的右子树中结点权值$>v$的权值。
    • 储存方式:
    struct node {         // 描述二叉树的一个结点
           int f, l, r;   //父节点、左子节点、右子节点
    };
    node tree[MAXN];

    然后在使用一个变量储存根节点的下标。

    • 时间复杂度:时间复杂度取决于树的高度,最坏$O(n)$;平均$O(\log n)$。

    总结

    今天考搜索,虽然说不是很难但是还是很容易错,很耗时间的(我NOIP2018$T3$就打了一个半小时然后才拿5分QAQ)。现在最重要的是勤练习,我终于凑够3$k$字了,哈哈哈哈哈哈。

    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/9/
    最后修改时间:2020-04-13 11:09:20
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论