文章目录

一、AcWing 4455. 出行计划（简单）

1. 实现思路

2. 实现代码

二、AcWing 4510. 寻宝！大冒险！（简单）

1. 实现思路

2. 实现代码

三、AcWing 3422. 左孩子右兄弟（中等）

1. 实现思路

2. 实现代码

四、AcWing 4728. 乘方 （简单）

1. 实现思路

2. 实现代码

五、AcWing 4729. 解密（简单）

1. 实现思路

2. 实现代码

一、AcWing 4455. 出行计划（简单）

题目描述

最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。

具体来时，如果在 t tt 时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。

这里我们假定等待核酸检测结果需要 k kk 个单位时间，即在 t + k t+kt+k 时刻可以获得结果。

如果一个场所要求持 24 2424 个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第 t + k t+kt+k 时刻到第 t + k + 23 t+k+23t+k+23 时刻进入该场所。

小 C CC 按时间顺序列出接下来的 n nn 项出行计划，其中第 i ii 项（1 ≤ i ≤ n 1 ≤ i ≤ n1≤i≤n）可以概括为：t i t_it

i

 时刻进入某场所，该场所需持有 c i c_ic

i

 个单位时间内的核酸检测结果入内，其中 0 < c i ≤ 2 × 1 0 5 0 < c_i ≤ 2 ×10^{5}0<c

i

≤2×10

5

。

为了合理安排核酸检测时间，试根据小 C CC 的出行计划，回答如下查询：

如果在 q qq 时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？

这样的查询共有 m mm 个，分别为 q 1 ， q 2 ， ⋯ ， q m q_1，q_2，⋯，q_mq

1

，q

2

，⋯，q

m

；查询之间互不影响。

输入格式

输入的第一行包含空格分隔的三个正整数 n nn、m mm 和 k kk，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。

接下来输入 n nn 行，其中每行包含用空格分隔的两个正整数 t i t_it

i

、c i c_ic

i

，表示一项出行计划；出行计划按时间顺序给出，满足 0 < t 1 ≤ t 2 ≤ ⋯ ≤ t n ≤ 2 × 1 0 5 0 < t_1 ≤ t_2 ≤ ⋯ ≤ t_n ≤ 2×10^{5}0<t

1

≤t

2

≤⋯≤t

n

≤2×10

5

。

最后输入 m mm 行，每行仅包含一个正整数 q i q_iq

i

，表示一个查询。m mm 个查询亦按照时间顺序给出，满足 0 < q 1 < q 2 < ⋯ < q m ≤ 2 × 1 0 5 0 < q_1 < q_2 < ⋯ < q_m ≤ 2×10^{5}0<q

1

<q

2

<⋯<q

m

≤2×10

5

。

输出格式

输出共 m 行，每行一个整数，表示对应查询的答案。

数据范围

40% 的测试数据满足 0 < n ， k ≤ 1000 、 m = 1 0 < n，k≤1000、m=10<n，k≤1000、m=1；

70% 的测试数据满足 0 < n ， m ， k ≤ 1000 0<n，m，k≤10000<n，m，k≤1000；

全部的测试数据满足 0 < n ， m ， k ≤ 1 0 5 0<n，m，k≤10^{5}0<n，m，k≤10

5 。

输入样例

6 2 10

5 24

10 24

11 24

34 24

35 24

35 48

1

2

输出样例

3

3

样例解释

时刻 1 11 做检测，可以满足第三、四、六项出行计划；

时刻 2 22 做检测，可以满足第四、五、六项出行计划。

具体实现

1. 实现思路

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m, k;
int b[N];
int main()
{
    cin >> n >> m >> k;
    //n个场所
    while (n -- )
    {
        int t, c;
        cin >> t >> c;
        int l = t - k - c + 1, r = t - k;
        //差分
        if (r > 0) 
        {
            b[max(1, l)] ++, b[r + 1] -- ;
        }
    }
    for (int i = 1; i < N; i ++ ) 
    {
        b[i] += b[i - 1];
    }
    //m个询问
    while (m -- )
    {
        int t;
        cin >> t;
        cout << b[t] << endl;
    }
    return 0;
}

二、AcWing 4510. 寻宝！大冒险！（简单）

题目描述

输入格式

输入样例 1

5 100 2

0 0

1 1

2 2

3 3

4 4

0 0 1

0 1 0

1 0 0

输出样例 1

3

样例 1 解释

绿化图上 ( 0 , 0 ) 、 ( 1 , 1 ) (0,0)、(1,1)(0,0)、(1,1) 和 ( 2 , 2 ) (2,2)(2,2) 三处均可能埋有宝藏。

输入样例 2

5 4 2

0 0

1 1

2 2

3 3

4 4

0 0 0

0 1 0

1 0 0

输出样例 2

0

样例 2 解释

如果将藏宝图左下角与绿化图 ( 3 , 3 ) (3,3)(3,3) 处对应，则藏宝图右上角会超出绿化图边界，对应不成功。

具体实现

1. 实现思路

2. 实现代码

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = 55, INF = 1e8;
//n表示树的数量，m表示A矩阵的边长，k表示B矩阵的边长
int n, m, k;
//树的存储
PII tree[N];
//B矩阵的存储
int b[M][M];
int main()
{
    cin >> n >> m >> k;
    //读入树的坐标
    for (int i = 0; i < n; i ++ )
    {
        cin >> tree[i].x >> tree[i].y;
    }
    //B中树的数量
    int tc = 0;   
    //读入B矩阵
    for (int i = k; i >= 0; i -- )
    {
        for (int j = 0; j <= k; j ++ )
        {
            cin >> b[i][j];
            tc += b[i][j];
        }
    }
    //res表示可以匹配的数量
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int sx = tree[i].x, sy = tree[i].y;
        //判断是否越界
        if (sx + k > m || sy + k > m)
        {
            continue;
        }
        //A中树的个数
        int cnt = 0;
        //枚举每一个树
        for (int j = 0; j < n; j ++ )
        {
            int x = tree[j].x, y = tree[j].y;
            //如果这棵树在A和B中
            if (x >= sx && x - sx <= k && y >= sy && y - sy <= k)
            {
                //判断B的对应位置
                if (!b[x - sx][y - sy])
                {
                    cnt = -INF;
                }
                else
                {
                    cnt ++ ;
                }
            }
        }
        if (cnt == tc)
        {
            res ++ ;
        }
    }
    cout << res << endl;
    return 0;
}

三、AcWing 3422. 左孩子右兄弟（中等）

题目描述

对于一棵多叉树，我们可以通过 “左孩子右兄弟” 表示法，将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。

换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。

给定一棵包含 N NN 个结点的多叉树，结点从 1 11 至 N NN 编号，其中 1 11 号结点是根，每个结点的父结点的编号比自己的编号小。

请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树，高度最高是多少。

注：只有根结点这一个结点的树高度为 0 00。

其中最后一种高度最高，为 4 44。

输入格式

输入的第一行包含一个整数 N NN。

以下 N − 1 N−1N−1 行，每行包含一个整数，依次表示 2 22 至 N NN 号结点的父结点编号。

输出格式

输出一个整数表示答案。

数据范围

对于 30% 的评测用例，1 ≤ N ≤ 20 1≤N≤201≤N≤20；

对于所有评测用例，1 ≤ N ≤ 1 0 5 1≤N≤10^{5}1≤N≤10

5

。

输入样例

5

1

1

1

2

输出样例

4

具体实现

1. 实现思路

• 左边存孩子，右边存兄弟。
• 每棵树最大可能形成的高度是其最深子树的高度（根节点高度为 0）与其子树数量的和。
• 每棵子树的深度只跟这棵子树内部有关，与其它节点没有关系。
• 因此，只需求出两部分分别的最大值即可。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int h[N], e[N], ne[N], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}
int dfs(int u)
{
    //hmax表示子树的最大高度
    //cnt表示子树的数量
    int hmax = 0, cnt = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        hmax = max(hmax, dfs(j));
        cnt ++ ;
    }
    return hmax + cnt;
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 2; i <= n; i ++ )
    {
        int p;
        cin >> p;
        add(p, i);
    }
    cout << dfs(1) << endl;
    return 0;
}

四、AcWing 4728. 乘方 （简单）

题目描述

输入样例 1

10 9

输出样例 1

1000000000

输入样例 2

23333 66666

输出样例 2

‐1

具体实现

1. 实现思路

• 此题比较简单，只需分情况讨论。
• 第一种情况，当 a=1 时，结果就是 1，就不用进入循环直接输出即可。
• 第二种情况，当 a＞1 时，进入循环，在中间要小心结果 res 超出范围，因此，res 使用 long long。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int a, b;
    cin >> a >> b;
    LL res = 1;
    while (a > 1 && b -- )
    {
        res *= a;
        if (res > 1e9)
        {
            res = -1;
            break;
        }
    }
    cout << res << endl;
    return 0;
}

五、AcWing 4729. 解密（简单）

题目描述

输入样例

10

770 77 5

633 1 211

545 1 499

683 3 227

858 3 257

723 37 13

572 26 11

867 17 17

829 3 263

528 4 109

输出样例

2 385

NO

NO

NO

11 78

3 241

2 286

NO

NO

6 88

具体实现

1. 实现思路

这里需要注意的是，要先输出数据小的那一部分。

由于数据范围是10.18要使用 long long。

因为输出的结果必须是正整数，所以需要对 dt 是否为正整数进行判断。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int k;
    cin >> k;
    while (k -- )
    {
        LL n, d, e;
        cin >> n >> d >> e;
        LL m = n - e * d + 2;
        LL dt = m * m - 4 * n;
        //开根号
        LL r = sqrt(dt);
        //如果dt小于0，或者dt不是整数（因为输出的结果必须是正整数）
        if (dt < 0 || r * r != dt)
        {
            puts("NO");
        }
        else 
        {
            cout << (m - r) / 2 << " " << (m + r) / 2 << endl;
        }
    }
    return 0;
}