[NOIP2005 普及组] 校门外的树

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

1
298

提示

【数据范围】

  • 对于 $20\%$ 的数据，保证区域之间没有重合的部分。
  • 对于 $100\%$ 的数据，保证 $1 \leq l \leq 10^4$，$1 \leq m \leq 100$，$0 \leq u \leq v \leq l$。

【题目来源】

NOIP 2005 普及组第二题

题解

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
37
38
39
#include <iostream>
#include <vector>
using namespace std;
int count_remaining_trees(int l, int m, const vector<pair<int, int>>& regions) {
    // 初始化马路上每个位置的树木数量为1
    vector<int> trees(l + 1, 1);

    // 遍历每个区域，将区域内的树木数量减去相应的数量
    for (const auto& region : regions) {
        int start = region.first;
        int end = region.second;
        for (int i = start; i <= end; ++i) {
            trees[i] = 0;
        }
    }
    // 统计数组中剩余树木的总数
    int remaining_trees = 0;
    for (int tree : trees) {
        remaining_trees += tree;
    }
    return remaining_trees;
}
int main() {
    int l, m;
    cin >> l >> m;

    // 读取区域信息
    vector<pair<int, int>> regions;
    for (int i = 0; i < m; ++i) {
        int start, end;
        cin >> start >> end;
        regions.push_back({start, end});
    }
    // 计算剩余树木数量并输出结果
    int result = count_remaining_trees(l, m, regions);
    cout << result << endl;

    return 0;
}

首先count_remaining_trees函数用来计算剩余树木的数量，regions存储区域和区域里的树，然后创建一个l+1的向量trees，用来表示马路每个位置的树木数量。然后遍历每个区域，让区域里的树木直接从1变成0，从而将剩余树木相加。main函数用来输入l（马路的长度）、m（区域的数量），并用循环读取每个区域的起始点和终止点，并存储在regions向量中，调用count_remaining_trees函数输出结果

[NOIP2012 普及组] 质因数分解

题目描述

已知正整数 $n$ 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

输入一个正整数 $n$。

输出格式

输出一个正整数 $p$，即较大的那个质数。

样例 #1

样例输入 #1

1
21

样例输出 #1

1
7

提示

$1 \le n\le 2\times 10^9$

NOIP 2012 普及组 第一题

题解

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
#include <iostream>
#include <cmath>
using namespace std;
int largest_prime_factor(int n) {
    int largest_prime = 1;

    // 处理输入为偶数的情况
    while (n % 2 == 0) {
        largest_prime = 2;
        n /= 2;
    }
    // 循环从 3 开始，每次增加 2
    for (int i = 3; i <= sqrt(n); i += 2) {
        while (n % i == 0) {
            largest_prime = i;
            n /= i;
        }
    }

    // 如果 n 是质数，则其本身就是最大质因数
    if (n > 2)
        largest_prime = n;
    return largest_prime;
}
int main() {
    int n;
    cin >> n;

    int result = largest_prime_factor(n);
    cout << result << endl;

    return 0;
}

首先largest_prime_factor函数主要是计算最大质因数，如果这个数是偶数，就不断除以2直到不能整除为止，这样就找到2这个质因数了。然后通过从3开始，每次增加2找到其他质因数，直到这个数成为质数为止。最后如果这个数大于2，那么这个数本身就是质数就赋值给largest_prime。main函数则是输入这个数，并通过largest_prime_factor函数找到最大质因数。

[NOIP2004 普及组] 不高兴的津津

题目描述

津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。

输入格式

输入包括 $7$ 行数据，分别表示周一到周日的日程安排。每行包括两个小于 $10$ 的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。

输出格式

一个数字。如果不会不高兴则输出 $0$，如果会则输出最不高兴的是周几（用 $1, 2, 3, 4, 5, 6, 7$ 分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。

样例 #1

样例输入 #1

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

样例输出 #1

1
3

提示

NOIP2004 普及组第 1 题

  • 2021-10-27：增加一组 hack 数据
  • 2022-06-05：又增加一组 hack 数据

题解

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
#include <iostream>
#include <vector>
using namespace std;
int calculate_happiness(const vector<pair<int, int>>& schedule) {
    int max_unhappiness = 0;
    int unhappiest_day = 0;

    for (int day = 0; day < 7; ++day) {
        int total_hours = schedule[day].first + schedule[day].second;
        if (total_hours > 8) {
            int unhappiness = total_hours - 8;
            if (unhappiness > max_unhappiness) {
                max_unhappiness = unhappiness;
                unhappiest_day = day + 1; // 天数从1开始
            }
        }
    }

    return unhappiest_day;
}
int main() {
    vector<pair<int, int>> schedule(7);

    // 读取输入
    for (int i = 0; i < 7; ++i) {
        int school_hours, extra_hours;
        cin >> school_hours >> extra_hours;
        schedule[i] = make_pair(school_hours, extra_hours);
    }
    // 计算并输出结果
    int result = calculate_happiness(schedule);
    cout << result << endl;

    return 0;
}

首先calculate_happiness函数用来计算总时长，如果总时长大于8个小时，就表示不高兴，然后记录不高兴的小时数和对应的天数，然后要比较不高兴的程度和天数，最后返回最不高兴的那一天的天数。main函数里则是创建pair类型的向量用来存储一周的小时数，用for循环将每天的时长存储到schedule向量里，最好输出calculate_happiness函数计算出的最不高兴的一天。

[NOIP2004 提高组] 津津的储蓄计划

题目描述

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 $300$ 元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上 $20\%$ 还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于 $100$ 元或恰好 $100$ 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如 $11$月初津津手中还有 $83$ 元，妈妈给了津津 $300$ 元。津津预计$11$月的花销是 $180$ 元，那么她就会在妈妈那里存 $200$ 元，自己留下 $183$ 元。到了 $11$ 月月末，津津手中会剩下 $3$ 元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据 $2004$ 年 $1$ 月到 $12$ 月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到 $2004$ 年年末，妈妈将津津平常存的钱加上 $20\%$ 还给津津之后，津津手中会有多少钱。

输入格式

$12$ 行数据，每行包含一个小于 $350$ 的非负整数，分别表示 $1$ 月到 $12$ 月津津的预算。

输出格式

一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出 $-X$，$X$ 表示出现这种情况的第一个月；否则输出到 $2004$ 年年末津津手中会有多少钱。

注意，洛谷不需要进行文件输入输出，而是标准输入输出。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
290
230
280
200
300
170
340
50 
90 
80 
200
60

样例输出 #1

1
-7

样例 #2

样例输入 #2

1
2
3
4
5
6
7
8
9
10
11
12
290 
230 
280 
200 
300 
170 
330 
50 
90 
80 
200 
60

样例输出 #2

1
1580

题解

1