C++ | 经典试题

[toc]

本文是备考时学习的一些较经典的例题

重要提示

  1. 注意整型溢出问题
  2. 注意题目中的特殊情况（边界、极值等）
  3. 程序 秒钟能执行的操作数大约为 108−10910^8-10^9
  4. 机考过程中无法得知自己的分数，因此做完之后需要自己构造一些数据进行测试，尽可能覆盖各种边界情况
  5. 根据刚刚得知的去年的题目，难度不大，主要在于细心，避免翻车
  6. 由于刚刚才得知去年的难度，原先推荐的CSP认证真题不再适合训练（太难了），现在推荐这个网站：http://ybt.ssoier.cn:8088/index.php 。只需要刷基础（一）：C++语言的题目即可，特别是其中循环和数组这两个章节的题目，大概率有原题或类似的题目！做不完也尽量把其中的例题做完（小声：http://ybt.ssoier.cn:8088/problem_show.php?pid=2045 个人猜测可能会有类似这道题的题目）
  7. 如果题目里要求保留x位小数，在输出的前一行加上这样一行代码：cout<<fixed<<setprecision(x); 把x换成题目要求的位数即可。（如果没用万能头文件（见“二、最基础的模板”）的话，需要加上这个头文件： #include<iomanip> ）
  8. 看清题目里的数据范围，数组的大小比最大的范围还要大一些，大两倍最保险！已经发现很多同学的代码都是因为数组开小了而导致错误！！！数组最大大概可以开到10的7次方到8次方（多维数组的话就是每一维乘积在10的7次方到10的8次方）。
  9. 机考使用devc++写代码，建议训练时也用这个
  10. 机考时可以带教材，把这份文档打印下来一页一页贴在书里带进考场也是允许的

基础模板

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    // 此处开始写你的代码
    return 0;
}

解释：

  1. 第一行为万能头文件，防止有些内置函数无法使用
  2. #define int long long 将所有 int 替换为 long long ，防止整型溢出
  3. signed main() 中的 signed 等同于 int ，但是由于我们将 int 替换为 long long 故这里需
    要用 signed

大小写转换

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>

using namespace std;

void change(char x) 
{
	x += 32;
	cout << x << endl;
}

int main() {
	char a;
	cin >> a;
	change(a);
	return 0;
}

思路

利用大小写字母的ASCII相差32，遍历字符串的每一个字符。

其他

  • a-z：97-122
  • A-Z：65-90
  • 0-9：48-57

大小写字母相差32，可用于大小写转换。
数字和大写字母相差17，和小写字母相差49，可用于进制转换。

计算圆的周长和面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
#define PI 3.14

class Circle
{
public:
	Circle(double radius) {
		this->C = 2 * PI * radius;
		this->S = PI * radius * radius;
		cout << this->C << " " << this->S << endl;
	}
	double S;
	double C;
};
int main() {
	double radius;
	cin >> radius;
	Circle a(radius);
	return 0;
}

判断是否是闰年

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

int main()
{
    int year;
    cin >> year;
    if((year % 4 == 0 && year % 100) || (year % 400 == 0))
    {
        cout << year << "是闰年" << endl;
    }
    else
    {
        cout << year << "不是闰年" << endl;
    }
    return 0;
}
1
2
3
4
5
// 判断year这一年是不是闰年
bool is_leap_year(int year)
{
    return year % 400 == 0 || year % 4 == 0 && year % 100;
}

思路

四年一闰，百年不闰，四百年再闰。

打点滴问题

在医院打点滴（吊针）的时候，如果滴起来有规律，先是滴一滴，停一下；然后滴二滴，停一下；再滴三滴，停一下…，现在有一个问题：这瓶盐水一共有v毫升，每一滴是d毫升，每一滴的速度是一秒（假设最后一滴不到d毫升，则花费的时间也算一秒），停一下的时间也是一秒，这瓶水什么时候能滴完呢？(0 < d < v <6000)

输入：一滴是多少毫升和一瓶盐水有多少毫升，中间用空格隔开.

输出：滴完需要多少时间.

解题

思路

杨辉三角

解题

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
#include <iomanip>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define int long long

int a[110][110];

signed main()
{
    int n;
    cin >> n;
    a[1][1] = 1;
    //计算杨辉三角
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
        }
    }
    //输出前n行
    for (int i = 1; i<= n;i++)
    {
        for (int j = 1; j<=i; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

判断素数

1
2
3
4
5
6
7
8
9
10
11
12
//判断是不是素数
bool is_prime(int x)
{
    for (int i = 2; i <= x / i; i++)
    { // 防止溢出，使用了i<=x/i的写法
        if (x % i == 0)
        {
            return false;
        }
    }
    return x != 1; // 需要注意的就是1不是素数
}

斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    // 这里用前50项作为演示，实际上第50项就已经超出int的范围，需要用long long
    int a[55] = {0, 1, 1};//初始化数组前三项分别为0, 1, 1
    for (int i = 3; i <= 50; i++)
    {
        a[i] = a[i - 2] + a[i - 1];
    }
    // 此时a[i]代表斐波那契数列第i项的值
    return 0;
}

数组排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>//vector需要用
#include <algorithm>//sort()需要用

using namespace std;

void work()
{                     // 定义一个函数work，不接受任何参数，也不返回任何值
    int n;            // 定义一个整数变量n，用来存储输入的个数
    cin >> n;         // 从标准输入读取一个整数，赋值给n
    vector<int> a(n); // 定义一个整数向量a，大小为n，用来存储输入的数据 // 如果是小数就把int改成double，是字符串就改成string
    for (int i = 0; i < n; i++)
        cin >> a[i];          // 用一个循环，从标准输入读取n个整数，依次存入向量a的每个位置
    sort(a.begin(), a.end()); // 调用sort函数，对向量a从头到尾进行排序 // 此时a数组中即为从小到大排好序的数据
    for (int i = 0; i < n; i++)
        cout << a[i] << " "; // 用一个循环，从向量a的每个位置依次取出数据，并用空格隔开打印到标准输出 // 输出数据，题目要求从大到小的顺序就倒着输出
}

最大公约数、最小公倍数

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h> //__gcd需要使用

int gcd(int a, int b)
{
    return __gcd(a, b); // __gcd是一个内置函数（需要使用万能头文件），可以直接返回两个数的最大公约数，其中__就是两个下划线
}
int lcm(int a, int b)
{
    return a * b / __gcd(a, b);
}

求 ab%pa^b \% p 的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 计算a的b次方对p取模的结果，也就是(a^b) mod p。它使用了快速幂算法，可以在O(log b)的时间复杂度内完成计算。
// 定义一个函数ipow，接受三个整数参数a,b,p
int ipow(int a, int b, int p)
{
    int res = 1; // 初始化结果为1
    while (b)
    { // 当b不为0时，循环执行以下操作
        if (b & 1)
        {
            res = res * a % p;
        }              // 如果b的最低位是1，说明当前项需要乘到结果中，所以用res乘以a再对p取模
        a = a * a % p; // 将a自乘再对p取模，相当于计算下一项的系数
        b >>= 1;       // 将b右移一位，相当于除以2，去掉最低位
    }
    return res; // 返回最终结果
}

约瑟夫问题

n个人标号0, 1, …, n-1 。逆时针站一圈，从 0号开始，每一次从当前的人逆时针数 k个，然后让
这个人出局。

  • 输出每一次出局的人的编号
  • 问最后剩下的人是谁
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
//输出每一次出局的人的编号
#include <iostream>
#include <vector>//vector需要用
#include <algorithm>//sort()需要用
#include <deque> //deque要用

using namespace std;

void josephus(int n, int k)
{
    deque<int> q;
    for (int i = 0; i < n; i++)
        q.push_back(i);
    while (!q.empty())
    {
        int cnt = 0;
        while (++cnt < k)
        {
            q.push_back(q.front());
            q.pop_front();
        }
        cout << q.front() << " "; // 这里的编号是从0开始的，若题目中人的编号从1开始，则需要+1
        q.pop_front();
    }
}
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
//最后出局的人
// 当n<10的8次方时使用
int josephus(int n, int k)
{
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = (res + k) % i;
    return res; // 这里的编号是从0开始的，若题目中人的编号从1开始，则需要+1
}
// 当n>10的8次方时使用
int josephus(int n, int k)
{
    if (n == 1)
        return 0;
    if (k == 1)
        return n - 1;
    if (k > n)
        return (josephus(n - 1, k) + k) % n;
    int res = josephus(n - n / k, k);
    res -= n % k;
    if (res < 0)
        res += n;
    else
        res += res / (k - 1);
    return res; // 这里的编号是从0开始的，若题目中人的编号从1开始，则需要+1
}

判断回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
// 使用string进行存储
bool is_leap(string s)
{
    int lens = s.size() - 1;
    for (int i = 0; i < lens / 2; i++)
    {
        if (s[i] != s[lens - i])
        {
            return false;
        }
    }
    return true;
}

数组排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void work()
{                     // 定义一个函数work，不接受任何参数，也不返回任何值
    int n;            // 定义一个整数变量n，用来存储输入的个数
    cin >> n;         // 从标准输入读取一个整数，赋值给n
    vector<int> a(n); // 定义一个整数向量a，大小为n，用来存储输入的数据
    // 如果是小数就把int改成double，是字符串就改成string
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }                         // 用一个循环，从标准输入读取n个整数，依次存入向量a的每个位置
    sort(a.begin(), a.end()); // 调用sort函数，对向量a从头到尾进行排序
    // 此时a数组中即为从小到大排好序的数据
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    } // 用一个循环，从向量a的每个位置依次取出数据，并用空格隔开打印到标准输出
      // 输出数据，题目要求从大到小的顺序就倒着输出
}

括号匹配

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
40
41
42
43
#include <iostream>
#include <vector>    //vector需要用
#include <algorithm> //sort()需要用
#include <deque>
#include<stack>

using namespace std;

int main()
{
    string str;    // 字符串，输入的东西
    stack<char> s; // 存符号的栈
    cin >> str;    // 读入
    for (int i = 0; str[i]; i++)
    { // 遍历一遍字符串
        if (str[i] == '<' || str[i] == '(' || str[i] == '[' || str[i] == '{')
        { // 如果是左括号
            s.push(str[i]);
        }
        else
        { // 否则是右括号
            if (s.empty())
            { // 如果数组是为空的，说明这个字符串多出一个右括号，肯定是错的
                cout << "no" << endl;
                return 0;
            }
            else if ((str[i] == '>' && s.top() == '<') || (str[i] == ')' && s.top() == '(') || (str[i] == ']' && s.top() == '[') || (str[i] == '}' && s.top() == '{'))
            { // 如果匹配
                s.pop();
            }
            else
            { // 否则不匹配，那就是错误的
                cout << "no" << endl;
                return 0;
            }
        }
    }
    if (s.empty())
        cout << "yes" << endl; // 为空，说明都能匹配
    else
        cout << "no" << 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
23
24
25
26
int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), q(n + 1);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int cur = 0;
    q[0] = -2e9;
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = cur;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i])
                l = mid;
            else
                r = mid - 1;
        }
        cur = max(cur, r + 1);
        q[r + 1] = a[i];
    }
    cout << cur;
    return 0;
}

HJ1 字符串最后一个单词的长度

描述

计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
输入描述：
输入一行，代表要计算的字符串，非空，长度小于5000。

输出描述：
输出一个整数，表示输入字符串最后一个单词的长度。

1
2
3
4
5
6
7
示例1
输入：
hello nowcoder
输出：
8
说明：
最后一个单词为nowcoder，长度为8

思路

用一个字符串保存每次输入的值，持续输入至不再输入，此时输出字符串长度即可。

解题

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>

using namespace std;

int main()
{
    string str;
    while(cin>>str);
    int len = str.length();
    cout << len << endl;
}

其他

求字符串长度

  • sizeof() 是操作数所占空间的字节数大小，是一个基本运算符，参数可以是可以类型、指针、数组、函数，获得保证能容纳实现所建立的最大对象的字节大小，这个值在编译的时候就已经计算完成，不能用于动态分配内存。例如
1
2
3
char str[30];
gets(str); //输入12345
cout << sizeof(str) << endl;

输出结果是30（字符数组长度），而不是5（输入的字符数）。

  • strlen() 是函数，用于计算 字符串 的长度，\0 作为终止符，可以用于动态内存。
  • size()
  • length()

HJ2

描述

写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）

数据范围：1≤n≤10001≤n≤1000

输入描述：
第一行输入一个由字母、数字和空格组成的字符串，第二行输入一个字符（保证该字符不为空格）。

输出描述：
输出输入字符串中含有该字符的个数。（不区分大小写字母）

1
2
3
4
5
输入：
ABCabc
A
输出：
2

思路

解题

其他

HJ3 明明的随机数

描述

明明生成了 NN 个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。

数据范围：
1≤n≤10001≤n≤1000，输入的数字大小满足 1≤val≤5001≤val≤500

输入描述：
第一行先输入随机整数的个数 N 。 接下来的 N 行每行输入一个整数，代表明明生成的随机数。 具体格式可以参考下面的"示例"。

输出描述：
输出多行，表示输入数据处理后的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入：
    3
    2
    2
    1
输出：
    1
    2
说明：
输入解释：
第一个数字是3，也即这个小样例的N=3，说明用计算机生成了3个1到500之间的随机整数，接下来每行一个随机数字，共3行，也即这3个随机数字为：
    2
    2
    1
所以样例的输出为：
    1
    2

思路

使用一个bool数组 arr 来储存数字输入的状态，有此数字输入，对应的 arr[i] 为 true，其余为false，输出时 arr[i] 为真，输出 i，否则不输出。

解题

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
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int N = 0;
    cin >> N;
    bool arr[1001];
    memset(arr, false, sizeof(arr));
    for (int i = 1; i <= N; i++)
    {
        int x;
        cin >> x;
        arr[x] = true;
    }
    for (int i = 1; i <= 1001; i++)
    {
        if (arr[i] == true)
        {
            cout << i << endl;
        }
    }
    return 0;
}

HJ4 字符串分隔

描述

  • 输入一个字符串，请按长度为8拆分每个输入字符串并进行输出；
  • 长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。

输入描述：
连续输入字符串(每个字符串长度小于等于100)

输出描述：
依次输出所有分割后的长度为8的新字符串

思路

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

using namespace std;

int main() 
{
    string str;
    while (cin >> str) {
        while (str.length() % 8) {
            str += '0';
        }
        for (int i = 0; i < str.length() / 8; i++) {
            cout << str.substr(i * 8, 8) << endl;
        }
    }
    return 0;
}

HJ5 进制转换

描述

思路

诸葛读取字符串，

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>

using namespace std;

int main() {
    std::string a;
    std::cin >> a;
    int b = 0;
    int c = 1;
    for (int i = a.size() - 1; i >= 2; i--) {
        int temp = (int)a[i];
        if (temp >= 65) {temp = temp - 55;}
        if (temp >= 48) {temp = temp - 48;}
        b += temp *  c;
        c = 16 * c;
    }
    std::cout << b;
}

其他

字符串匹配

解题

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/* CCF201409-3 字符串匹配 */

#include <iostream> // 引入输入输出流头文件
#include <cctype>   // 引入字符处理头文件
#include <string>   // 引入字符串头文件

using namespace std; // 使用标准命名空间

int main()
{
    string key, s, st; // 定义三个字符串变量，key是关键字，s是原始字符串，st是转换后的字符串
    int option, n;     // 定义两个整数变量，option是匹配模式，n是输入的字符串个数
    // 读入数据
    cin >> key >> option >> n; // 从标准输入读入关键字，匹配模式和字符串个数
    // 将字符串key中的大写字符转换为小写字符
    if (option == 0) // 大小写无关
    {
        for (int i = 0; key[i]; i++) // 遍历关键字中的每个字符
        {
            if (isupper(key[i])) // 如果是大写字符
            {
                key[i] = tolower(key[i]); // 转换为小写字符
            }
        }
    }
    // 循环处理若干输入，并输出结果
    for (int i = 1; i <= n; i++) // 对于每个输入的字符串
    {
        cin >> s;        // 从标准输入读入原始字符串
        if (option == 0) // 大小写无关
        {
            st = s;                     // 将原始字符串赋值给转换后的字符串
            for (int i = 0; st[i]; i++) // 遍历转换后的字符串中的每个字符
            {
                if (isupper(st[i])) // 如果是大写字符
                {
                    st[i] = tolower(st[i]); // 转换为小写字符
                }
            }
            int pos = st.find(key); // 在转换后的字符串中查找关键字，返回第一次出现的位置，如果没有找到则返回-1
            if (pos >= 0)           // 如果找到了关键字
            {
                cout << s << endl; // 输出原始字符串，并换行
            }
        }
        else // option = 1，大小写有关
        {
            int pos = s.find(key); // 在原始字符串中查找关键字，返回第一次出现的位置，如果没有找到则返回-1
            if (pos >= 0)          // 如果找到了关键字
            {
                cout << s << endl; // 输出原始字符串，并换行
            }
        }
    }
    return 0; // 程序正常结束，返回0
}

求解一个序列中出现次数最多的数字

用数组模拟哈希表（用于记录每个数字出现的个数），遍历一遍哈希表找出现自处最多且值最小的数

时间复杂度预估：1000 + 10000（1000为读入数组 ，10000为遍历数组）

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 <algorithm>
#include <cstring>
using namespace std;

const int N = 10010;

int a[N]; //用数组模拟哈希表，下标为当前出现的数，数组内部记录该数出现的次数
int n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        a[x] ++;
    }
    int res = 0; //记录出现最大那个数
    for (int i = 0; i < N; i ++)
    {
        if(a[i] > a[res]) res = i;
    }
    
    cout << res;
    return 0;
}

ISBN校验码

计算识别码

用字符串储存ISBN，求和至s.length()-2即可。

检验识别码

比对计算出的校验码和输入的校验码，需要转换字符和整形。将字符型数字转化为整型实际数字时需要-‘0’，而整形变为字符型时需要+'0'。比对正确则输出Right，错误则进行更正。

方案

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
40
41
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

string s;
int main()
{
    cin >> s;
    // 求解识别码
    int sum = 0;
    int j = 1; // 权数
    for (int i = 0; i < s.length() - 1; i++)
    {
        if (s[i] != '-')
        {
            sum += (s[i] - '0') * j++;
        }
    }
    // 计算余数，此时余数是整数形式，需要后续加上ASCII码48才能变成字符型的数字
    char c = sum % 11;
    if (c == 10)
    {
        c = 'X';
    }
    else
    {
        c += '0';
    }
    // 比较识别码
    if (c == s[s.length() - 1])
    {
        cout << "Right" << endl;
    }
    else
    {
        s[s.length() - 1] = c;
        cout << s << endl;
    }
    return 0;
}

代码思路

这是一段用于判断ISBN号码校验码是否正确的代码，与之前简单的ISBN校验代码相比，这里还加入了对于分隔符的处理。

具体实现方式：

  1. 读入输入的ISBN号码。
  2. 遍历ISBN号码中除最后一位外的所有字符，计算权值和sum。对于每个字符，如果不是分隔符，就将其表示的数字乘以权值 j，并将 j 增加 1。
  3. 计算 sum 对 11 取模后得到的余数，并将余数转换为对应的字符 c。如果余数为 10，则将字符 c 赋值为 ‘X’，否则将其转换为数字对应的字符。
  4. 如果计算得到的 c 与输入的ISBN号码中的最后一位相同，表示校验码正确，则输出 “Right”。
  5. 否则，需要修正输入的ISBN号码中的校验码，将其替换为计算得到的校验码，并输出修改后的ISBN号码。

该算法时间复杂度为O(n)，其中n为读入的ISBN号码的长度。因为需要对于ISBN号码中的每个字符进行遍历和计算，时间复杂度与ISBN号码的长度成正比。

其他

字符减’0’可以到相应的整数。
在C++中，使用string定义的字符串变量中，每个字符都是一个ASCII码值。例如，字符’0’的ASCII码值是48，字符’1’的ASCII码值是49，以此类推。减去字符’0’的原因是，字符在计算机中是用ASCII码表示的，ASCII码是一个整数值，表示字符的编码。例如，字符’0’的ASCII码是48，字符’1’的ASCII码是49，依次类推，字符’9’的ASCII码是57。如果我们直接用s[i]乘以j，那么得到的是字符的ASCII码乘以权重，而不是字符表示的数字乘以权重。为了得到正确的数字，我们需要用s[i]减去字符’0’，这样就可以把字符的ASCII码转换为数字。例如，如果s[i]是字符’5’，那么s[i] - '0’就等于53 - 48，也就是5。这样就可以得到正确的加权值。

相反数

解题

相反数的绝对值相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <stdlib.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int ans = 0;       // 统计对数
    int a[1001] = {0}; // 初始化整形数组，统计出现次数
    for (int i = 1; i <= n; i++)
    {
        int temp = 0;
        cin >> temp;
        int tempabs = abs(temp);
        a[tempabs]++;
        // 如果出现过两次，a[tempabs]就会等于2，用ans来统计对数即可
        if (a[tempabs] == 2)
            ans++;
    }
    cout << ans << endl;
    return 0;
}

代码思路

该代码是一个统计绝对值相同的数字对个数的程序，其思路为：

  1. 读入n个整数，然后每次读入一个数temp，计算它的绝对值tempabs。
  2. 使用大小为1010的数组a来统计每个绝对值出现的次数。将a[tempabs]加1。
  3. 每次将a[tempabs]加1后，如果a[tempabs]为2，说明当前这个绝对值出现了两次，可以构成一个数字对，将ans加1。
  4. 最后输出ans即为所求的绝对值相等的数字对个数。

需要注意的是，这里用到了 计数排序 的思想，将每个数的绝对值作为数组a的下标，这样能够节省查找是否有相同绝对值的数的时间，从而提高代码效率。

其他

还可以利用相反数相加为0的思想：

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0; i < n; i++)
{
        int temp = 0, Temp = 0;
        cin >> temp;
        Temp = abs(temp);
        A[Temp] += temp;
        if(A[Temp] == 0) 
        {
            cnt++；
        }
}

相差为1的数对

解题

方法一（暴力）

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>

using namespace std;

int N[1000];
int n; // 整数个数
int m; // 对数

int main()
{
    N[1000] = 0;
    cin >> n;
    if (n >= 1 && n <= 1000)
    {
        for (int i = n; i; i--)
        {
            int k = i;
            cin >> N[i];
        }
        for (int k = 1; k <= n; k++)
        {
            for (int j = k; j <= n; j++)
            {
                if (abs(N[k] - N[j]) == 1)
                {
                    m++;
                }
            }
        }
        cout << m << 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
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>

using namespace std;

int N[1000];
int n; // 整数个数
int m; // 对数

int main()
{
    N[1000] = 0;
    cin >> n;
    if (n >= 1 && n <= 1000)
    {
        for (int i = n; i; i--)
        {
            int k = i;
            cin >> N[i];
        }
        sort(N, N + (n + 1));
        for (int i = 1; i < n; i++)
        {
            if (abs(N[i] - N[i + 1]) == 1)
            {
                m++;
            }
        }
        cout << m << endl;
    }
    return 0;
}

代码思路

  • 第一种方法是暴力求解
  • 第二种方法是利用sort()，形成相邻递增数列，减少求解次数。

核心思路

  • 输入数组
  • 判断条件，符合条件则计数器++

其他

用到了sort()，在此做笔记

1
2
3
4
5
6
7
#include <algorithm>

int main()
{
    int arr[10];
    sort(arr, arr+10);
}

sort()函数可以对给定区间所有元素进行排序。它有三个参数sort(begin, end, cmp)，其中begin为指向待sort()的数组的第一个元素的指针，end为指向待sort()的数组的最后一个元素的下一个位置的指针，cmp参数为排序准则，cmp参数可以不写，如果不写的话，默认从小到大进行排序。如果我们想从大到小排序可以将cmp参数写为greater<int>()就是对int数组进行排序，当然<>中我们也可以写double、long、float等等。如果我们需要按照其他的排序准则，那么就需要我们自己定义一个bool类型的函数来传入。比如我们对一个整型数组进行从大到小排序：