PAT乙级常用函数用法总结

 一、注意事项

1. 所有的题目利用最基本的C语言知识就可以解决，一些要用到结构体，涉及到的数据结构最多到链表，最常用的函数就是strcmp，strcpy，qsort，abs，fabs等
2. 大数组最好设置为全局，因为main函数在栈空间内，而栈的大小只有几十KB，数组太大会出现栈溢出，因此大数组设置为全局，全局变量占用堆空间，堆空间按需分配，可大可小
3. 对于错误，末尾的换行不影响格式，
          段错误一般是设置的数组小于题目给定的要求，
          答案错误一般就是代码逻辑有错误，
          运行超时说明题目不能用暴力破解，或者i--写成i++之类的循环体里的错误
4. 对于测试用例，最好自己带到DEV C++或者其他编译器上面测试一下，一般能发现很多错误，方便改正
5. 对于时间超时有可能是cin输入数据造成的：

   scanf（"%d",&elem）;  // 元素的类型我们已经告知了，机器不用再去查找元素类型。
   
   cin>>elem;  // 元素类型由机器自己查找，在需要大量输入数据的时候，时间的冗余就十分明显了
   

   曾有人做过比较：在相同数据量的情况下cin的耗时是scanf的3.5~4倍。
   但是，值得一提的是，cin的安全性比scanf优越。

6. 对于时间要求严格的题目（PAT乙级2022年春季考试7-5 前K大数），可以考虑尽量少用乘除法，以及用数组操作代替使用STL。

7. %.f会自动进行四舍五入，若题意要求结果向下取整，如1070 结绳，可使用强制类型转换。

   printf("%.f", ans);      //结果四舍五入
   printf("%d", (int)ans);  //结果向下取整

8. AC和代码完全正确是两个概念，如果你能确定未通过的点的具体输入与输出，就可以进行特判，例如知道测试点4的数据是25000，但是代码跑不通，就在主循环中插入

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

   这只是一个例子，具体技巧见晴神PAT机试技巧

---

二、常用函数

1、sort() 排序函数

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() 获取子串

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

• 输出结果：2345

---

3、reverse() 倒置函数

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

• 输出结果：dcbaefghi

---

4、vector 常用操作

vector<int>  v1(n,1);//初始化一个大小为n，值全为1的数组

v1.push_back(2);//在vector末尾插入元素2
v1.pop_back();//删除vector末尾元素

v1.insert(v1.begin(),3);//在v1第一个位置前插入3
v1.insert(v1.begin()+1,4);//在v1第二个位置前插入4
v1.insert(v1.begin(),5,6);//在v1第一个位置前连续插入5个6

v1.erase(v1.begin());//删除第一个元素
v1.erase(v1.begin()+1);//删除第二个元素
v1.erase(v1.begin(),v1.begin()+3);//删除前三个元素

---

5、itoa() & atoi() & stoi() & to_string()转换

int i = 579;
char s[10];
itoa(i, s, 8); //第三个参数为转换的进制数
cout << s;

• itoa()输出结果：1103

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

• atoi()输出结果：107

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

• stoi()输出结果：107

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

• to_string()输出结果：19732777

---

6、isdigit() & isalpha() & isalnum() & isupper() & islower() 判断字符是否是数字字母

char a = '7', b = 'C';
cout << isdigit(a) << " " << isdigit(b) << "\n"; //判断是否是数字
cout << isalpha(a) << " " << isalpha(b) << "\n"; //判断是否是字母
cout << isalnum(a) << " " << isalnum(b) << "\n"; //判断是否是数字或字母
cout << isupper(a) << " " << isupper(b) << "\n"; //判断是否是大写字母
cout << islower(a) << " " << islower(b) << "\n"; //判断是否是小写字母

• 输出结果：

  4 0
  0 1
  4 1
  0 1
  0 0

---

7、round() 四舍五入

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

• 输出结果：0 1

---

8、toupper() & tolower() 转换大小写

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

• 输出结果：65 98

---

9、string::npos 用法

string s = "abcdefg";
int idx = s.find('.');   //作为return value，表示没有匹配项
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作为长度参数，表示直到字符串结束
cout << s;

• 输出结果：

  This string does not contain any period!
  abcx

---

10、upper_bound() & lower_bound() 寻找上界和下界

• 注意：这里返回的是地址,通过减去数组名获得下标。
• upper_bound() 寻找小于指定值的界限（找到第一个大于3的位置），lower_bound() 寻找大于等于指定值的界限（找到第一个大于等于3的位置）

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

• 输出结果：4 2

---

11、 map用法

1. map的遍历

   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);
   }

   输入：

   This is a simple TEST.

   输出：

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

2. map常用操作

   begin() 返回指向 map 头部的迭代器
   clear(） 删除所有元素
   count() 返回指定元素出现的次数
   empty() 如果 map 为空则返回 true
   end() 返回指向 map 末尾的迭代器
   erase() 删除一个元素
   find() 查找一个元素
   insert() 插入元素
   key_comp() 返回比较元素 key 的函数
   lower_bound() 返回键值>=给定元素的第一个位置
   max_size() 返回可以容纳的最大元素个数
   rbegin() 返回一个指向 map 尾部的逆向迭代器
   rend() 返回一个指向 map 头部的逆向迭代器
   size() 返回 map 中元素的个数
   swap() 交换两个 map
   upper_bound() 返回键值>给定元素的第一个位置
   value_comp() 返回比较元素 value 的函数
   

---

12、sscanf() & sprintf() 用法

• sscanf() – 从一个字符串中读进与指定格式相符的数据
• sprintf() – 字符串格式化命令，主要功能是把格式化的数据写入某个字符串中 

scanf("%s", str1);
sscanf(str1, "%lf", &temp);		//在str1中读取一个浮点数给temp
sprintf(str2, "%.2lf", temp);	//把temp以保留两位小数的字符串形式给str2

 输入：

aaa 
2.3.4 
1.23ab2.3

输出：

aaa 0 0.00
2.3.4 2.3 2.30
 1.23 1.23

---

三、常用算法 

1、isPrime：求素数

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：辗转相除法求最大公约数

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

• 输出结果：gcd(21, 27) = 7

---

3、dfs：深度优先搜索算法

• B1096 大美数
• B1104 天长地久

void dfs(int step){    
	剪枝{
		相应操作;
		return;
	}
    判断边界{
        相应操作;
        return;
    }
    尝试每一种可能{
        满足check条件{
            标记;
            继续下一步dfs(step+1);
            恢复初始状态（回溯的时候要用到);
        }
    }
}