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 授权协议，转载请注明来源，谢谢！