题目描述：

输入一个整数n，输出它的各位数字之和

输入输出格式：

输入格式：

输入一个整数n

输出格式：

输出一个整数，表示n的各位数字之和

样例输入输出

样例输入#1：

1

3

样例输出#1：

1

3

样例输入#2：

1

136

样例输出#2：

1

10

解析

首先我们考虑一个问题：如何获取一个整数的第n位？
如果你没有思路，我们先把问题特殊化：如何获取一个整数的第1位，也就是个位数字？
首先，我们先详细介绍一下模运算和整除运算：
模运算，读作模，C++中的运算符为“%”。它的意义便是小学数学中的取余数
整除运算，读作整除，C++中的运算符为“/”（想不起来翻笔记去）。它的意义便是小学数学中和取余数一起出现的那个。。。
带大家回顾一下小学的带余数除法吧：
15 ÷ 2 = 7 …… 1
8 ÷ 4 = 2 …… 0
4 ÷ 9 = 0 …… 4
ps：如果你感觉自己上了假小学，那我没办法救你的呀。。。
所以，将上面的式子用我们今天的知识写出来，就是这样的：
15 / 2 = 7 15 % 2 = 1
8 / 4 = 2 8 % 4 = 0
4 / 9 = 0 4 % 9 = 4
为什么要提模运算呢？
我们发现，一个数的个位数等于这个数模10
eg：4 % 10 = 4
256 % 10 = 6
是不是很神奇！
但是我们的问题还是没有解决，我们只获取了个位，那其他位的数字怎么办？
我比较懒，所以我想到了：如果其他位也能变成个位该多好。。。
所以，现在我们思考，怎么把其他位变为个位
我们想到了整除运算：
eg：46 / 10 = 4
2775 / 100 = 27
天哪，一个整数整除10之后，十位变成了个位；整除100后，百位变成了个位；整除$ 10^{i - 1} $之后，第i位变成了个位！
综上，如果我们把一个整数n从右向左数第i位数字记为ai的话，则：

$ ai = (n / 10^{i-1}) $ % $ 10 $

小白：老师，指数怎么算。。
我们可以不用算指数
结合上面的知识，观察并理解下面一个过程：
1256 % 10 = 6 1256 / 10 = 125
125 % 10 = 5 125 / 10 = 12
12 % 10 = 2 12 / 10 = 1
1 % 10 = 1 1 / 10 = 0
如果你理解了这样的过程，那么你就能理解下面的代码了

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>

using namespace std;

int main() {
    int n, ans = 0;         //ans累加求得各位数字之和
    cin >> n;
    while(n) {              //等价于：while(n != 0)，判断是否已经累加完所有数字
        ans += n % 10;      //取当前的各位数字，累加到ans
        n /= 10;            //等价于：n = n / 10
    }
    cout << ans;
    return 0;
}

题目描述

输入n个整数，询问这些数中的最大值是多少？

输入输出格式

输入格式：

第1行：一个整数n，表示输入整数的个数
第2行：n个整数

输出格式：

一个整数，表示之前整数中的最大值

样例输入输出

样例输入#1：

1
2

5
3 5 6 4 1

样例输出#1：

1

6

解析

我们要做的就是求出输入数据中的最大值
我们可以这样做：每读入一个数，将这个数和我们读入这个数之前的最大值比较，如果这个数比之前的最大值要大，那么更新最大值，否则跳过这个数。当我们所有数都进行完上述判断之后，我们便得到了这组数据的最大值
思路很简单，但这里有一个问题：我们每次将读入的数和之前的最大值比较，那我们读第一个数的时候和什么比较呢？换句话说，我们的最大值应该怎么初始化呢？
这是一个令人头疼的问题，这里给出两种解决方式

将最大值赋值为第一个数据

我们将最大值赋值为第一个数据，相当于让第一个数据直接参与了和最大值的比较
如果后面有数据大于它，那么他会被更新
如果没有，那么它就是最大值
我们发现，这样的操作是可以达到我们的要求的
具体见代码1

假想极小值

我们可以将最大值初始化为一个极小值，我们后面的数据肯定要比这个极小值要大，因此，它会被后面的数据（往往是第一个数据）更新
在用这种方法时，我们一定要根据题目给出的数据范围理性分析，避免出现数据溢出/极小值不够小的问题
具体见代码2

实现的过程（以样例为例）：
先令maxn = -100000（感觉够小了）
下面开始读入数据：
1：3 > -100000，maxn变为3（这样就更新了最大值）
2：5 > 3，maxn变为5
3：6 > 5，maxn变为6
4：4 < 6，maxn不变，为6
5：1 < 6，maxn不变，为6
这样，我们就得到了这些数据中的最大值6

标程

代码1

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

#include <iostream>

using namespace std;

int main() {
    //我们不一定要用数组把所有数都存下来，可以边读边操作
    //对一个变量x循环进行读入就可以了
    //当然，如果我们要对数据进行更多更复杂的操作，那就应该读到数组里
    int n, x, maxn;
    cin >> n;
    cin >> maxn;                        //将最大值初始化为第一个数
    for(int i = 1; i <= n - 1; i++) {   //第一个数已经被读入了，只需要n-1次操作即可
        cin >> x;
        if(x > maxn)                    //如果这个数比前面的最大值更大，则更新最大值为这个数
            maxn = x;
    }
    cout << maxn;
    return 0;
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>

using namespace std;

int main() {
    int n, x, maxn = -100000;           //将最大值初始化为极小值
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x;
        if(x > maxn)                    //如果这个数比前面的最大值更大，则更新最大值为这个数
            maxn = x;
    }
    cout << maxn;
    return 0;
}

小结

记录最大值的方法，虽然算不上什么算法，但确实十分重要，是很多算法的基础。在很长时间的学习后，当你开始学习更高级的最大值维护方法的时候，你就离成功不远了~

题目描述

计算出1~n之间所有整数中，能被a或b整除的所有数的和

输入输出格式

输入格式：

输入仅一行，三个整数n，a，b

输出格式：

输出一个整数，表示所有满足条件的整数之和

样例输入#1：

1

20 2 3

样例输出#1：

1

137

样例输入#2：

1

160 23 25

样例输出#2：

1

1008

样例输入输出说明

样例1：
满足条件的数：2 + 3 + 4 + 6 + 8 + 9 + 10 + 12 + 14 + 15 + 16 + 18 + 20 = 137

解析

根据题意模拟即可

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <iostream>

using namespace std;

int main() {
    int n, a, b, sum = 0;
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++) {           //让i从1循环到n    
        if(i % a == 0 || i % b == 0)        //如果能被a或b整除
            sum += i;                       //累加
    }
    cout << sum;
    return 0;
}

题目背景

李老师家里要交水费了

题目描述

李老师这两个月用了x（x <= 200）方水，他所在的小区实行分段收费制度，在30方及以下的部分只收取5元/方的基础费用，30到80（包括80）方的部分要额外收取基础费用10%的水税（暂且认为有这种税），超过80的部分要额外收取基础费用30%的水税。李老师的计算器坏了，手机也没电了，他想让你设计一个程序，帮他算一算他应该交多少水费

输入输出格式

输入格式：

一行一个整数x，表示李老师的用水量

输出格式：

一个小数（保留2位小数），表示李老师需要交的水费

样例输入输出

样例输入#1：

1

15

样例输出#1：

1

75.00

样例输入#2：

1

85

样例输出#2：

1

457.50

解析

实质就是一个分段函数
最简单的思路就是把基础部分和额外部分(那个叫水税的东西）分开考虑
基础部分都是5 * x
再分情况讨论每个区间下的水税收取情况，两部分相加即可

标程

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

#include <cstdio>
/*
对于需要输出确定长度的，或输出n位小数的，我们一般用printf。这
也就是为什么让大家不要忘记printf和scanf的原因：在某些情况下，
他们要比cin和cout更为方便
*/

using namespace std;

int main() {
    int x;              //这里就不用初始化，当然初始化0也是没有问题的 
    cin >> x;
    if(x <= 30)         //第一档 
        printf("%.2lf", 5 * x);
    else if(x <= 80)    //第二档 
        printf("%.2lf", 5 * x + 5 * 0.1 * (x - 30));
    else                //都不是肯定是第三档 
        printf("%.2lf", 5 * x + 5 * 0.1 * 50 + 5 * 0.3 * (x - 80));
    return 0;
}

并查集是一种用来维护多个集合（或对象）之间集合关系的数据结构，在很多题目中可以直接应用。它也经常被用在图论的算法优化中，是一种简单实用，又十分重要的数据结构

题目引入

例题1

有n（1 <= n <= 20）个元素，分别属于编号为1-n的集合。现有t（1 <= t <= 20）次询问，每次询问对应如下两种操作：
A：将两个元素所在的集合合并
B：询问两个元素是否在同一集合中

解答：直接开数组模拟
对于操作A：遍历所有数组，寻找两个元素所在的集合，将一个集合中的元素全部移入另一个集合
对于操作B：依然遍历寻找集合，判断集合编号是否相同

例题2

题目要求不变，数据范围改为：1 <= n <= 10000, 1 <= t <= 200000

解答：暴力模拟肯定超时，需要并查集

定义

并查集是由若干树（又称森林）组成的。起始时所有结点无儿子，且父亲为它本身。

在合并操作后，如果两个节点属于同一棵树，那么他们属于同一个集合。换而言之，一棵树的所有节点构成一个集合
如图，将1合并到2后，1，2构成一棵树，则1，2属于同一个集合

实现

储存

我们一般使用数组来维护并查集：
定义一个fa（father）数组，记录每个结点的父节点
根据定义，每个结点的父亲需初始化为它自己，即fa[i] = i
代码如下：

1
2
3
4
5
6
7
8
9

//初始化部分
int fa[100005], n;
//n：集合个数

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        fa[i] = i;
}

基本操作

从字面上就能够看出，并查集的基本操作就是“并”和“查”，也就是例题中的两种操作
我们先来研究怎么“查”

查询

根据定义，我们不难得到这样的性质：

在并查集中，每个结点有且仅有一个最高祖先（即树的根），这个祖先的父亲是他自己

有了这样的性质，我们不难发现，判断两个结点是否属于同一个集合，等价于判断他们的最高祖先是否相同
那么，我们的核心任务便成了如何找到每个结点的最高祖先
我们只需要根据fa数组，寻找它的父亲，再寻找父亲的父亲，再寻找父亲的父亲的父亲……直到找到一个结点，它的父亲是它自己，那么我们就找到了最高祖先。
对于查询操作，我们常用递归写法，代码如下：

1
2
3
4
5
6

//查找部分
int find(int x) {
    if(x == fa[x])          //x == fa[x]当且仅当x为最高祖先
        return x;
    return find(fa[x]);     //递归找爸爸。。。
}

综上所述，我们判断两个结点x, y是否属于同一个集合，只需判断find(x)和find(y)是否相等即可

合并

那我们怎么将两个结点x, y所在的集合合并为一个集合呢？
我们只有一个fa数组，当然还是从它入手了
我们发现，除了根结点的fa可以用，其他的fa都不是空闲的：随意改变这些fa的值会让以它为根的子树从原集合脱离
所以我们还是要找到根，也就是最高祖先。之前的find()便派上用场了
如果我们现在找到了x的最高祖先t，那么我们只需要让fa[t] = y，以t为根的这棵树就成为了y这棵树的子树，那么根据定义，这两个集合便成为一个集合了
代码如下：

1
2
3
4
5

//合并操作（有漏洞）
void merge(int x, int y) {
    int t = find(x);
    fa[t] = y;
}

我们的想法是正确的，但是遗漏了一点：如果x和y本来就在一个集合中怎么办？如果按我们刚才的想法操作，那么并查集就可能会变成一个有环图，再次find的时候就会死循环
所以，我们还要先判断x, y是否属于同一个集合，如果属于，则不进行任何操作
到了这里，我们再回想之前的合并操作：我们直接将t并到了y上。其实，我们可以将t并在y的最高祖先上，不难发现这样的操作和刚才所能达到的效果是相同的。但是，之前的操作会使下次find的时间增加：合并后，如果find某个原来在x这棵树上的结点，那么它一定要先到y，再从y找到y的最高祖先。而如果直接合并到y的最高祖先，那么就可以跳过y到它的最高祖先这一段路径，时间复杂度减少O(y的深度)
代码如下：

1
2
3
4
5
6
7
8

//合并操作
void merge(int x, int y) {
    x = find(x);
    y = find(y);            //将x, y分别赋值为他们各自的最高祖先
    if(x == y)              //如果已经在一个集合，直接返回
        return;
    fa[x] = y;              //将x的最高祖先并到y的最高祖先
}

这就是并查集的基本操作，但是，如果数据喜（bian）人（tai），这样朴素的做法还是会超时。下一节将重点介绍并查集的优化策略