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

字符串

  • 一个带空格的句子的存储办法可以是str[100]这样的指定长度的字符串（C语言风格）
  • 另一种办法是用封装好的字符串类string（C++风格），动态分配长度
    • 可以进行赋值、连接、获取长度等操作

类型 char string
定义 char str[size] string s
求长度 函数strlen(str)，操作运算符sizeof(str) 成员函数length()、成员函数size()，也可以转换为char*类型,使用char的strlen（通过s.c_str()）
复制 strcpy(str1, str2) s1 = s2
整行输入 cin.getline(str, needsize) getline(cin, s)
备注 空字符也要算入needsize
读取及修改单个字符 str[i] s[i]

对字符串赋值

C语言

  1. C语言中，可以通过字符数组进行初始化。注意，不可以对数组名直接赋值。
    char str[10] = "China";//还可以写成char str[10] ;str[10] = "China";
  2. 使用strcpy函数进行初始化。需要注意的是，使用strcpy函数，strcpy(str1,str2)，字符数组1必须定义的足够大，以便容纳被复制的字符串2，避免数组越界。在C语言中，将一个字符串赋值给另一个字符串，只能使用strcpy函数，但是，可以使用赋值号实现对单个字符的赋值，此时需要注意的是，结束后一定要自行添加 ‘\0’。
1
2
3
4
5
6
7
int main()
{
	char str1[10],str2[] = "China";
	strcpy(str1, str2);//此行代码还可以写为 strcpy(str1,"China");
	printf("str1 = %s", str1);
	return 0;
}

string

按单词分隔

1
2
3
4
5
6
7
8
9
string str;
getline(cin, str); //整行输入
   isstringstream ss(str); // 将字符串 str 转换为输入流 ss
   vector<string> ops; // 定义一个向量 ops，用于存储分割后的单词
   string op; // 定义一个字符串 op，用于存储每个单词
   while (ss >> op) // 从输入流 ss 中读取一个单词，赋值给 op，直到 ss 为空
   {
       ops.push_back(op); // 将 op 追加到 ops 的末尾
   }

查找

从str里找a，默认从第0个字符开始查找
str.find(a, 0)

数组

蛇形输出

思路就是：判断是否再边界内且未曾填过数，从而确定是否填入数字，用while循环依次从右上到右下再到左下再到左上再到右上，进行循环。一共填入n*n 个数字，所以最大值也是 n*n

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
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int a[30][30] = {0};

int main()
{
    int x, y, d, n;
    cin >> n;
    d = 1;
    x = 0;
    y = n - 1;
    memset(a, 0, sizeof(a));
    a[x][y] = 1;
    while (d < n * n)
    { // 向下填数
        while (x < n - 1 && !a[x + 1][y])
        {
            a[++x][y] = ++d;
        }
        // 向左填数
        while (y > 0 && !a[x][y - 1])
        {
            a[x][--y] = ++d;
        }
        // 向上填数
        while (x > 0 && !a[x - 1][y])
        {
            a[--x][y] = ++d;
        }
        // 向右填数
        while (y < n - 1 && !a[x][y + 1])
        {
            a[x][++y] = ++d;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

排序

用到了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类型的函数来传入。比如我们对一个整型数组进行从大到小排序

输入输出

输出
printf 的输出
使用格式控制符来指定输出的格式。格式控制符以 % 开头，可以和其他字符组合使用。基本的语法是：printf("格式控制", 内容);
格式控制 可以把内容进行格式化，例如 %d 十进制整数、%o 八进制整数、%c 一个字符、%s 字符串、%f 小数形式输出实数（包括单精度、双精度）、%e 指数形式输出实数、%g 字段选择小数形式或指数形式输出，且不输出无意义的0.
m 可确定输出范围，n 确定小数位数

特别地，对于字符串

  • %ms：输出的字符串占m列，如字符串本身长度大于m，则突破获m的限制,将字符串全部输出。若串长小于m，则左补空格。
  • %-ms：如果串长小于m，则在m列范围内，字符串向左靠，右补空格。
  • %m.ns：输出占m列，但只取字符串中左端n个字符。这n个字符输出在m列的右侧，左补空格。

输入

  • C语言可使用
    • scanf()，读取不包括空格和终止符（默认换行符）
    • fgets()
  • C++中可使用
    • cin >>类似于scanf()，是std中的。
    • cin.get()读取单个或指定长度字符，读取包括空格，不包括终止符（默认换行符）。
    • cin.getline()读取指定长度的字符，读取包括空格，不包括终止符，且读取完成后会把输入流设定为Fail状态。可用于char str[100]这样的char类型的字符串整行输入cin.getline(str, sizeof(str))。
    • getline 读取所有空白字符（整个缓存区），不包括换行符，读取完后无残留。是字符串流的函数，只能读取string对象，使用时需要包含头文件<stirng>。可用于string s这样的的string类型的字符串的整行输入getline(cin, s);。

小数位数控制

  1. c语言printf格式化："%.nf"，n是输出的小数位数，默认6位
  2. c++引用<iomanip>，cout << fixed << setprecision(2);控制输出位数，此后输出的都是2位小数

百分数的输出
C语言 printf 中，在%前面再加一个%

字符的ASCII码
就是char转换int的值

第n位数的获取
对于一个n位数，求任意第m位数其实都一样，就是两个思路：

  • 用/得到任意位数的首位数，用%得到末位数字
  • 对于中间位数也就是第m位数，可以把这个n位数用除法变成n-m位数，也就相当于把这个中间位数用除法变到末位，用%得到末位数字

可以获得最右边的数，然后逐次除以10向左继续获取下一位

取整问题

  • 向上取整ceil
  • 向下取整floor
  • 四舍五入round
  • 朝0方向取整fix，正数向下取，负数向上取

最大公约数
c++直接用现成的库函数__gcd(a, b)，属于库algorithm

同理可求出最小公倍数=a * b / __gcd(a, b)

大小写转换

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

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;
}
  • 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;
}

杨辉三角

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
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;
}