一个合法的身份证号码前17个数字加1位校验码组成。校验码的计算规则如下：
首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：
Z：0 1 2 3 4 5 6 7 8 9 10
M：1 0 X 9 8 7 6 5 4 3 2
现给定一个身份证号，从标准输入读取，判断该身份证是否合理，如果合理输出"YES"，如果不合理输出"NO"。
输入示例:
37070419881216001X
输出示例:
YES
注意char和int类型的转换即可，关键在于理解题意。
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>
using namespace std;
int w[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
char m[11] = {'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'};
bool isValid(string &s) {
int sum = 0;
for (int i = 0; i < 17; i++) {
if (!isdigit(s[i])) {
return false;
}
sum += w[i] * (s[i] - '0');
}
return (m[sum % 11] == s[17]);
}
int main(int argc, char *argv[]) {
string s;
cin >> s;
cout << (isValid(s) ? "YES" : "NO");
return 0;
}
|
判断给定的数字是否可以拆分为两个2的幂的和的形式，如果可以输出拆分方案，不能输出"NO"。
输入示例:
5
输出示例:
5 = 2^0 + 2^1
输入示例:
7
输出示例:
NO
判断该数字对应二进制位是否有两个1即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
#include <bitset>
using namespace std;
int main(int argc, char *argv[]) {
int num;
cin >> num;
bitset<32> bits(num);
if (bits.count() != 2) {
cout << "NO";
} else {
int a[2], idx = 0, tmp = num;
for (int i = 0; i < 32; i++) {
if (tmp & 1)
a[idx++] = i;
tmp >>= 1;
}
printf("%d = 2^%d + 2^%d\n", num, a[0], a[1]);
}
return 0;
}
|
给出前缀式，只有加减乘除，求结果。前缀式从文件pre.in中读取，将结果输出到标准输出中，题目保证输入的前缀式有效。
输入示例:
- + 1 * + 2 3 4 5
输出示例:
16
笔者在复习做到这道题目时直接忘了前缀式如何处理，因为平时只处理过中缀表达式和后缀表达式，忘记了的同学可以看看这篇文章。其实和后缀表达式求值原理一样，只不过是从右向左扫描的。
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
|
#include <fstream>
#include <iostream>
#include <stack>
using namespace std;
int calc(int lhs, int rhs, char op) {
if (op == '+')
return lhs + rhs;
else if (op == '-')
return lhs - rhs;
else if (op == '*')
return lhs * rhs;
else
return lhs / rhs;
}
int main(int argc, char *argv[]) {
ifstream ifs("./pre.in");
string s;
getline(ifs, s);
stack<int> numStk;
for (int i = s.size() - 1; i >= 0; i--) {
char c = s[i];
if (isspace(c)) continue;
if (isdigit(c)) {
numStk.push(c - '0');
continue;
}
int lhs = numStk.top();
numStk.pop();
int rhs = numStk.top();
numStk.pop();
numStk.push(calc(lhs, rhs, c));
}
cout << numStk.top();
return 0;
}
|
求集合的所有划分，集合从文件set.in中读取，结果输出到标准输出中。
输入示例:
a b c
输出示例:
{{a,b,c}}
{{a,b},{c}}
{{a,c},{b}}
{{a},{b,c}}
{{a},{b},{c}}
注：输入 a b c 代表集合{a,b,c}
采用dfs和回溯进行解答，用vector<vector<char>>来存储所有的子集，对于一个新元素，可以选择将其加入一个已经存在的子集，也可以将其加入一个新的子集。
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
|
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
void print(vector<vector<char>> &subsets) {
cout << '{';
int flag1 = 0;
for (auto &a : subsets) {
if (flag1) cout << ',';
cout << '{';
int flag2 = 0;
for (auto &b : a) {
if (flag2) cout << ',';
cout << b;
flag2 = 1;
}
cout << '}';
flag1 = 1;
}
cout << '}';
cout << endl;
}
void solve(vector<char> &v, vector<vector<char>> &subsets, int idx) {
if (idx == v.size()) {
print(subsets);
return;
}
for (int i = 0; i < subsets.size(); i++) {
subsets[i].push_back(v[idx]);
solve(v, subsets, idx + 1);
subsets[i].pop_back();
}
subsets.push_back({v[idx]});
solve(v, subsets, idx + 1);
subsets.pop_back();
}
int main(int argc, char *argv[]) {
ifstream ifs("./set.in");
char c;
vector<char> v;
while (ifs >> c) {
v.push_back(c);
}
vector<vector<char>> subsets;
solve(v, subsets, 0);
return 0;
}
|
给出一个二叉排序树的层次遍历，求从它的一个叶子结点到另一个叶子结点的路径，要求路径上经过结点的数值之和最大。二叉树的层次遍历序列从文件tree.in中读取，结点数值大于0，将结果输出到标准输出中。
输入示例:
25 15 40 5 20 30 50 10 35
输出示例:
165
根据上述输入可以构建如下二叉树，最长路径为 20, 15, 25, 40, 30, 35，和为165，这里注意最长路径不一定经过树的根节点。
25
/ \
15 40
/ \ / \
5 20 30 50
\ \
10 35
首先根据输入建立二叉排序树，然后直接暴力递归即可，按照如下代码
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
|
#include <fstream>
#include <iostream>
#include <cassert>
using namespace std;
struct TreeNode {
TreeNode *left{nullptr};
TreeNode *right{nullptr};
int val;
TreeNode(int val): val{val} {}
};
TreeNode *root = nullptr;
void insertNode(int val) {
if (!root) {
root = new TreeNode(val);
return;
}
TreeNode *cur = root;
TreeNode *prev = nullptr;
while (cur) {
prev = cur;
if (val < cur->val) {
cur = cur->left;
} else if (val > cur->val) {
cur = cur->right;
} else {
assert(false);
}
}
assert(prev);
if (val < prev->val) {
prev->left = new TreeNode(val);
} else {
prev->right = new TreeNode(val);
}
}
#define MAX(a, b, c) max(a, max(b, c))
// 求从根节点到叶结点的最短路径
int getMaxPath(TreeNode *root) {
if (!root) {
return 0;
}
int ans = root->val + max(getMaxPath(root->left), getMaxPath(root->right));
return ans;
}
// 求以root为根节点的树中，两个叶结点之间的最长路径，有三种可能性：
// 1. 最长路径经过该根节点
// 2. 最长路径在左子树
// 3. 最长路径在右子树
int getMaxDist(TreeNode *root) {
if (!root) {
return 0;
}
return MAX(getMaxDist(root->left), getMaxDist(root->right),
root->val + getMaxPath(root->left) + getMaxPath(root->right));
}
int main() {
ifstream ifs("tree.in");
int val;
while (ifs >> val) {
insertNode(val);
}
cout << getMaxDist(root) << endl;
return 0;
}
|
以上代码对于 getMaxPath 的重复计算较多，可以使用如下方式优化：
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
|
struct TreeNode {
TreeNode *left{nullptr};
TreeNode *right{nullptr};
int val;
// 从以该结点为根节点的子树到叶结点的最长路径
int maxpath{-1};
TreeNode(int val): val{val} {}
};
int getMaxPath(TreeNode *root) {
if (!root) {
return 0;
}
if (root->maxpath != -1) {
return root->maxpath;
}
int ans = root->val + max(getMaxPath(root->left), getMaxPath(root->right));
root->maxpath = ans;
return ans;
}
int getMaxDist(TreeNode *root) {
if (!root) {
return 0;
}
return MAX(getMaxDist(root->left), getMaxDist(root->right),
root->val + getMaxPath(root->left) + getMaxPath(root->right));
}
|