Day 3 高中部寒假集训 - 粉粉何所似？

Day3：

先放课程表：

2019.1.25

上午

讲解订正 $Day2$ 晚上考试的题目。

下午

图论：二叉搜索树、堆。

晚上

考试：搜索

考试（选讲）

时空限制：1000ms/128MB

调和数列问题（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：
CPP
#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：
CPP
#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; }

数字环打印（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;
}

序列（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
CPP
#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; }
信息（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
CPP
#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
CPP
#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$ 字了，哈哈哈哈哈哈。