题目A：B2050 三角形判断

1、思路

设三条线段的长度分别为a、b、c，判断这三条线段能否构成三角形的充分必要条件为a+b>c&&b+c>a&&a+c>b，满足以上关系表达式即可认定这三条线段能构成三角形，反之则不能构成三角形

2、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main() {
	int a, b, c; // 定义三条线段 
	cin >> a >> b >> c; // 输入 
	if (a + b > c && b + c > a && a + c > b) { // 判断是否满足条件 
		cout << "1"; //  满足输出1 
	} else {
		cout << "0"; // 不满足输出0 
	}
	return 0;
}

题目B：B2047 分段函数

1、思路

由于分段函数的定义域没有交集，所以可以利用if-else分支结构判断定义域x的范围从而选择对应的分段函数输出

容易忽略的地方：题目要求输出结果保留三位小数

2、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int main() {
	double x, y; // 定义自变量x和因变量y 
	cin >> x;
	if (0 <= x && x < 5) { // 0 <= x < 5 时 
		y = -x + 2.5; 
	} else if (x >= 5 && x < 10) { // 5 <= x < 10时 
		y = 2 - 1.5 * (x - 3) * (x - 3);
	} else { // 其他情况，即 10 <= x < 20时 
		y = x / 2 - 1.5;
	}
	printf("%.3lf", y); // 题目要求y的结果保留三位小数 
	return 0;
}

问题C：B2112 石头剪子布

1、思路

本题要求实现一个程序来判断石头剪刀布游戏的结果，因为有N次游戏，不妨将判断程序封装成一个函数，利用函数返回值判断游戏结果，达到简化代码，增加复用性和可读性的效果

判断程序judge设计如下

1、返回值：类型为int ，有三个状态，0表示TIe，1表示Player1胜利， 2表示Player2胜利

2、形参列表：string x, string y， 分别表示 Player1，Player2 的选择

3、主体判断逻辑如下：

三种情况

①如果Player1，Player2的选择一样，即x == y，就说明Tie，返回0

②如果 x == “Rock” && y == “Scissors”
|| x == “Paper” && y == “Rock”
|| x == “Scissors” && y == “Paper”

即x为石头、y为剪刀或x为布、y为石头或x为剪刀、y为布时Player1胜利，返回1

③剩下的一种情况只能是Player2胜利，返回2

主函数接收对应的返回值并输出对应的提示文字即可

2、AC代码

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
#include <iostream>
using namespace std;
int judge(string x, string y) {
	if (x == y) { // Tie的情况 
		return 0; // 返回0 
	} else if (x == "Rock" && y == "Scissors" 
		|| x == "Paper" && y == "Rock"
		|| x == "Scissors" && y == "Paper") { // Player1胜利 
		return 1; // 返回1 
	} else { // Player2胜利 
		return 2; // 返回2 
	}
}
int main() {
	int n; // 定义游戏场次n 
	cin >> n; 
	while (n--) { // n次游戏，循环n次 
		string player1, player2; // 用于接收Player1和Player2的选择 
		cin >> player1 >> player2;
		int flag = judge(player1, player2); // flag用于接收judge函数返回值 
		if (flag == 0) { // 平手 
			cout << "Tie" << endl;
		} else if (flag == 1) { // Player1胜利 
			cout << "Player1" << endl;
		} else { // Player2胜利 
			cout << "Player2" << endl;
		} 
	}
	return 0;
}

问题D：P1789 【Mc生存】插火把

1、思路

本题要求判断方阵中有几个点会生成怪物

①我们可以用二维数组来实现方阵，二维数组的值有0和1，0代表会生成怪物的地方，1代表不会生成怪物的地方

二维数组定义如下

1
2
// 定义一个n * n的二维数组v, 初值均为0
vector<vector<int> > v(n, vector<int>(n, 0));

②可以用函数来模拟火把或萤石照亮填充方阵的过程，同时用一个全局变量cnt来统计当前方阵已填充点的个数

全局变量cnt定义如下

1
int cnt = 0; // 因为作用是统计当前方阵已填充点的个数，所以初始化为0

定义两个函数分别模拟火把和萤石

模拟火把：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 形参说明
// vector<vector<int> > &v 表示以引用的方式传入二维数组v
// int x和int y分别表示火把的坐标
void getFire(vector<vector<int> > &v, int x, int y) {
    // 枚举火把的过程代码量太大，这里选择用方向数组的形式来简化代码
    // 定义两个方向数组X和Y，分别表示相对火把坐标（x，y）的偏移量
	int X[13] = {0, -1, -2, 1, 2, 0, 0, 0, 0, -1, -1, 1, 1};
	int Y[13] = {0, 0, 0, 0, 0, 1, 2, -1, -2, -1, 1, -1, 1};
	for (int i = 0; i < 13; i++) { // 开始填充
		if (x + X[i] >= 0 && x + X[i] < v.size() // 填充范围为（0~列大小v.size()-1）
		        && y + Y[i] >= 0 && y + Y[i] < v.size()) { // 满足填充范围的点才能填充
			if (v[x + X[i]][y + Y[i]] == 0) { // 如果当前填充点还没有被填充
				v[x + X[i]][y + Y[i]] = 1; // 就置为1，表示已填充
				cnt++; // 同时已填充点+1
			}
		}
	}
}

模拟萤石:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 形参说明
// vector<vector<int> > &v 表示以引用的方式传入二维数组v
// int x和int y分别表示萤石的坐标
void getStone(vector<vector<int> > &v, int x, int y) {
     // 枚举萤石的过程代码量太大，这里选择用方向数组的形式来简化代码
    // 定义两个方向数组X和Y，分别表示相对萤石坐标（x，y）的偏移量
	int X[25] = {0, -1, -2, 1, 2, 0, 0, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, 1, 1, 1, 1, 2, 2, 2, 2};
	int Y[25] = {0, 0, 0, 0, 0, 1, 2, -1, -2, -1, -2, 1, 2, -1, -2, 1, 2, -1, -2, 1, 2, -1, -2, 1, 2};
	for (int i = 0; i < 25; i++) {  // 开始填充
		if (x + X[i] >= 0 && x + X[i] < v.size() // 填充范围为（0~列大小v.size()-1）
		        && y + Y[i] >= 0 && y + Y[i] < v.size()) { // 满足填充范围的点才能填充
			if (v[x + X[i]][y + Y[i]] == 0) { // 如果当前填充点还没有被填充
				v[x + X[i]][y + Y[i]] = 1; // 就置为1，表示已填充
				cnt++; // 同时已填充点+1
			}
		}
	}
}

③可能生成怪物点的个数即方阵所有点个数n * n减去已填充点的个数cnt，输出该结果即可

2、AC代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector> // 包含STL的vector库，二维数组会用到
using namespace std
    
int cnt = 0; // 因为作用是统计当前方阵已填充点的个数，所以初始化为0

// 形参说明
// vector<vector<int> > &v 表示以引用的方式传入二维数组v
// int x和int y分别表示火把的坐标
void getFire(vector<vector<int> > &v, int x, int y) {
    // 枚举火把的过程代码量太大，这里选择用方向数组的形式来简化代码
    // 定义两个方向数组X和Y，分别表示相对火把坐标（x，y）的偏移量
	int X[13] = {0, -1, -2, 1, 2, 0, 0, 0, 0, -1, -1, 1, 1};
	int Y[13] = {0, 0, 0, 0, 0, 1, 2, -1, -2, -1, 1, -1, 1};
	for (int i = 0; i < 13; i++) { // 开始填充
		if (x + X[i] >= 0 && x + X[i] < v.size() // 填充范围为（0~列大小v.size()-1）
		        && y + Y[i] >= 0 && y + Y[i] < v.size()) { // 满足填充范围的点才能填充
			if (v[x + X[i]][y + Y[i]] == 0) { // 如果当前填充点还没有被填充
				v[x + X[i]][y + Y[i]] = 1; // 就置为1，表示已填充
				cnt++; // 同时已填充点+1
			}
		}
	}
}

// 形参说明
// vector<vector<int> > &v 表示以引用的方式传入二维数组v
// int x和int y分别表示萤石的坐标
void getStone(vector<vector<int> > &v, int x, int y) {
     // 枚举萤石的过程代码量太大，这里选择用方向数组的形式来简化代码
    // 定义两个方向数组X和Y，分别表示相对萤石坐标（x，y）的偏移量
	int X[25] = {0, -1, -2, 1, 2, 0, 0, 0, 0, -1, -1, -1, -1, -2, -2, -2, -2, 1, 1, 1, 1, 2, 2, 2, 2};
	int Y[25] = {0, 0, 0, 0, 0, 1, 2, -1, -2, -1, -2, 1, 2, -1, -2, 1, 2, -1, -2, 1, 2, -1, -2, 1, 2};
	for (int i = 0; i < 25; i++) {  // 开始填充
		if (x + X[i] >= 0 && x + X[i] < v.size() // 填充范围为（0~列大小v.size()-1）
		        && y + Y[i] >= 0 && y + Y[i] < v.size()) { // 满足填充范围的点才能填充
			if (v[x + X[i]][y + Y[i]] == 0) { // 如果当前填充点还没有被填充
				v[x + X[i]][y + Y[i]] = 1; // 就置为1，表示已填充
				cnt++; // 同时已填充点+1
			}
		}
	}
}

int main() {
	int n, m, k; // n,m,k分别用来接收方阵的行数、火把的个数、萤石的个数
	cin >> n >> m >> k;
    // 定义一个n * n的二维数组v, 初值均为0
	vector<vector<int> > v(n, vector<int>(n, 0)); 
	while (m--) { // m个火把，填充m次
		int x, y; // x和y用来接收火把在方阵中的位置
		cin >> x >> y; 
        // 开始填充
        // 不传x传x-1、不传y传y-1是因为题目方阵坐标从1开始
        // 而我们的方阵坐标从0开始
		getFire(v, x - 1, y - 1);
	}
	while (k--) { // k个萤石，填充k次
		int x, y; // x和y用来接收萤石在方阵中的位置
		cin >> x >> y;
        // 开始填充
        // 不传x传x-1、不传y传y-1是因为题目方阵坐标从1开始
        // 而我们的方阵坐标从0开始
		getStone(v, x - 1, y - 1);
	}
    // 可能生成怪物点的个数即方阵所有点个数n * n减去已填充点的个数cnt
	cout << n * n - cnt; // 输出结果
	return 0;
}

题目E：B2104 矩阵加法

1、思路

本题要求实现两个n行m列的矩阵A和B的加法，并且输出它们的和A+B

我们可以分别定义两个n行m列的矩阵A和B，并且将矩阵A加到矩阵B上去，矩阵B累加的结果就是矩阵A+B的结果

矩阵A，B定义如下

1
2
3
定义两个n行m列的矩阵A和B
vector<vector<int> > A(n, vector<int>(m));
vector<vector<int> > B(n, vector<int>(m));

接下来填充A和B的值并且执行矩阵加法，最后输出矩阵B即可

注意：注意输出结果每一行的末尾不能有空格，这个坑我已经踩过了

2、AC代码

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 main() {
	int n, m; // n和m分别接收行和列的大小
	cin >> n >> m;
    // 定义两个n行m列的矩阵A和B
	vector<vector<int> > A(n, vector<int>(m));
	vector<vector<int> > B(n, vector<int>(m));
    // 填充矩阵A
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> A[i][j];
		}	
	}
    // 填充矩阵B并且执行A+B
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> B[i][j]; 
            // 将B对应位置的A元素加到B上去
			B[i][j] += A[i][j];
		}	
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << B[i][j]; // 输出相加结果
			if (j != m - 1) { // 没有到达列的末尾输出空格
				cout << " ";
			} else {
				cout << endl; // 到达列的末尾输出换行符'\n'
			}
		}
	}
	return 0;
}

问题F：B3617 古籍翻译

1、思路

题目要求将八进制字符串转化为十六进制字符串

字符串的长度最高可达1000，这显然无法用任何整形变量存储，只能通过字符串存储

① 八进制转化成十六进制的方法的讨论

先将八进制转化成十进制或二进制，再将十进制或二进制转化成十六进制

  1. 如果直接将整个八进制字符串s转化成对应的十进制或二进制字符串，再将这个十进制或二进制字符串转化成十六进制的话，就非常复杂了，将涉及到快速幂算法（八进制转化成对应的十进制或二进制时），大数高精度加法、大数高精度乘法等知识，所以此方法行不通

  2. 我们可以采用分治法，将一个大的问题拆分成一个个的小问题，小问题解决了自然大的问题也就解决了，在本题中分治法十分出色

本题我们的中间态选择十进制

  • 由于每4个八进制码包含12个bit信息，对应3个十六进制码，受此启发，我们可以将整个八进制字符串看成由许多包含4个字符的子字符串组成（Divide）

  • 将每一个字符串从八进制转化成十进制，再从十进制转化成十六进制，最后将子字符串的结果拼接成一个字符串，这个字符串的结果就是我们转化后的结果（Conquer）

由此我们就很好的解决了这个问题

②程序函数结构的设计

  • int十进制数转string十六进制数表示的函数transform

    作用：将十进制数转十六进制数表示，例如10转化成a、11转化成b等

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 返回值为转化结果，返回类型为string
    string transform(int s) {
    	string result; // 待返回值变量 
    	if (s >= 0 && s <= 9) { // 如果s为0~9
    		result += s + '0'; // 结果为对应的数字
        } else { // 如果s为 10~15
    		result += s + 'a' - 10; // 结果为对应的字母
    	}
    	return result; // 返回
    }

  • 将八进制数转化成十进制数的函数oct_to_dec

    作用：将八进制int转化成十进制int

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 返回值为int，为转化结果
    // 形参int s表示待转化的数
    int oct_to_dec(int s) {
    	int ans = 0; // 待返回结果变量
    	int g = 0; // 指数递增器
    	do {  // 开始转化（数位分离+基数幂算法）
    		int temp = s % 10; 
    		ans += temp * pow(8, g++);
    		s /= 10;
    	} while (s > 0); // s <= 0就停止转化 
    	return ans; // 返回
    }

  • 将int十进制数转化成string十六进制数的函数dec_to_hex

    作用：将int十进制数转化成string十六进制数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //这里用递归实现转化
    // 返回类型值为void是因为递归转换，设置了temp为string&类型，相当于返回值
    // 形参int s为待转化的数值, string& temp为引用类型，可以看做返回值
    void dec_to_hex(int s, string &temp) {
    	if (s < 16) { // 递归出口
    		temp += transform(s % 16); // 将结果保存
    	} else {
    		dec_to_hex(s / 16, temp); // 继续递归，递归式子
    		temp += transform(s % 16); // 将结果保存
    	}
    }

  • 主转化函数–实现将八进制转化成十六进制convert

    作用：实现将八进制转化成十六进制convert

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 返回值类型为string，表示转化的结果十六进制数
    // 形参string s为待转化的八进制数
    string convert(string s) {
    	int num = stoi(s); // 将string类型转化为int类型，需包含string头文件
    	string result; // 待返回结果
    	int dec = oct_to_dec(num); //将八进制数转化成十进制数，dec用于接收结果  
    	dec_to_hex(dec, result); // 将十进制数转化成十六进制数
        // 以下为转化结果不满足3位需要补前导0
    	if (result.size() == 2) { // 2位时 
    		result = '0' + result; // 补一个0
    	} else if (result.size() == 1) { // 1位时
    		result = "00" + result; // 补两个0
    	}
    	return result; // 返回
    }

  • 主函数

    作用：控制输入和输出，操控各个子函数

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
int main() {
	string s; // 待转化的八进制字符串
	stack<string> stk; // 定义一个string栈，用于输出正确的转化结果（原结果是相反的）
	cin >> s;
	int i; // 控制变量i
    // 开始分割字符串，每四个字符分割一次
	for (i = s.length() - 1; i - 3 >= 0 ; i = i - 4) {
		stk.push(convert(s.substr(i - 3, 4))); // 将分割后的子字符串转化结果压入栈中
	}
	if (i >= 0 && i <= 2) { // 有可能有不满足四位的，单独处理
	stk.push(convert(s.substr(0, i + 1))); // 将分割后的子字符串转化结果压入栈中
	}
	string ans; // 用于存放最后输出结果
    // 将栈中结果持续出栈，ans来进行拼接，实现结果翻转
	while (!stk.empty()) { // 如果栈不为空
		ans += stk.top(); // 拼接结果
		stk.pop(); // 出栈
	}
    // 以下程序段为处理前导0，并输出转化结果
	bool flag = false; // 开关，出现第一个不为‘0’的字符时打开
	for (int k = 0; k < ans.size(); k++) {
		if (ans[k] != '0') { // 打开开关
			flag = true;
		} 
		if (flag == true) { // 开关打开就进行输出，输出结果不包含前导‘0’
			cout << ans[k]; // 输出
		}
	}
	return 0;
}

③代码实现的细节

  • 字符串分割是从后往前每四个字符分割一次，也就是说先分割出的字符串是后处理的，符合栈先进后出的特性，我们可以通过栈来实现输出结果的一致性，先分割的先处理

  • 在某些4位八进制数转化成3位十六进制数的过程中，转化结果位数可能不足3位，需要根据实际位数补前导0

  • 最后输出结果时，注意前导0不要输出

2、AC代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <cmath>
using namespace std; 

// 返回值为转化结果，返回类型为string
string transform(int s) {
	string result; // 待返回值变量 
	if (s >= 0 && s <= 9) { // 如果s为0~9
		result += s + '0'; // 结果为对应的数字
    } else { // 如果s为 10~15
		result += s + 'a' - 10; // 结果为对应的字母
	}
	return result; // 返回
}

// 返回值为int，为转化结果
// 形参int s表示待转化的数
int oct_to_dec(int s) {
	int ans = 0; // 待返回结果变量
	int g = 0; // 指数递增器
	do {  // 开始转化（数位分离+基数幂算法）
		int temp = s % 10; 
		ans += temp * pow(8, g++);
		s /= 10;
	} while (s > 0); // s <= 0就停止转化 
	return ans; // 返回
}

//这里用递归实现转化
// 返回类型值为void是因为递归转换，设置了temp为string&类型，相当于返回值
// 形参int s为待转化的数值, string& temp为引用类型，可以看做返回值
void dec_to_hex(int s, string &temp) {
	if (s < 16) { // 递归出口
		temp += transform(s % 16); // 将结果保存
	} else {
		dec_to_hex(s / 16, temp); // 继续递归，递归式子
		temp += transform(s % 16); // 将结果保存
	}
}

// 返回值类型为string，表示转化的结果十六进制数
// 形参string s为待转化的八进制数
string convert(string s) {
	int num = stoi(s); // 将string类型转化为int类型
	string result; // 待返回结果
	int dec = oct_to_dec(num); //将八进制数转化成十进制数，dec用于接收结果  
	dec_to_hex(dec, result); // 将十进制数转化成十六进制数
    // 以下为转化结果不满足3位需要补前导0
	if (result.size() == 2) { // 2位时 
		result = '0' + result; // 补一个0
	} else if (result.size() == 1) { // 1位时
		result = "00" + result; // 补两个0
	}
	return result; // 返回
}

int main() {
	string s; // 待转化的八进制字符串
	stack<string> stk; // 定义一个string栈，用于输出正确的转化结果（原结果是相反的）
	cin >> s;
	int i; // 控制变量i
    // 开始分割字符串，每四个字符分割一次
	for (i = s.length() - 1; i - 3 >= 0 ; i = i - 4) {
		stk.push(convert(s.substr(i - 3, 4))); // 将分割后的子字符串转化结果压入栈中
	}
	if (i >= 0 && i <= 2) { // 有可能有不满足四位的，单独处理
	stk.push(convert(s.substr(0, i + 1))); // 将分割后的子字符串转化结果压入栈中
	}
	string ans; // 用于存放最后输出结果
    // 将栈中结果持续出栈，ans来进行拼接，实现结果翻转
	while (!stk.empty()) { // 如果栈不为空
		ans += stk.top(); // 拼接结果
		stk.pop(); // 出栈
	}
    // 以下程序段为处理前导0，并输出转化结果
	bool flag = false; // 开关，出现第一个不为0时打开
	for (int k = 0; k < ans.size(); k++) {
		if (ans[k] != '0') { // 打开开关
			flag = true;
		} 
		if (flag == true) { // 开关打开就进行输出，输出结果不包含前导0
			cout << ans[k];
		}
	}
	return 0;
}

问题G：P5639 【CSGRound2】守序者的尊严

1、思路

题目要求计算出小Z安全到达外卖驻点所需要的时间

注意到小 Z 通过任意个数关闭的监控的时间均为 1，监控不能持续工作，工作一秒之后要暂停休息一秒，可知监控只有两种状态：0代表关闭，1代表工作，连续相同状态的监控可以看做一个整体，这样就可以将这条道路上的监控简化为相邻监控状态不同的集体

例如 0 0 1 1 0 1可以看做 0 1 0 1， 0 0 0 0 0 0 可以看做 0

注意到小Z安全到达外卖驻点所需要的时间为简化后的监控数组的个数

原理：通过相同状态的监控需要1秒，监控切换状态时间也需要1秒，时间具有同时性，通过一个状态的监控后（此监控一定是关闭状态），另一个状态的监控切换状态（由开启转为关闭），由于监控只有开启和关闭两个状态，此时另一个状态的监控关闭，小Z可以立即再次通过另一个状态的监控，以此类推，可以推出小Z安全到达外卖驻点所需要的时间为简化后的监控数组的元素个数

2、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector> 
using namespace std;
int main() {
	int n; // 用来接收监控的个数
	cin >> n;
	vector<int> ans; // ans数组用来存放简化后的监控数组
	for (int i = 0; i < n; i++) {
		int temp; // 暂时存放当前输入监控的状态
		cin >> temp;
        // i==0时为第一个监控，必须压入ans数组中，以便和后面监控的状态进行比较
        // 当i!=0时当前状态的监控需要和前一个状态的监控进行比较，如果不同，就压入ans数组中
		if (i == 0 || ans.back() != temp) {
			ans.push_back(temp); // 压入监控状态
		} 
	}
	cout << ans.size(); // 输出ans数组中元素的个数，即小Z通过监控道路的时间
	return 0;
}

问题H：P6195 [EER1]迫害

1、思路

X拥有n个1，有m个大小可选定的数，有K个人，每个人有一个数字，分别为1~k，X能用手中若干个数的加和等于被迫害人的数字，一次迫害就成功，而且不消耗数字，求X最多能够连续迫害多少个人

  • 我们可以运用推理的方法

    1. 由于题目要求是连续，先用掉X手中的n个1，由于迫害成功不会消耗数字，此时最多可以迫害n个人

      • 为什么要先用掉X手里的n个1：如果不先用掉n个1的话，后面这个1就无法使用，迫害最多的人数肯定没有用完n个1的多

    2. 如果此时X手里还拥有m个大小可选定的数

      考虑连续迫害

      第n+1张牌我们可以选择数值为n+1n+1，此时最多可以连续迫害的人数为

      n+(n+1)=2n+1=21(n+1)−1n + (n + 1) = 2n + 1= 2^{1}(n+1)-1

      第n+2张牌我们可以选择数值为2n+22n+2，此时最多可以连续迫害的人数为

      n+(n+1)+(2n+2)=4n+3=22(n+1)−1n + (n + 1) + (2n + 2) = 4n + 3= 2^{2}(n+1)-1

      第n+3张牌我们可以选择数值为4n+44n+4，此时最多可以连续迫害的人数为n+(n+1)+(2n+2)+(4n+4)=8n+7=23(n+1)−1n + (n + 1) + (2n + 2) + (4n + 4)= 8n + 7= 2^{3}(n+1)-1

      以此类推

      第m张牌时我们最多可以连续迫害的人数为 2m(n+1)−12^{m}(n+1)-1

​ 由此我们推出当X拥有n个1，有m个大小可选定的数时，最多可以连续迫害的人数为 2m(n+1)−12^{m}(n+1)-1

  • 由于结果涉及到高次方幂2m2^{m},所以我们可以用套用快速幂算法模板，大大提升运算效率，体会二分的魅力

    由于需要对答案进行 1000000007取模，由取模公式

    1. (a + b) % p = (a % p + b % p) % p
    2. (a * b) % p = (a % p * b % p) % p

​ 结合快速幂算法模板代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 返回值类型为long long,防止返回值溢出
// 形参long long power表示传入的指数，题目限定为底数为2，所以只传指数即可
// 部分条件表达式用位运算表示，可以达到压榨性能的效果
long long quickPower(int power) {
	long long result = 1; // 用于存放运算结果
	long long base = 2; // 底数固定为2
	while (power > 0) { // power > 0时继续循环
		if(power & 1) { // 此处等价与 power % 2==0,当指数为奇数时
			result = (result * base) % 1000000007; // 分离底数与result累乘,并对结果取模
		}
		power >>= 1; // 此处等价于 power /= 2
		base = (base * base) % 1000000007; // 底数继续累乘base，并对结果取模
	}
	return result; // 返回结果
}
  • 最后结合快速幂算法和推出的表达式2m(n+1)−12^{m}(n+1)-1，按照题目取模要求即可得到答案

2、AC代码

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>
using namespace std;

// 返回值类型为long long,防止返回值溢出
// 形参long long power表示传入的指数，题目限定为底数为2，所以只传指数即可
// 部分条件表达式用位运算表示，可以达到压榨性能的效果
long long quickPower(int power) {
	long long result = 1; // 用于存放运算结果
	long long base = 2; // 底数固定为2
	while (power > 0) { // power > 0时继续循环
		if(power & 1) { // 此处等价与 power % 2==0,当指数为奇数时
			result = (result * base) % 1000000007; // 分离底数与result累乘,并对结果取模
		}
		power >>= 1; // 此处等价于 power /= 2
		base = (base * base) % 1000000007; // 底数继续累乘base，并对结果取模
	}
	return result; // 返回结果
}

int main() {
	int n, m; // n和m记录X有n个1，m个自由数字
	cin >> n >> m;
	long long ans = (quickPower(m) % 1000000007) * ((n + 1) % 1000000007) - 1; // 套用推出来的公式,并多次取模
	cout << ans % 1000000007; // 结果对1000000007取模
	return 0;
}

问题I：P3654 First Step (ファーストステップ)

1、思路

本题要求求出Aqours队员在矩阵中总共的站位方式，首先需要对矩阵进行存储，由于矩阵元素为字符char类型，所以用一个二维字符数组进行存储，数组有两种值：‘#’ 表示不可站位，’.'表示可站位

二维数组定义如下

1
2
// 定义了一个R行C列的二维字符数组s
vector<vector<char> > s(R, vector<char>(C));

接着题目需要从矩阵中求出可以排成一条1*K的直线的位置，即至少有一条包含K个连续可站位的直线，才可以满足

直线就包括行直线和列直线，因此需要分别对每一行和每一列进行统计

我们可以在填充矩阵时先对行可行的站位方式进行统计

接着再遍历矩阵的每一列，对列可行的站位方式进行统计

  • 定义一个int型变量count用来统计每一行或每一列中当前连续可站位的个数，初始化为0，表示当前还没有连续可站位
1
int count = 0;
  • 定义一个变量ans进行统计整个矩阵中可站位方式数量
1
int ans = 0;

  • 统计每一行和每一列的过程中，有以下几种情况

    1. 如果s[i] [j]== ‘.’,说明有可站位，count++
    2. 如果s[i] [j]==’#’&&count>0,说明连续可站位中断，分为两种处理方式
      1. 此时如果count >= K，即连续可站位count大于队员人数K，说明此行或此列存在可站位方式，数量为count-K+1，让ans += count - K + 1，将情况累加进ans中，清空count，令count=0
      2. 如果此时count < K，清空count，令count=0即可
    3. 还要考虑遍历当前行或当前列后没有遇到s[i] [j]==’#'的情况，判断是否count >= K，如果满足，让ans += count - K + 1，将情况累加进ans中，后面进入到新的行或者列，自动清空count

  • 注意：K=1时，会重复统计一遍，此时最后的ans需要除以2

    重复统计的原因：K=1时，在矩阵中相当于一个点，行和列都会包含一次，所以就造成了重复统计

  • 统计完总共的站位方式数量ans后，输出即可

2、AC代码

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 <vector> 
using namespace std;
int main() {
	int R, C, K; // R,C,K分别用来表示矩阵行数、列数以及队员人数
	cin >> R >> C >> K;
    // 定义了一个R行C列的二维字符数组s
	vector<vector<char> > s(R, vector<char>(C));
	int ans = 0; // ans统计整个矩阵中可站位方式数量
    // 开始填充矩阵并且扫描行，统计行对应的可站位方式数量
	for (int i = 0; i < R; i++) {
		int count = 0; // count用来统计当前行连续的可站位的数量，初始化为0
		for (int j = 0; j < C; j++) {
			cin >> s[i][j];
			if (s[i][j] == '.') { // 如果有可站位
				count++; // 当前行连续的可站位数量+1
			} else if (count > 0 && s[i][j] == '#') { //有连续可站位但是连续可站位中断
				if (count >= K) { // 满足队员的可站位方式
					ans += (count - K + 1); // 将可站位方式数量count-K+1累加进ans中
				}
				count = 0; // 无论怎样，进入这个if语句内count都要归零
			}
		}
		if (count >= K) { // 考虑遍历当前行后没有遇到s[i] [j]=='#'的情况,如果count>=k,
            			// 说明也存在可行性站位方式，也要将这种情况累加进ans中
			ans += (count - K + 1);
		}
	} 
    // 一下循环对矩阵的每一列进行扫描，统计出列队员的可站位方式
	for (int j = 0; j < C; j++) {
		int count = 0; // count用来统计当前列连续的可站位的数量，初始化为0
		for (int i = 0 ; i < R; i++) {
			if (s[i][j] == '.') { // 如果有可站位
				count++; // 当前行连续的可站位数量+1
			} else if (count > 0 && s[i][j] == '#') { //有连续可站位但是连续可站位中断
				if (count >= K) { // 满足队员的可站位方式
					ans += (count - K + 1);  // 将可站位方式数量count-K+1累加进ans中
				}
				count = 0;  // 无论怎样，进入这个if语句内count都要归零
			}	
		}
		if (count >= K) {  // 考虑遍历当前行后没有遇到s[i] [j]=='#'的情况,如果count>=k,
            
			ans += (count - K + 1); // 说明也存在可行性站位方式，也要将这种情况累加进ans中
		}
	}
	if (K == 1) { // 对K==1的情况单独处理，这种情况ans重复统计了一遍，ans需要除以2
		ans /= 2; // ans除以2
	}
	cout << ans; // 输出总共的站位方式数量
	return 0;
}