小鲸鱼的梦境
0%

『洛谷』数组基础

发表于 分类于 ， Valine：
本文字数： 7.7k 阅读时长 ≈ 7 分钟

入门级-数组基础

P1046 [NOIP2005 普及组] 陶陶摘苹果

题目描述

陶陶家的院子里有一棵苹果树，每到秋天树上就会结出 10 个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个 30 厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。

现在已知 10 个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。

输入格式

输入包括两行数据。第一行包含 10 个 100 到 200 之间（包括 100 和 200 ）的整数（以厘米为单位）分别表示 10 个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个 100 到 120 之间（包含 100 和 120 ）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。

输出格式

输出包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。

输入输出样例

输入: #1

1
2
100 200 150 140 129 134 167 198 200 111
110

输出: #1

1
5

说明&提示

无

解题思路

计数即可

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int PickApples(vector<int>& nums, int h) {
        // nums 记录苹果高度，h 记录陶陶身高
        int cnt = 0;
        h += 30;
        for (int apple: nums) {
            if (h >= apple) cnt++;
        }
        return cnt;
    }
};

int main() {
    Solution s;
    int h;
    vector<int> nums(10);
    for (int i = 0; i < 10; ++i) {
        cin >> nums[i];
    }
    cin >> h;
    cout << s.PickApples(nums, h) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import Java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main s = new Main();
        int[] nums = new int[10];
        for (int i = 0; i < 10; ++i) {
            nums[i] = sc.nextInt();
        }
        int h = sc.nextInt();
        sc.close();
        System.out.println(s.PickApples(nums, h + 30));
    }

    public int PickApples(int[] nums, int h) {
        int cnt = 0;
        for (int apple: nums) {
            if (h >= apple) cnt++;
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
from typing import List
class Solution():
    def PickApples(self, nums: List[int], h: int) -> int:
        """陶陶摘苹果"""
        return sum(1 for apple in nums if h >= apple)

print(Solution().PickApples(map(int, input().split()), int(input()) + 30))

P1047 [NOIP2005 普及组] 校门外的树

题目描述

某校大门外长度为 l 的马路上有一排树，每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 l 的位置；数轴上的每个整数点，即 0, 1, 2, …, l，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

第一行有两个整数，分别表示马路的长度 l 和区域的数目 m。

接下来 m 行，每行两个整数 u, v，表示一个区域的起始点和终止点的坐标。

输出格式

输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

输入输出样例

输入: #1

1
2
3
4
500 3
150 300
100 200
470 471

输出: #1

1
298

说明&提示

数据范围

  • 对于 20% 的数据，保证区域之间没有重合的部分。
  • 对于 100% 的数据，保证 1 ≤ l ≤ 104，1 ≤ m ≤ 100，0 ≤ u ≤ v ≤ l。

解题思路

  1. 逐个标记
  2. 线段树(简单题没必要用这么复杂的做法。。。才不是不会呢)

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <vector>
using namespace std;

class Solution {
public:
    int CountTree(int s, vector<vector<int>>& nums) {
        vector<int> vis(s + 1, 1);
        for (vector<int>& loc : nums) {
            int start = loc[0], end = loc[1];
            for (int i = start; i <= end; ++i) {
                vis[i] = 0;
            }
        }
        int cnt = 0;
        for (int i : vis) {
            cnt += i;
        }
        return cnt;
    }
};

int main() {
    Solution s;
    int l, n;
    scanf("%d%d", &l, &n);
    vector<vector<int>> nums(n, vector<int>(2));
    for (int i = 0; i < n; ++i) {
        int start, end;
        scanf("%d%d", &start, &end);
        nums[i][0] = start;
        nums[i][1] = end;
    }
    printf("%d", s.CountTree(l, nums));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt(), m = sc.nextInt();
        int[] tree = new int[l + 1];
        for (int i = 0; i < m; ++i) {
            int start = sc.nextInt(), end = sc.nextInt();
            for (int j = start; j <= end; ++j) {
                tree[j] = 1;
            }
        }
        sc.close();
        int cnt = 0;
        for (int i : tree)
            cnt += i;
        System.out.println(l + 1 - cnt);
    }
}

P1427 小鱼的数字游戏

题目描述

小鱼最近被要求参加一个数字游戏，要求它把看到的一串数字 ai（长度不一定，以 0 结束），记住了然后反着念出来（表示结束的数字 0 就不要念出来了）。这对小鱼的那点记忆力来说实在是太难了，你也不想想小鱼的整个脑袋才多大，其中一部分还是好吃的肉！所以请你帮小鱼编程解决这个问题。

输入格式

一行内输入一串整数，以 0 结束，以空格间隔。

输出格式

一行内倒着输出这一串整数，以空格间隔。

输入输出样例

输入: #1

1
3 65 23 5 34 1 30 0

输出: #1

1
30 1 34 5 23 65 3

说明&提示

对于 100% 的数据，保证 0 ≤ ai ≤ 231 − 1，数字个数不超过 100。

解题思路

用数组存储最后逆序输出即可

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
int nums[107];
int main() {
    int i = -1, s;
    scanf("%d", &s);
    while (s != 0) {
        nums[++i] = s;
        scanf("%d", &s);
    }
    while (i >= 0) {
        printf("%d ", nums[i--]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import Java.util.*;

public class Main {
    static int[] nums = new int[107];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = -1, s = sc.nextInt();
        while (s != 0) {
            nums[++i] = s;
            s = sc.nextInt();
        }
        while (i >= 0) {
            System.out.print(nums[i--] + " ");
        }
        sc.close();
    }
}
1
print(" ".join(input().split()[-2::-1]))

P2141 [NOIP2014 普及组] 珠心算测验

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

(本题目为2014NOIP普及T1)

输入格式

共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。

第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

输出格式

一个整数，表示测验题答案。

输入输出样例

输入: #1

1
2
4
1 2 3 4

输出: #1

1
2

说明&提示

【样例说明】

由1 + 2 = 3, 1 + 3 = 4，故满足测试要求的答案为2。

注意，加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于100%的数据，3 ≤ n ≤ 100，测验题给出的正整数大小不超过10, 000。

解题思路

求满足 a + b = c 且 a, b, c 均在所给集合中的 c 的数量

枚举其中两个数即可得到第三个数，检查第三个数是否在集合中即可

也可以枚举 c 然后双指针查找另外两个数(要求数组要先排序)，时间复杂度不变

时间复杂度：O(n2) 时间界在于枚举两个数，双指针法同理 空间复杂度：O(n)

解答代码

方法一：枚举+集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, v;
    scanf("%d", &n);
    unordered_set<int> s;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &v);
        s.emplace(v);
    }
    unordered_set<int> ans;
    for (auto i = s.begin(); i != s.end(); i++) {
        for (auto j = next(i); j != s.end(); j++) {
            if (s.find(*i + *j) != s.end())
                ans.emplace(*i + *j);
        }
    }
    printf("%d", ans.size());
    return 0;
}

方法二：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import Java.util.*;

public class Main {
    static int[] nums = new int[107];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = sc.nextInt();
        }
        sc.close();
        Arrays.sort(nums);
        int cnt = 0;
        // A + B = C
        for (int i = 0; i < n; ++i) {
            // 枚举C，双指针查找 A,B
            int C = nums[i];
            int left = 0, right = i - 1;
            while (left < right && nums[left] + nums[right] != C) {
                int s = nums[left] + nums[right];
                if (s < C)
                    left++;
                else if (s > C)
                    right--;
            }
            if (left < right && nums[left] + nums[right] == C)
                cnt++;
        }
        System.out.println(cnt);
    }
}

P5594 【XR-4】模拟赛

题目描述

X 校正在进行 CSP 前的校内集训。

一共有 n 名 OIer 参与这次集训，教练为他们精心准备了 m 套模拟赛题。

然而，每名 OIer 都有各自的时间安排，巧合的是，他们在接下来的 k 天中都恰好有 m 天有空打模拟赛。

为了方便管理，教练规定一个人必须按顺序打完 m 套模拟赛题。

比如，小 X 在接下来的第 2, 3, 5 天有空打模拟赛，那么他就必须在第 2 天打第 1 套模拟赛题，第 3 天打第 2 套模拟赛题，第 5 天打第 3 套模拟赛题。

教练需要为每一个人的每一次模拟赛做准备，为了减小工作量，如果在某一天有多个人打同一套模拟赛题，那么教练只需要在这一天准备一场使用这一套题的模拟赛即可。

你作为机房大佬，教练想请你帮他计算一下，他每天需要准备多少场模拟赛。

输入格式

第一行三个整数 n, m, k。

接下来 n 行，每行 m 个整数，第 i 行第 j 列的整数 ai, j 表示第 i 个人在接下来的 k 天中第 j 个有空的日子为第 ai, j 天。

输出格式

一行 k 个整数，第 i 个整数表示接下来的第 i 天教练需要准备的模拟赛场数。

输入输出样例

输入: #1

1
2
1 3 5
2 3 5

输出: #1

1
0 1 1 0 1

输入: #2

1
2
3
4
5
6
7
6 3 7
2 3 4
2 5 7
3 5 7
1 3 5
5 6 7
1 2 3

输出: #2

1
1 2 3 1 3 1 1

输入: #3

1
2
3
4
5
6
7
8
9
10
11
10 10 20
2 3 4 8 9 11 12 16 17 18
2 3 6 10 12 13 14 15 19 20
1 3 7 10 11 13 14 15 17 19
1 2 4 6 7 9 15 17 19 20
2 3 5 6 9 11 14 16 19 20
1 2 3 8 9 10 11 12 15 19
1 4 6 7 9 12 13 17 18 19
1 7 8 9 10 11 13 15 18 20
1 5 6 7 8 9 13 16 18 19
4 5 7 10 11 13 14 17 18 20

输出: #3

1
1 2 2 3 2 2 4 3 3 3 3 4 2 1 3 1 2 2 2 1

说明&提示

本题采用捆绑测试。

  • Subtask 1（13 points）：n = m = k = 1。
  • Subtask 2（24 points）：n = 1。
  • Subtask 3（24 points）：m = 1。
  • Subtask 4（39 points）：无特殊限制。

对于 100% 的数据，1 ≤ n, m, k ≤ 103，m ≤ k，1 ≤ ai, 1 < ai, 2 < ⋯ < ai, m ≤ k。

解题思路

理顺题目就好，没什么难点

解答代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, k, d;
    scanf("%d%d%d", &n, &m, &k);
    vector<vector<int>> s(k + 1, vector<int>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &d);
            s[d][j] = 1;
        }
    }
    for (int i = 1; i <= k; ++i){
        int cnt = 0;
        for (int v: s[i]) {
            cnt += v;
        }
        printf("%d ", cnt);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import Java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt(), d;
        int[][] s = new int[k + 1][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                d = sc.nextInt();
                s[d][j] = 1;
            }
        }
        sc.close();
        for (int i = 1; i <= k; ++i) {
            int cnt = 0;
            for (int v : s[i])
                cnt += v;
            System.out.printf("%d ", cnt);
        }
    }
}
--- ♥ end ♥ ---

欢迎关注我呀~