2020/4/11 网易游戏后台开发笔试，4道编程题

class Solution {
public:
	/**
	* 接收两个表示9进制数的字符串，返回表示它们相加后的9进制数的字符串
	* @param num1 string字符串 第一个加数
	* @param num2 string字符串 第二个加数
	* @return string字符串
	*/
	string add(string num1, string num2) {
		string s1, s2, z1, z2;
		s1 = findSmallPart(num1);
		s2 = findSmallPart(num2);
		z1 = findZhengPart(num1);
		z2 = findZhengPart(num2);
		int rest = 0;
		string small = handleSmallPart(s1, s2, rest);
		string zheng = handleZhengPart(z1, z2, rest);
		if (small.size() == 0) {
			return zheng;
		}
		return zheng + '.' + small;
	}

	char itos(int i) { // 将int 转换成 char
		stringstream s;
		string str;
		s << i;
		str = s.str();
		return str[0];
	}

	string handleZhengPart(string z1, string z2, int rest) {
		// 处理成等长
		if (z1.size() != z2.size()) {
			if (z1.size() > z2.size()) {
				while (z1.size() > z2.size()) { z2.insert(0, 1, '0'); }
			}
			else if (z2.size() > z1.size()) {
				while (z2.size() > z1.size()) { z1.insert(0, 1, '0'); }
			}
		}
		string tmp(z1.size(), '0');
		if (z1.size() != z2.size()) { cout << "mark2" << endl; return tmp; }
		for (int i = z1.size() - 1; i >= 0; --i) {
			int x1 = z1[i] - '0';
			int x2 = z2[i] - '0';
			int sum = x1 + x2 + rest;
			if (sum < 9) {
				tmp[i] = itos(sum);
				rest = 0;
			}
			else {
				tmp[i] = itos(sum - 9);
				rest = 1;
			}
		}
		if (rest != 0) {
			tmp.insert(0, 1, itos(rest));
		}
		return tmp;
	}

	string handleSmallPart(string s1, string s2, int& rest) {
		if (s1.size() == 0 && s2.size() == 0) {
			return "";
		}
		// 处理成等长
		if (s1.size() != s2.size()) {
			if (s1.size() > s2.size()) {
				while (s1.size() > s2.size()) { s2 += '0'; }
			}
			else if (s2.size() > s1.size()) {
				while (s2.size() > s1.size()) { s1 += '0'; }
			}
		}
		string tmp(s1.size(), '0');
		if (s1.size() != s2.size()) { cout << "mark1" << endl; return tmp; }
		for (int i = s1.size() - 1; i >= 0; --i) {
			int x1 = s1[i] - '0';
			int x2 = s2[i] - '0';
			int sum = x1 + x2 + rest;
			if (sum < 9) {
				tmp[i] = itos(sum);
				rest = 0;
			}
			else {
				tmp[i] = itos(sum - 9);
				rest = 1;
			}
		}
		return tmp;
	}

	string findSmallPart(string num) {
		string tmp;
		int pointPos = -1;
		for (size_t i = 0; i < num.size(); ++i) {
			if (num[i] == '.') {
				pointPos = i;
				break;
			}
		}
		if (pointPos == -1) {
			return tmp;
		}
		for (size_t i = pointPos + 1; i < num.size(); ++i) {
			tmp += num[i];
		}
		return tmp;
	}

	string findZhengPart(string num) {
		string tmp;
		int pointPos = -1;
		for (size_t i = 0; i < num.size(); ++i) {
			if (num[i] == '.') {
				pointPos = i;
				break;
			}
		}
		if (pointPos == -1) {
			return num;
		}
		for (int i = 0; i < pointPos; ++i) {
			tmp += num[i];
		}
		return tmp;
	}

};

int main() {
	Solution sss;
	string num1 = "1.28";
	string num2 = "1.71";
	cout << sss.add(num1, num2) << endl;
	system("pause");
}

void DFS(vector<int> workPower, vector<int> staffHard, int worker, vector<int> hasDone, int& count) {
	if (hasDone.size() == staffHard.size()) {
		++count;
		return;
	}
	for (size_t i = 0; i < staffHard.size(); ++i) {
		if (workPower[worker] < staffHard[i] || find(hasDone.begin(), hasDone.end(), i) != hasDone.end()) {
			continue;
		}
		hasDone.push_back(i);
		DFS(workPower, staffHard, worker + 1, hasDone, count);
		hasDone.pop_back();
	}
}

int main() {
	int n, m;
	cin >> n;
	vector<int> workPower(n);
	vector<int> staffHard(n);
	for (int i = 0; i < n; ++i) {
		cin >> workPower[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> staffHard[i];
	}
	cin >> m;
	
	sort(workPower.begin(), workPower.end());
	sort(staffHard.begin(), staffHard.end());
	for (int i = 0; i < n; ++i) {
		if (workPower[i] < staffHard[i]) {
			cout << 0 << endl;
			//system("pause");
			return 0;
		}
	}

	vector<int> hasDone;
	int count = 0;
	DFS(workPower, staffHard, 0, hasDone, count);
	cout << count % m << endl;
	//system("pause");
	return 0;
}

class Solution {
public:
	/**
	*
	* @param boxes int整型二维数组
	* @param boxesRowLen int boxes数组行数
	* @param boxesColLen int* boxes数组列数
	* @return int整型
	*/
	int maxBoxes(int** boxes, int boxesRowLen, int* boxesColLen) {
		// 转为vector
		vector<vector<int> > Boxes;
		int row = boxesRowLen, col = *boxesColLen;
		for (int i = 0; i < row; ++i) {
			vector<int> rowTmp;
			for (int j = 0; j < col; ++j) {
				rowTmp.push_back(boxes[i][j]);
			}
			Boxes.push_back(rowTmp);
		}
		// 1
		sort(Boxes.begin(), Boxes.end(), sortByL);
		vector<int> bigBox = Boxes.back();
		int count1 = 1;
		for (int i = Boxes.size() - 2; i >= 0; --i) {
			if (leftContainRight(bigBox, Boxes[i])) {
				++count1;
				bigBox = Boxes[i];
			}
		}
		// 2
		sort(Boxes.begin(), Boxes.end(), sortByW);
		bigBox = Boxes.back();
		int count2 = 1;
		for (int i = Boxes.size() - 2; i >= 0; --i) {
			if (leftContainRight(bigBox, Boxes[i])) {
				++count2;
				bigBox = Boxes[i];
			}
		}
		// 3
		sort(Boxes.begin(), Boxes.end(), sortByH);
		bigBox = Boxes.back();
		int count3 = 1;
		for (int i = Boxes.size() - 2; i >= 0; --i) {
			if (leftContainRight(bigBox, Boxes[i])) {
				++count3;
				bigBox = Boxes[i];
			}
		}
		// 4
		sort(Boxes.begin(), Boxes.end(), sortByV);
		bigBox = Boxes.back();
		int count4 = 1;
		for (int i = Boxes.size() - 2; i >= 0; --i) {
			if (leftContainRight(bigBox, Boxes[i])) {
				++count4;
				bigBox = Boxes[i];
			}
		}
		int count = max(max(max(count1, count2), count3), count4);
		return count;
	}

	static bool sortByL(const vector<int>& b1, const vector<int>& b2) {
		return b1.front() < b2.front();
	}

	static bool sortByW(const vector<int>& b1, const vector<int>& b2) {
		return b1[1] < b2[1];
	}

	static bool sortByH(const vector<int>& b1, const vector<int>& b2) {
		return b1[2] < b2[2];
	}

	static bool sortByV(const vector<int>& b1, const vector<int>& b2) {
		return b1[0]*b1[1]*b1[2] < b2[0] * b2[1] * b2[2];
	}

	static bool leftContainRight(const vector<int>& b1, const vector<int>& b2) {
		if (b1.size() != 3 || b2.size() != 3) {
			cout << "Wrong data!" << endl;
			return false;
		}
		if (b2[0] < b1[0] && b2[1] < b1[1] && b2[2] < b1[2]) {
			return true;
		}
		else {
			return false;
		}
	}

};