Our Discord: https://discord.gg/ajezQHdnRU. Please email mathteca@gmail.com if any organization or society wants to partner with Mathteca.
Enumerate is a problem-solving strategy that guesses the answer based on existing knowledge.
The idea of enumeration is to constantly guess, try one by one from the possible set, and then judge whether the conditions of the question are true.
Give the solution space
Build concise mathematical models. When enumerating, think clearly: What are the possible situations? What elements are to be enumerated?
Reduce enumeration space
What is the scope of the enumeration? Does everything need to be enumerated?
When using enumeration to solve a problem, you must think clearly about these two things, otherwise it will cause unnecessary time overhead.
Choose the appropriate enumeration order
Judge based on the question. For example, if the example question requires the largest prime number that meets the conditions, then it is naturally more appropriate to enumerate from large to small.
The following is an example of using enumerations to solve problems and optimize the enumeration range.
The numbers in an array are different from each other. Find the number of pairs of numbers whose sum is 0.
Solution
It is easy to write a program to enumerate two numbers.
C++
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (a[i] + a[j] == 0) ++ans;
Python
for i in range(n):
for j in range(n):
if a[i] + a[j] == 0:
ans += 1
Let’s see how the enumeration range can be optimized. Since the question does not require that the pairs of numbers be ordered, the answer is twice as long as the ordered case (consider that if (a, b) is the answer, then (b, a) is also the answer). In this case, just count the answers after the artificial order is required, and finally multiply by 2
You might as well require the first number to appear in the front position. code show as below:
C++
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
if (a[i] + a[j] == 0) ++ans;
Python
for i in range(n):
for j in range(i):
if a[i] + a[j] == 0:
ans += 1
It is not difficult to find that the enumeration range of j has been reduced here, reducing the time overhead of this code.
We can further optimize on top of this.
Do both numbers have to be enumerated? After enumerating one of the numbers, the condition of the question has already determined the conditions of the other elements (another number). If you can find a way to directly determine whether the number required by the question exists, you can save the need to enumerate the latter number. It's time. More advancedly, if the data range allows, we can use bucket 1 to record the traversed numbers.
C++
bool met[MAXN * 2];
memset(met, 0, sizeof(met));
for (int i = 0; i < n; ++i) {
if (met[MAXN - a[i]]) ++ans;
met[MAXN + a[i]] = true;
}
Python
met = [False] * MAXN * 2
for i in range(n):
if met[MAXN - a[i]]:
ans += 1
met[a[i] + MAXN] = True
Time complexity analysis: The question requirements can be completed by traversing the a array once. When n is large enough, the time complexity is O(n).
Space complexity analysis: O(n+max{|x|:x∈a).
Lights Out: http://bailian.openjudge.cn/practice/2811/ (Openjudge)