[编程|100分] 竖式填空
时间限制：1秒
空间限制：65536K
题目描述
小Q是名小学生，他最喜欢数学中的加法竖式填空了。例如下面的填空题，每个空格表示1…9中的一个数字。
有时候这种竖式题不一定只有唯一解，小Q很想知道，给定一个这样的竖式，总共可能的解有多少个。
被加数和加数的位数不会超过3位。和的位数不会超过4位。空格只可能存在于被加数和加数中。
输入描述:
每个输入数据包含多个测试点。
第一行为测试点的个数T(T<=30)。
每个测试点包含一行，包含了三个长度大于0的字符串，分别表示被加数，加数和结果。每个字符串之间有一个空格。每个字符串只会包含“X”和“1”…“9”，其中“X”表示竖式中的空格。保证竖式至少有一个解。
输出描述:
对于每个测试点，输出一行，表示一共可能的解的个数。
输入例子:
2
X7 9X 123
X X 4
输出例子:
1
3
（样例解释：样例1的解为27+96，样例2的解为1+3,2+2,3+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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<vector>
#include<iostream>
#include<algorithm>
#include<sstream>
void dfsTwo(std::string num, int index, int remain, int& result){
if (index == num.size()){
int num_i = stoi(num);
//std::istringstream(num) >> num_i;
if (num_i == remain) result++;
return;
}
if (num[index] != 'X') dfsTwo(num, index + 1, remain, result);
else{
for (int i = 1; i < 10; ++i){
num[index] = i + '0';
dfsTwo(num, index + 1, remain, result);
}
}
}
void dfs(std::string numOne, std::string& numTwo, int index, int sum, int& result){
if (index == numOne.size()){
int num_i = stoi(numOne);
//std::istringstream(numOne) >> num_i;
dfsTwo(numTwo, 0, sum - num_i, result);
return;
}
if (numOne[index] != 'X')
dfs(numOne, numTwo, index + 1, sum, result);
else{
for (int i = 1; i < 10; ++i){
numOne[index] = i + '0';
dfs(numOne, numTwo, index + 1, sum, result);
}
}
}
int main(){
int looper = 0;
std::cin >> looper;
for (int i = 0; i < looper; ++i){
std::string numOne, numTwo;
std::cin >> numOne >> numTwo;
std::string sum;
std::cin >> sum;
int i_sum = stoi(sum);
//std::istringstream(sum) >> i_sum;
int result = 0;
dfs(numOne, numTwo, 0, i_sum, result);
std::cout << result << std::endl;
}
system("pause");
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
33
34
35
36
37
38
39
40
41
42
#include<vector>
#include<iostream>
#include<algorithm>
#include<sstream>
using namespace std;
bool isCompatible(int num, const std::string& str){
const std::string& tmp = std::to_string(num);
if (tmp.size() != str.size()) return false;
for (int i = 0; i < str.size(); ++i){
if (str[i] != 'X' && str[i] != tmp[i]){
return false;
}
}
return true;
}
int main(){
int looper = 0;
std::cin >> looper;
for (int i = 0; i < looper; ++i){
std::string numOneStr, numTwoStr, sumStr;
std::cin >> numOneStr >> numTwoStr >> sumStr;
int endOne = std::pow(10, numOneStr.size());
int startOne = endOne / 10;
int endTwo = std::pow(10, numTwoStr.size());
int startTwo = endTwo / 10;
int sum = std::stoi(sumStr);
int result = 0;
for (int i = startOne; i < endOne; ++i){
if (!isCompatible(i, numOneStr)) continue;
for (int k = startTwo; k < endTwo; ++k){
if (!isCompatible(k, numTwoStr)) continue;
result += (i + k == sum) ? 1 : 0;
}
}
std::cout << result << std::endl;
}
system("pause");
return 0;
}总结：
1.算法渣渣，写得不好的地方还请大大们指教；
2.最近在刷Leetcode，DP类题目，遇到问题一般都是直接先走DFS，再想想如何DP，所以做这题时，直接想到的是递归的解法，算法效率不高，勉强通过；
3.今天又想了一下题目，发现自己当时是太紧张了，因为数据范围有限，用迭代更容易；
4.算法还是太弱了，希望好好刷题，脚踏实地，不断提升自己；
最后
以上就是孝顺蜜粉最近收集整理的关于网易游戏2017互娱实习笔试编程（竖式填空）的全部内容，更多相关网易游戏2017互娱实习笔试编程（竖式填空）内容请搜索靠谱客的其他文章。
发表评论 取消回复