HBC236060[SHOI2009] 舞会,高精度,容斥原理与鸽巢原理,排列组合,数学The Matching System题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

As the leader of the safety department, you are asked to check an ancient matching system in your company. The system is fed with two strings, a to-be-matched string and a pattern string, and w

As the leader of the safety department, you are asked to check an ancient matching system in your company. The system is fed with two strings, a to-be-matched string and a pattern string, and will determine whether the former can match the latter. The former string is a strict binary string(i.e., contains only0and1), and the latter string consists of four types of characters0,1,*,^, where*means match zero or more arbitrary binary characters, and^means match exactly one binary character. The system has two matching methods: maximum matching and minimum matching. Consider the starting positions of the two strings. The maximum matching method will make different decisions based on the current character of the pattern string: *: The system will enumerate iii from LLL to 000, where LLL is the remaining length of the to-be-matched string. Before each enumeration starts, the system consumes 1 unit of energy. Then it temporarily assumes that the current*in the pattern string matches the consecutive iii characters in the to-be-matched string, and tries to match the remaining positions of two strings recursively. As long as one attempt is successful, the system will give up the remaining enumeration and stop the whole system. Otherwise, it will try the next enumeration until all attempts are tried and finally return to the previous*enumeration. 0,1: The system will stop and return to the previous*enumeration if the to-be-matched string has been exhausted. Otherwise, it consumes 111 unit of energy to compare the current characters between the pattern string and the to-be-matched string. It will continue analyzing the remaining positions of these two strings if the result is the same, otherwise, return back to the previous*enumeration. ^: The system will stop and return to the previous*enumeration if the to-be-matched string has been exhausted. Otherwise, it consumes 111 unit of energy and moves on of two strings. When the pattern string is exhausted, the system will check the to-be-matched string at the same time. It will return"Yes" and stop the whole process if the to-be-matched string is also exhausted, otherwise, it will return to the previous*enumeration. After all attempts are tried and no matching method is found, the system will eventually return "No". Minimum matching does a similar thing except for the enumeration order of*(i.e., enumerate iii from 000 to LLL). These two matching methods seem not very effective, so you want to hack them. Please construct both a pattern string and a to-be-matched string of length nnn for each matching method, so that the system answers "Yes" and the energy consumption is as large as possible.

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC236060[SHOI2009] 舞会 高精度 容斥原理与鸽巢原理 排列组合 数学The Matching System题解