Day 3 高中部寒假集训

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 个整数:NS

    • 输出格式:打印数字环,所有的数字要上下对齐。

    • 输入样例 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\leq50\leq L_i\leq R_i\leq15。对于 100% 的数据:N\leq10000\leq L_i \leq R_i \leq10001 \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 nT_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)

总结

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

本文链接:https://snowflake.pink/archives/9/
This blog is under a CC BY-NC-ND 4.0 Unported License