Pay attention to how to reduce the number and range of enumerations as much as possible

Example 1: physiological cycle

 

 

 

 

 

 

 

 

Solution idea: this problem is still relatively simple. It is easy to think of solving the problem by enumeration. The condition is to enumerate every day and see if the distance from the given peak can be% 23 28 33 = = 0 at the same time. However, if it is designed in this way, it is obvious that it will use triple cycle, with high time complexity. If the given data is large, it is likely to overflow. Therefore, we choose to find a way to reduce the number or range of enumeration. Then what shall I do?

 

The answer is: jump. Because there is no need to enumerate the corresponding interval between each two cycles, the optimization idea is to find the position of the first peak of physical strength first, and then jump the cycle, because it is also the physical cycle to meet the EQ cycle at the same time, until a position where the two cycles overlap is found, When trying later, just try the days when both physical strength and emotional intelligence peak. The interval between double peak days is obviously the least common multiple of the two. So now jump their least common multiple to find the day that overlaps the third peak.

 

code:

 

 

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int main() {
 5     int p, e, i, d, caseNo = 0;
 6     while (cin >> p >> e >> i >> d && p != -1) {//This input still needs to be learned
 7         caseNo++;
 8         int k;//This is the number of days
 9         for (k = d + 1; (k - p) % 23; ++k);
10         for (; (k - e) % 28; k += 23);
11         for (; (k - i) % 23; k += 23 * 28);
12         //such for The use of recycling should be careful not to be replaced by previous ones for The use of rigid circulation has been imprisoned
13         cout << "Case " << caseNo << ": the next triple peak occurs in " << k - d <<endl;
14     }
15     return 0;
16 }

 

Summary:

This problem tells us that we can reduce the number of enumerations through the design of loops. There are also some tips on how to write code.

 

 

Example 2: weighing coins (poj 1013):

Title Link: http://poj.org/problem?id=1013

 

Main idea of the title:

 

 

 

 

 

Solution: it must be enumeration! How to enumerate? Is to enumerate the weight and light of each coin on both sides of the balance. No, every coin is assumed to be light. See if the hypothetical balance is consistent with the title. If not, assume that the balance is heavy. In fact, I think this enumeration is relatively not obvious and not easy to think of.

code:

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 char left[3][7];
 5 char right[3][7];
 6 char result[3][7];
 7 bool IsFake(char c, bool light) {
 8     for(int i = 0;i<3;i++){
 9         char *pleft *pright;
10         if(light){
11             pleft = left[i];
12             pright = left[i];
13         }else{
14             pleft = right[i];
15             pright = left[i];
16         }
17         switch(result[i][0]){
18             case 'u':
19                 if(strchr(pright,c)==NULL)
20                     return false;
21                 break;
22             case 'e':
23                 if(strchr(pleft,c)||strchr(pright,c))
24                     return false;
25                 break;
26             case 'd':
27                 if(strchr(pleft,c) == NULL)
28                     return false;
29                 break; 
30         }
31         return true;
32     }
33     
34 }
35 int main() {
36     int t;
37     cin >> t;
38     while (t--) {
39         for (int i = 0; i < 3; i++)
40             cin >> left[i] >> right[i] >> result[i];
41         for(char c = 'A';c<='L';c++){
42             if(IsFake(c,true)){
43                 cout<<c<<"is the counterfeit coid and it is light.\n";
44                 break;
45             }
46             if(IsFake(c,false)){
47                 cout<<c<<"is the counterfeit coid and it is height.\n";
48                 break;
49             }
50         } 
51     }
52     return 0;
53 }

 

Explanation and summary of the code: the first is the storage of data. There are three kinds of data in total. Therefore, A two-dimensional array is used in this place to store the coins on both sides of the balance (the number of coins on the left and right sides is equal and from A to L) and the results (i.e. whether the right side of the balance is high or flat or low). Note that this place judges the position of light coins based on the height on the right side of the balance. The first is the cycle of case number, which is the cycle of three examples. The innermost part is the cycle of each coin. Within each cycle, it enumerates the light or heavy of each coin. Here, the judgment of weight is put in A function. This IsFake has two parameters. The first parameter is the coin to be judged, and the second bool type parameter is to judge whether it is light or not.

In the loop of the function, two pointers are designed to point to the left end and right section of the balance respectively. If it is heavy here, exchange the position, point the left pointer to the right and the right pointer to the left, so that there is no need to write judgment on both sides. If it is high on the left and the coin is light, it means that the light coin is on the left. strchr is used to judge whether the character is in the string. Here is to judge whether the coin is on the left. If it is equal, the coin cannot be on the left or right. If the right side is low, the coin is on the left. If it is heavy, these situations are exchanged, which is why the exchange is written in the front.