Pat class B common function Usage Summary

  One 、 matters needing attention

1. All topics use the most basic C Language knowledge can solve , Some structures are used , The most data structures involved are linked lists , The most commonly used function is strcmp,strcpy,qsort,abs,fabs etc.
2. Large arrays are best set to global , because main Function in stack space , The stack size is only dozens KB, Stack overflow will occur if the array is too large , Therefore, the large array is set to global , Global variables occupy heap space , Heap space is allocated on demand , It can be big or small.
3. For mistakes , The newline at the end does not affect the format ,
           The segment error is generally that the set array is smaller than the requirements given by the topic ,
           The wrong answer usually means that the code logic is wrong ,
           Running timeout indicates that the problem cannot be solved by force , perhaps i-- It's written in i++ Such errors in the loop body
4. For test cases , You'd better bring it yourself DEV C++ Or test it on other compilers , Generally, many mistakes can be found , Convenient correction
5. For time-out, it may be cin Caused by input data ：

   scanf（"%d",&elem）;  //  We have already told you the type of element , Machines no longer have to look for element types .
   
   cin>>elem;  //  The element type is found by the machine itself , When you need a lot of input data , The redundancy of time is very obvious 
   

   Someone once made a comparison ： With the same amount of data cin Time consuming is scanf Of 3.5~4 times .
   however , It is worth mentioning that ,cin The safety ratio of scanf superior .

6. For topics with strict time requirements （PAT Class B 2022 Spring exam 7-5 front K Large number ）, Consider using multiplication and division as little as possible , And use array operation instead of STL.

7. %.f Will be automatically rounded , If the meaning of the question requires the result to be rounded down , Such as 1070 Knot rope , You can use cast .

   printf("%.f", ans);      // The result is rounded to the nearest 
   printf("%d", (int)ans);  // The result is rounded down 

8. AC And completely correct code are two concepts , If you can determine the specific input and output of the failed points , You can make a special judgment , For example, know the test point 4 The data of 25000, But the code doesn't work , Just insert in the main loop

   if(n == 25000)
       printf("No Solution");

   This is just an example , See Qingshen PAT Machine test skills

---

Two 、 Common functions

1、sort()  Sorting function

bool cmp(struct node a,struct node b) {
	if ((a.de + a.cai) != (b.de + b.cai))
		return (a.de + a.cai) > (b.de + b.cai);
	else if (a.de != b.de)
		return a.de > b.de;
	else
		return a.num < b.num;
}

struct node
{
	int num, de, cai;
}v[4];

sort(v[i].begin(), v[i].end(), cmp);

---

2、substr()  Get substring

string s = "123456";
cout << s.substr(2, 4);

• Output results ：2345

---

3、reverse()  Inversion function

char res[10] = "abcdefghi";
reverse(begin(res), begin(res) + 4);
cout << res;

• Output results ：dcbaefghi

---

4、vector  Common operations

vector<int>  v1(n,1);// Initialize a size of n, It's worth it all 1 Array of 

v1.push_back(2);// stay vector Insert the element at the end 2
v1.pop_back();// Delete vector End element 

v1.insert(v1.begin(),3);// stay v1 Insert before the first position 3
v1.insert(v1.begin()+1,4);// stay v1 Insert before the second position 4
v1.insert(v1.begin(),5,6);// stay v1 Insert consecutively before the first position 5 individual 6

v1.erase(v1.begin());// Delete first element 
v1.erase(v1.begin()+1);// Delete the second element 
v1.erase(v1.begin(),v1.begin()+3);// Delete the first three elements 

---

5、itoa() & atoi() & stoi() & to_string() transformation

int i = 579;
char s[10];
itoa(i, s, 8); // The third parameter is the converted decimal number 
cout << s;

• itoa() Output results ：1103

char s[4] = "107";
int num = atoi(s);
cout << num;

• atoi() Output results ：107

char s[4] = "107";
int num = stoi(s);
cout << num;

• stoi() Output results ：107

int num = 19732;
string s = to_string(num);
s += "777";
cout << s;

• to_string() Output results ：19732777

---

6、isdigit() & isalpha() & isalnum() & isupper() & islower() Determine whether the character is a numeric letter

char a = '7', b = 'C';
cout << isdigit(a) << " " << isdigit(b) << "\n"; // Judge whether it's a number 
cout << isalpha(a) << " " << isalpha(b) << "\n"; // Decide if it's a letter 
cout << isalnum(a) << " " << isalnum(b) << "\n"; // Judge whether it's a number or a letter 
cout << isupper(a) << " " << isupper(b) << "\n"; // Decide if it's a capital letter 
cout << islower(a) << " " << islower(b) << "\n"; // Determine if it's lowercase 

• Output results ：

  4 0
  0 1
  4 1
  0 1
  0 0

---

7、round() rounding

#define CLK_TCK 100
double t1 = 100, t2 = 149, t3 = 150;
cout << round((t2 - t1) / CLK_TCK) << " " << round((t3 - t1) / CLK_TCK);

• Output results ：0 1

---

8、toupper() & tolower() Convert case

char a = 'a', b = 'B';
cout << toupper(a) << " " << tolower(b);

• Output results ：65 98

---

9、string::npos  usage

string s = "abcdefg";
int idx = s.find('.');   // As return value, Indicates that there is no match 
if (idx == string::npos)
    cout << "This string does not contain any period!" << endl;
idx = s.find('c');
s.replace(idx + 1, string::npos, "x");  string::npos As a length parameter , Indicates until the end of the string 
cout << s;

• Output results ：

  This string does not contain any period!
  abcx

---

10、upper_bound() & lower_bound() Find the upper and lower bounds

• Be careful ： The address returned here , Get the subscript by subtracting the array name .
• upper_bound()  Find a limit smaller than the specified value （ Find the first one greater than 3 The location of ）,lower_bound()  Find a limit greater than or equal to the specified value （ Find the first one greater than or equal to 3 The location of ）

vector<int> nums = { 1, 2, 3, 3, 4, 4, 5 };
int index = upper_bound(nums.begin(), nums.end(), 3) - nums.begin();
cout << index << endl; // >: 4
index = lower_bound(nums.begin(), nums.end(), 3) - nums.begin();
cout << index << endl; // >: 2

• Output results ：4 2

---

11、 map usage

1. map The traversal

   map<char, int> mp;
   char c;
   while ((c = cin.get()) != '\n') 
   	if(isalpha(c))
   		mp[c]++;
   for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {
   	printf("%c %d  ", it->first, it->second);
   }

   Input ：

   This is a simple TEST.

   Output ：

   E 1  S 1  T 3  a 1  e 1  h 1  i 3  l 1  m 1  p 1  s 3

2. map Common operations

   begin()  Return to point  map  The iterator of the head 
   clear(）  Delete all elements 
   count()  Returns the number of occurrences of the specified element 
   empty()  If  map  If it is blank, return  true
   end()  Return to point  map  Iterator at the end 
   erase()  Delete an element 
   find()  Find an element 
   insert()  Insert elements 
   key_comp()  Returns the comparison element  key  Function of 
   lower_bound()  Return key value >= Given the first position of the element 
   max_size()  Returns the maximum number of elements that can be accommodated 
   rbegin()  Return a point  map  The backward iterator of the tail 
   rend()  Return a point  map  The reverse iterator of the head 
   size()  return  map  The number of elements in 
   swap()  Two exchanges  map
   upper_bound()  Return key value > Given the first position of the element 
   value_comp()  Returns the comparison element  value  Function of 
   

---

12、sscanf() & sprintf() usage

• sscanf() – Reads data from a string that matches the specified format
• sprintf() – String formatting command , The main function is to write the formatted data into a string  

scanf("%s", str1);
sscanf(str1, "%lf", &temp);		// stay str1 Read a floating-point number to temp
sprintf(str2, "%.2lf", temp);	// hold temp Give... As a string with two decimal places str2

  Input ：

aaa 
2.3.4 
1.23ab2.3

Output ：

aaa 0 0.00
2.3.4 2.3 2.30
 1.23 1.23

---

3、 ... and 、 Commonly used algorithm  

1、isPrime： Find prime number

bool isPrime(int a) {
	if (a == 0 || a == 1) return false;
	for (int i = 2; i <= sqrt(a); i++) {
		if (a % i == 0)return false;
	}
	return true;
}

---

2、gcd： Find the greatest common divisor by division

int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}

• Output results ：gcd(21, 27) = 7

---

3、dfs： Depth first search algorithm

• B1096 Great beauty number
• B1104 Enduring as the universe

void dfs(int step){    
	 prune {
		 Corresponding operation ;
		return;
	}
     Judgement boundary {
         Corresponding operation ;
        return;
    }
     Try every possibility {
         Satisfy check Conditions {
             Mark ;
             Move on to the next step dfs(step+1);
             Restore to initial state （ It's used in backtracking );
        }
    }
}